The complexity of a cyclic scheduling problem with identical machines and precedence constraints |
| |
| Institution: | 1. College of Business, Stony Brook University, Stony Brook, NY 11794, United States;2. Department of Management, Bennett S. LeBow College of Business, Drexel University, Philadelphia, PA 19104, United States;1. Department of Information Systems and Operations Management, Business School, The University of Auckland, Auckland, New Zealand;2. Faculty of Mathematics and Statistics, University of Isfahan, Isfahan, Iran;3. Department of Industrial Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran |
| |
| Abstract: | We consider a set T of tasks with unit processing times. Each of them must be executed infinitely often. A uniform constraint is defined between two tasks and induces a set of precedence constraints on their successive executions. We limit our study to a subset of uniform constraints corresponding to two hypotheses often verified in practice: Each execution of T must end by a special task f, and uniform constraints between executions from different iterations start from f. We have a fixed number of identical machines. The problem is to find a periodic schedule of T which maximizes the throughput. We prove that this problem is NP-hard and show that it is polynomial for two machines. We also present another nontrivial polynomial subcase which is a restriction of uniform precedence constraints. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
