Optimal strategies for a class of sequential control problems with precedence relations

DOI10.1214/009053606000001569MaRDI QIDQ2456018zbMATH OpenOpenAlexFDO

Authors Hock Peng Chan, Cheng-Der Fuh, Inchi Hu

Publication date 17 October 2007

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609431

zbMATH Keywords

Markov chainslikelihood ratiooptimal stoppingschedulingmulti-armed banditsWald's equationKullback-Leibler numbersingle-machine job sequencing

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Sequential statistical design (62L05) Sequential statistical methods (62L99) Optimal stochastic control (93E20) Stochastic scheduling theory in operations research (90B36)

Abstract: Consider the following multi-phase project management problem. Each project is divided into several phases. All projects enter the next phase at the same point chosen by the decision maker based on observations up to that point. Within each phase, one can pursue the projects in any order. When pursuing the project with one unit of resource, the project state changes according to a Markov chain. The probability distribution of the Markov chain is known up to an unknown parameter. When pursued, the project generates a random reward depending on the phase and the state of the project and the unknown parameter. The decision maker faces two problems: (a) how to allocate resources to projects within each phase, and (b) when to enter the next phase, so that the total expected reward is as large as possible. In this paper, we formulate the preceding problem as a stochastic scheduling problem and propose asymptotic optimal strategies, which minimize the shortfall from perfect information payoff. Concrete examples are given to illustrate our method.

Recommendations

• Optimal Orderings for Parallel Project Selection
• scientific article; zbMATH DE number 4062809
• scientific article; zbMATH DE number 3925673
• Optimal control policies for resource allocation in an activity network
• Approximate policy iteration for dynamic resource-constrained project scheduling

Cites work

• scientific article; zbMATH DE number 4078557 (Why is no real title available?)
• scientific article; zbMATH DE number 47588 (Why is no real title available?)
• scientific article; zbMATH DE number 194374 (Why is no real title available?)
• scientific article; zbMATH DE number 6193740 (Why is no real title available?)
• Adaptive treatment allocation and the multi-armed bandit problem
• Asymptotically Efficient Adaptive Choice of Control Laws inControlled Markov Chains
• Asymptotically efficient adaptive allocation rules
• Asymptotically efficient adaptive allocation schemes for controlled Markov chains: finite parameter space
• Asymptotically efficient adaptive allocation schemes for controlled i.i.d. processes: finite parameter space
• Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-Part I: I.I.D. rewards
• Asymptotically efficient strategies for a stochastic scheduling problem with order constraints.
• Bayesian Adaptive Stochastic Process Termination
• Contributions to the "Two-Armed Bandit" Problem
• Irreversible adaptive allocation rules
• Markov additive processes. I: Eigenvalue properties and limit theorems
• Markov chains and stochastic stability
• On the undiscounted tax problem with precedence constraints
• Optimal stopping and supermartingales over partially ordered sets
• Optimal strategies for a class of constrained sequential problems
• Some aspects of the sequential design of experiments
• Strategy evaluation for stochastic scheduling problems with order constraints

This page was built for publication: Optimal strategies for a class of sequential control problems with precedence relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2456018)