The complexity of preemptive scheduling given interprocessor communication delays |
| |
| Affiliation: | 1. Mer Mec S.p.A., Treviso, Italy;2. Dept. of Science and Technology, Parthenope University of Naples, Naples, Italy;1. College of Computer Science and Software Engineering, Shenzhen University, Shenzhen 518060, China;2. School of Computer Science, University of Birmingham, B15 2TT, UK;3. Department of Biomedical Engineering, Shenzhen University, Shenzhen 518060, China |
| |
| Abstract: | We discuss the problem of scheduling af set of independent tasks T, each ti ϵ T of lenght ℓi ϵ Z+, on m identical processors. We allow preemption but assume a communication delay of time k ϵ N. Whenever a task is preempted from one processor to another, there must be a delay of at least k time units. We show that if k = 1, an optimal schedule can be found in polynomial time but if k ⩾ 2, the corresponding decision problem is NP-complete. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
