Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

12.1 Introduction

The manufacturing process involves various operational steps in converting raw materials (used in a generic sense) into finished products. In order to make the process efficient and cost effective, analytical tools such as queueing theory have been used extensively with the advancement of technology. They play an important role in the performance analysis, design, and planning and control of manufacturing processes (see Govil and Fu (1999)). The objective of this chapter is not to review all important contributions that queueing theory has made to manufacturing. Here we provide a few glimpses of such contributions and give three illustrative examples.

There have been several surveys of applications of queueing theory in manufacturing systems. Buzacott and Yao (1986), Bitran and Dasu (1992), Kouvelis et al. (1992), Rao et al. (1998), and Kumar and Kumar (2001) are some of them. The variety of problems in manufacturing where queueing theory has been applied, identified in the comprehensive survey of Rao et al. (1998), are the following: transfer line and flow line production systems, job shop, advanced manufacturing systems that include flexible manufacturing systems (FMSs) and Just-in-Time (JIT) operations, capacity planning and control, production support functions, and other manufacturing situations such as automated guided-vehicle systems (AGVs) and computer controlled storage facilities. Of these flow line and transflow line systems, job shops, and FMS can be easily identified as obvious application areas for queueing theory. As noted by the authors even other applications are no less significant.

The Jackson networks, including open and closed queueing networks (OQN and CQN, see Chapter 7) were analyzed initially to solve problems related to job-shop scheduling. Those analyses were further expanded into the analyses of FMS. Thus, queueing networks have become fundamental to the modeling and analysis of manufacturing systems. Before going to specific cases, we provide a brief overview of some research available in the literature in general terms.

Production processes on multistage assembly lines in which workpieces from two or more input stations are merged to form a new one for further processing is the subject of study in Manitz (2008). The ultimate objective is the determination of the throughput and other performance measures of such assembly lines while considering finite buffer capacities and generally distributed processing times. One of the illustrative examples (see Section 3) used later gives some details of the procedure used in the article.

Significant amount of research work in queueing theory application can be found in the literature related to production planning and control. Many of those cases are beyond a single manufacturer and are involved with multiple organizations that form, what we call supply chain, which is covered later in this section. Boucherie et al. (2003) introduce a new class of queueing networks called arrival first networks. The new model is developed for the production systems operating under a Kanban protocol. Karrer et al. (2012) propose a framework for developing production control strategy. The framework is used to address some important questions in production control such as, how to limit work in process and position order penetration point, and to cope with demand uncertainty. It is formulated as a queueing network model and solved numerically using simulation. Gayon et al. (2009) study a production planning problem for a single item make-to-stock production system with backorders. The problem is to determine optimal stock and capacity allocation policies for the cases where production may be interrupted and restarted. An M/E \(_r\)/1 queueing model is used and a heuristic policy is developed and assessed based on the results of the model analysis.

FMS was very popular in 1980s and 1990s with the rising of technologies such as robots, CNC machines, material handling systems, sensors, and computers. This is also the time when the bulk of the research on queueing theory application in FMS can be found. Buzacott and Yao (1986) outline state-of-the-art studies in FMS using analytical queueing network models. Their focus is to identify the major features of the models that are related to the operational characteristics of FMS (see Section 2). Kouvelis et al. (1992) survey layout problems in an FMS environment, which deals with the allocation of workstations to equal number or more candidate locations in order to meet the throughput requirement of the system. One of their emphases is the queueing and dynamic aspects of the layout decisions. A key part of any FMS is the common conveyor subsystem that interconnects all the workstations. Coffman et al. (1988) find a new queueing problem in their study of FMS conveyor system, which has input–output dependencies resulting from the fact that the conveyor transports items both to and from a workstation. Dallery and Stecke (1990) consider single-class, multi-server closed queueing networks for the design and planning problems of flexible manufacturing. Their results are useful for characterizing optimal allocations of servers and workload using the optimal configuration of subnetworks that maximize the overall network or FMS throughput. Lin et al. (1994) also study the closed queueing network for FMS. However, their focus is to model a maintenance float network problem, which integrates with a cost optimization model to determine the best number of standby units and repair stations.

Semiconductor manufacturing systems is another leading industrial sector where queueing theory has been extensively applied. The readers may refer to surveys by Kumar and Kumar (2001) and Shanthikumar et al. (2007) for details.

The globalization of world economy has transformed the traditional manufacturing system into a distributed manufacturing and supply chain system. Most of the companies no longer manufacture their products completely in a single location and totally by themselves. Outsourcing and offshoring have been popular for a couple of decades already as companies have been looking for ways to reduce their cost and innovate their products in order to gain financial and technological edge in their competitive markets. In a distributed manufacturing environment supported by supply chains, lead time and uncertainty in and between operations typically are of concern more than in a stand-alone environment. This trend is evidenced by the high volume of research in the area of supply chain, including the application of queueing theory. The majority of articles that can be found in the literature related to the application of queueing theory in supply chain can be categorized as follows: supply chain design, supply chain planning and control, inventory control in supply chain, supply chain performance, product and process design for supply chain, logistics and transportation, and maintenance and spare parts management.

Kerbache and Smith (2004) develop a methodology based on analytical queueing network coupled with nonlinear optimization to design supply chain topologies and evaluate various performance measures. Their approach has proved useful for analyzing congestion problems and evaluating the performance of supply chains. Most of the applications of queueing theory are found in the area of supply chain planning and control, including inventory control. Bhaskar and Lallement (2010) look at a supply chain as a two-input, three-stage queueing network. Orders to the supply chain are modeled as two stochastic variables, one for the order arrival time and the other for the order quantity. The objective of the study is to obtain the minimum response time for the delivery of the orders along the three stages of the network. Thus, the optimum capacity of the queueing network can be obtained as the average number of order quantity that can be delivered within this minimum response time. Vericourt et al. (2002) study a capacitated supply chain that produces a single product demanded by several classes of customers with different backorder costs. The supply system is modeled as a multi-customer make-to-stock queue with stock allocation as a key decision problem. The problem is solved for optimal allocation policy using dynamic programming and heuristic algorithm. Bai et al. (2004) consider an inventory-queue, which is an inventory system controlled by a processing station with queueing. The most important issue for inventory-queues is the behavior of their departure processes that are triggered either by a new job arrival when the output buffer is not empty or when a service completion occurs. Their objective is to obtain the probability distribution and squared coefficient of variation of inter-departure times. Liu et al. (2004) develop a multistage inventory-queue model with an approach of a job-queue decomposition that evaluates the performance of serial manufacturing and supply systems with inventory control at each stage. The objective of their research is to find an efficient procedure to minimize the overall inventory in the system while meeting the required service level. Arda and Hennet (2006) analyze an enterprise network for an end-product manufacturer that makes production and supply plan to minimize its total holding and stock-out costs. The manufacturer has more than one supplier for each of its main components. Both the customer order arrival time and supplier delivery time are random. Arda and Hennet model the supply system as a queueing network with the inventory position level and the supply allocation as decision variables.

In addition to design, planning, and inventory control, the applications of queueing theory can also be found in performance evaluation and improvement, logistics and transportation, and other areas of supply chain. Viswanadham and Raghavan (2000) have investigated a dynamic modeling technique for analyzing supply chain network using generalized stochastic petri nets (GSPNs). They have used the framework of integrated GSPN-queueing network modeling, with the GSPN at the higher level and a generalized queueing network at the lower level, to solve the decoupling point location problem in supply chain. Their objective is to minimize the total relevant cost: inventory carrying cost and the delay costs. Wu and Dong (2008) develop a new methodology for performance analysis of multiproduct supply chain by combining multi-class queueing networks and inventory models. They employ a job-queue decomposition strategy to analyze the major performance measures and propose an approach for aggregating input streams and separating output streams to link all the sites or nodes in the supply chain together. Woensel et al. (2008) consider a vehicle routing problem with dynamic travel times due to traffic congestion. Their approach uses queueing theory to capture travel times. This approach is compared with other approaches and its benefits are evaluated and quantified. Lieckens and Vandaele (2012) consider a single product reverse logistics network design problem with multiple layers and multiple routings. They build a new advanced strategic planning model with integrated queueing relationships. The model takes into account stochastic delays due to various processes like collection, production, and transportation, as well as disturbances due to various sources of variability like uncertain supply, uncertain process times, unknown quality, breakdowns, etc. One of many other areas of application of queueing theory in supply chain is maintenance and spare parts management. Sleptchenko et al. (2005) examine the impact of repair priorities in spare part network. They model repair shops by multi-class, multi-server priority queues. Their objective is to reduce the inventory investment, which is necessary to attain target system availability, and to increase the utilization of repair shop.

Next, we select three articles from the literature as illustrative examples of applications of queueing theory in the analysis of manufacturing systems. In these examples we emphasize the modeling part of the article, rather than complete results with the assumption that interested readers can go to the articles to understand the complete analysis.

The readers should note that the notations used in the illustrative examples are mostly those of the authors of the articles and may not be the same as those used in earlier chapters.

12.2 Modeling a Flexible Manufacturing System Using Jackson Networks

(Buzacott and Yao 1986)

Queueing theory has long been applied in the modeling of FMS which is an integrated system that consists of several workstations. An FMS differs from the traditional manufacturing system in its flexibility. FMS has a set of versatile machines that can perform a variety of different types of operations with negligible setup times. Thus, the system can process a variety of jobs simultaneously. An integrated FMS is often controlled by computers, so jobs can have flexible routings, resulting in different paths of successive machine visits to complete their operations. In order to fully exploit the flexibility of an FMS to enhance its productivity, it is necessary to develop some models that can be used to predict its performance, and provide the guidelines for its design and control. Buzacott and Yao (1986) have discussed some of queueing network models that are applied to FMS.

An FMS is basically a flexible job shop in which machines or workstations are interconnected with automated conveyers controlled by computers. Jobs can enter and leave the system at any workstation, and their arrival and operation times at workstations are usually random. Based on these characteristics, it is natural to model the FMS as a Jackson queueing network. We assume that there are \(M\) workstations in the FMS modeled as an open queueing network.

Let \(J_i\) denote the total number of jobs at workstation \(i\), which includes both the jobs in the queue and the jobs in service. Let \(\mathbf {J} =(J_1,J_2,,J_M)\) and \(|\mathbf {J}| = \sum _{i=1}^M J_i\) , where \(\mathbf {J}\) is a job vector for the jobs in all workstations and \(|\mathbf {J}|\) is the total number of jobs in the system. Assume that jobs arrive at the system in a Poisson process and their service times follow exponential distributions. The job arrival rate is a function of total number of jobs in the system, \(\lambda (|\mathbf {J}|)\). The service rate at each workstation is a function of its queue length, \(\mu _i (J_i )\),\(i = 1,\ldots ,M\). A new job could arrive at any workstation with certain probability. Let \(\alpha _{0j}\) be such a probability for workstation \(j\). Once a job enters the system, it will route through a number of workstations to complete its operations. The routing of jobs follows a Markov chain. Let \([\alpha _{ij}]\),\((i,j = 1,\ldots ,M)\) be the routing matrix, where \(\alpha _{ij}\) is the routing or transition probability from workstation \(i\) to workstation \(j\). Let \(\alpha _{i0}\) be the probability that a job leaves the system through workstation \(i\). It is obvious that \(\alpha _{i0} + \sum ^M_{j=1}\alpha _{ij} = 1\).

The main differences between the open Jackson network discussed in Chapter 7 and the FMS model used here are the number of servers at each network node, in this case the workstation, the initial arrival rate at the system, and the service rates at different nodes or workstations. In the general open Jackson network discussion, we assumed multiple servers, constant new customer arrival rate, and constant service rate at each node. However, in the FMS model being discussed, we assume that there is only one server at each workstation; new job arrival rate is the same for all workstations, but not constant; and service rates are different for different workstations and not constant. The actual jobs arriving at a workstation include the new jobs from outside the system and routed jobs from other workstations. So the effective job arrival rate at a workstation is not the same as the new job arrival rate. Let \(\gamma _j\) denote the effective job arrival rate at workstation \(j\). The effective job arrival rates can be obtained by solving the following traffic equations.

$$ \gamma_j = \alpha_{0j} +\sum_{i=1}^M \gamma_i\alpha_{ij}, \quad j = 1,...,M . $$
(12.2.1)

Let \(\mathbf {n} = (n_1,\,\)… \(,n_M)\) and \(|\mathbf {n}| = \sum _{i=1}^M n_i\), where \(\mathbf {n}\) is a vector with nonnegative integers as elements. The equilibrium probability distribution of the number of jobs in the FMS, the most important property of the underlying Jackson network, can be expressed as follows:

$$ P[\textbf{J = n}] = G^{-1} \Pi^{|n|-1}_{j=0} \lambda(j) \Pi^M_{i=1}f_i(n_i) , $$
(12.2.2)

where

$$ f_i(n_i) = \gamma_i^{n_i}\Pi^{n_i}_{j=1} \mu^{-1}_i(j), \quad i=1,...,M, $$
(12.2.3)

and \(G\) is a normalizing constant (\(<\alpha \)),

$$ G = \sum^\infty_{k=0} \Pi^{k-1}_{j=0}\lambda(j) \sum_{|n|=k} \Pi^M_{i=1}f_i(n_i) . $$
(12.2.4)

Certain data are required to apply the above FMS model. First is the job routing matrix \([\alpha _{ij}]\),\((i,j = 1,\ldots ,M)\), where the probability \(\alpha _{ij}\) can be interpreted as the proportion of jobs leaving workstation \(i\) for next operation at workstation \(j\). The second is the mean service times at the workstations and mean inter-arrival times of new jobs to the system. Certain control mechanisms may be exercised to optimize the system performance through the dispatching of arriving jobs to artificially adjust the job arrival rate.

There are several special cases of the FMS model described above. The first is the fixed arrival rate for new jobs. The second is the closed queueing network. The third is the restricted open queueing network. We only discuss the first two cases here and refer the readers to Buzacott and Yao (1986) for the third case.

Constant Arrival Rate

Let \(\lambda (\cdot ) = \lambda \) be the constant arrival rate of new jobs from outside. The distribution function in (12.2.2) can be simplified as:

$$ P[\mathbf{J} = \mathbf{n}] = P[\mathbf{Q} = {\mathbf{n}}] = \Pi_{i=1}^M P[Q_i = n_i], $$
(12.2.5)

where \(\mathbf {Q} =(Q_1,\ldots ,Q_M )\) is a random vector for the equilibrium number of jobs at different workstations in the system.

Closed Queueing Network

For a certain positive integer number \(N\), let \(\lambda (j) = 0\) if \(j \geq N\) and \(\lambda (j)= \infty \) otherwise. So we have, \(\Pi _{j=0}^k \lambda (j) = 0\) for all \(k \geq N\). This special case implies that there are a fixed number of jobs, \(N\), in the FMS. As soon as one job completes its operations and leaves the system, a new job will be dispatched into the system. With the infinite arrival rates appearing in both numerator and denominator in (12.2.2), taking limits, we have

$$ P[\mathbf{J} = \mathbf{n}] = G^{-1}{(N)} \Pi_{i=1}^M f_i(n_i), $$
(12.2.6)

where

$$ G(N) = \sum_{|n|=N} \Pi_{i=1}^M f_i(n_i), $$
(12.2.7)

and \(f_i (n_i)\) remains the same as in (12.2.3).

With \(\alpha _{0j} = 0\),\(a_{i0} = 0\), and \(\sum _{j=1}^M \alpha _{ij} = 1\) for all \(i,j = 1,\ldots ,M\), the traffic equations in (12.2.1) will need another equation to have a unique solution. The equation \(\sum _{i=1}^M \gamma _i = 1\) will serve the purpose. In this case, \(\gamma _i\) can be interpreted as the job visit frequency to workstation \(i\). The probability distribution in equation (12.2.6) can also be expressed as,

$$ P[\mathbf{J} = \mathbf{n}] = \frac{\Pi^M_{i=1}P[Q_i = n_i]}{P[|\mathbf{Q}| = |\mathbf{n}|]} = P[\mathbf{Q} = \mathbf{n}||\mathbf{Q}| = |\mathbf{n}|]. $$
(12.2.8)

From the above equation or (12.2.6), the marginal job length distribution can be expressed as follows:

$$ P[J_i = n_i ] = \frac{f_i(n_i)G_i(N-n_i)}{G(N)}, \quad (n_i \leq N) $$
(12.2.9)

where \(G_i(N-n_i)\) can be considered as the normalizing constant for a closed queueing network with \(M-1\) workstations, excluding station \(i\) in the original \(M\) station network, with the reduced network having \(N-n_i\) jobs.

From (12.2.3), it can be derived that \(\mu _i(n_i)f_i(n_i) = \gamma _i f_i(n_i-1)\). By the definition of \(G_i(N - n_i)\) and (12.2.7), the following can also be derived:

$$ \sum_{n_i=1}^N f_i(n_i-1)G_i(N-n_i) = G(N-1). $$
(12.2.10)

Let \(TH_i\) be the throughput of workstation \(i\). The throughput can be expressed as follows:

$$ TH_i = \sum_{n_i=1}^N \mu_i(n_i)P[J_i = n_i] = \frac{\gamma_i G(N-1)}{G(N)}, \quad (i = 1,...,M). $$
(12.2.11)

Let \(TH\) be the FMS’s throughput. With the assumption that \(\sum _{i=1}^M \gamma _i = 1\),\(TH = \sum _{i=1}^M TH_i\) .

Buzacott and Yao (1986) outline the state of the art in the use of queueing theory in FMS at that time. What is given here is just an introduction and the article includes other topics such as reversible networks in FMS, approximate queueing networks, and performance models. Even though the article is nearly 30-years-old, for beginning readers in the area of queueing theory applications in FMS, it is highly recommended.

12.3 Assembly Lines with Finite Buffers

(Manitz 2008)

Queueing phenomenon can be observed on multistage assembly lines where work-in-process (WIP) parts are merged at certain assembly stations from multiple sourcing stations. Material flows are asynchronous, processing times are random, and there are buffers in-between stations. Manitz (2008) develops a queueing model for analyzing such assembly lines by decomposing them into a series of two-station subsystems. The two are then analyzed by using G/G/1/N stopped-arrival queueing models.

Assume that an assembly line has \(M\) stations. There is a finite buffer between any two successive stations. Let \(B_{im}\) denote the buffer between stations \(i\) and \(M\) for WIP parts of station \(i\) waiting for processing at station \(M\). Let \(C_{im}\) be the capacity of buffer \(B_{im}\).

When multiple parts from multiple predecessor stations are merged at an assembly station, the operation at the station can only be started after all the parts are available. This synchronization constraint extends the holding time of a part at the server. It is assumed that parts can be loaded onto the server of the assembly station independently. This implies that the waiting part will not consume the input buffer. An assembly station is considered as blocked if it cannot transfer a processed part into the following buffer because it is fully occupied. The blocked part is added to the queue in the buffer which effectively increases its capacity by one. An assembly station is defined as starving if it is completely empty.

We assume that the processing times can be represented by random variables. Let \(T_m^S\) be the processing time for a part at station \(M\), which is distributed with a general distribution with the following mean:

$$ E\{T_m^S\} = \frac{1}{\mu_m} \quad (m = 1,2,\ldots,M), $$
(12.3.1)

where \(\mu _M\) is the processing rate at station \(M\). Its coefficient of variation is defined as,

$$ CV\{T_m^S\} = \zeta_m \quad (m = 1,2,\ldots,M). $$
(12.3.2)

Let \(X\) be the effective production or output rate of the finished product, which is defined as the mean number of finished product out of the last assembly station, say \(M\), per unit time. The effective production rate, which is also called the throughput of the assembly line, can be expressed as the follows:

$$ X = \mu_m P \{{\text{station}}\;M\;{\text{is\;busy}}\}. $$
(12.3.3)

The main question of the problem is how to determine the probability that the last assembly station is busy. The busy period of the station excludes the repair, starving, waiting for synchronization, or other idle times. Manitz presents an algorithm to estimate the blocking and starving probabilities, and then the effective production rate of the assembly line.

The assembly line with \(M\) stations can be virtually decomposed into \(M-1\) subsystems, each of such subsystems consisting of two adjacent stations connected by a buffer. Let \((i,m)\) denote a subsystem with stations \(i\) and \(M\), connected by the buffer \(B_{im}\). The upstream station of the subsystem is denoted by \(M_u(i,m)\) and the downstream station by \(M_d (i,m)\). Consider a given station \(M\) which has a succeeding station \(s_m\). Let \(\mathbf {S}_m\) be the set of station \(M\)’s successor stations and \(\mathbf {P}_m\) be the set of station \(M\)’s predecessor stations. Set \(\mathbf {S}_m\) contains at most one station while set \(\mathbf {P}_m\) contains at least one station. Thus, the multi-predecessor subsystem can be decomposed into several two-station subsystems. Let \(p_{mj}\) denote the \(j\)th predecessor station of the assembly line station \(M\), where \(j = 1,\ldots ,|\mathbf {P}_m|\).

A decomposed two-station subsystem \((i,m)\) can be modeled as a G/G/1/N queueing system. When its buffer \(B_{im}\) is full, the processed part at its preceding station \(i\) has to wait at the station. Also it stops processing any other part at that station. This stoppage switches off the arrival process to the subsystem. The maximum possible number of parts in the subsystem is the buffer capacity plus the two additional parts, one blocked in the upstream station \(i\) and one in the downstream station \(M\), either being processed or waiting for synchronization.

The upstream station \(M_u (i,m)\) in the decomposed subsystem \((i,m)\) represents the segment of the assembly line upstream of the buffer \(B_{im}\). The virtual arrival rate of the arrival process into the buffer \(B_{im}\) is denoted as \(\mu _u(i,m)\), which is the effective arrival rate when the arrival process is switched on. This effective arrival rate is not the same as the processing rate \(\mu _i\) of station \(i\) as the former includes the factors of starving and synchronization at the station. The coefficient of variation for the inter-arrival time to the subsystem is denoted as \(\zeta _u (i,m)\). For an assembly station like station \(M\), it may appear as a downstream station in multiple subsystems in parallel. The downstream station \(M_d (i,m)\) represents the segment of the assembly line downstream of the buffer \(B_{im}\) including these parallel subsystems. Let \(\mu _d (i,m)\) denote the effective service rate of the subsystem, the rate at which the processed parts leave the subsystem \((i,m)\) when it is not starved. Similar to the effective arrival rate, \(\mu _d (i,m)\) differs from the processing rate \(\mu _M\) of station \(M\) as the former includes the effects of blocking and waiting for synchronization. The coefficient of variation for the time experienced by parts at the downstream station is denoted as \(\zeta _d(i,m)\).

Consider a subsystem \((m,s_m\)), in which station \(M\) is an upstream station that generates the arrival process to the subsystem. If the arrival process is not blocked, the effective time between two consecutive service completions can be expressed as \(T_{mj}^{IS} + T_{mj}^{IW} + T_m^S\), where \(T_{mj}^{IS}\) is the starving time of station \(M\) for parts from the \(j\)th preceding station \(p_{mj}\); \(T_{mj}^{IW}\) is the waiting time of a part from station \(p_{mj}\) at station \(M\) for synchronization; \(T_m^S\) is the processing time at station \(M\). We may identify these three components as phases, all of which may not be necessary for every part. The expected virtual inter-arrival time in the queueing system \((m,s_m)\) and its squared coefficient of variation can be written as

$$ \begin{aligned} \frac{1}{\mu_u(m,s_m)} &=& E[T_{mj}^{IS} + T_{mj}^{IW} + T_m^S] \\ && (m \in \left\{\{1,\dots,M\}|\boldsymbol{S}_m \neq \mathbf{0}\right\}; j = 1,\ldots,|\mathbf{P}_m|), \end{aligned} $$
(12.3.4)
$$ \begin{aligned} \zeta_u^2(m,s_m) &=& \mu_u^2(m,s_m )Var[T_{mj}^{IS} + T_{mj}^{IW} +T_m^S] \nonumber \\ &&(m \in \left\{\{1,\ldots,M\}|\boldsymbol{S}_m \neq \mathbf{0}\right\}; \quad j = 1,...,|P_m|). \end{aligned} $$
(12.3.5)

We assume that the phase lengths for each component of the completion time are independent and identically distributed (i.i.d) for all parts and all three time components are independent of each other for a particular part. We now need to determine the expected values and variances of the phase lengths. For the processing time \(T_m^S\), the expected value and variance can be computed from the given data:

$$ \begin{aligned} E[T_m^S] &=& \frac{1}{\mu_m} \quad (m \in \{1,...,M\}), \end{aligned} $$
(12.3.6)
$$ \begin{aligned} \\ Var[T_m^S] &=& \frac{\zeta^2_m}{\mu^2_m} \quad (m \in 1,...,M). \end{aligned} $$
(12.3.7)

The starving time \(T_{mj}^{IS}\) is the time that station \(M\) is starved for parts from station \(p_{mj}\) until the next service completion at the station. This time period is basically the remaining inter-arrival time in the subsystem \((p_{mj},m)\). As an approximation, assuming that the probability distribution of the remaining inter-arrival time is the same as the full inter-arrival time, a memoryless characteristic of exponential distribution, the expected value and variance of \(T_{mj}^{IS}\) can be derived as,

$$ \begin{aligned} E[T^{IS}_{mj}] &=& p^*_s(p_{mj},m)\frac{1}{\mu_u(p_{mj},m)} \\ && (m \in \left\{\{1,...,M\}|\mathbf{P}_m \neq \mathbf{0}\right\}; \quad j = 1,...,|P_m|), \end{aligned} $$
(12.3.8)
$$ \begin{aligned} Var[T_{mj}^{IS}] &=& p^*_S(p_{mj},m)(\frac{\zeta^2_u(p_{mj},m) + 1}{\mu^2_u(p_{mj},m)} - p^*_s(p_{mj},m)\frac{1}{\mu^2_u(p_{mj},m)}) \nonumber \end{aligned} $$
$$ \begin{aligned} &&(m \in \left\{\{1,...,M\}|\mathbf{P}_m \neq \mathbf{0}\right\}; \quad j=1,...,|\mathbf{P}_m|) , \end{aligned} $$
(12.3.9)

where \(p^*_s(p_{mj},m)\) is the probability that station \(M\) is starved for parts from \(p_{mj}\) at its service completion.

The waiting time of a part from station \(p_{mj}\) at station m for synchronization, \(T_{mj}^{IW}\), is the longest remaining starving time among the parallel subsystems, \((i,m),i \in \mathbf {P}_m/\{p_{mj}\}\). In addition to the assumption of the memorylessness of the starving time, Manitz also assumes that the moment of a maximum of some random variables can be approximated by the maximum of their moments. (See article for the derivation of \(E[T_{mj}^{IW}]\) and \(Var[T^{IW}_{mj}]\).)

The virtual service time of the subsystem \((p_{mj},m)\) is the time that a part from station \(p_{mj}\) experiences at station \(M\), which should include the waiting time \(T_{mj}^{IW}\) for synchronization, the original processing time \(T_m^S\), and the blocking time \(T_m^B\). Accordingly, the expected value of the virtual service time and its squared coefficient of variation can be defined as,

$$ \begin{aligned} \frac{1}{\mu_d(p_{mj},m)} &=& E[T_{mj}^{IW} + T_m^S + T_m^B] \\ (m \in \{\{1,...,M\}||\mathbf{P}_m| &\geq& 2, \mathbf{S}_m \neq \mathbf{0}\}; \quad j = 1,...,|\mathbf{P}_m|), \end{aligned} $$
(12.3.10)
$$ \begin{aligned} \zeta^2_d(p_{mj}, m) &=& \mu_d^2(p_{mj},m)Var[T^{IW}_{mj} + T^S_m + T^B_m] \\ (m \in \{\{1,...,M\}||P_m| \geq 2, \mathbf{S}_m &\neq& \mathbf{0}\}; \quad j = 1,...,|P_m|) . \end{aligned} $$
(12.3.11)

The only unknown component in the above equations is the blocking time \(T_m^B\) at station \(M\), which is the remaining time of a part at station \(s_m\), which, in turn, is the remaining virtual service time in the corresponding queueing system. The expected value and variance of the blocking time at station m can be shown as,

$$ \begin{aligned} E[T_m^B] &=& p_B^*(m,s_m)\frac{1}{\mu_d (m,s_m)} \\ &&(m \in \{\{1,...,M\}|\mathbf{S}_m \neq \mathbf{0} \}), \end{aligned} $$
(12.3.12)
$$ \begin{aligned} Var[T_m^B] &=& p_B^*(m,s_m)\left(\frac{\zeta_d^2(m,s_m) + 1}{\mu_d^2(m,s_m)}-p_B^*(m,s_m)\frac{1}{\mu_d^2 (m,s_m)}\right) \\ &&(m \in \{\{1,...,M\}|\mathbf{S}_m \neq \mathbf{0}\}), \end{aligned} $$
(12.3.13)

where \(p_B^*(m,s_m)\) is the probability that station \(M\) is blocked at the time of a service completion. The expected value and squared coefficient of variation of the virtual service time as defined in (12.3.10) and (12.3.11) can be derived from (12.3.12) and (12.3.13), as described in the article.

Some of the performance measures of the assembly line can now be calculated with the parameter values of the virtual queueing systems derived above. One of the key performance measures is the production rate of the assembly line, which is the effective output rate of the last station. This is equivalent to the virtual service rate of the last subsystem in the assembly line when it is not starved. Assume that the downstream station in the last subsystem is station \(M\) and the upstream station is \(p_{M1}\). The production rate \(X\) can be expressed as,

$$ X = \mu_d (p_{M1},M)(1-p_{S}(p_{M1},M)), $$
(12.3.14)

where \(p_S (p_{M1},M)\) is the probability that the subsystem \((p_{M1},M)\) is empty. This probability can be expressed as,

$$ p_{s}(p_{M1},M){=}P_0(\mu_u(p_{M1},M),\zeta_u(p_{M1},M),\mu_d(p_{M1},M),\zeta_d(p_{M1},M),C_{p_{M1},\!M} {+} 2), $$
(12.3.15)

where \(P_0(\lambda ,c_A,\mu ,c_S,N)\) is the long-term probability that a queueing system, with arrival rate \(\lambda \), service rate \(\mu \), coefficient of variations of inter-arrival times and service times \(c_A\) and \(c_S\) respectively, and capacity \(N\), is empty. For probability calculations, Manitz uses the results given by Buzacott and Shanthikumar (1993). He also provides expressions for other performance measures such as, effective output rates and blocking probabilities of other subsystems.

With the derived virtual parameters for the arrival and service processes of the \(M-1\) subsystems, the author develops an algorithm that iteratively calculates the upstream parameters in a forward pass from station 1 to \(M\), and downstream parameters in a backward pass. The algorithm also includes the procedures to calculate the blocking and starving probabilities for each subsystem. Finally, the production rate of the assembly line and other performance metrics can be calculated using the iteratively computed virtual parameters of the subsystems and the associated blocking and starving probabilities. Manitz has also conducted several numerical tests for his algorithm which can be found in his original article.

12.4 A Supply Chain with Multiple Suppliers

(Toktas-Palut and Ulengin 2011)

Supply chains consist of suppliers, manufacturers, warehouses, and distribution centers. In Toktas-Palut and Ulengin (2011) the authors consider a supply chain with two stages: multiple independent suppliers and a manufacturer with limited production capacities. The following assumptions are made:

  • The number of suppliers is \(n(\geq 2)\).

  • The suppliers operate on a make-to-stock basis and apply base stock policy to manage their inventories.

  • \(S_i\) is the base stock level of supplier \(i\).

  • No inventory is held by the manufacturer (make-to-order strategy).

  • The customer demands arrive in a Poisson process with rate \(\lambda \) in single units.

  • The service times of supplier \(i\) are i.i.d. with exponential distributions with mean \(1/\mu _i\).

  • The manufacturer’s service time is also exponentially distributed with mean \(1/\mu _M\).

  • The traffic intensity of supplier \(i\) \((i =1,2,...,n)\) and the manufacturer are \(\rho _i\) and \(\rho _M\), respectively. It is assumed \(\rho _i</1\) and \(\rho _M</1\).

When the manufacturer receives a demand, it triggers each supplier. If the supplier’s stock is not empty, the demand is met immediately. If the stock is empty, the component is released to the manufacturer only when its production is complete. It should be understood that when the supplier’s stock is empty, there are outstanding back orders. The manufacturer can start production only after receiving components from all suppliers. The customer demand is met when the manufacturer completes its production. All orders are processed on an first-come, first-served (FCFS) basis at all facilities. It is also assumed that the transfer times between facilities are negligible.

The modeling of this seemingly simple system has to be done in two stages. The first stage is when the production is at the supplier. The second stage is the production at the manufacturer, which can start only when all components have arrived from the suppliers. The key is the determination of the inter-arrival time distribution at the manufacturer stage. When that is known the system at that level can be modeled as a G/M/1 queue.

When there is only one supplier Buzacott et al. (1992) have derived the probability density function (p.d.f.)\(f_{(\cdot )}(t)\) of the inter-departure times of the supplier (that are the inter-arrival times of the manfacturer) as

$$ f_A(t) = \lambda e^{-\lambda t}(1 - \rho_1^{S_1+1}) + \mu_1e^{-\mu_1t}\rho_1^{S_1-1} - (\lambda + \mu_1)e^{-(\lambda+\mu_1)t}(1-\rho^2_1)\rho^{S_1-1}_1 , $$
(12.4.1)

where \(A\) stands for inter-arrival times. When the number of suppliers gets larger, the authors devise a strategy to derive an approximate distribution in place of (12.4.1).

Since the manufacturer cannot start production until all components have arrived, the supplier with the minimum base stock level is likely to affect the inter-arrival times for the manufacturer the most. With this assumption and using (12.4.1) an approximate p.d.f. in the multiple supplier case can be obtained as

$$ f_A(t) \simeq \lambda e^{-\lambda t}(1 - \rho_j^{S_j+1}) + \mu_j e^{-\mu_j t}\rho_j^{S_j-1} - (\lambda + \mu_j)e^{-(\lambda + \mu_j)t}(1-\rho^2_j)\rho_j^{S_j-1} , $$
(12.4.2)

where supplier \(j\) is the one with the minimum base stock level among all suppliers. This distribution gives an approximate squared coefficient of variation as

$$ C^2_A \simeq 1 - 2\rho_j^{S_j+1} \frac{1-\rho_j}{1 + \rho_j}. $$
(12.4.3)

After simulation studies involving two, three, and four suppliers, customer demand rate at one, traffic intensities of the suppliers and the manufacturer at 0.50, 0.67, and 0.80, and with the base stock levels of the suppliers as 3, 5, and 7, the authors conclude the approximate inter-arrival time distribution of the product for the manufacturer given in (12.4.2) as quite appropriate, giving an error of only 2.47 % (as compared to 71.6 % for an approximate exponential distribution).

We give here three performance measures of the system derived by the authors using the results derived above:\(E(B_i)\), expected outstanding back- orders for supplier \(i\); \(E(I_i)\), expected inventory level for supplier \(i\); and \(E(N_M)\), expected number of jobs in the manufacturer subsystem. Since at the supplier level, the subsystem acts like an M/M/1 queue, following Buzacott and Shanthikumar (1993), the first two measures can be given as

$$ E[B_i] = \frac{\rho_i^{S_i+1}}{1-\rho_i}, \quad i=1,...,n $$
(12.4.4)

and

$$ E[I_i] = S_i - \frac{\rho_i(1-\rho_i^{S_i})}{1-\rho_i}, \quad i = 1,...,n . $$
(12.4.5)

At the manufacturer’s subsystem, one can use a G/M/1 queueing model with (12.4.2) as the inter-arrival time distribution, and an exponential distribution with rate \(\mu _M\) for service times. Again without closed form expressions for \(E(N_M)\) when the inter-arrival times have a general distribution of the type (12.4.2), the authors resort to approximate results based on coefficients of variation of the two distributions available in the literature. After comparing different formulas with the help of simulation models used earlier, the authors use Marchal’s (1976) approximation formula for the average number of jobs in the manufacturer’s subsystem. This is given as

$$ E[N_M] \simeq \rho_M + (\frac{\rho^2_M(1+C^2_S)}{1+\rho^2_MC^2_S})(\frac{C^2_A+\rho^2_MC_S^2}{2(1-\rho_M)}) $$
(12.4.6)

where \(C^2_A\) and \(C_S^2\) are the squared coefficients of variation of the inter-arrival time distribution and the service time distribution, respectively. Substituting from (12.4.3) for \(C^2_A\) and noting \(C^2_S=1\), we get

$$ E[N_M] \simeq \rho_M + (\frac{2\rho^2_M}{1+\rho^2_M})(\frac{(1+\rho_j)(1+\rho^2_M)-2\rho_j^{S_j+1}(1-\rho _j)}{2(1+\rho_j)(1-\rho_M)}) $$
(12.4.7)

where supplier \(j\) is the one with the minimum base stock level.

With this analysis the authors derive results for two other quantities: Expected value of \(N_{qM}\), the number of jobs in the manufacturer’s queue and expected value of \(B_M\), the outstanding backorders at the manufacturer.

The authors also explore two decision problems related to costs in this system: (1) A centralized model in which optimization is based on the overall supply chain and (2) A decentralized model in which, the suppliers individually and the manufacturer separately optimize based only on their own entity. Interested readers may refer to the paper for details.