×

Semi-online scheduling with decreasing job sizes. (English) Zbl 1024.90044

Summary: We investigate the problem of semi-online scheduling jobs on \(m\) identical parallel machines where the jobs arrive in order of decreasing sizes. We present a complete solution for the preemptive variant of semi-online scheduling with decreasing job sizes. We give matching lower and upper bounds on the competitive ratio for any fixed number \(m\) of machines; these bounds tend to \((1+\sqrt 3)/2\approx 1.36603\), as the number of machines goes to infinity. Our results are also the best possible for randomized algorithms. For the non-preemptive variant of semi-online scheduling with decreasing job sizes, a result of Graham [SIAM J. Appl. Math. 17, 416–429 (1969; Zbl 0188.23101)] yields a \((4/3-1/(3m))\)-competitive deterministic non-preemptive algorithm. For \(m=2\) machines, we prove that this algorithm is the best possible (it is \(7/6\)-competitive). For \(m=3\) machines we give a lower bound of \((1+ \sqrt{37})/6 \approx 1.18046\). Finally, we present a randomized non-preemptive \(8/7\)-competitive algorithm for \(m=2\) machines and prove that this is optimal.

MSC:

90B35 Deterministic scheduling theory in operations research
68W40 Analysis of algorithms

Citations:

Zbl 0188.23101

Software:

Mathematica
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Albers, Better bounds for online scheduling, Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 130-139.; S. Albers, Better bounds for online scheduling, Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 130-139. · Zbl 0968.68008
[2] Y. Azar, O. Regev, Online bin stretching, Proceedings of RANDOM, 1998, pp. 71-82.; Y. Azar, O. Regev, Online bin stretching, Proceedings of RANDOM, 1998, pp. 71-82.
[3] Bartal, Y.; Fiat, A.; Karloff, H.; Vohra, R., New algorithms for an ancient scheduling problem, J. Comput. System Sci., 51, 359-366 (1995) · Zbl 1295.90008
[4] Bartal, Y.; Karloff, H.; Rabani, Y., A better lower bound for on-line scheduling, Inform. Process. Lett., 50, 113-116 (1994) · Zbl 0807.68013
[5] Chen, B.; van Vliet, A.; Woeginger, G., A lower bound for randomized on-line scheduling algorithms, Inform. Process. Lett., 51, 219-222 (1994) · Zbl 0821.68011
[6] Chen, B.; van Vliet, A.; Woeginger, G., New lower and upper bounds for on-line scheduling, Oper. Res. Lett., 16, 221-230 (1994) · Zbl 0823.90059
[7] Chen, B.; van Vliet, A.; Woeginger, G., An optimal algorithm for preemptive on-line scheduling, Oper. Res. Lett., 18, 127-131 (1995) · Zbl 0855.90069
[8] Faigle, U.; Kern, W.; Turàn, G., On the performance of on-line algorithms for partition problems, Acta Cybernet., 9, 107-119 (1989) · Zbl 0689.68051
[9] Galambos, G.; Woeginger, G., An online scheduling heuristic with better worst case ratio than Graham’s list scheduling, SIAM J. Comput., 22, 349-355 (1993) · Zbl 0781.90051
[10] Graham, R. L., Bounds for certain multiprocessing anomalies, Bell Systems Tech. J., 45, 1563-1581 (1966) · Zbl 0168.40703
[11] Graham, R. L., Bounds on multiprocessing timing anomalies, SIAM J. Appl. Math., 17, 263-269 (1969) · Zbl 0188.23101
[12] Karger, D.; Phillips, S.; Torng, E., A better algorithm for an ancient scheduling problem, J. Algorithms, 20, 400-430 (1996) · Zbl 0844.68010
[13] Kellerer, H.; Kotov, V.; Speranza, M.; Tuza, Z., Semi online algorithms for the partition problem, Oper. Res. Lett., 21, 235-242 (1997) · Zbl 0908.90165
[14] Liu, W. P.; Sidney, J. B.; van Vliet, A., Ordinal algorithms for parallel machine scheduling, Oper. Res. Lett., 18, 223-232 (1996) · Zbl 0855.90070
[15] Reingold, N.; Westbrook, J.; Sleator, D., Randomized competitive algorithms for the list update problem, Algorithmica, 11, 15-32 (1994) · Zbl 0782.68062
[16] S.S Seiden, Randomized algorithms for that ancient scheduling problem, Proceedings of the Fifth Workshop on Algorithms and Data Structures, 1997, pp. 210-223.; S.S Seiden, Randomized algorithms for that ancient scheduling problem, Proceedings of the Fifth Workshop on Algorithms and Data Structures, 1997, pp. 210-223.
[17] S.S. Seiden, Randomized online multiprocessor scheduling, Algorithmica, to appear.; S.S. Seiden, Randomized online multiprocessor scheduling, Algorithmica, to appear. · Zbl 0961.68018
[18] J. Sgall, On-line scheduling on parallel machines, Ph.D. thesis, Carnegie-Mellon University, 1994; J. Sgall, On-line scheduling on parallel machines, Ph.D. thesis, Carnegie-Mellon University, 1994
[19] Sgall, J., A lower bound for randomized on-line multiprocessor scheduling, Inform. Process. Lett., 63, 51-55 (1997) · Zbl 1336.68107
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.