Hybrid Queueing Theory and Scheduling Models for Dynamic Environments with Sequence-Dependent Setup Times

Authors

  • Tony Tran University of Toronto
  • Daria Terekhov University of Toronto
  • Doug Down McMaster University
  • J. Beck University of Toronto

DOI:

https://doi.org/10.1609/icaps.v23i1.13552

Keywords:

Dynamic Scheduling, Queueing Theory

Abstract

Classically, scheduling research in artificial intelligence has concentrated on the combinatorial challenges arising in a large, static domain where the set of jobs, resource capacities, and other problem parameters are known with certainty and do not change. In contrast, queueing theory has focused primarily on the stochastic arrival and resource requirements of new jobs, de-emphasizing the combinatorics. We study a dynamic parallel scheduling problem with sequence-dependent setup times: arriving jobs must be assigned (online) to one of a set of resources. The jobs have different service times on different resources and there exist setup times that are required to elapse between jobs, depending on both the resource used and the job sequence. We investigate four models that hybridize a scheduling model with techniques from queueing theory to address the dynamic problem. We demonstrate that one of the hybrid models can significantly reduce observed mean flow time performance when compared to the pure scheduling and queueing theory methods. More specifically, at high system loads, our hybrid model achieves a 15% to 60% decrease in mean flow time compared to the pure methodologies. This paper illustrates the advantages of integrating techniques from queueing theory and scheduling to improve performance in dynamic problems with complex combinatorics.

Downloads

Published

2013-06-02

How to Cite

Tran, T., Terekhov, D., Down, D., & Beck, J. (2013). Hybrid Queueing Theory and Scheduling Models for Dynamic Environments with Sequence-Dependent Setup Times. Proceedings of the International Conference on Automated Planning and Scheduling, 23(1), 215-223. https://doi.org/10.1609/icaps.v23i1.13552