Scheduling Multiple Divisible Loads

Abstract

In this paper we study the scheduling of multiple divisible loads on a star network of processors. We show that this problem is computationally hard. Special cases solvable in polynomial time are identified.

Keywords

divisible loads scheduling computational complexity

Get full access to this article

View all access options for this article.

References

Beaumont, O. , Casanova, H. , Legrand, A. , Robert, Y. , and Yang, Y. 2005. Scheduling divisible loads on star and tree networks: results and open problems , IEEE Transactions on Parallel and Distributed Systems 16: 207–218 .

Bharadwaj, V. , Ghose, D. , Mani, V. , and Robertazzi, T. 1996. Scheduling Divisible Loads in Parallel and Distributed Systems, IEEE Computer Society Press, Los Alamitos, CA .

Blazewicz, J. and Drozdowski, M. 1997. Distributed processing of divisible jobs with communication startup costs . Discrete Applied Mathematics 76: 21–41 .

Blazewicz, J. , Ecker, K. , Pesch, E. , Schmidt, G. , and Weglarz, J. 1996. Scheduling Computer and Manufacturing Processes, Springer-Verlag, Heidelberg .

Drozdowski, M. 1997. Selected Problems of Scheduling Tasks in Multiprocessor Computer Systems, Series Monographs, No. 321, Poznan University of Technology Press, Poznan (http://www.cs.put.poznan.pl/mdrozdowski/h.ps).

Drozdowski, M. , Lawenda, M. , and Guinand, F. 2004. Scheduling multiple divisible loads. Technical Report RA-007/04, Institute of Computing Science, Poznan University of Technology (http://www.cs.put.poznan.pl/mdrozdowski/xrapIIn/RA07-04ps.zip).

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

Johnson, S. M. 1954. Optimal two and three-stage production schedules with setup times included . Naval Research Logistics Quarterly 1: 61–67 .

Ko, K. , and Robertazzi, T. G. 2002. Scheduling in an environment of multiple job submission. Proceedings of the Conference on Information Sciences and Systems, Princeton University, Princeton NJ , March.

10.

Marchal, L. , Yang, Y. , Casanova, H. , and Robert, Y. 2004. A realistic network/application model for scheduling divisible loads on large-scale platforms. Research Report 2004-21, École Normale Supérieure de Lyon, Laboratoire de l’Informatique du Parallélisme .

11.

Pinedo, M. 1995. Scheduling: Theory, Algorithms, and Systems, Prentice-Hall, Englewood Cliffs, NJ .

12.

Robertazzi, T. 2003. Ten reasons to use divisible load theory , Computer 36: 63–68 .

13.

Sohn, J. and Robertazzi, T. 1994. A multijob load sharing strategy for divisible jobs on bus networks. Technical Report 697, Department of Electrical Engineering, SUNY at Stony Brook, Stony Brook, New York .

14.

Veeravalli, B. and Barlas, G. 2002. Efficient scheduling strategies for processing multiple divisible loads on bus networks . Journal of Parallel and Distributed Computing 62: 132–151 .