We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have machine-type dependent sizes and have individual deadlines. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. Since we observe the slack of jobs to have a fundamental influence on the competitiveness, we study the model when instances are parameterized by their (minimum) slack. An instance is called to have a slack of @math if, for all jobs, the difference between the job's release time and the latest point in time at which it needs to be started is at least @math . While for @math no finite competitiveness is possible, our main result is an @math -competitive online algorithm for @math with @math , where @math and @math denotes the largest setup time and the cost ratio of the machine-types, respectively. It is complemented by a lower bound of @math .
A different, but closely related problem is that of . In this problem, @math jobs with release times and deadlines are considered and the objective is to finish each job before its deadline while minimizing the number of machines used. This problem has been studied in online and offline settings for the general and different special cases. The first result is due to @cite_2 where an offline algorithm with approximation factor of @math is given. This was later improved to @math by @cite_13 . Better bounds have been achieved for special cases; if all jobs have a common release date or equal processing times, constant approximation factors are achieved @cite_10 . In the online case, a lower bound of @math and an algorithm matching this bound is given in @cite_14 . For jobs of equal size, an optimal @math -competitive algorithm is presented in @cite_6 .
@cite_13 @cite_14 @cite_6 @cite_2 @cite_10
2047204419 2168012204 2091164478 1966527086
We consider the following scheduling problem. The input is a set of jobs with equal processing times, where each job is specified by its release time and deadline. The goal is to determine a single-processor nonpreemptive schedule that maximizes the number of completed jobs. In the online version, each job arrives at its release time. We give two online algorithms with competitive ratios below @math and show several lower bounds on the competitive ratios. First, we give a barely random @math -competitive algorithm that uses only one random bit. We also show a lower bound of @math on the competitive ratio of barely random algorithms that randomly choose one of two deterministic algorithms. If the two algorithms are selected with equal probability, we can further improve the bound to @math . Second, we give a deterministic @math -competitive algorithm in the model that allows restarts, and we show that in this model the ratio @math is optimal. For randomized algorithms with restarts we show a lower bound of @math . We study an online unit-job scheduling problem arising in buffer management. Each job is specified by its release time, deadline, and a nonnegative weight. Due to overloading conditions, some jobs have to be dropped. The goal is to maximize the total weight of scheduled jobs. We present several competitive online algorithms for various versions of unit-job scheduling, as well as some lower bounds on the competitive ratios. We first give a randomized algorithm RMix with competitive ratio of e (e-1) 1.582. This is the first algorithm for this problem with competitive ratio smaller than 2. Then we consider s-bounded instances, where the span of each job (deadline minus release time) is at most s. We give a 1.25-competitive randomized algorithm for 2-bounded instances, matching the known lower bound. We also give a deterministic algorithm Edf"@a, whose competitive ratio on s-bounded instances is 2-2 s+o(1 s). For 3-bounded instances its ratio is @f 1.618, matching the known lower bound. In s-uniform instances, the span of each job is exactly s. We show that no randomized algorithm can be better than 1.25-competitive on s-uniform instances, if the span s is unbounded. For s=2, our proof gives a lower bound of 4-22 1.172. Also, in the 2-uniform case, we prove a lower bound of 2 1.414 for deterministic memoryless algorithms, matching a known upper bound. Finally, we investigate the multiprocessor case and give a 1 (1-(mm+1)^m)-competitive algorithm for m processors. We also show improved lower bounds for the general and s-uniform cases. A companion paper Part I considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper Part II considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. We describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since we describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, we describe a special case of the problem which is polynomially solvable. The problem considered here is the same as the one discussed in [G. Galambos and G. J. Woeginger, eds., SIAM J. Comput., 22 (1993), pp. 349--355]. It is an m-machine online scheduling problem in which we wish to minimize the competitive ratio for the makespan objective. In this paper, we show that @math is a lower bound on this competitive ratio for m=4. In particular, we show how to force a lower bound of @math for any positive @math . This reduces the gap between the performance of known algorithms [S. Albers, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing, ACM, New York, 1997, pp. 130--139] and the lower bound. The method used introduces an approach to building the task master's strategy.