Using an Eraser or a Pencil for Two-Processor Scheduling
Tóm tắt
Given a set of tasks with precedence constraints, each of them requiring one unit of time to be completed by a processor, what are the hidden structures which prescribe the minimal completion time? To deal with this question, we introduce a notion of minimality for partial orders on a set of tasks. We characterize these minimal orders in the case of two processors. Another notion of maximality leads to a new proof (communicated by M. Pouzet) of a classic result in two-processor scheduling.
Tài liệu tham khảo
Coffman, E. G., Jr. and Graham, R. L. (1972) Optimal scheduling for two-processor systems, Acta Informat. 1, 200–213.
Fujii, M., Kasami, T. and Ninomiya, K. (1969) Optimal sequencing of two equivalent processors, SIAM J. Appl. Math. 17, 784–789. Erratum 1971 20, p. 141.