On the asymptotic probabilistic analysis of scheduling problems in the presence of precedence constraints

AbstractIn this paper we address a hierarchical scheduling problem for n jobs to be processed on a suitable number of parallel machines: the jobs require random amounts of processing time, no job splitting is allowed, and random precedence constraints between the jobs are present.We present two stochastic 2-stage heuristics, called LB and GLB, for the solution of the problem and analyze their asymptotic behavior. We find conditions on the processing times and on the depth of the precedence graph, that is, the degree of inherent parallelism of the jobs, that guarantee the expected and almost sure asymptotic relative optimality of both heuristics.As regards optimality in expectation, our results for the LB heuristic nicely extend those of Dempster et al. ((1983), Math. Oper. Res. 8, 525–537), which hold when there are no precedence constraints; for the new GLB heuristic we obtain stronger results. Optimal convergence almost surely of the two heuristics is established under identical conditions