An analysis of shift class design problems

In this paper we consider a generalization of the Fixed Job Schedule Problem (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 time to a fixed finish time. These jobs must be carried out by a n...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 1994-12, Vol.79 (3), p.417-430
Main Authors: Kolen, Antoon W.J., Kroon, Leo G.
Format: Article
Language:English
Subjects:
Applied sciences
Computational complexity
Exact sciences and technology
Fixed Job Schedule Problem
non-preemptive scheduling
Operational research and scientific management
Operational research. Management science
Preemptive
Scheduling, sequencing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we consider a generalization of the Fixed Job Schedule Problem (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 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.
ISSN:0377-2217
1872-6860
DOI:10.1016/0377-2217(94)90056-6