Parallel Machine Scheduling with Uncertain Communication Delays
Aziz Moukrim, Eric Sanlaville, Frédéric Guinand
Abstract. This paper is concerned with scheduling
when the data are not fully known before the execution. In that case computing
a complete schedule off-line with estimated data may lead to poor performances.
Some flexibility must be added to the scheduling process.
We propose to start from a partial schedule and to postpone
the complete scheduling until execution, thus introducing what we call
a stabilization scheme. This is applied to the m machine problem with communication
delays: in our model an estimation of the delay is known at compile time;
but disturbances due to network contention, link failures,... may occur
at execution time. Hence the processor assignment and a partial sequencing
on each processor are determined off-line.
Some theoretical results for tree-like precedence constraints
and an experimental study show the interest of this approach compared with
fully on-line scheduling.
Keywords: Parallel Computing, Scheduling with Communication Delays, Disturbances on Communication Delays, List Scheduling, Flexibility.