The combinatorics in divisible load scheduling

• Autorzy: Drozdowski M. , Lawenda M.
• Języki publikacji: EN

Abstrakty

EN

Divisible load scheduling problem is studied in this work. Though tractability of this problem in the practical cases is considered as its great advantage, we show that it has a hard combinatorial core. Computational hardness and polynomial time solvability of some special cases are shown.

Słowa kluczowe

EN

divisible loads; scheduling; computational complexity

PL

szeregowanie

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2005
• Tom: Vol. 30, No. 4
• Strony: 297--308
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Drozdowski M.

• Institute of Computing Science, Poznań University of Technology, ul.Piotrowo ЗА, 60-965 Poznań, Poland

autor

Lawenda M.

• Poznań Supercomputing and Networking Center, ul. Noskowskiego 10, 61-794 Poznań, Poland

Bibliografia

• [1] Bharadwaj V., Ghose D., Mani V., Optimal Sequencing and Arrangement in Distributed Single-Level Tree Networks with Communication Delays, IEEE Trans. on Parallel and Distributed Systems, 5, 9, 1994, 968-976.
• [2] Bharadwaj V., Ghose D., Mani V., Robertazzi Т., Scheduling divisible loads in parallel and distributed systems, IEEE Computer Society Press, Los Alamitos, 1996.
• [3] Bharadwaj V., Ghose D., Robertazzi Т., Divisible load theory: A new paradigm for load scheduling in distributed systems. Cluster Computing, 6, 1, 2003, 7-17.
• [4] Błażewicz J., Drozdowski M., Distributed processing of divisible jobs with communication startup costs. Discrete Applied Mathematics, 76, 1-3, 1997, 21-41.
• [5] Błażewicz J., Drozdowski M., Ecker K., Management of Resources in Parallel Systems, in: J.Błażewicz, К. Ecker, В. Plateau, D. Trystram, Handbook on Parallel and Distributed Processing, Springer, Heidelberg, 2000, 263-341.
• [6] Charcranoon S., Robertazzi Т., Luryi S., Load sequencing for a parallel processing utility, Journal of Parallel and Distributed Computing, 64, 1, 2004, 29-35.
• [7] Drozdowski M., Selected problems of scheduling tasks in multiprocessor computer systems, Poznań University of Technology Press, Series: Monographs, No.321, Poznań (1997). Also: http://www.cs.put.poznan.pl/~maciejd/txt/h.ps
• [8] Drozdowski M., Wolniewicz P., Optimum divisible load scheduling on heterogeneous stars with limited memory, 2002, accepted in European Journal of Operational Research.
• [9] Garey M.R., Johnson D.S., Computers and Intractability: A guide to the theory of NP-completeness, Freeman, San Francisco, 1979.
• [10] Robertazzi Т., Ten reasons to use divisible load theory, IEEE Computer, 36, 5, 2003, 63-68.
• [11] Sohn J., Robertazzi Т., Luryi S., Optimizing computing costs using divisible load analysis, IEEE Trans. on Parallel and Distributed Systems, 9, 3, 1998, 225-234.
• [12] Xiaolin L., Studies on Divisible Load Scheduling Strategies in Distributed Computing Systems: Design, Analysis and Experiments, PhD thesis, National University of Singapore, 2001.