The complexity of a cyclic scheduling problem with identical machines and precedence constraints

The complexity of a cyclic scheduling problem with identical machines and precedence constraints

0.00 Avg rating0 Votes
Article ID: iaor1999169
Country: Netherlands
Volume: 91
Issue: 3
Start Page Number: 471
End Page Number: 480
Publication Date: Jun 1996
Journal: European Journal of Operational Research
Authors:
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.

Reviews

Required fields are marked *. Your email address will not be published.