The Multiprocessor Scheduling of Precedence-Constrained Task Systems in the Presence of Interprocessor Communication Delays

References

• Ali H., El-Rewini H. An optimal algorithm for scheduling interval ordered tasks with communication on N processors. (1991) . Technical report TR-91-20, University of Nebraska at Omaha, Department of Computer ScienceGoogle Scholar
• Chrétienne P. Tree scheduling with communication delays. Discrete Appl. Math. (1994) 49:129–141Crossref, Google Scholar
• Chrétienne P., Picouleau C., Chrétienne, et al. Scheduling with communication delays: A survey. Scheduling Theory and Its Applications (1995) (John Wiley and Sons)Google Scholar
• Colin J. Y., Chrétienne P. CPM scheduling with small communication delays and task duplication. Opns. Res. (1991) 39(4):680–684Link, Google Scholar
• Cormen T., Leiserson C., Rivest R.Introduction to Algorithms (1990) (MIT Press)Google Scholar
• Darbha S., Agrawal D. P. SDBS: A task duplication based optimal scheduling algorithm. Proc. Scalable High Performance Computing Conf. (1994) 756–763Crossref, Google Scholar
• Garey M., Johnson D.Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) (W. H. Freeman and Company)Google Scholar
• Graham R. Bounds on multiprocessor timing anomalies. SIAM J. Appl. Math. (1969) 17:416–429Crossref, Google Scholar
• Guinard F., Rapine C., Trystram D. Worst-case analysis of lawler's algorithm for scheduling trees with communication delays. (1995) . Technical report LMC-IMAG, Grenoble, FranceGoogle Scholar
• Hwang J., Chow Y., Anger F., Lee C. Scheduling precedence graphs in systems with interprocessor communication times. SIAM J. Comput. (1989) 18(2):244–257Crossref, Google Scholar
• Hanen C., Munier A. An approximation algorithm for scheduling dependent tasks on m processors with small communication delays. (1995) . Technical report, Laboratoire Informatique Theorique et Programmation, Institut Blaise Pascal, Universite Pierre et Marie CurieGoogle Scholar
• Isaak G. Scheduling rooted forests with communication delays. Order (1994) 11:309–316Crossref, Google Scholar
• Kruatrachue B.Static Task Scheduling and Grain Packing in Parallel Processing Systems (1987) . Ph.D. thesis, Oregon State UniversityGoogle Scholar
• Lawler E., Lenstra J., Rinnooy Kan A., Dempster M., et al. Recent development in deterministic sequencing and scheduling: A survey. Deterministic and Stochastic Scheduling (1982) (D. Reidel, Dordrecht) Crossref, Google Scholar
• Munier A., Hanen C. An approximation algorithm for scheduling unitary tasks on m processors with communication delays. (1994) . Technical report, Laboratoire Informatique Theorique et Programmation, Institut Blaise Pascal, Universite Pierre et Marie CurieGoogle Scholar
• Munier A., Hanen C. Using duplication for scheduling unitary tasks on m processors with communication delays. (1995) . Technical report, Laboratoire Informatique Theorique et Programmation, Institut Blaise Pascal, Universite Pierre et Marie CurieGoogle Scholar
• Papadimitriou C., Yannakakis M. Towards an architecture-independent analysis of parallel algorithms. SIAM J. Comput. (1990) 19(2):322–328Crossref, Google Scholar
• Ullman J. NP-complete scheduling problems. J. Comput. System Sci. (1975) 10:384–93Crossref, Google Scholar
• Varvarigou T. A., Roychowdhury V. P., Kailath T., Lawler E. Scheduling in and out forests in the presence of communication delays. IEEE Trans. Parallel and Distributed Systems (1993) Google Scholar