Robustness in parallel machine scheduling

Abstract

In parallel machine scheduling with precedence relations between jobs, the delay of a single task could hinder several other machines. The traditional method for avoiding this situation involves adding idle time between jobs that are dependent on each other, to avoid having to postpone the scheduled execution of successor jobs when the predecessor is delayed. In this thesis we look at a previously introduced alternative definition of robustness, which measures the chances of the propagation of these delays. By minimising this metric, we minimise the possibilities of machines having to wait for others because of a breakdown. Note that a machine that has to wait for itself to complete a task after a breakdown is inevitable.

To explore the effectiveness of this approach, we introduce the concept of fixations, defined such that the jobs involved in a fixated relation are to be scheduled on the same machine. This ensures that these fixated relation can not attribute to the propagation of delays, as their jobs are not on different machines. By maximising the number of fixated relations then, we are minimising the chances of delay propagations, and thereby maximising the robustness of our schedules.

To simplify the implementation of our approach, we start by relaxing the precedence relations to mere correlations, dropping the partial ordering of the jobs. These correlations still signify a connection between two jobs, which we would like to have executed by the same machine, although the order in which this is done is irrelevant. Later we also add proper precedence relations, and include additional correlations to improve the robustness measure.

For finding solutions using our objective of maximising the number of fixated relations, we introduce two local search algorithms: one based on a genetic algorithm and one using simulated annealing. As the additional constraints that demand pairs of jobs are scheduled on the same machine might make it impossible to actually construct a schedule, we have to check every solution that is generated. For quickly evaluating this feasibility of a solution, we define a linear programming formulation that is incrementally solved using column generation. Furthermore we present several extensions to the problem category, to deal with release dates, deadlines and weighted relations. Finally we present another search method that combines the columns generated for the evaluation linear program into new solutions.

After finalising the approach and discussing the experiments used to test its effectiveness, we conclude that the presented heuristic is a very good method for solving larger problems with many machines. It is therefore an excellent complement to the integer linear programming formulation that solves instances to optimality, which is more efficient in solving problems with only a few machines, but has difficulties finding solutions for those with more machines, because of the symmetry in its definition.