ICML-98 Submission #86

Value Function Based Production Scheduling

   Jeff G. Schneider, Justin A. Boyan, and Andrew W. Moore

   All authors are at: The Robotics Institute
                       Carnegie Mellon University
                       5000 Forbes Ave, Pittsburgh, PA 15213
   

Abstract (250 word maximum):

    Production scheduling, the problem of sequentially configuring a
    factory to meet forecasted demands, is a critical problem
    throughout the manufacturing industry.  The requirement of
    maintaining product inventories in the face of unpredictable
    demand and stochastic factory output makes standard scheduling
    models, such as job-shop, inadequate.  Currently applied
    algorithms, such as simulated annealing and constraint
    propagation, must employ ad-hoc methods such as frequent
    replanning to cope with uncertainty.
    
    
    In this paper, we describe a Markov Decision Problem (MDP)
    formulation of production scheduling which captures stochasticity
    in both production and demands.  The solution to this MDP is a
    value function which can be used to generate optimal scheduling
    decisions online.  A simple example illustrates the theoretical
    superiority of this approach over replanning-based methods.  We
    then describe an industrial application and two reinforcement
    learning methods for generating an approximate value function on
    this domain.  Our results demonstrate that in both deterministic
    and noisy scenarios, value function approximation is an effective
    technique.


Keywords:
   Reinforcement learning, Production scheduling, Optimization,
   Applications.

Email address of contact author: schneide@cs.cmu.edu

Phone number of contact author: 412-268-2339