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.
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 Systems16:
207–218
.
2.
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
.
3.
Blazewicz, J.
and
Drozdowski, M.1997.
Distributed processing of divisible jobs with communication startup costs
. Discrete Applied Mathematics76:
21–41
.
4.
Blazewicz, J.
,
Ecker, K.
,
Pesch, E.
,
Schmidt, G.
, and
Weglarz, J.1996. Scheduling Computer and Manufacturing Processes,
Springer-Verlag, Heidelberg
.
5.
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).
6.
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).
7.
Garey, M. R.
and
Johnson, D. S.1979. Computers and Intractability: A Guide to the Theory of
NP-Completeness,
Freeman, San Francisco
.
8.
Johnson, S. M.1954.
Optimal two and three-stage production schedules with setup times included
. Naval Research Logistics Quarterly1:
61–67
.
9.
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
.
Robertazzi, T.2003.
Ten reasons to use divisible load theory
, Computer36:
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 Computing62:
132–151
.
