|Title||Parallel machine scheduling with related jobs.|
|Supervisor||Marjan van den Akker and Han Hoogeveen|
|Related Course(s)||Scheduling and Timetabling|
We consider the problem of scheduling a set of jobs on a set of parallel
identical machines. Our basic assumption is that we know the durations of
the jobs in advance.
However, things often take longer than expected. Even worse, jobs may influence each other in the sense that if one job is delayed this causes another job to be delayed.
For example, if a bus trip of line 12 driving towards the central station has a delay because of traffic jam and then the next trip of this bus driving back to the Uithof is also delayed.
We say that delays propagate.
We model this delay propagation by a graph. The jobs are the nodes and
there is an arc between two jobs, if a delay of the first job causes a
delay of the second job.
The purpose of this project is to develop an algorithm for this parallel
machine scheduling problem where we want to minimize the makespan