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_0: This paper presents a comprehensive study of the effect of job interleaving by preemption on the throughput of a single server where requests arrive with a given processing time and slack. The problem is to decide which requests to serve so as to maximize the server's utilization. This simple model captures many situations, both at the application (e.g., delivery of video) as well as at the network transmission levels (e.g., scheduling of packets from input to output interface of a switch). The problem is on-line in nature, and thus we use competitive analysis for measuring the performance of our scheduling algorithms. We consider two modes of operation - with and without commitment - and derive upper and lower bounds for each case. Since competitive analysis is based on the worst-case scenario, the average-case performance of the algorithms is also examined by a simulation study.
@cite_9: 
@cite_17: We consider the online competitiveness for scheduling a single resource non-preemptively in order to maximize its utilization. Our work examines this model when parameterizing an instance by a new value which we term the patience. This parameter measures each job's willingness to endure a delay before starting, relative to this same job's processing time. Specifically, the slack of a job is defined as the gap between its release time and the last possible time at which it may be started while still meeting its deadline. We say that a problem instance has patience κ, if each job with length ||J|| has a slack of at least κ ċ ||J||.Without any restrictions placed on the job characteristics, previous lower bounds show that no algorithm, deterministic or randomized, can guarantee a constant bound on the competitiveness of a resulting schedule. Previous researchers have analyzed a problem instance by parameterizing based on the ratio between the longest job's processing time and the shortest job's processing time. Our main contribution is to provide a fine-grained analysis of the problem when simultaneously parameterized by patience and the range of job lengths. We are able to give tight or almost tight bounds on the deterministic competitiveness for all parameter combinations.If viewing the analysis of each parameter individually, our evidence suggests that parameterizing solely on patience provides a richer analysis than parameterizing solely on the ratio of the job lengths. For example, in the special case where all jobs have the same length, we generalize a previous bound of 2 for the deterministic competitiveness with arbitrary slacks, showing that the competitiveness for any κ ≥ 0 is exactly 1 + 1 (⌊κ⌋ + 1). Without any bound on the job lengths, a simple greedy algorithm is (2+ 1 κ)- competitive for any κ > 0. More generally we will find that for any fixed ratio of job lengths, the competitiveness of the problem tends towards 1 as the patience is increased. The converse is not true, as for any fixed κ > 0 we find that the competitiveness is bounded away from 1, no matter what further restrictions are placed on the ratio of job lengths.
@cite_8: No on-line scheduling algorithm operating in an uniprocessor environment can guarantee to obtain a useful processor utilization greater than 0.25 under conditions of overload. This result holds in the general case, where the deadlines of the input tasks can be arbitrarily "tight." We address here the issue of improving overload performance in environments where there is a limit on the tightness of task deadlines. In particular, we present a new scheduling algorithm, ROBUST, that efficiently takes advantage of these limits to provide improved overload performance and is asymptotically optimal. We also introduce the concept of overload tolerance, wherein a system's overload performance never falls below its design capacity, and describe how ROBUST may be used to construct overload tolerant systems.
Baruah and Haritsa @cite_8 were among the first to present results for problems with slack when they addressed the single machine problem with preemption and commitment. For this problem, they gave an algorithm with a competitive ratio @math and a lower bound of @math . For the corresponding non-preemptive problem on a single machine, Goldwasser's algorithm @cite_9 @cite_17 guarantees a tight deterministic competitive ratio of @math . A similar competitive ratio is also given by @cite_0 .