[Dept. of Computer Science]

Experimentation Project ACS


Title Parallel machine scheduling with related jobs.
Student Vacancy
Supervisor Marjan van den Akker and Han Hoogeveen
ECTS 15
Related Course(s) Scheduling and Timetabling
Description 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.
To avoid delay propagation, we try to schedule related jobs on the same machine.

The purpose of this project is to develop an algorithm for this parallel machine scheduling problem where we want to minimize the makespan
(completion time of the last job) and maximize the reward of scheduling related job on the same machine.