Time complexity of single- and identical parallel-machine scheduling with GERT network precedence constraints

Abstract.

In this paper we deal with the time complexity of single- and identical parallel-machine scheduling problems in which the durations and precedence constraints of the activities are stochastic. The stochastic precedence constraints are given by GERT networks. First, we sketch the basic concepts of GERT networks and machine scheduling with GERT network precedence constraints. Second, we discuss the time complexity of some open single-machine scheduling problems with GERT network precedence constraints. Third, we investigate the time complexity of identical parallel-machine scheduling problems with GERT network precedence constraints. Finally, we present an efficient reduction algorithm for the problem of computing the expected makespan for the latter type of scheduling problem.