## On the computational complexity of (maximum) shift class scheduling.(English)Zbl 0776.90038

Summary: We consider a generalization of the Fixed Job Scheduling Problem (FSP) 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.

### MSC:

 90B35 Deterministic scheduling theory in operations research 90C60 Abstract computational complexity for mathematical programming problems

### Keywords:

fixed job scheduling problem; aircraft maintenance
Full Text:

### References:

 [1] Arkin, E. M.; Silverberg, E. L., Scheduling jobs with fixed start and end times, Discrete Applied Mathematics, 18, 1-8 (1987) · Zbl 0636.90042 [2] Carter, M. W.; Tovey, C. A., When is classroom assignment hard?, (Working paper 89-02. Working paper 89-02, Operations Research (1989), University of Toronto, Department of Industrial Engineering: University of Toronto, Department of Industrial Engineering Toronto), To appear in · Zbl 0745.90049 [3] Dantzig, G. L.; Fulkerson, D. R., Minimizing the number of tankers to meet a fixed schedule, Naval Research Logistics Quarterly, 1, 217-222 (1954) [4] Dondeti, V. R.; Emmons, H., Resource requirements for scheduling with different processor sizes, Parts I and II, (Technical memoranda 579 and 589 (1986), Case Western Reserve University, Department of Operations Research: Case Western Reserve University, Department of Operations Research Cleveland) · Zbl 0870.90068 [5] Dondeti, V. R.; Emmons, H., Interval scheduling with processors of two types, (Operations Research (1989), Case Western Reserve University, Department of Operations Research: Case Western Reserve University, Department of Operations Research Cleveland), to appear in · Zbl 0870.90068 [6] Fredman, M. L.; Weide, L., On the complexity of computing the measure of $$U[a_i, b_i]$$, Communications of the ACM, 21, 540-544 (1978) · Zbl 0378.68032 [7] Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs (1980), Academic Press: Academic Press New York · Zbl 0541.05054 [8] Garey, M. R.; Johnson, D. S., Computers and Intractability: A guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 [9] Gertsbakh, I.; Stern, H. I., Minimal resources for fixed and variable job schedules, Operations Research, 18, 68-85 (1978) · Zbl 0371.90058 [10] Gupta, U. L.; Lee, D. T.; Leung, J. Y.-T., An optimal solution to the channel assignment problem, IEEE Transactions on Computers, 28, 807-810 (1979) · Zbl 0422.68031 [11] Kindervater, G. A.P., Excercises in parallel computing, (Ph.D. Thesis (1989), Centre of Mathematics and Computer Science: Centre of Mathematics and Computer Science Amsterdam) · Zbl 0756.68047 [12] Kolen, A. W.J.; Kroon, L. G., On the computational complexity of (maximum) class scheduling, European Journal of Operational Research, 54, 1, 23-38 (1991) · Zbl 0741.90035 [13] Kolen, A. W.J.; Lenstra, J. K.; Papadimitriou, C. H., Interval scheduling problems (1987), unpublished manuscript [14] Kroon, L. G., Job scheduling and capacity planning in aircraft maintenance, (Ph.D. Thesis (1990), Erasmus University: Erasmus University Rotterdam)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.