AN ANALYSIS OF SHIFT CLASS DESIGN-PROBLEMS

In this paper we consider a generalization of the Fixed Job Schedule P roblem (FJSP) 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 spe cific shifts only. The jobs must be carried out in a non-preemptive wa y, although at the end of a shift preemption of a job is allowed somet imes. The problem is to choose the number of machines in each of the s hifts in such a way that all jobs can be carried out and that the tota l costs of the machines or the total number of machines are minimum. I n this paper we present an analysis of the computational complexity of these problems. We also analyse the worst case behaviour of the preem ptive variant versus the non-preemptive variant.