×

Algorithms with limited number of preemptions for scheduling on parallel machines. (English) Zbl 1296.90052

Summary: In previous study on comparing the makespan of the schedule allowed to be preempted at most \(i\) times and that of the optimal schedule with unlimited number of preemptions, the worst case ratio was usually obtained by analyzing the structures of the optimal schedules. For \(m\) identical machines case, the worst case ratio was shown to be \(2m/(m+i+1)\) for any \(0\leq i\leq m-1\) [O. Braun and G. Schmidt, SIAM J. Comput. 32, No. 3, 671–680 (2003; Zbl 1023.90021)], and they showed that \(LPT\) algorithm is an exact algorithm which can guarantee the worst case ratio for \(i=0\). In this paper, we propose a simpler method which is based on the design and analysis of the algorithm and finding an instance in the worst case. It can not only obtain the worst case ratio but also give a linear algorithm which can guarantee this ratio for any \(0\leq i\leq m-1\), and thus we generalize the previous results. We also make a discussion on the trade-off between the objective value and the number of preemptions. In addition, we consider the \(i\)-preemptive scheduling on two uniform machines. For both \(i=0\) and \(i=1\), we give two linear algorithms and present the worst-case ratios with respect to \(s\), i.e., the ratio of the speeds of two machines.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Citations:

Zbl 1023.90021
Full Text: DOI

References:

[1] Braun O, Schmidt G (2003) Parallel processor scheduling with limited number of preemptions. SIAM J Comput 32(3):671-680 · Zbl 1023.90021 · doi:10.1137/S0097539702410697
[2] Coffman Jr EG, Garey MR (1993) Proof of the 4/3 conjecture for preemptive vs. nonpreemptive two-processor scheduling. J Assoc Comput Mach 20:991-1018 · Zbl 0794.68015 · doi:10.1145/174147.174148
[3] Correa JR, Skutella M, Verschae J (2012) The power of preemption in unrelated machines and applications to scheduling orders. Math Oper Res 37(2):379-398 · Zbl 1238.90062 · doi:10.1287/moor.1110.0520
[4] Ebenlendr T, Sgall J (2009) Optimal and online preemptive scheduling on uniformly related machines. J Sched 12(5):517-527 · Zbl 1176.90208
[5] Gonzalez T, Sahni S (1978) Preemptive scheduling of uniform processor systems. J Assoc Comput Mach 25:92-101 · Zbl 0364.68046 · doi:10.1145/322047.322055
[6] Graham RL (1969) Bounds on multiprocessing timing anomalies. SIAM J Appl Math 17:416-429 · Zbl 0188.23101 · doi:10.1137/0117039
[7] Horvath EC, Lam S, Sethi R (1977) A level algorithm for preemptive scheduling. J Assoc Comput Mach 24:32-43 · Zbl 0354.90044 · doi:10.1145/321992.321995
[8] Hong KS, Leung JYT (1992) Some results on Liu’s conjecture. SIAM J Discrete Math 5:500-523 · Zbl 0786.90030 · doi:10.1137/0405041
[9] Klonowska K, Lundberg L, Lennerstad H (2009) The maximum gain of increasing the number of preemptions in multiprocessor scheduling. Acta Inform 46:285-295 · Zbl 1179.68019 · doi:10.1007/s00236-009-0096-5
[10] Liu, CL, Optimal scheduling on multi-processor computing systems, 155-160 (1972), Los Alamitos · doi:10.1109/SWAT.1972.16
[11] Liu, JWS; Yang, A., Optimal scheduling of independent tasks on heterogeneous computing systems, San Diego, California
[12] McNaughton R (1959) Scheduling with deadlines and loss functions. Manag Sci 6:1-12 · Zbl 1047.90504 · doi:10.1287/mnsc.6.1.1
[13] Shachnai H, Tamir T, Woeginger GJ (2005) Minimizing makespan and preemption costs on a system of uniform machines. Algorithmica 42(3-4):309-334 · Zbl 1086.90028 · doi:10.1007/s00453-005-1171-0
[14] Woeginger GJ (2000) A comment on scheduling on uniform machines under chain-type precedence constraints. Oper Res Lett 26(3):107-109 · Zbl 0955.90036 · doi:10.1016/S0167-6377(99)00076-0
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.