Heuristic algorithms for job-shop scheduling problems with stochastic precedence constraints

This paper deals with job-shop scheduling with stochastic precedence constraints given by so-called OR networks. At first, a job-shop problem with stochastic OR network precedence constraints is described, where the expected makespan is to be minimized. Next, the concept of an aggregate schedule is discussed, which represents a deterministic static scheduling policy for our stochastic problem. The construction of an appropriate aggregate disjunctive graph permits us to adapt the shifting bottleneck heuristic. After that, a priority-rule method is proposed for finding an approximate aggregate schedule. An experimental performance analysis shows that both heuristics provide good approximate solutions. Finally, we briefly discuss a flow-shop problem with OR network precedence constraints and the case of cyclic OR networks.