Exit time recursions, recording principles, and queue equivalence in generalized regular flow lines

Sang Yoon Bae, James Morrison

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Tandem queues with stochastic arrivals, deterministic service times, one server devoted to each stage, and finite intermediate buffers are often referred to as deterministic flow lines (DFLs). Such systems are common components of modern automated assembly lines and closely model the internal behaviors of robotic cluster tools. For DFLs, three classic and fundamental properties exist: (i) an exit time recursion, (ii) a complete server reordering principle, and (iii) a queue equivalence. Despite the elegance of these classic results and their usefulness, they have not been extended to more general systems. In this paper we consider two extensions of basic DFLs: hybrid DFLs (HDFLs) and multi-class DFLs (MDFLs). A hybrid DFL allows for more than one server devoted to each stage. A multi-class DFL allows for a finite number of customer classes that each possess their own deterministic service times as a function of class and stage. We prove that HDFLs possess an exit time recursion and this recursion implies a complete reordering principle. Further, we demonstrate that an HDFL exhibits a queue equivalence with a simple G/D/m queue if and only if certain structural conditions hold. For MDFLs under certain assumptions on the service times, an exit time recursion exists. However, only a partial reordering principle is implied by this recursion. We finally identify a queue equivalence with a particular G/G/1 queue. While these recursion, reordering, and queue equivalence results are complicated by the more complex nature of the HDFLs and MDFLs, they retain some of the intuitive nature of the classic DFL results.

Original languageEnglish
Title of host publication2019 IEEE 15th International Conference on Automation Science and Engineering, CASE 2019
PublisherIEEE Computer Society
Pages922-929
Number of pages8
ISBN (Electronic)9781728103556
DOIs
StatePublished - Aug 2019
Event15th IEEE International Conference on Automation Science and Engineering, CASE 2019 - Vancouver, Canada
Duration: Aug 22 2019Aug 26 2019

Publication series

NameIEEE International Conference on Automation Science and Engineering
Volume2019-August
ISSN (Print)2161-8070
ISSN (Electronic)2161-8089

Conference

Conference15th IEEE International Conference on Automation Science and Engineering, CASE 2019
Country/TerritoryCanada
CityVancouver
Period08/22/1908/26/19

Fingerprint

Dive into the research topics of 'Exit time recursions, recording principles, and queue equivalence in generalized regular flow lines'. Together they form a unique fingerprint.

Cite this