Scheduling jobs with Communication Delays

Participants: Rolf H. Möhring,
Markus Schäffter,
Andreas S. Schulz

Project description: In many scheduling problems, precedence constraints go along with the transport of material, intermediate products or data. Whenever two successive jobs are executed by different machines, there is some time necessary for transportation after the first job is completed and before the successive jobs may start execution. This time is called a communication delay. Such communication delays occurs in different situations, ranging from production planning where material has to be transferred between different machines, up to multiprocessor networks where the data produced by one job has to be transmitted to the successive jobs. The underlying characteristic of all these applications is that communication only occurs between successive jobs that are executed by different machines.

Hence, the occurrence of a communication delay depends on the particular machine assignment. For this reason, communication delays cannot be modelled properly by introducing additional jobs in advance. For communication delays that do not exceed the processing times of the jobs, this approach only leads to a 3-approximation algorithm.

Communication delays rather represent a new kind of constraints which have given a new impact on the classical scheduling problems on identical parallel machines and which therefore have to be treated specifically.

An example for series-parallel orders. Composing schedules which are optimal on sub-orders may not result in an overall optimal schedule for a series-parallel order.

We exploited the framework of Hanen, König and Munier which first finds a solution while neglecting the machine restrictions and then apply modified list scheduling to establish the machine restrictions. While finding an optimal schedule on sufficiently many machines is already {\rm NP}--hard for arbitrary partial orders, it can be solved efficiently and optimally for a number of special cases, such as forests, interval-orders and series-parallel orders. For arbitrary partial orders, we adopt the linear programming formulation of König and Munier in the extention of Hanen and Munier which yields an approximation guarantee of 4/3.

A series-parallel decomposition tree. Composing sub-schedules on sufficiently many machines following the series-parallel decomposition tree bottom-up.

The obtained solution is then used to serve as input for a modification of Graham's list scheduling algorithm which constructs feasible schedules for any given number of machines. The only necessary modification is to take the communication delays into account by redefining the availability of the jobs. For so-called small communication delays, i.e. delays that do not exceed the processing times of the jobs, this can be done in an efficient way. We studied the different resulting approximation algorithms. As an example, we obtain a 7/3-approximation algorithm for arbitrary partial orders and small communication delays.

The resulting schedules. The above schedule and the resulting schedule on two machines. Below a schedule on two machines with communication delays modelled by additional jobs.

The above framework also works for the average weighted completion time objective when the linear programming formulation of Hanen and Munier is extended by adding constraints of A. S. Schulz in order to estimate the load of the problem instance in terms of the completion times of single jobs. Applying this approach to an interval intersection technique, which has already been used by Chakrabarti, Phillips and Schulz, yields a 6.142-approximation algorithm for arbitrary processing times. If an optimal schedule on sufficiently many machines is known (e.g. for series-parallel orders, unit processing times and unit communication delays), this bound can be improved to 5.81. These are the first algorithms with a constant time approximation guarantee for this problem.


See also: