Scheduling rooted forests with communication delays
Order - 1994
Tóm tắt
We show that a greedy algorithm for scheduling unit time jobs on two machines with unit communication delays produces an optimal schedule when the precedence constraints are given by a rooted forest. We also give a min/max relationship for the length of such a schedule. The min/max result (for forests and two machines) shows that the addition of unit communication delays increases the optimal schedule length by at most one.
Từ khóa
Tài liệu tham khảo
Chretienne, P. and Picouleau, C. (1992) Scheduling with communication delays: A survey, inPr Summer School on Scheduling Theory and its Applications, to appear.
Lawler, E. L. (1993) Scheduling trees on multiprocessors with unit communication delays, manuscript.
Lawler, E. L. and Lenstra, J. K. (1982) Machine scheduling with precedence constraints, in I. Rival (ed.),Ordered Sets, Reidel, 655–675.
Lawler, E. L., Lenstra, J. K., Rinooy Kan, A. H. J., and Shmoys, D. (1993) Sequencing and scheduling: algorithms and complexity, in S. C. Graveset al. (eds),Handbook in Operations Research and Management Science, vol. 4;Logistics of Production and Inventory, Elsevier, 445–522.
Lenstra, J. K., Veldhorst, M., and Veltman, B. (1993) The complexity of scheduling trees with communication delays, manuscript, preliminary version, in T. Lengauer (ed.),Algorithms — ESA '93, Lecture Notes in Computer Science 726, Springer-Verlag, 284–294.
Picouleau, C. (1992)Etude de problèmes d'optimisation dans les systèmes distributes, Ph.D. Thesis, Univ. Pierre et Marie Curie, Paris.
Poguntke, W. (1986) Order-theoretic aspects of scheduling, in I. Rival (ed.),Combinatorics and Ordered Sets, AMS Contemp. Math., vol. 57, 1–31.
Rayward-Smith, V. J. (1987) UET scheduling with unit interprocessor communication delays,Disc. Appl. Math. 18, 55–71.
Varvarigou, T. A., Roychowdhury, V. P., and Kailath, T. (1992) Scheduling in and out forests in the presence of communication delays, manuscript.
Veltman, B., Lageway, B. J., and Lenstra, J. K. (1990) Multiprocessor scheduling with communication delays,Parallel Computing 16, 173–182.