Scheduling deteriorating jobs subject to job or machine availability constraints |
| |
Authors: | Stanis?aw Gawiejnowicz |
| |
Institution: | Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Umultowska 87, 61-614 Poznań, Poland |
| |
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). |
| |
Keywords: | Complexity theory Scheduling Deteriorating jobs |
本文献已被 ScienceDirect 等数据库收录! |
|