Analysis of a stochastic lot scheduling problem with strict due-dates

Nicolaas van Foreest, Jacob Wijngaard

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review


This chapter considers admission control and scheduling rules for a
single machine production environment. Orders arrive at a single
machine and can be grouped into serveral product families. Each
order has a family dependent due-date, production duration, and
reward. When an order cannot be served before its due-date it has
to be rejected. Moreover, when the machine changes the production of
one type of family to another family, a setup time is incurred. The
problem is to find long-run average optimal policies that accept or
reject orders and schedule the accepted orders.

To obtain insight into the optimal performance of the system we
model it as a Markov decision process (MDP). This formal description
leads to, at least, three tangible goals. First, for small scale
problems the optimal admission and scheduling policy can be obtained
with, e.g., policy iteration. Second, simple heuristic policies can
be formulated in terms of the concepts developed for the MDP, i.e.,
the states, actions and (action-dependent) transition
matrices. Finally, the simulator required to study the performance
of heuristic policies for large scale problems can be directly
implemented as an MDP. Thus, the formal description of the system in
terms of an MDP has considerable off-spin beyond the mere numerical
aspects of solving the MDP for small-scale systems.
Original languageEnglish
Title of host publicationMarkov Decision Processes in Practice
EditorsRichard Boucherie, Nico M. van Dijk
Number of pages16
ISBN (Print)978-3-319-47766-4
Publication statusPublished - 2017

Publication series

NameInternational Series in Operations Research and Management Science

Cite this