Abstract
We present hardness and approximation results for the problem of preemptive scheduling of n independent jobs on m identical parallel machines subject to a migration delay d with the objective to minimize the makespan. We give a sharp threshold on the value of d for which the complexity of the problem changes from polynomial time solvable to NP-hard. Next, we give initial results supporting a conjecture that there always exists an optimal schedule with at most m − 1 job migrations. Finally, we provide a O(n) time (1 + 1/log2 n)-approximation algorithm for m = 2.
Similar content being viewed by others
References
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.
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.
Tanaev, V.S., Gordon, V.S., and Shafransky, Ya.N., Teoriya raspisanii. Odnostadiinye sistemy (Theory of Scheduling. Single-stage Systems), Moscow: Nauka, 1984.
McNaughton, R., Scheduling with Deadlines and Loss Functions, Manage. Sci., 1959, vol. 6, no. 1, pp. 1–12.
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.
Rothkopf, M.H., Scheduling Independent Tasks on Parallel Processors, Manage. Sci., 1966, vol. 12, no. 5, pp. 437–447.
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.
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.
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.
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.
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.
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.
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.
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
Engels, D.W., Scheduling for Hardware-software Partitioning in Embedded System Design, PhD Thesis, Cambridge: Massachusetts Inst. of Technology, 2000.
Garey, M.R. and Johnson, D.S., Computers and Intractability: A Guide to the Theory of NP-completeness, San Francisco: Freeman, 1979.
Blum, M., Floyd, R., Pratt, V., Rivest, R., and Tarjan, R., Time Bounds for Selection, J. Comp. Syst. Sci., 1973.
Author information
Authors and Affiliations
Additional information
Original Russian Text © S.V. Sevastyanov, R.A. Sitters, A.V. Fishkin, 2010, published in Avtomatika i Telemekhanika, 2010, No. 10, pp. 90–99.
This work was supported by the Russian Foundation for Basic Research, project no. 08-01-00370.
Rights and permissions
About this article
Cite this article
Sevastyanov, S.V., Sitters, R.A. & Fishkin, A.V. Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays. Autom Remote Control 71, 2093–2101 (2010). https://doi.org/10.1134/S0005117910100085
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0005117910100085