In some cases, machines must be set up before they can start producing jobs. Consider, for example, a machine that paints jobs in red and blue.¹¹ In realistic problems there can be tens of families. Often, the setup time depends on the sequence in which the families are produced, for example, a switch in color from white to black might take less cleaning time than from black to white. The problem then includes determining a production sequence that minimizes the sum of the setup times to produce the families, and finding suitable batch sizes that minimize the average waiting times. When the machine requires a color change, it may be necessary to clean up the machine, which takes time. Another example is an oven that needs a temperature change when different job types require different production temperatures. Service operations form another setting with setup times: When servers (personnel) have to move from one part of a building to another, the time spent moving cannot be spent serving customers.

In all such cases, the setups, or change-over times, consume a significant amount of time; in fact, setup times of an hour or more are not uncommon. To avoid overloading the server, it is necessary to produce in batches such that a server first processes a batch of jobs of one type²² Producing one type of job is often called a `run'. , then performs a setup to serve a batch of another type, and so on.

Here we use Sakasegawa's formula to model the effect of setup times on the average sojourn time of jobs. In the main text, we provide a list of elements required to compute \(\E \J\); in Ex 6.2.6 we illustrate in detail how to carry out the computations.

Assume a single machine produces runs of red and blue jobs arriving at a rate \(\lambda_r\) and \(\lambda_b\). The scv of the inter-arrival times of both job types is given by \(C_a^2\). When the server changes from one color to the other, it needs a setup time. Once the server is set up for the correct color, we assume for simplicity that for all jobs the net service times \(\sim S_{0}\).³³ It is a simple exercise to generalize the notation to allow service times to depend on color. Finally, the setup times \(R_{k} \sim R\) with mean \(\E R\) and variance \(\V R\), and are assumed to be independent of the service times of the job.

The sojourn time of a job in the entire system is built as follows. First, we assemble the jobs into batches of the same color. For simplicity, we take \(B\) constant and the same for both colors.⁴⁴ In general, \(B\) should depend on the arrival rate of the job type when the arrival rates vary considerably between the families. Once \(B\) jobs of one color have arrived, the batch is complete, and the batch enters a queue; thus we consider a queue with batches, not single jobs. After some time, the batch reaches the head of the queue, and its service starts as soon as the machine becomes free. To serve a batch, the machine first performs a setup and then processes each job individually until the batch is finished. Once a job's service is completed, it leaves the server.

It remains to build a quantitative model of this queueing system.

When a job of color \(i\) arrives, the expected time for its batch to be formed is given by⁵⁵ Ex 6.2.7.

When the batch is complete, the batch joins the queue, so we next compute the average time batches spend in queue.⁶⁶ Note that we shift interpretation: batches (not individual jobs) form the queue. For this we can use Sakasegawa's formula; we only have to find expressions for each of its components.

The total arrival rate of jobs is \(\lambda= \lambda_b+\lambda_r\). Thus, \(\lambda_B=\lambda/B\) is the arrival rate of batches.

The expected service time of a batch is

With the batch arrival rate and the expected batch service time, the load becomes \(\rho = \lambda_B \E{S_B}\)

It is essential that \(B\) is sufficiently large to ensure that \(\rho<1\). With Eq. (6.2.2) this leads to the condition that \(B\) must be larger than some minimal batch size,

Now that we have identified the arrival rate and the service times of the batches, it remains to find expressions for the scv of the batch inter-arrival times \(C_{a,B}^2\) and the batch service times \(C_{s,B}^2\). It is easy to derive that⁷⁷ Ex 6.2.8 Ex 6.2.9.

where

Observe that now we have all components for Sakasegawa's formula.

It can be useful to convert the effects of the setup time into an effective service time of individual jobs. Since there are \(B\) jobs per batch, by dividing by \(B\) we see

Note in particular that the variance of the effective service time is larger than the variance of the net service time.

It remains to find a rule to determine what happens to a job after it has been processed. If the job has to wait until all the jobs in the batch are served, the expected time it spends at the server is \(\E R + B \E{S_0}\). However, if the job can leave right after being served, the expected time at the server is⁸⁸ Ex 6.2.10.

the setup takes \(\E{R}\), on average \(\frac{B-1}{2}\) jobs are served before the job itself, and then the job requires \(\E{S_0}\) of service. Our model is complete!

We can obtain a number of important insights from the above model. Using the code from Ex 6.2.6 we plot the sojourn time \(\E{\J_r}\) of a red job for various values of \(B\) in the figure at the right.

First, as \(B\) increases, we see a sharp decrease of \(\E{\J_r}\). The reason for this is that the load \(\rho\) decreases as a function of \(B\). Since \(\E\W \sim (1-\rho)^{-1}\), it is essential to avoid critically loading the server.

When \(B\) becomes quite large, we see that the sojourn time increases linearly. This follows immediately from Eq. (6.2.1) and Eq. (6.2.5), because the time to (dis)assemble batches is linear in \(B\).

Finally, observe that the graph is not symmetric around the minimum. It is much worse to take \(B\) too small than too large. More generally, when designing systems, we can use such graphs to understand how sensitive the system is to variation and measurement errors.

Here is the code used to make Fig. 1.⁹⁹ It follows directly from the above math.

import matplotlib.pyplot as plt

from latex_figures import apply_figure_settings

apply_figure_settings(use=True)

labda_r = 0.5  # red jobs
labda_b = 2.5  # blue jobs
labda = labda_r + labda_b
Cae = 1.0  # assumption on inter arrival times
ES0 = 15.0 / 60  # hour
Cse = 1.0  # scv of service times
VS0 = Cse * ES0**2
ER = 2.0  # setup time
VR = 1.0  # Variance of setup times

x = list(range(25, 50))
y = []

for B in x:
    ESe = ES0 + ER / B
    rho = labda * ESe

    # The time to form a red batch
    EW_r = (B - 1) / (2 * labda_r)

    # Now the time a batch spends in queue
    CaB = Cae / B
    VSe = B * VS0 + VR
    ESb = B * ES0 + ER
    CeB = VSe / ESb**2
    EW = (CaB + CeB) / 2 * rho / (1 - rho) * ESb

    # The time to unpack the batch, i.e., the time at the server.
    ES = ER + (B - 1) / 2 * ES0 + ES0

    total = EW_r + EW + ES
    y.append(total)


def cm_to_inch(cm):
    return cm / 2.54


plt.figure(figsize=(cm_to_inch(5), cm_to_inch(6)))
plt.xlim(20, 50)
plt.plot(x, y, label=r"$\mathsf{E}[J_r]$", lw=0.7)
plt.xlabel("$B$")
plt.legend(loc="lower right")
plt.tight_layout()
plt.savefig("/figures/setups.pdf")
plt.savefig("/figures/setups.png", dpi=300)

Before dealing with technical derivations, let us first see how to apply the model.¹⁰¹⁰ Before dealing with technical derivations, let us first see how to apply the model.

labda = 3  # per hour
ES0 = 15.0 / 60  # hour
ER = 2.0
Bmin = labda * ER / (1 - labda * ES0)
print(f"{ES0=}, {Bmin=}")

ES0=0.25, Bmin=24.0

B = 30
ES = ES0 + ER / B
rho = labda * ES
print(f"{rho=}")

rho=0.95

labda_r = 0.5
EW_r = (B - 1) / (2 * labda_r)
print(f"{EW_r=}")  # in hours

EW_r=29.0

labda_b = labda - labda_r
EW_b = (B - 1) / (2 * labda_b)
print(f"{EW_b=}")  # in hours

EW_b=5.8

Cae = 1.0
CaB = Cae / B
Ce = 1.0  # scv of service times
VS0 = Ce * ES0 * ES0
VR = 1.0 * 1.0  # Var setups is sigma squared
VS = B * VS0 + VR
ESb = B * ES0 + ER
CeB = VS / (ESb * ESb)
EW = (CaB + CeB) / 2 * rho / (1 - rho) * ESb
print(f"{CaB=:.4f}, {CeB=:.4f}, {EW=:.4f}")

CaB=0.0333, CeB=0.0319, EW=5.8833

Eunpack = ER + (B - 1) / 2 * ES0 + ES0
print(f"{Eunpack=}")

Eunpack=5.875

total = EW_r + EW + Eunpack
print(f"{total=:.4f}")

total=40.7583