Semi-Markov decision models for real-time scheduling

Semi-Markov decision models for real-time scheduling

0.00 Avg rating0 Votes
Article ID: iaor1992153
Country: United Kingdom
Volume: 29
Issue: 11
Start Page Number: 2331
End Page Number: 2346
Publication Date: Nov 1991
Journal: International Journal of Production Research
Authors: ,
Keywords: programming: markov decision
Abstract:

The authors present a class of real-time scheduling problems and show that these can be formulated as semi-Markov decision problems. Then they 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, the authors 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.

Reviews

Required fields are marked *. Your email address will not be published.