Preemptive open shop scheduling with multiprocessors: polynomial cases and applications
| 详细信息 | 推荐本文 | |
- 作者：Dominique de Werra ; Tam谩s Kis and Wieslaw Kubiak
- 关键词：Preemptive open shop scheduling ; Multiprocessor operations ; Polynomial time algorithms
- 刊名：Journal of Scheduling
- 出版时间：February, 2008
- 出版年：2008
- 期刊代码：94_1094-6136
- 类别：cp
- 卷：11
- 期：1
- 页码：75-83
- 数据来源：sp
摘要
This paper addresses a multiprocessor generalization of the preemptive open-shop scheduling problem. The set of processors is partitioned into two groups and the operations of the jobs may require either single processors in either group or simultaneously all processors from the same group. We consider two variants depending on whether preemptions are allowed at any fractional time points or only at integer time points. We reduce the former problem to solving a linear program in strongly polynomial time, while a restricted version of the second problem is solved by rounding techniques. Applications to course scheduling and hypergraph edge coloring are also discussed.