Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
477811 | European Journal of Operational Research | 2007 | 7 Pages |
Abstract
We consider two problems of scheduling a set of independent, non-preemptable and proportionally deteriorating jobs on a single machine. In the first problem, the machine is not continuously available for processing but the number of non-availability periods, the start time and end time of each period are known in advance. In the second problem, the machine is available all the time but for each job a ready time and a deadline are defined. In both problems the criterion of schedule optimality is the maximum completion time. We show that the decision version of the first (the second) problem is NP-complete in the ordinary or in the strong sense, depending on the number of non-availability periods (the number of ready times and deadlines).
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Stanisław Gawiejnowicz,