Abstract
We have seen a variety of on-line scheduling problems. Many of them are understood satisfactorily, but there are also many interesting open problems. Studied scheduling problems differ not only in the setting and numerical results, but also in the techniques used. In this way on-line scheduling illustrates many general aspects of competitive analysis.
Preview
Unable to display preview. Download preview PDF.
References
S. Albers. Better bounds for on-line scheduling. In Proc. of the 29th Ann. ACM Symp. on Theory of Computing, 130–139. ACM, 1997.
J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts. On-line load balancing with applications to machine scheduling and virtual circuit routing. J. ACM, 44(3):486–504, 1997.
A. Avidor, Y. Azar, and J. Sgall. Ancient and new algorithms for load balancing in the L p norm. In Proc. of the 9th Ann. ACM-SIAM Symp. on Discrete Algorithms, 426–435. ACM-SIAM, 1998.
B. Awerbuch, Y. Azar, E. F. Grove, M.-Y. Kao, P. Krishnan, and J. S. Vitter. Load balancing in the l p norm. In Proc. of the 36th Ann. IEEE Symp. on Foundations of Computer Sci., 383–391. IEEE, 1995.
Y. Azar. On-line load balancing. Chapter 8 in On-Line Algorithms: The State of the Art, eds. A. Fiat and G. Woeginger, Lecture Notes in Comput. Sci. Springer-Verlag, 178–195, 1998.
Y. Azar, J. Naor, and R. Rom. The competitiveness of on-line assignments. J. of Algorithms, 18:221–237, 1995.
Y. Azar and O. Regev. On-line bin-stretching. Manuscript, 1997.
Y. Bartal, A. Fiat, H. Karloff, and R. Vohra. New algorithms for an ancient scheduling problem. J. Comput. Syst. Sci., 51(3):359–366, 1995.
Y. Bartal, H. Karloff, and Y. Rabani. A new lower bound for m-machine scheduling. Inf. Process. Lett., 50:113–116, 1994.
Y. Bartal, S. Leonardi, A. Marchetti-Spaccamela, J. Sgall, and L. Stougie. Multiprocessor scheduling with rejection. In Proc. of the 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, 95–103. ACM-SIAM, 1996. To appear in SIAM J. Disc. Math.
S. Baruah, G. Koren, B. Mishra, A. Raghunatan, L. Roiser, and D. Sasha. On-line scheduling in the presence of overload. In Proc. of the 32nd Ann. IEEE Symp. on Foundations of Computer Sci., 100–110. IEEE, 1991.
S. Ben-David, A. Borodin, R. M. Karp, G. Tardos, and A. Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11:2–14, 1994.
A. Borodin and R. El-Yaniv. On-line Computation and Competitive Analysis. Cambridge University Press, 1998.
S. Chakrabarti, C. A. Phillips, A. S. Schulz, D. B. Shmoys, C. Stein, and J. Wein. Improved scheduling algorithms for minsum criteria. In Proc. of the 23th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Comput. Sci. 1099, 646–657. Springer-Verlag, 1996.
C. Chekuri, R. Motwani, B. Natarajan, and C. Stein. Approximation techniques for average completion time scheduling. In Proc. of the 8th Ann. ACM-SIAM Symp. on Discrete Algorithms, 609–618. ACM-SIAM, 1997.
B. Chen, A. van Vliet, and G. J. Woeginger. A lower bound for randomized on-line scheduling algorithms. Inf. Process. Lett., 51:219–222, 1994.
B. Chen, A. van Vh'et, and G. J. Woeginger. New lower and upper bounds for on-line scheduling. Oper. Res. Lett., 16:221–230, 1994.
B. Chen, A. van Vliet, and G. J. Woeginger. An optimal algorithm for preemptive on-line scheduling. Oper. Res. Lett., 18:127–131, 1995.
B. Chen and A. P. A. Vestjens. Scheduling on identical machines: How good is lpt in an on-line setting? Oper. Res. Lett., 21:165–169, 1998.
B. Chen, A. P. A. Vestjens, and G. J. Woeginger. On-line scheduling of twomachine open shops where jobs arrive over time. J. of Combinatorial Optimization, 1:355–365, 1997.
B. Chen and G. J. Woeginger. A study of on-line scheduling two-stage shops. In D.-Z. Du and P. M. Pardalos, editors, Minimax and Applications, 97–107. Kluwer Academic Publishers, 1995.
Y. Cho and S. Sahni. Bounds for list schedules on uniform processors. SIAM J. Comput., 9(1):91–103, 1980.
E. Davis and J. M. Jaffe. Algorithms for scheduling tasks on unrelated processors. J. ACM, 28(4):721–736, 1981.
X. Deng and P. Dymond. On multiprocessor system scheduling. In Proc. of the 7th Ann. ACM Symp. on Parallel Algorithms and Architectures, 82–88. ACM, 1996.
X. Deng, N. Gu, T. Brecht, and K. Lu. Preemptive scheduling of parallel jobs on multiprocessors. In Proc. of the 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, 159–167. ACM-SIAM, 1996.
X. Deng and E. Koutsoupias. Competitive implementation of parallel programs. In Proc. of the 4th Ann. ACM-SIAM Symp. on Discrete Algorithms, 455–461. ACM-SIAM, 1993.
X. Deng, E. Koutsoupias, and P. MacKenzie. Competitive implementation of parallel programs. To appear in Algorithmica, 1998.
M. Dertouzos and A. Mok. Multiprocessor on-line scheduling with release dates. IEEE Transactions on Software Engineering, 15:1497–1506, 1989.
J. Edmonds, D. D. Chinn, T. Brecht, and X. Deng. Non-clairvoyant multiprocessor scheduling of jobs with changing execution characteristics. In Proc. of the 29th Ann. ACM Symp. on Theory of Computing, 120–129. ACM, 1997.
L. Epstein, J. Noga, S. S. Seiden, J. Sgall, and G. J. Woeginger. Randomized online scheduling for two related machines. Work in progress, 1997.
U. Faigle, W. Kern, and G. Turan. On the performance of on-line algorithms for partition problems. Acta Cybernetica, 9:107–119, 1989.
U. Faigle and W. M. Nawijn. Note on scheduling intervals on-line. Discrete Applied Mathematics, 58:13–17, 1995.
A. Feldmann, M.-Y. Kao, J. Sgall, and S.-H. Teng. Optimal on-line scheduling of parallel jobs with dependencies. In Proc. of the 25th Ann. ACM Symp. on Theory of Computing, 642–651. ACM, 1993. To appear in a special issue of J. of Combinatorial Optimization on scheduling.
A. Feldmann, B. Maggs, J. Sgall, D. D. Sleator, and A. Tomkins. Competitive analysis of call admission algorithms that allow delay. Technical Report CMU-CS-95-102, Carnegie-Mellon University, Pittsburgh, PA, U.S.A., 1995.
A. Feldmann, J. Sgall, and S.-H. Teng. Dynamic scheduling on parallel machines. Theoretical Comput. Sci., 130(1):49–72, 1994.
A. Fiat and G. J. Woeginger. On-line scheduling on a single machine: Minimizing the total completion time. Technical Report Woe-04, TU Graz, Austria, 1997.
G. Galambos and G. J. Woeginger. An on-line scheduling heuristic with better worst case ratio than Graham's list scheduling. SIAM J. Comput., 22(2):349–355, 1993.
G. Galambos and G. J. Woeginger. On-line bin packing — a restricted survey. ZOR — Mathematical Methods of Operations Research, 42:25–45, 1995.
M. R. Garey and D. S. Johnson. Computers and Intractability: a Guide to the Theory of NP-compteteness. Freeman, 1979.
M. X. Goemans. Improved approximation algorithms for scheduling with release dates. In Proc. of the 8th Ann. ACM-SIAM Symp. on Discrete Algorithms, 591–598. ACM-SIAM, 1997.
M. X. Goemans, M. Queyranne, A. S. Schulz, M. Skutella, and Y. Wang. Manuscript, 1997.
T. F. Gonzales and D. B. Johnson. A new algorithm for preemptive scheduling of trees. J. ACM, 27:287–312, 1980.
R. L. Graham. Bounds for certain multiprocessor anomalies. Bell System Technical J., 45:1563–1581, Nov. 1966.
R. L. Graham. Bounds on multiprocessor timing anomalies. SIAM J. Appl. Math., 17(2):416–429, 1969.
L. A. Hall, A. S. Schulz, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Mathematics of Operations Research, 22:513–544, 1997.
L. A. Hall and D. B. Shmoys. Approximation schemes for constrained scheduling problems. In Proc. of the 30th Ann. IEEE Symp. on Foundations of Computer Sci., 134–139. IEEE, 1989.
L. A. Hall, D. B. Shmoys, and J. Wein. Scheduling to minimize average completion time: Off-line and on-line algorithms. In Proc. of the 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, 142–151. ACM-SIAM, 1996.
K. S. Hong and J. Y.-T. Leung. On-line scheduling of real-time tasks. IEEE Transactions on Computers, 41(10):1326–1331, 1992.
J. A. Hoogeveen and A. P. A. Vestjens. Optimal on-line algorithms for singlemachine scheduling. In Proc. of the 5th Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 1084, 404–414. Springer-Verlag, 1996.
S. Irani and V. Leung. Scheduling with conflicts, and applications to traffic signal control. In Proc. of the 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, 85–94. ACM-SIAM, 1996.
B. Kalyanasundaram and K. R. Pruhs. Fault-tolerant scheduling. In Proc. of the 26th Ann. ACM Symp. on Theory of Computing, 115–124. ACM, 1994.
B. Kalyanasundaram and K. R. Pruhs. Speed is as powerful as clairvoyance. In Proc. of the 36th Ann. IEEE Symp. on Foundations of Computer Sci., 214–221. IEEE, 1995.
B. Kalyanasundaram and K. R. Pruhs. Fault-tolerant real-time scheduling. In Proc. of the 5th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci. 1284, 296–307. Springer-Verlag, 1997.
D. Karger, C. Stein, and J. Wein. Scheduling algorithms. To appear in Handbook of Algorithms and Theory of Computation, M. J. Atallah, editor. CRC Press, 1997.
D. R. Karger, S. J. Phillips, and E. Torng. A better algorithm for an ancient scheduling problem. J. of Algorithms, 20:400–430, 1996.
H. Kellerer, V. Kotov, M. G. Speranza, and Z. Tuza. Semi on-line algorithms for the partition problem. To appear in Oper. Res. Lett., 1998.
H. Kellerer, T. Tautenhahn, and G. J. Woeginger. Approximability and nonaproximability results for minimizing total flow time on a single machine. In Proc. of the 28th Ann. ACM Symp. on Theory of Computing, 418–426. ACM, 1996. To appear in SIAM J. Comput.
J. Labetoulle, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Preemptive scheduling of uniform machines subject to release dates. In W. R. Pulleyblank, editor, Progress in Combinatorial Optimization, 245–261. Academic Press, 1984.
E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys. Sequencing and scheduling: Algorithms and complexity. In S. C. Graves, A. H. G. Rinnooy Kan, and P. Zipkin, editors, Handbooks in Operations Research and Management Science, Vol. 4: Logistics of Production and Inventory, 445–552. North-Holland, 1993.
S. Leonardi and A. Marchetti-Spaccamela. On-line resource management with application to routing and scheduling. In Proc. of the 22th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Comput. Sci. 944, 303–314. Springer-Verlag, 1995. To appear in Algorithmica.
S. Leonardi and D. Raz. Approximating total flow time with preemption. In Proc. of the 29th Ann. ACM Symp. on Theory of Computing, 110–119. ACM, 1997.
R. J. Lipton and A. Tomkins. On-line interval scheduling. In Proc. of the 5th Ann. ACM-SIAM Symp. on Discrete Algorithms, 302–305. ACM-SIAM, 1994.
R. Motwani, S. Phillips, and E. Torng. Non-clairvoyant scheduling. Theoretical Comput. Sci., 130:17–47, 1994.
C. Philips, C. Stein, and J. Wein. Minimizing average completion time in the presence of release dates. In Proc. of the 4th Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 955, 86–97. Springer-Verlag, 1995. To appear in Math. Programming.
C. A. Phillips, C. Stein, E. Torng, and J. Wein. Optimal time-critical scheduling via resource augmentation. In Proc. of the 29th Ann. ACM Symp. on Theory of Computing, 140–149. ACM, 1997.
S. Sahni and Y. Cho. Nearly on line scheduling of a uniform processor system with release times. SIAM J. Comput., 8(2):275–285, 1979.
A. S. Schulz and M. Skutella. Scheduling-LPs bear probabilities: Randomized approximations for min-sum criteria. Technical Report 533/1996, Department of Mathematics, Technical University of Berlin, Berlin, Germany, 1996 (revised 1997).
A. S. Schulz and M. Skutella. Scheduling-LPs bear probabilities. In Proc. of the 5th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci. 1284, 416–429. Springer-Verlag, 1997.
S. S. Seiden. More multiprocessor scheduling with rejection. Technical Report Woe-16, TU Graz, Austria, 1997.
S. S. Seiden. Randomization in On-line Computation. PhD thesis, University of California, Irvine, CA, U.S.A., 1997.
S. S. Seiden. A randomized algorithm for that ancient scheduling problem. In Proc. of the 5th Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 1272, 210–223. Springer-Verlag, 1997.
J. Sgall. On-Line Scheduling on Parallel Machines. PhD thesis, Technical Report CMU-CS-94-144, Carnegie-Mellon University, Pittsburgh, PA, U.S.A., 1994.
J. Sgall. Randomized on-line scheduling of parallel jobs. J. of Algorithms, 21:149–175, 1996.
J. Sgall. A lower bound for randomized on-line multiprocessor scheduling. Inf. Process. Lett., 63(1):51–55, 1997.
D. B. Shmoys, J. Wein, and D. P. Williamson. Scheduling parallel machines online. SIAM J. Comput., 24:1313–1331, 1995.
D. D. Sleator. A 2.5 times optimal algorithm for packing in two dimensions. Inf. Process. Lett., 10:37–40, 1980.
A. Steinberg. A strip-packing algorithm with absolute performance bound 2. SIAM J. Comput., 26(2):401–409, 1997.
L. Stougie. Personal communication, 1995.
L. Stougie and A. P. A. Vestjens. Randomized on-line scheduling: How low can't you go? Manuscript, 1997.
A. P. A. Vestjens. Scheduling uniform machines on-line requires nondecreasing speed ratios. Technical Report Memorandum COSOR 94-35, Eindhoven University of Technology, 1994. To appear in Math. Programming.
A. P. A. Vestjens. On-line Machine Scheduling. PhD thesis, Eindhoven University of Technology, The Netherlands, 1997.
Q. Wang and K. H. Cheng. A heuristic of scheduling parallel tasks and its analysis. SIAM J. Comput., 21(2):281–294, 1992.
G. J. Woeginger. On-line scheduling of jobs with fixed start and end times. Theretical Comput. Sci., 130:5–16, 1994.
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Sgall, J. (1998). On-line scheduling. In: Fiat, A., Woeginger, G.J. (eds) Online Algorithms. Lecture Notes in Computer Science, vol 1442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0029570
Download citation
DOI: https://doi.org/10.1007/BFb0029570
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64917-5
Online ISBN: 978-3-540-68311-7
eBook Packages: Springer Book Archive