Carnegie Mellon University
Randomizing Dispatch Scheduling Policies

Vincent Cicirello and Stephen Smith
The 2001 AAAI Fall Symposium: Using Uncertainty Within Computation, November, 2001.

  • Adobe portable document format (pdf) (96KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

The factory is a complex dynamic environment and scheduling operations for such an environment is a challenging problem. In practice, dispatch scheduling policies are commonly employed, as they offer an efficient and robust solution. However, dispatch scheduling policies are generally myopic, and as such they are susceptible to sub-optimal decision-making. In this paper, we attempt to improve upon results of such dispatch policies by introducing non-determinism into the decision-making process, and instead using a given policy as a baseline for biasing stochastic decisions. We consider the problem of weighted tardiness scheduling with sequence-dependent setups with unknown arrival times in a dynamic environment, and show that randomization of state-of-the-art dispatch heuristics for this problem in this manner can improve performance. Furthermore, we find that the ``easier'' the problem, the less benefit there is from randomization; the ``harder'' the problem, the more benefit. Our method of randomization is based on a model of the way colonies of wasps self-organize social hierarchies in nature.

Associated Center(s) / Consortia: Center for Integrated Manfacturing Decision Systems
Associated Lab(s) / Group(s): Reliable Autonomous Systems Lab and Intelligent Coordination and Logistics Laboratory
Associated Project(s): Distributed Coordination of Resources and Federation of Intelligent Robotic Explorers Project
Number of pages: 8

Text Reference
Vincent Cicirello and Stephen Smith, "Randomizing Dispatch Scheduling Policies," The 2001 AAAI Fall Symposium: Using Uncertainty Within Computation, November, 2001.

BibTeX Reference
   author = "Vincent Cicirello and Stephen Smith",
   title = "Randomizing Dispatch Scheduling Policies",
   booktitle = "The 2001 AAAI Fall Symposium: Using Uncertainty Within Computation",
   month = "November",
   year = "2001",