On equilibrium probabilities for the delays in deterministic flow lines with random arrivals

Woo Sung Kim, James R. Morrison

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


While flow line models have been studied for decades, excepting some cases with three servers or less, their equilibrium probabilities remain elusive. As such, approximations based on aggregation or decomposition methods are generally employed. In this paper, by focusing on flow lines with deterministic service durations and a renewal arrival process, we develop exact methods for steady-state analysis. Our starting point is the investigation of recursions for customer delay based on exact decomposition methods. We demonstrate that the delay a customer faces in each server possesses a Markovian property. For discrete-time flow lines, we obtain a multidimensional discrete-time time-homogeneous Markov chain for the delays; there are an infinite number of balance equations for the equilibrium probabilities. Exploiting a similarity between our system and the GI/D/1 queue allows us to reduce these to a finite number of balance equations that can be solved numerically. We also investigate the implications for continuous-time flow lines and consider an example inspired by production time windows in semiconductor manufacturing. To our knowledge, these are the first results that allow one to exactly obtain the equilibrium probabilities in flow lines consisting of more than three servers. Note to Practitioners - Flow line models can be used to model manufacturing systems such as automobile production and assembly lines. In semiconductor manufacturing, they have shown promise as equipment models for clustered photolithography tools (CPTs), in which the semiconductor wafers typically receive service from the tool's process modules in sequential order. In CPTs, an internal wafer buffer is often used to maximize throughput in the presence of random variations in production events or setups. The larger buffer allows the CPT to produce wafers at a greater throughput rate. However, the quality of the wafers may degrade; process restrictions often require wafers to advance promptly from one process to the next. The results developed in this paper can enable the exact calculation of the distribution of time a wafer resides in each module. These probabilities not only enable us to understand such manufacturing systems but can be exploited to assess the tradeoff between an internal wafer buffer and delays in a CPT.

Original languageEnglish
Article number6874595
Pages (from-to)62-74
Number of pages13
JournalIEEE Transactions on Automation Science and Engineering
Issue number1
StatePublished - Jan 1 2015


  • Clustered photolithography tools
  • equilibrium probabilities
  • flow lines
  • semiconductor wafer manufacturing
  • tandem queues


Dive into the research topics of 'On equilibrium probabilities for the delays in deterministic flow lines with random arrivals'. Together they form a unique fingerprint.

Cite this