SEMI-MARKOV DECISION-MODELS FOR REAL-TIME SCHEDULING

被引：29

作者：

YIH, Y

THESEN, A

机构：

[1] School of Industrial Engineering Purdue University, West Lafayette, IN

[2] Department of Industrial Engineering, University of Wisconsin-Madison, Madison, WI

来源：

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH | 1991年 / 29卷 / 11期

关键词：

D O I：

10.1080/00207549108948086

中图分类号：

T [工业技术];

学科分类号：

08 ;

摘要：

We first present a class of real-time scheduling problems and show that these can be formulated as semi-Markov decision problems. Then we discuss two practical difficulties in solving such problems. The first is that the resulting model requires a large amount of data that is difficult to obtain; the second is that the resulting model usually has a state space that is too large for analytic consideration. Finally, we present a non-intrusive 'knowledge acquisition' method that identifies the states and transition probabilities that an expert uses in solving these problems. This information is then used in the semi-Markov optimization problem. A circuit board production line is used to demonstrate the feasibility of this method. The size of the state space is reduced from 2035 states to 308 by an empirical procedure. An 'optimal' solution is derived based on the model with the reduced state space and estimated transition probabilities. The resulting schedule is significantly better than the one used by the observed expert.

引用

页码：2331 / 2346

页数：16

共 12 条

[1]

Fabian T., Fisher J.L., Sasieni M.W., Yardeni A., Purchasing raw material on a fluctuating market, Operations Research, 7, 1, pp. 107-122, (1959)

[2]

Fi-Dkrgruen A., Groenevklt H., Tijms H.C., Coordinated replenishments in a multi-item inventory system with compound poisson demands, Management Sciences, 30, 3, pp. 344-357, (1984)

[3]

Hodgson T.J., King R.E., Monteith S.K., Schultz S.R., Developing control rules for AGVs using Markov decision processes, Material Flow, 4, pp. 85-96, (1987)

[4]

Howard R.A., Dynamic Programming and Markov Processes, (1961)

[5]

Howard R.A., Dynamic Probabilistic Systems, 1, (1971)

[6]

Howarii R.A., B, Dynamic Probabilistic Systems. Volume II: Semi-Markovian and Decision Processes, (1971)

[7]

Siiidmann A., Schweitzer P.J., Part selection polidy for a flexible manufacturing cell feeding several production lines, HE Transactions, 16, 4, pp. 355-362, (1984)

[8]

Tijms H.C., Eikeboom A.M., A simple technique in Markovian control with applications to resource allocation in communication networks, Operations Research Letters, 5, 1, pp. 25-32, (1986)

[9]

White D.J., Real applications of Markov decision processes, Interfaces, 15, 6, pp. 73-83, (1985)

[10]

Wungaard J., Decomposition for dynamic programming in production and inventory control, Engineering and Process Economics, 4, pp. 385-388, (1979)

← 1 2 →