Online Scheduling with Bounded Migration

References

• Afrati F., Bampis E., Chekuri C., Karger D., Kenyon C., Khanna S., Milis I., et al. Approximation schemes for minimizing average weighted completion time with release dates. Proc. 40th Annual IEEE Sympos. Foundations Comput. Sci. (1999) (New York)32–43Google Scholar
• Albers S. Better bounds for online scheduling. SIAM J. Comput. (1999) 29:459–473Crossref, Google Scholar
• Albers S. Online algorithms: A survey. Math. Programming (2003) 97:3–26Crossref, Google Scholar
• Andrews M., Goemans M. X., Zhang L. Improved bounds for on-line load balancing. Algorithmica (1999) 23:278–301Crossref, Google Scholar
• Azar Y., Epstein L. On-line machine covering. J. Algorithms (1998) 1:67–77Google Scholar
• Bartal Y., Fiat A., Karloff H., Vohra R. New algorithms for an ancient scheduling problem. J. Comput. System Sci. (1995) 51:359–366Crossref, Google Scholar
• Brinkmann A., Salzwedel K., Scheideler C. Compact, adaptive placement schemes for non-uniform requirements. 14th ACM Sympos. Parallel Algorithms and Architectures (2002) (ACM, New York) 53–62Google Scholar
• Chen B., van Vliet A., Woeginger G. J. Lower bounds for randomized online scheduling. Inform. Processing Lett. (1994) 51:219–222Crossref, Google Scholar
• Coffman E. G., Garey M. R., Johnson D. S. An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. (1978) 7:1–17Crossref, Google Scholar
• Epstein L., Levin A., Bugliesi M., Preneel B., Sassone V., Wegener I. A robust APTAS for the classical bin packing problem. Automata, Languages and Programming (2006) 4051(Springer, Berlin) 214–225Lecture Notes in Computer ScienceCrossref, Google Scholar
• Fleischer R., Wahl M. Online scheduling revisited. J. Scheduling (2000) 3:343–353Crossref, Google Scholar
• Friesen D. K. Tighter bounds for the multifit processor scheduling algorithm. SIAM J. Comput. (1984) 13:170–181Crossref, Google Scholar
• Garey M. R., Johnson D. S. Strong np-completeness results: Motivation, examples and implications. J. ACM (1978) 25:499–508Crossref, Google Scholar
• Graham R. L. Bounds for certain multiprocessing anomalies. Bell System Tech. J. (1966) 45:1563–1581Crossref, Google Scholar
• Graham R. L. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. (1969) 17:263–269Crossref, Google Scholar
• Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Hochbaum D. S., Hochbaum D. S. Various notions of approximation: Good, better, best, and more. Approximation Algorithms for NP-Hard Problems (1996) (Thomson, PWS Publishing Company, Boston) 346–398Google Scholar
• Hochbaum D. S., Shmoys D. B. Using dual approximation algorithms for scheduling problems: Theoretical and practical results. J. ACM (1987) 34:144–162Crossref, Google Scholar
• Karger D. R., Phillips S. J., Torng E. A better algorithm for an ancient scheduling problem. J. Algorithms (1996) 20:400–430Crossref, Google Scholar
• Langston M. A. Processor scheduling with improved heuristic algorithms. (1981) . Ph.D. thesis, Texas A&M University, College StationGoogle Scholar
• Lenstra H. W. Integer programming with a fixed number of variables. Math. Oper. Res. (1983) 8:538–548Link, Google Scholar
• Patterson D., Gibson G., Katz R. A case for redundant arrays of inexpensive disks (RAID). Proc. ACM SIGMOD'88 (1988) (ACM, New York) 109–116Google Scholar
• Rudin J. F. Improved bounds for the on-line scheduling problem. (2001) . Ph.D. thesis, The University of Texas at Dallas, RichardsonGoogle Scholar
• Rudin J. F., Chandrasekaran R. Improved bounds for the online scheduling problem. SIAM J. Comput. (2003) 32:717–735Crossref, Google Scholar
• Sahni S. Algorithms for scheduling independent tasks. J. ACM (1976) 23:116–127Crossref, Google Scholar
• Sanders P. Algorithms for scalable storage servers. SOFSEM 2004: Theory and Practice of Computer Science, LNCS (2004) 2932(Springer, Berlin) 82–101Crossref, Google Scholar
• Sanders P., Sivadasan N., Skutella M., Diaz J., Karhumäki J., Lepistö A., Sannella D. Online scheduling with bounded migration. Automata, Languages and Programming (2004) 3142(Springer, Berlin) 1111–1122Lecture Notes in Computer ScienceCrossref, Google Scholar
• Schrijver A.Theory of Linear and Integer Programming (1986) (John Wiley & Sons, Chichester, UK) Google Scholar
• Sgall J. A lower bound for randomized on-line multiprocessor scheduling. Inform. Processing Lett. (1997) 63(1):51–55Crossref, Google Scholar
• Sgall J., Fiat A., Woeginger G. J. On-line scheduling—A survey. Online Algorithms: The State of the Art (1998) 1442(Springer, Berlin) 196–231Lecture Notes in Computer ScienceCrossref, Google Scholar
• Sgall J. Personal communication. (2008) NovemberGoogle Scholar
• Westbrook J. Load balancing for response time. J. Algorithms (2000) 35:1–16Crossref, Google Scholar
• Woeginger G. J. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Oper. Res. Lett. (1997) 20:149–154Crossref, Google Scholar