Stochastic identical parallel machine scheduling with Operational Research OR precedence constraints

The authors deal with stochastic identical parallel machine scheduling where the precedence constraints are given by so-called Operational Research OR networks. Operational Research OR networks represent special GERT project networks that have been introduced to model projects with stochastic evolution structure and feedback. First some polynomial algorithms for deterministic parallel machine scheduling problems with precedence constraints are summarized. Second some results from stochastic single-machine scheduling with Operational Research OR precedence constraints are given. Since all nontrivial identical parallel machine scheduling problems with Operational Research OR precedence constraints are NP-hard, the authors discuss polynomial-time heurstics and simulation. They sketch some schedule construction procedures based upon known algorithms from deterministic and single-machine Operational Research OR scheduling. Moreover, the authors show how to use local search and simulated annealing as schedule improvement procedures.