Diffusion approximation and decomposition of queueing networks with batch processing

Diffusion approximation and decomposition of queueing networks with batch processing

There is an increasing relevance of simulation methods in the area of planning and implementing of production facilities and supply chains. But the increased complexity of production systems and the highly integrated supply chains require more accurate and faster simulation models which are capable to consider all kinds of typical interferences that could impact the production system or supply chain, like machine outages or the variation of process or transportation times.

Motivation and technical background

Commercial planning or simulation systems often get criticized for not providing means to model stochastic influences appropriately or even ignoring them completely by using deterministic cycle times. As consequence parts often get released to early for manufacturing which yields to an unnecessarily high work in progress and corresponding long cycle times. The usage of event driven stochastic simulation could help but this approach has the drawback of long execution times. Thus analytical models based on stochastic queueing theory are considered as beneficial alternative by many manufacturers running complex production facilities alike semiconductor.

Production systems to be considered

In many fabrications parts get processed as groups in parallel as well as moved in groups to downstream operations. In particular, this is a typical characteristic of semiconductor fabrication, where wafers get processed at many workstations as co called batches and get moved between workstations in boxes called FOUPs. Lead time and work in progress are key performance indicators in this fast-paced business and therefore it is crucial to have models which are able to calculate these indicators quickly and accurately. Since there are no exact queueing formulas available for the case of general process time distributions to model a single work station one relies on approximation formulas which are usually based on limit theorems for stochastic processes, diffusion approximation or decomposition methods. The theme of this project is to enhance existing approximation formulas for G/G/s queueing systems and queueing networks of G/G/c queues in a manner that they can be applied for queueing networks with batch service at each server and lot or bulk arrivals at each server. Challenging but important for the relevance of the models is the modeling of multi class networks.

State of the Art

Decomposition methods for queueing networks are know for a while and have been introduced e.g. by Whart Whitt in the Queueing Network Analyzer in 1989. But the methods used there have limited applicability in the case parts get processed as batch.

The production planning system EPOS has been developed in cooperation with the working group "Stochastic models within engineering" at the Clausthal University of Tecnology and IBM. EPOS is capable to take into account the impact of stochastic interferences on cycle times, work in progress and cost of production systems. The underlying queueing model is based on decomposition methods and diffusion approximation approaches. The goal is to develop further enhancements of these methods in order to meet more requirements of semiconductor fabrications and to allow a more granular modeling of multi class networks representing multi product groups in such fabrications.

Involved Scientist