Article ID: | iaor19961134 |
Country: | Netherlands |
Volume: | 64 |
Issue: | 1 |
Start Page Number: | 138 |
End Page Number: | 151 |
Publication Date: | Jan 1993 |
Journal: | European Journal of Operational Research |
Authors: | Kroon Leo G., Kolen Antoon W.J. |
Keywords: | computational analysis |
In this paper the authors consider a generalization of the Fixed Job Scheduling Problem which appears in a natural way in the aircraft maintenance process at an airport. A number of jobs has to be carried out, where the main attributes of a job are: a fixed start time, a fixed finish time and a value representing the priority of the job. For carrying out these jobs a number of machines is available. These machines are available in specific time intervals (shifts) only. A job can be carried out by a machine only if the interval between the start time and the finish time of the job is a subinterval of the shift of the machine. Furthermore, the jobs must be carried out in a non-preemptive way and each machine can be carrying out at most one job at the same time. Within this setting one can ask for a feasible schedule for all jobs or, if such a schedule does not exist, for a feasible schedule for a subset of jobs of maximum total value. In this paper a classification of the computational complexity of two classes of combinatorial problems related to these questions is presented.