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

Kolen, Antoon W. J.; Kroon, Leo G.

Eur. J. Oper. Res. 64, No. 1, 138-151 (1993).

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

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)