We investigate online scheduling with commitment for parallel identical machines. Our objective is to maximize the total processing time of accepted jobs. As soon as a job has been submitted, the commitment constraint forces us to decide immediately whether we accept or reject the job. Upon acceptance of a job, we must complete it before its deadline @math that satisfies @math , with @math and @math being the processing time and the submission time of the job, respectively while @math is the slack of the system. Since the hard case typically arises for near-tight deadlines, we consider @math . We use competitive analysis to evaluate our algorithms. Our first main contribution is a deterministic preemptive online algorithm with an almost tight competitive ratio on any number of machines. For a single machine, the competitive factor matches the optimal bound @math of the greedy acceptance policy. Then the competitive ratio improves with an increasing number of machines and approaches @math as the number of machines converges to infinity. This is an exponential improvement over the greedy acceptance policy for small @math . In the non-preemptive case, we present a deterministic algorithm on @math machines with a competitive ratio of @math . This matches the optimal bound of @math of the greedy acceptance policy for a single machine while it again guarantees an exponential improvement over the greedy acceptance policy for small @math and large @math . In addition, we determine an almost tight lower bound that approaches @math for large @math and small @math .
@cite_14: 
@cite_4: In this paper we develop an easily applicable algorithmic technique tool for developing approximation schemes for certain types of combinatorial optimization problems. Special cases that are covered by our result show up in many places in the literature. For every such special case, a particular rounding trick has been implemented in a slightly different way, with slightly different arguments, and with slightly different worst case estimations. Usually, the rounding procedure depended on certain upper or lower bounds on the optimal objective value that have to be justified in a separate argument. Our easily applied result unifies many of these results, and sometimes it even leads to a simpler proof. We demonstrate how our result can be easily applied to a broad family of combinatorial optimization problems. As a special case, we derive the existence of an FPTAS for the scheduling problem of minimizing the weighted number of late jobs under release dates and preemption on a single machine. The approximability status of this problem has been open for some time.
@cite_23: 
@cite_15: The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography.
@cite_10: The scheduling problem 1|pmtn, r j |Σw j U j calls forn jobs with arbitrary release dates and due dates to be preemptively scheduled for processing by a single machine, with the objective of minimizing the sum of the weights of the late jobs. A dynamic programming algorithm for this problem is described. Time and space bounds for the algorithm are, respectively,O(nk2W2) andO(k2W), wherek is the number of distinct release dates andW is the sum of the integer job weights. Thus, for the problem 1|pmtn, r j |ΣU j , in which the objective is simply to minimize the number of late jobs, the pseudopolynomial time bound becomes polynomial, i.e.O(n3k2).
@cite_12: In this paper we provide a tight bound for the price of preemption for scheduling jobs on a single machine (or multiple machines). The input consists of a set of jobs to be scheduled and of an integer parameter @math . Each job has a release time, deadline, length (also called processing time) and value associated with it. The goal is to feasibly schedule a subset of the jobs so that their total value is maximal; while preemption of a job is permitted, a job may be preempted no more than k times. The price of preemption is the worst possible (i.e., largest) ratio of the optimal non-bounded-preemptive scheduling to the optimal k-bounded-preemptive scheduling. Our results show that allowing at most k preemptions suffices to guarantee a Θ( +1 n, log_k+1 P ) @math . As part of the proof, we introduce the notion of the Bounded-Degree Ancestor-Free Sub-Forest (BAS). We investigate the problem of computing the maximal-value BAS of a given forest and give a tight bound for the loss factor, which is Θ(log_k+1 n)$ as well, where n is the size of the original forest and k is the bound on the degree of the sub-forest.
Using the three field notation of @cite_15 , the @math problem admits a pseudopolynomial time algorithm, see Lawler @cite_10 , and a FPTAS due to a technique by Pruhs and Woeginger @cite_4 . We are not aware of any simplifications when assuming @math . For preemption without migration, these ideas were further extended to admit a @math approximation @cite_23 . A reduction from preemptive to non-preemptive due to Kalyanasundaram and Pruhs @cite_14 yields a @math approximation. Recently, @cite_12 analyzed the gap between schedules with a bounded number of @math preemptions and an unbounded number of preemptions. They show that the utilization ratio is at most @math , which is asymptotically optimal.