Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems

Dempster, M.A.H., Fisher, M.L., Jansen, L., Lageweg, B.J., Lenstra, J.K., & Rinnooy Kan, A.H.G. (1983). Analysis of Heuristics for Stochastic Programming: Results for Hierarchical Scheduling Problems. IIASA Research Report (Reprint). IIASA, Laxenburg, Austria: RR-84-005. Reprinted from Mathematics of Operations Research, 8(4):525-537 [1983].

[thumbnail of RR-84-05.pdf]
Preview
Text
RR-84-05.pdf - Published Version
Available under License Creative Commons Attribution.

Download (4MB) | Preview

Abstract

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.

Item Type: Monograph (IIASA Research Report (Reprint))
Research Programs: System and Decision Sciences - Core (SDS)
Bibliographic Reference: Reprinted from Mathematics of Operations Research; 8(4):525-537 [1983]
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 01:52
Last Modified: 27 Aug 2021 17:35
URI: https://pure.iiasa.ac.at/2170

Actions (login required)

View Item View Item