Parallel machine covering with limited number of preemptions. (English) Zbl 1313.90088
Summary: In this paper, we investigate the \(i\)-preemptive scheduling on parallel machines to maximize the minimum machine completion time, i.e., machine covering problem with limited number of preemptions. It is aimed to obtain the worst case ratio of the objective value of the optimal schedule with unlimited preemptions and that of the schedule allowed to be preempted at most \(i\) times. For the \(m\) identical machines case, we show the worst case ratio is \(\frac{2m-i-1}m\), and we present a polynomial time algorithm which can guarantee the ratio for any \(0\leq i\leq m-1\). For the \(i\)-preemptive scheduling on two uniform machines case, we only need to consider the cases of \(i=0\) and \(i=1\). For both cases, we present two linear time algorithms and obtain 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 |
| 90C27 | Combinatorial optimization |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Y Azar, L Epstein. Approximation schemes for covering and scheduling on related machines machine covering, Proc of APPROX’1998, 1998, 39–47. · Zbl 0911.90199 |
| [2] | O Braun, G Schmidt. Parallel processor scheduling with limited number of preemptions, SIAMJ Comput, 2003, 32(3): 671–80. · Zbl 1023.90021 · doi:10.1137/S0097539702410697 |
| [3] | J R Correa, M Skutella, J Verschae. The power of preemption in unrelated machines and applications to scheduling orders, Math Oper Res, 2012, 37(2): 379–398. · Zbl 1238.90062 · doi:10.1287/moor.1110.0520 |
| [4] | J Csirik, H Kellerer, G Woeginger. The exact LPT-bound for maximizing the minimum completion time, Oper Res Lett, 1992, 11: 281–287. · Zbl 0767.90034 · doi:10.1016/0167-6377(92)90004-M |
| [5] | B Deuermeyer, D Friesen, M Langston. Scheduling to maximize the minimum processor finish time in a multiprocessor system, SIAM J Discrete Methods, 1982, 3: 190–196. · Zbl 0489.68031 · doi:10.1137/0603019 |
| [6] | L Epstein. Optimal preemptive on-line scheduling on uniform processors with non-decreasing speed ratios, Oper Res Lett, 2001, 29: 93–98. · Zbl 0981.90024 · doi:10.1016/S0167-6377(01)00085-2 |
| [7] | L Epstein. Tight bounds for online bandwidth allocation on two links, Discrete Appl Math, 2005, 148(2): 181–188. · Zbl 1138.90343 · doi:10.1016/j.dam.2005.02.002 |
| [8] | T Gonzalez, S Sahni. Preemptive scheduling of uniform processor systems, J ACM, 1978, 25: 92–101. · Zbl 0364.68046 · doi:10.1145/322047.322055 |
| [9] | R L Graham. Bounds on multiprocessing timing anomalies, SIAM J Appl Math, 1969, 17: 416–429. · Zbl 0188.23101 · doi:10.1137/0117039 |
| [10] | E C Horvath, S Lam, R Sethi. A level algorithm for preemptive scheduling, J ACM, 1977, 24: 32–43. · Zbl 0354.90044 · doi:10.1145/321992.321995 |
| [11] | J Y Jiang, T Y Tan, Y He. Preemptive machine covering on parallel machines, J Comb Optim, 2005, 10: 345–363. · Zbl 1093.90016 · doi:10.1007/s10878-005-4923-5 |
| [12] | Y W Jiang, Z W Weng, J L Hu. Algorithms with limited number of preemptions for scheduling on parallel machines, J Comb Optim, 2012, DOI: 10.1007/s10878-012-9545-0. · Zbl 1304.90094 |
| [13] | K Klonowska, L Lundberg, H Lennerstad. The maximum gain of increasing the number of preemptions in multiprocessor scheduling, Acta Inform, 2009, 46: 285–295. · Zbl 1179.68019 · doi:10.1007/s00236-009-0096-5 |
| [14] | R McNaughton. Scheduling with deadlines and loss functions, Manage Sci, 1959, 6: 1–12. · Zbl 1047.90504 · doi:10.1287/mnsc.6.1.1 |
| [15] | G J Woeginger. Applynomial time approximation scheme for maximizing the minimum machine completion time, Oper Res Lett, 1977, 20: 149–154. · Zbl 0879.90121 · doi:10.1016/S0167-6377(96)00055-7 |
| [16] | G J Woeginger. A comment on scheduling on uniform machines under chain-type precedence constraints, Oper Res Lett, 2000, 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.
