MIN SUM AND MIN MAX SINGLE-MACHINE SCHEDULING WITH STOCHASTIC TREE-LIKE PRECEDENCE CONSTRAINTS - COMPLEXITY AND ALGORITHMS

Stochastic min-sum and min-max single-machine scheduling problems are considered where the precedence constraints are given by a so-called OR network. An OR network is a special stochastic activity network (GERT network) which may contain cycles and has some tree-structure property. It turns out that min-max problems are harder than min-sum problems in contrast to deterministic scheduling. If the objective function is the expected weighted flow time, an optimal scheduling policy can be computed in polynomial time. The min-max problem with unit-time activities, maximum expected completion time of the so-called operations as objective function, and precedence constraints given by an acyclic OR network is shown to be NP-Hard. However, if we restrict ourselves to priority lists of operations instead of general scheduling policies, there is a polynomial algorithm for the scheduling problem where the activity durations are generally distributed and the objective function is the maximum expected lateness.