Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays

1. Graham, R.L., Lawler, E.L., Lenstra, J.K., and Rinnooy Kan, A.H.G., Optimization and Approximation in Deterministic Scheduling: A Survey, Ann. Discret. Math., 1979, vol. 5, pp. 287–326.

   Article  MATH  MathSciNet  Google Scholar 

2. Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., and Shmoys, D.B., Sequencing and Scheduling: Algorithms and Complexity, in Logist. Product. Inventory, vol. 4 of Handbooks in Operation Research and Management Science, Amsterdam: Elsevier, 1993, pp. 445–522.

   Chapter  Google Scholar 

3. Tanaev, V.S., Gordon, V.S., and Shafransky, Ya.N., Teoriya raspisanii. Odnostadiinye sistemy (Theory of Scheduling. Single-stage Systems), Moscow: Nauka, 1984.

   Google Scholar 

4. McNaughton, R., Scheduling with Deadlines and Loss Functions, Manage. Sci., 1959, vol. 6, no. 1, pp. 1–12.

   Article  MATH  MathSciNet  Google Scholar 

5. Karp, R.M., Reducibility among Combinatorial Problems, in Complexity of Computer Computations, Miller, R.E. and Thatcher, J.W., Eds., New York: Plenum, 1972, pp. 85–103.

   Google Scholar 

6. Rothkopf, M.H., Scheduling Independent Tasks on Parallel Processors, Manage. Sci., 1966, vol. 12, no. 5, pp. 437–447.

   Article  MathSciNet  Google Scholar 

7. Hochbaum, D.S. and Shmoys, D., A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach, SIAM J. Comput., 1988, vol. 17, no. 3, pp. 539–551.

   Article  MATH  MathSciNet  Google Scholar 

8. Gordon, V.S. and Tanaev, V.S., Interruptions in Deterministic Systems with Parallel Machines and Arbitrary Release Dates, in Optimization of Collecting, Transmitting and Processing the Analogous and Discrete Information in Local ICS, Proc. of the 1st Joint Soviet-bulgarian Workshop of IEC AS BSSR—IEC BAS, Minsk, 1973, pp. 36–50.

9. Tanaev, V.S., Interruptions in Deterministic Service Systems with Identical Parallel Machines, Izv. Akad. Nauk BSSR, Ser. Fiz.-mat. Nauk, 1973, no. 6, pp. 44–48.

10. Hanen, C. and Munier, A., An Approximation Algorithm for Scheduling Dependent Tasks on m Processors with Small Communication Delays, Discret. Appl. Math., 2001, vol. 108, no. 3, pp. 239–257.

    Article  MATH  MathSciNet  Google Scholar 

11. Hoogeveen, J.A., Lenstra, J.K., and Veltman, B., Three, Four, Five, Six, or the Complexity of Scheduling with Communication Delays, Oper. Res. Lett., 1994, vol. 16, no. 3, pp. 129���137.

    Article  MATH  MathSciNet  Google Scholar 

12. Schuurman, P. and Woeginger, G.J., Polynomial Time Approximation Algorithms for Machine Scheduling: Ten Open Problems, J. Schedul., 1999, vol. 2, no. 5, pp. 203–213.

    Article  MATH  MathSciNet  Google Scholar 

13. Engels, D.W., Feldman, J., Karger, D.R., and Ruhl, M., Parallel Processor Scheduling with Delay Constraints, in Proc. of the SODA, Washington, 2001, pp. 577–585.

14. Afrati, F.N., Bampis, E., Finta, L., and Milis, I., Scheduling Trees with Large Communication Delays on two Identical Processors, J. Schedul., 2005, vol. 8, no. 2, pp. 179–190

    Article  MATH  MathSciNet  Google Scholar 

15. Engels, D.W., Scheduling for Hardware-software Partitioning in Embedded System Design, PhD Thesis, Cambridge: Massachusetts Inst. of Technology, 2000.

    Google Scholar 

16. Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-completeness, San Francisco: Freeman, 1979.

    MATH  Google Scholar 

17. Blum, M., Floyd, R., Pratt, V., Rivest, R., and Tarjan, R., Time Bounds for Selection, J. Comp. Syst. Sci., 1973.

Download references