Scheduling multiple divisible loads in homogeneous star systems
Tóm tắt
In this paper we analyze scheduling multiple divisible loads on a star-connected system of identical processors. It is shown that this problem is computationally hard. Some special cases appear to be particularly difficult, so it is not even known if they belong to the class NP. Exponential algorithms and special cases solvable in polynomial time are presented.
Tài liệu tham khảo
Bharadwaj, V., Ghose, D., Mani, V., & Robertazzi, T. (1996). Scheduling divisible loads in parallel and distributed systems. Los Alamitos: IEEE Computer Society Press.
Drozdowski, M. (1997). Monographs : Vol. 321. Selected problems of scheduling tasks in multiprocessor computer systems. Poznan University of Technology Press: Poznan. Downloadable from http://www.cs.put.poznan.pl/mdrozdowski/txt/h.ps.
Drozdowski, M., Lawenda, M., & Guinand, F. (2006). Scheduling multiple divisible loads. International Journal of High Performance Computing, 20(1), 19–30.
England, D., Veeravalli, B., & Weissman, J. B. (2007). A robust spanning tree topology for data collection and dissemination in distributed environments. IEEE Transactions on Parallel and Distributed Systems, 18(5), 608–620.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. San Francisco: Freeman.
Robertazzi, T. (2003). Ten reasons to use divisible load theory. IEEE Computer, 36(5), 63–68.
Rothkopf, M. H. (1966). Scheduling independent tasks on parallel processors. Management Science, 12, 347–447.
Sohn, J., & Robertazzi, T. (1994). A muli-job load sharing strategy for divisible jobs on bus networks (Technical Report 697). Department of Electrical Engineering, SUNY at Stony Brook, Stony Brook, New York.
Veeravalli, B., & Barlas, G. (2002). Efficient scheduling strategies for processing multiple divisible loads on bus networks. Journal of Parallel and Distributed Computing, 62, 132–151.