On the computational complexity of (maximum) class scheduling
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.
|Keywords||Scheduling, combinatorial analysis, computational complexity, fixed job intervals|
|Persistent URL||dx.doi.org/10.1016/0377-2217(91)90320-U, hdl.handle.net/1765/6681|
Kroon, L.G., & Kolen, A.W.J.. (1991). On the computational complexity of (maximum) class scheduling. European Journal of Operational Research, 23–38. doi:10.1016/0377-2217(91)90320-U