Heuristic procedures for parallel-machine scheduling problems with stochastic precedence constraints

This paper is concerned with stochastic scheduling problems with several identical parallel machines, where the task durations and precedence constraints are stochastic. The stochastic precedence constraints are given by special GERT networks. At first, basic concepts and results are surveyed for GERT networks and for single-machine and parallel-machine scheduling with GERT network precedence constraints. An example shows where GERT scheduling problems occur in practice. After that, two types of heuristics for identical parallel-machine GERT scheduling problems with objective functions E(C-max) maxE(C), and E(Sigma C) are proposed: generalizations of algorithms for corresponding deterministic scheduling problems and so-called priority-rule methods. An empirical analysis shows the best heuristics for each of the objective functions considered.