Universal distribution of batch completion times and time-cost tradeoff in a production line with arbitrary buffer size

Ruth Sagron and Rami Pugatch

European Journal of Operational Research, 2021, vol. 293, issue 3, 980-989

Abstract: We study the distribution of batch completion times in a serial line of processing stations with a finite buffer—a flow shop. Batch completion times in these lines are distributed according to the Tracy-Widom type 2 distribution from random matrix theory when there is no limitation on buffer size, and all processing durations are identically and exponentially distributed. We significantly extend this result to the case of finite and inhomogeneous buffers and general distributions of processing durations. Using numerically exact computation, we demonstrate the Tracy-Widom distribution matches the observed distribution of batch completion times even when the size of the buffer is finite or inhomogeneous or the distribution of processing durations differs from exponential. This universality is explained by observing that asymptotically batch completion times can be described by directed last passage percolation on the plane, a process whose asymptotic limit falls in the Tracy-Widom universality class. A generic tradeoff is found between the cost of the work-in-process and the average batch completion time, which arises because small buffers cost less but cause more blocking while large buffers are costly but cause less blocking. The maximal improvement in average batch completion time is bounded by ∼12 percent for a line with many exponential processing stations. In this case a small increase in the size of the buffers is sufficient for reaching the unlimited buffer regime. More generally, we found that the maximal improvement monotonically increases with the coefficient of variation of the processing duration distribution.

Keywords: Queueing; Tracy-Widom; Random matrix theory; Tandem queues; Batch completion time (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720310961
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:293:y:2021:i:3:p:980-989

DOI: 10.1016/j.ejor.2020.12.050

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().