A simple linear time approximation algorithm for multi-processor job scheduling on four processors
Tóm tắt
Multiprocessor job scheduling problem has become increasingly interesting, for both theoretical study and practical applications. Theoretical study of the problem has made significant progress recently, which, however, seems not to imply practical algorithms for the problem, yet. Practical algorithms have been developed only for systems with three processors and the techniques seem difficult to extend to systems with more than three processors. This paper offers new observations and introduces new techniques for the multiprocessor job scheduling problem on systems with four processors. A very simple and practical linear time approximation algorithm of ratio bounded by 1.5 is developed for the multi-processor job scheduling problem P
4|fix|C
max, which significantly improves previous results. Our techniques are also useful for multiprocessor job scheduling problems on systems with more than four processors.
Tài liệu tham khảo
Amoura AK, Bampis E, Kenyon C, Manoussakis Y (2002) Scheduling independent multiprocessor tasks. Algorithmica 32:247–261
Bianco L, Blazewicz J, Dell’Olmo P, Drozdowski M (1995) Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors. Ann Oper Res 58:493–517
Blazewicz J, Dell’Olmo P, Drozdowski M, Speranza M (1992) Scheduling multiprocessor tasks on the three dedicated processors. Inf Proc Lett 41:275–280
Blazewicz J, Dell’Olmo P, Drozdowski M, Speranza M (1992/1994) Corrigendum to Scheduling multiprocessor tasks on the three dedicated processors. Inf Proc Lett 41:275–280. Inf Proc Lett 49:269–270
Blazewicz J, Drozdowski M, Weglarz J (1986) Scheduling multiprocessor tasks to minimize scheduling length. IEEE Trans Comput 35:389–393
Blazewicz J, Drozdowski W, Weglarz J (1994) Scheduling multiprocessor tasks—a survey. Int J Microcomput Appl 13:89–97
Chen J, Lee C-Y (1999) General multiprocessor tasks scheduling. Naval Res Log 46:59–74
Chen J, Miranda A (2001) A polynomial time approximation scheme for general multiprocessor job scheduling. SIAM J Comput 31:1–17
Dell’Olmo P, Speranza MG, Tuza Zs (1997) Efficiency and effectiveness of normal schedules on three dedicated processors. Discrete Math 164:67–79
Dobson G, Karmarkar U (1989) Simultaneous resource scheduling to minimize weighted flow times. Oper Res 37:592–600
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco
Goemans MX (1995) An approximation algorithm for scheduling on three dedicated machines. Discrete Appl Math 61:49–59
Graham RL (1966) Bounds for certain multiprocessing anomalies. Bell Sys Tech J 45:1563–1581
Hall LA (1997) Approximation algorithms for scheduling. In: Hochbaum DS, (ed.) Approximation algorithms for NP-hard problems. PWS Publishing Company, pp 1–45
Hoogeveen JA, van de Velde SL, Veltman B (1994) Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete Appl Math 55:259–272
Jansen K, Porkolab L (2005) General multiprocessor task scheduling: approximate solutions in linear time. SIAM J Comput 35:519–530
Krawczyk H, Kubale M (1985) An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Trans Comput 34:869–872
Lee C-Y, Cai X (1999) Scheduling one and two-processor tasks on two parallel processors. IIE Trans 31:445–455
Lee C-Y, Lei L, Pinedo M (1997) Current trends in deterministic scheduling. Ann Ope Res 70:1–42