Cycle time of Single server queue with batching

Section 9.4 of Factory Physics presents an analysis of the (average) cycle time of single server queue with setups. This analysis is, for me at least, part confusing, partly wrong. In this note I make a slightly different model with the aim to repair some of the problems of the sequential batch model of FP and to unite my model with the transfer batch model of FP.

The Model

Jobs arrive at an assembly point in which they are batched in lot sizes of \(k\) jobs. These batches are sent to queue. A server removes batches from the head of the queue, performs a setup and serves the individual jobs. Once a job is finished, it leaves the system. Thus, the total cycle time can be split up into four terms:

  • Wait to batch time, i.e., time to complete the batch
  • Time in the queue
  • A wait in batch time, i.e., time a job waits to be served by the server
  • Service/processing time

In the sequel I will derive a formula for the average total cycle time. The formula uses the following data of single jobs:

\[\begin{split}k &= \text{number of jobs in the batch} \\ r_a &= \text{Arrival rate of single jobs}\\ t_a &= \text{Average interarrival time between two jobs}\\ c_a^2 &= \text{SCV of the interarrival times of single job}\\ t_e &= \text{Average processing time of a single job}\\ c_e^2 &= \text{SCV of processing time of a single job}\\ s &= \text{Time to perform a setup before the batch service starts}\end{split}\]

We assume that the interarrival times between jobs are independent and have the same distribution. Likewise, we assume that the processing times are independent and identically distributed. Finally, we assume that the setup time is constant. Note that it is easy to extend the derivation below to cases with stochastic setup times.

Wait to Batch Time

As jobs arrive at an assembly point at which they are batched, jobs have to wait until the batch is complete. The first job has to wait for \(k-1\) other jobs before the batch is complete, the second for \(k-2\) jobs, and so on, until the last, \(k\)-th, job, which does not have to wait as it completes the batch. The total amount of waiting time is therefore

\[(k-1) t_a + (k-2)t_a + \cdots + t_a + 0 = \frac{k(k-1)}2 t_a,\]

so that the average waiting time for a job becomes

\[\frac 1 k \frac{k(k-1)}{2} t_a = \frac{k-1}{2} t_a.\]

Average Queueing Time

Once a batch is compete, it is sent to a queue. The batch stays in the queue until it reaches the head of the queue. When the server becomes idle, it removes a batch from the queue. Thus, batches are queueing, not the individual jobs. As a consequence, the batches in the queue observe a processing time \(t_{e,b}\) of batches, not of single jobs, since the server removes batches from the queue, not single jobs. Moreover, batches arrive at the queue at a rate \(r_{a,b}\). Finally, to use the G/G/1 waiting time formula we need to derive expressions for the SCV \(c_{a,b}^2\) of the interarrival times of batches; we cannot directly use the SCV \(c_a^2\) of the jobs. Likewise, we need an expression for the SCV \(c_{e,b}^2\) of the processing time of a batch.

Let us write \(S_i\) for the interarrival time between jobs \(i-1\) and \(i\) in a batch. Thus, \(S_1\) is the interarrival time between the first job of a batch and the last job of the previous batch, \(S_2\) is the interarrival time between jobs 1 and 2, and so on. Thus, the interarrival time \(T_{a,b}\) between two batches can be written as

\[T_{a,b} = S_1 + \cdots + S_k.\]

The average interarrival time of batches is therefore

\[t_{a,b} = \E T_{a,b} = \E (S_1+\cdots S_k) = \E S_1 + \cdots \E S_k = t_a + \cdots + t_a = k t_a,\]

since we assume that all interarrival times have the same distribution. Hence, the interarrival times of batches is \(r_{a,b} = 1/t_{a,b} = 1/kt_a= r_a/k\).

Next, we write \(T_i\) for the processing time of the \(i\)-th job in a batch. Therefore the average processing time of a batch is

\[t_{e,b}= \E T_{b} = \E (s + T_1 + \cdots T_k) = s + \E T_1 + \cdots \E T_k = s + k t_e,\]

since the processing times have the same distribution.

The utilization of the server must then be

\[u_b = r_{a,b} t_{e, b} = \frac{r_a}{k} ( s + k t_e) = \frac{r_a} k s + r_a t_e.\]

With regard to the SCV of the interarrival times of the batches, we use the definition of the squared coefficient of variation of a random variable and the independence of the interarrival times \(\{S_i\}\) to observe that

\[\begin{split}c_{a,b}^2 &= \frac{\text{Var}(S_{a,b})}{(\E S_{a,b})^2} \\ &= \frac{\text{Var}(S_1 + \cdots + S_k )}{(\E S_1 + \cdots + \E S_k )^2} \\ &= \frac{\text{Var}(S_1) + \cdots + \text{Var}(S_k) }{(\E S_1 + \cdots + \E S_k )^2} \\ &= \frac{k \text{Var}(S_1) }{(k \E S_1)^2} \\ &= \frac{k}{k^2}\frac{\text{Var}(S_1)}{(\E S_1)^2} \\ &= \frac{1}{k}\frac{\text{Var}(S_1)}{t_a^2} \\ &= \frac{c_a^2}k,\end{split}\]

as \(\text{Var}(S_1)/t_a^2= c_a^2\). Note that the SCV of the batch interarrival times is now expressed in terms of the batch size \(k\) and the SCV \(c_e^2\) of the interarrival times of individual jobs. Since we assumed that \(c_a^2\) is known, it is simple to compute \(c_{a,b}^2\).

In a similar way, we derive the SCV of the processing times of batches. Using that the setup time is assumed to be constant,

\[\begin{split}c_{e,b}^2 &= \frac{\text{Var}(T_{a,b})}{(\E T_{a,b})^2} \\ &= \frac{\text{Var}(s + T_1 + \cdots + T_k }{(s + \E T_1 + \cdots + \E T_k )^2} \\ &= \frac{\text{Var}(T_1) + \cdots + \text{Var}(T_k) }{(s + \E T_1 + \cdots + \E T_k )^2} \\ &= \frac{k \text{Var}(T_1) }{(s + k \E T_1)^2} \\ &= \frac{k \text{Var}(T_1) }{(s + k t_e)^2} \\ &= \frac{k t_e^2 }{(s+kt_e)^2} \frac{\text{Var}(T_1)}{t_e^2} \\ &= \frac{t_e^2 }{(t_e+s/k)^2}\frac{c_e^2}k, \\\end{split}\]

where we use that \(\text{Var}(T_1)/t_e^2 = c_e^2\), i.e., the SCV of the processing time of a single job. Again, we note that \(c_{e,b}^2\) is expressed in terms of notions that are available for single jobs.

Wait in Batch Time

After a batch leaves the queue, each job individually has to be processed. The first job has to wait for the set up, the second job has to wait for the setup and the time to process the first job, and so on. Therefore the total time spent waiting for getting to the server is

\[s + (s + t_e) + (s + 2t_e) + \cdots (s + (k-1)t_e) = ks + k\frac{k-1}2 t_e,\]

so that the average wait in batch time becomes

\[\frac{1}{k} \left(ks + k\frac{k-1}2 t_e\right) = s + \frac{k-1}{2} t_e.\]

Total Average Cycle Time

The total CT is the sum of all the above terms plus the service time itself:

\[CT = \frac{k-1}{2} t_a + CT_{q,b} + s + \frac{k-1}{2} t_e + t_e,\]

where

\[CT_{q,b} = \frac{c_{a,b}^2 + c_{e,b}^2}{2} \frac{u_b}{1-u_b} t_{e,b}\]

and \(c_{a,b}^2\), \(c_{e,b}^2\) and \(u_b\) have been derived above.