Randomizing Dispatch Scheduling Policies

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

View Publication

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.

Abstract

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.


@conference{Cicirello-2001-8338,
author = {Vincent Cicirello and Stephen Smith},
title = {Randomizing Dispatch Scheduling Policies},
booktitle = {The 2001 AAAI Fall Symposium: Using Uncertainty Within Computation},
year = {2001},
month = {November},
} 2017-09-13T10:45:31-04:00