We propose a new approach to competitive analysis in online scheduling by introducing the novel concept of competitive-ratio approximation schemes. Such a scheme algorithmically constructs an online algorithm with a competitive ratio arbitrarily close to the best possible competitive ratio for any online algorithm. We study the problem of scheduling jobs online to minimize the weighted sum of completion times on parallel, related, and unrelated machines, and we derive both deterministic and randomized algorithms which are almost best possible among all online algorithms of the respective settings. We also generalize our techniques to arbitrary monomial cost functions and apply them to the makespan objective. Our method relies on an abstract characterization of online algorithms combined with various simplifications and transformations. We also contribute algorithmic means to compute the actual value of the best possi- ble competitive ratio up to an arbitrary accuracy. This strongly contrasts all previous manually obtained competitiveness results for algorithms and, most importantly, it reduces the search for the optimal com- petitive ratio to a question that a computer can answer. We believe that our concept can also be applied to many other problems and yields a new perspective on online algorithms in general.
The online makespan minimization problem has been extensively studied in a different online paradigm where jobs arrive one by one (see @cite_16 @cite_46 and references therein). Our model, in which jobs arrive online over time, is much less studied. In the identical parallel machine environment, Chen and Vestjens @cite_41 give nearly tight bounds on the optimal competitive ratio, @math , using a natural online variant of the well-known largest processing time first algorithm.
@cite_41 @cite_46 @cite_16
1970436181 1966527086 2769189507 1964506478
We consider the online scheduling problem on m parallel machines with eligibility constraints. The jobs arrive over time and have equal processing times. The objective is to minimize the makespan. We develop optimal deterministic online algorithms for the nested processing set case and the inclusive processing set case with an arbitrary number of machines, as well as the tree-like processing set case with three machines. 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. We study a natural generalization of the problem of minimizing makespan on unrelated machines in which jobs may be split into parts. The different parts of a job can be (simultaneously) processed on different machines, but each part requires a setup time before it can be processed. First we show that a natural adaptation of the seminal approximation algorithm for unrelated machine scheduling [11] yields a 3-approximation algorithm, equal to the integrality gap of the corresponding LP relaxation. Through a stronger LP relaxation, obtained by applying a lift-and-project procedure, we are able to improve both the integrality gap and the implied approximation factor to 1 + φ, where φ ≈ 1.618 is the golden ratio. This ratio decreases to 2 in the restricted assignment setting, matching the result for the classic version. Interestingly, we show that our problem cannot be approximated within a factor better than e e-1 ≈ 1.582 (unless P = NP). This provides some evidence that it is harder than the classic version, which is only known to be inapproximable within a factor 1.5 - e. Since our 1 + φ bound remains tight when considering the seemingly stronger machine configuration LP, we propose a new job based configuration LP that has an infinite number of variables, one for each possible way a job may be split and processed on the machines. Using convex duality we show that this infinite LP has a finite representation and can be solved in polynomial time to any accuracy, rendering it a promising relaxation for obtaining better algorithms. © 2014 Springer International Publishing Switzerland. We consider the classical problem of minimizing the total weighted flow-time for unrelated machines in the online non-clairvoyant setting. In this problem, a set of jobs J arrive over time to be scheduled on a set of M machines. Each job J has processing length pj, weight wj, and is processed at a rate of lij when scheduled on machine i. The online scheduler knows the values of wj and lij upon arrival of the job, but is not aware of the quantity pj. We present the first online algorithm that is scalable ((1+e)-speed O(1 2)-competitive for any constant e > 0) for the total weighted flow-time objective. No non-trivial results were known for this setting, except for the most basic case of identical machines. Our result resolves a major open problem in online scheduling theory. Moreover, we also show that no job needs more than a logarithmic number of migrations. We further extend our result and give a scalable algorithm for the objective of minimizing total weighted flow-time plus energy cost for the case of unrelated machines. In this problem, each machine can be sped up by a factor of f-1i(P) when consuming power P, where fi is an arbitrary strictly convex power function. In particular, we get an O(γ2)-competitive algorithm when all power functions are of form sγ. These are the first non-trivial non-clairvoyant results in any setting with heterogeneous machines. The key algorithmic idea is to let jobs migrate selfishly until they converge to an equilibrium. Towards this end, we define a game where each job's utility which is closely tied to the instantaneous increase in the objective the job is responsible for, and each machine declares a policy that assigns priorities to jobs based on when they migrate to it, and the execution speeds. This has a spirit similar to coordination mechanisms that attempt to achieve near optimum welfare in the presence of selfish agents (jobs). To the best our knowledge, this is the first work that demonstrates the usefulness of ideas from coordination mechanisms and Nash equilibria for designing and analyzing online algorithms.