×

Analysis of heuristics for stochastic programming: Results for hierarchical scheduling problems. (English) Zbl 0532.90078

Summary: Certain multistage decision problems that arise frequently in operations management planning and control allow a natural formulation as multistage stochastic programs. In job shop scheduling, for example, the first stage could correspond to the acquisition of resources subject to probabilistic information about the jobs to be processed, and the second stage to the actual allocation of the resources to the jobs given deterministic information about their processing requirements. For two simple versions of this two-stage hierarchical scheduling problem, we describe heuristic solution methods and show that their performance is asymptotically optimal both in expectation and in probability.

MSC:

90C15 Stochastic programming
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI Link