Task allocation on a multiprocessor architecture-Deterministic and stochastic models

This paper deals with the problem of task allocation, subjected to precedence constraints, on a multiprocessor architecture with shared memory. Two kinds of scheduling are considered: the deterministic scheduling (the duration of each task is known and constant) and the stochastic scheduling (the duration of each task is modelled by a probability law). For each of these two scheduling problems, the authors propose several scheduling methods and they build several models in order to estimate the efficiency of the obtained scheduling. The determination of deterministic scheduling is obtained by methods based on priority list algorithms or on the simulated annealing algorithm; models that the authors build use deterministic simulation. For the stochastic scheduling, they propose several methods which adjust the simulated annealing algorithm to stochastic optimization problems. Several models are built: a markovian model and a stochastic simulation model. Although this scheduling problem is NP-complete, these methods compute satisfactory solutions in reasonable computing times.