Eliminating Migration in Multi-processor Scheduling

Baruah, 1994, On-line scheduling to maximize task completions Baruah, 1992, On the competitiveness of on-line real-time task scheduling, J. Real-Time Systems, 4, 124, 10.1007/BF00365406 Bollobas, 1978 Brucker, 1995 P. Brucker, J. Hurink, and, S. Knust, Complexity results of scheduling problems, http://www.mathematik.uni-osnabrueck.de/research/OR/class. Dertouzos, 1989, Multiprocessor online scheduling of hard real-time tasks, IEEE Trans. Software Engrg., 15, 1497, 10.1109/32.58762 Edmonds, 1972, Theoretical improvements in algorithmic efficiency for network flow problems, J. ACM, 19, 248, 10.1145/321694.321699 Hall, 1997, Approximation algorithms for scheduling Kalyanasundaram, 1995, Speed is as powerful as clairvoyance, IEEE Foundations Comput. Sci., 214, 10.1109/SFCS.1995.492478 Kalyanasundaram, 1998, Maximizing job completions online, European Symp. Algorithms, 235 Koren, 1998, The power of migration in multi-processor scheduling of real-time systems, ACM/SIAM Symp. Discrete Algorithms, 226 Koren, 1994, MOCA: A multiprocessor on-line competitive algorithm for real-time systems scheduling, Theoret. Comput. Sci., 128, 75, 10.1016/0304-3975(94)90165-1 Lam, 1999, Trade-offs between speed and processor in hard-deadline scheduling, ACM/SIAM Symp. Discrete Algorithms, 623 Lawler, 1990, A dynamic programming algorithm for preemptive scheduling on a single machine to minimize the number of late jobs, Ann. Operations Res., 26, 125, 10.1007/BF02248588 Lawler, 1993, Sequencing and scheduling: Algorithms and complexity Phillips, 1997, Optimal time-critical scheduling via resource augmentation, ACM Symp. Theory Comput., 140 Sgall, 1998, On-line scheduling, 1442 Tarjan, 1983 Woeginger, 1994, On-line scheduling of jobs with fixed start and end time, Theoret. Comput. Sci., 130, 5, 10.1016/0304-3975(94)90150-3 Woeginger, 1999, When does a dynamic programming formulation guarantee the existence of an FPTAS?, ACM/SIAM Symp. Discrete Algorithms, 820