An analysis of shift class design problems

In this paper we consider a generalization of the Fixed Job Schedule Problem which appears in the aircraft maintenance process at an airport. A number of jobs must be carried out where each job requires processing from a fixed start time to a fixed finish time. These jobs must be carried out by a number of machines which are available in specific shifts only. The jobs must be carried out in a non-preemptive way, although at the end of a shift preemption of a job is allowed sometimes. The problem is to choose the number of machines in each of the shifts in such a way that all jobs can be carried out and that the total costs of the machines or the total number of machines are minimum. In this paper we present an analysis of the computational complexity of these problems. We also analyse the worst case behaviour of the preemptive variant versus the non-preemptive variant.