On the computational complexity of (maximum) shift class scheduling
January 1993
Article
| Related Files |
|---|
View PDF Version
(eur_kroon_17.pdf, 1.1MB) |
|
Redirect to publisher's version
(publisher's version.url.txt, 50 bytes) |
In this paper 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.
- shift
- machine
- problem
- class
- schedule
- instance
- complexity
- number
- scheduling
- polynomial time
- job class 1
- n 3dm
- interval
- polynomial
- kroon /
- end times
- lemma
- j jobs
- graph
- shifts x
