contents
|
. . . . | communication delays |
|
|
Scheduling jobs with Communication Delays
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.
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.
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 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.
References:
- Rolf R. H. Möhring, Markus W. Schäffter,
Andreas S. Schulz:
Scheduling Jobs with Communication Delays -
Using Infeasible Solutions for Approximation.
Proceedings of the Fourth European Symposium on Algorithms,
Lecture Notes in Computer Science, Springer-Verlag, September 1996
- Scheduling Jobs with Communication Delays -
Complexity Results and Approximation Algorithms
Ph.D. thesis Markus W. Schäffter.
See also:
|
top