On the computational complexity of (maximum) class scheduling
View PDF Version
Redirect to publisher's version
(publisher's version.url.txt, 50 bytes)
In this paper we consider several generalizations of the Fixed Job Scheduling Problem (FSP) which appear in a natural way in the aircraft maintenance process at an airport: A number of jobs have to be carried out, where the main attributes of a job are: a fixed start time, a fixed finish time, a value representing the job's priority and a job class. For carrying out these jobs a number of machines are available. These machines can be split up into a number of disjoint machine classes. For each combination of a job class and a machine class it is known whether or not it is allowed to assign a job in the job class to a machine in the machine class. 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 the jobs of maximum total value. In this paper we present a complete classification of the computational complexity of two classes of combinatorial problems related this operational job scheduling problem.
- machine class 3
- job class
- machine class 1
- matrix l
- machine class 3.
- job class 2
- job class 1