Flexibly Serving A Finite Number of Heterogeneous Jobs in A Tandem System

Introduction

A tandem system consists of a sequence of work stations. Servers work on jobs that go through the stations sequentially. The value of each job increases as it progresses from the start to the end of the tandem system. Tandem systems are common in the manufacturing industry (Hopp and Spearman 2008). For example, workers (servers) in a tandem system transform raw materials into finished goods in a production plant. Tandem systems can also be found in the service industry (Cachon and Terwiesch 2013). For instance, in a hospital, a tandem system diagnoses patients (jobs) through a sequence of medical tests. Since the labor cost constitutes a substantial portion of the operating cost in these environments, it is important to effectively make use of a tandem system's workforce to maximize its productivity.

We consider a tandem system with two stations shown in Figure . Each station can serve at most one job at a time. There are M < ∞ jobs available at an initial position in front of station 1 to be served by the tandem system. We consider only a finite number of jobs to be served by the system because this is quite common in practice. For example, the number of patients that visit a hospital for medical tests is finite every day. There is a buffer of size B between the two stations. Every job is first served by station 1. Upon completion at station 1, the job enters station 2 if the latter is available. Otherwise, the job either enters the buffer (if the buffer is not full) or stays at station 1 (if the buffer is full). There are at most B + 1 jobs waiting to enter station 2. The jobs maintain the same sequence as they go through the system.

OPEN IN VIEWER

Figure 1

A Tandem System with Two Stations, Two Servers, and a Finite Number of Jobs

There are two flexible servers that are cross‐trained to work at both stations. Each server can work at only one station at a time. After he finishes a job he can move to another station, which takes negligible time and cost. We assume that the duration for a server to finish a job at a station is exponentially distributed with a rate that depends on the server, the station, and the job. Thus, the jobs are heterogeneous because they may have different service‐time distributions even if they are served by the same server at the same station. Furthermore, we assume that the two servers can work together on the same job at the same station simultaneously with additive service rates (Andradóttir et al. 2001).

Define makespan as the duration to complete all the jobs of the system. Our objective is to identify an efficient policy to dynamically assign the servers to the stations such that the expected makespan is minimized.

We describe the contributions of this study in the following paragraphs.

To minimize the expected makespan, we formulate a stochastic dynamic program for B = 1 to find an optimal policy that dynamically assigns the servers to the stations. Unfortunately, the optimal policy is too complicated to characterize when the number of jobs M is large. This motivates us to develop simpler and more intuitive policies in this paper. We will use the optimal policy derived from the dynamic program as a benchmark when we evaluate these simpler policies.

We extend the analysis to a system with a general buffer size

B ∈ N

. We derive the expected makespan of a system under a general non‐idling policy as well as under the three specific non‐idling policies. We prove that all the optimality results for the system with a buffer size B = 1 still hold. We also extend the model to incorporate moving costs and service defects. We derive the expected total moving cost and the expected number of perfect jobs (without service defects) under a general non‐idling policy. We then compare the three specific non‐idling policies with respect to these two performance measures.

After reviewing the literature in section 2, we formulate the problem for B = 1 as a stochastic dynamic program in section 3. Section 4 derives the expected makespan of a system with B = 1 under a general non‐idling policy. Section 5 describes the three specific non‐idling policies and their expected makespan. Section 6 discusses the optimality conditions of these non‐idling policies, and compares the policies against the optimal one derived from the dynamic program. Section 7 extends the analysis to a system with a general buffer size

B ∈ N

Related Literature

This study is related to two streams of literature: dynamic server assignment and dynamic line balancing. We discuss each stream of literature as follows.

Problem Formulation for Buffer Size B = 1

We first study a system with buffer size B = 1. Assume the time duration for server i to serve job m at station j is exponentially distributed with rate

μ i , j ( m )

μ 1 , 1 ( m ) + μ 2 , 1 ( m )

We assume that at time t = 0, both servers work on job 1 at station 1. Whenever a job is finished at a station, a server assignment policy instructs each server where to work next: station 1 or station 2. Let D _m denote the departure time of job m from the system, and let E[D _m ] denote its expected value. The objective of the problem is to find a server assignment policy that minimizes the expected makespanE[D _M ], which represents the expected time duration to complete all the M jobs. A server assignment policy is optimal if it minimizes the expected makespan. It is straightforward to show that each server must be non‐idling at any time under an optimal server assignment policy. Therefore, we only focus on non‐idling policies that make both servers always busy until they complete the M jobs. At any instant under a non‐idling policy, there are four possible server assignments: (i) both servers at station 1, (ii) both servers at station 2, (iii) server 1 at station 1 and server 2 at station 2, and (iv) server 1 at station 2 and server 2 at station 1.

At time t, let U(t) denote the number of jobs that are not yet finished at station 1. We have U(t) ∈ {0,1,…,M}. Let V(t) denote the number of jobs that are finished at station 1 but not yet finished at station 2. We have V(t) ∈ {0,1,…,3}. Note that U(t) + V(t) ≤ M. Assume that at t = 0, all the M jobs are available at the initial position in front of station 1. Thus, given U(t) and V(t), we know exactly the locations of all the jobs. For example, (U(t),V(t)) = (6,2) implies that jobs M,M − 1,…,M − 4 are at the initial position, job M − 5 is at station 1, job M − 6 is at the buffer, job M − 7 is at station 2, and all the other jobs are completed and have left the system. Since service times are exponentially distributed and therefore memoryless, we define the state of the system as (U(t),V(t)).

For some special system states, it is straightforward to identify an optimal server assignment. (i) If V(t) = 0 (station 2 is starved), then it is optimal to assign both servers to station 1. (ii) If V(t) = 3 (station 1 is blocked) or U(t) = 0 (no more jobs to be served at station 1), then it is optimal to assign both servers to station 2. Thus, we only need to study the server assignment for other system states. For any state (u,v), let f _(u,v) be the minimum expected time duration to serve all the remaining jobs in the system. The problem can be formulated as a stochastic dynamic program shown in Table .

OPEN IN VIEWER

Table 1

Dynamic Programming Formulation for a System with a Buffer Size B = 1

f (0,0) = 0.

For u = 1,…,M,

f ( u , 0 ) = 1 μ 1 , 1 ( M − u + 1 ) + μ 2 , 1 ( M − u + 1 ) + f ( u − 1 , 1 ) .

For u = 1,…,M−3,

f ( u , 3 ) = 1 μ 1 , 2 ( M − u − 2 ) + μ 2 , 2 ( M − u − 2 ) + f ( u , 2 ) .

For v = 1,…,3,

f ( 0 , v ) = 1 μ 1 , 2 ( M − v + 1 ) + μ 2 , 2 ( M − v + 1 ) + f ( 0 , v − 1 ) .

For u = 1,…,M−v; v = 1,2,

f ( u , v ) = min { f ( u , v ) I , f ( u , v ) II , f ( u , v ) III , f ( u , v ) IV } ,

where

f ( u , v ) I = 1 μ 1 , 1 ( M − u + 1 ) + μ 2 , 1 ( M − u + 1 ) + f ( u − 1 , v + 1 ) ;

f ( u , v ) II = 1 μ 1 , 2 ( M − u − v + 1 ) + μ 2 , 2 ( M − u − v + 1 ) + f ( u , v − 1 ) ;

f ( u , v ) III = 1 μ 1 , 1 ( M − u + 1 ) + μ 2 , 2 ( M − u − v + 1 ) + μ 1 , 1 ( M − u + 1 ) μ 1 , 1 ( M − u + 1 ) + μ 2 , 2 ( M − u − v + 1 ) f ( u − 1 , v + 1 ) + μ 2 , 2 ( M − u − v + 1 ) μ 1 , 1 ( M − u + 1 ) + μ 2 , 2 ( M − u − v + 1 ) f ( u , v − 1 ) ;

f ( u , v ) IV = 1 μ 2 , 1 ( M − u + 1 ) + μ 1 , 2 ( M − u − v + 1 ) + μ 2 , 1 ( M − u + 1 ) μ 2 , 1 ( M − u + 1 ) + μ 1 , 2 ( M − u − v + 1 ) f ( u − 1 , v + 1 ) + μ 1 , 2 ( M − u − v + 1 ) μ 2 , 1 ( M − u + 1 ) + μ 1 , 2 ( M − u − v + 1 ) f ( u , v − 1 ) .

Note that

f ( u , v ) I

corresponds to assignment I with both servers at station 1;

f ( u , v ) II

corresponds to assignment II with both servers at station 2;

f ( u , v ) III

corresponds to assignment III with server 1 at station 1 and server 2 at station 2; and

f ( u , v ) IV

corresponds to assignment IV with server 2 at station 1 and server 1 at station 2. The derivation of

f ( u , v ) I

,

f ( u , v ) II

,

f ( u , v ) III

, and

f ( u , v ) IV

is given in the online supplement.

We can obtain the optimal policy by solving the dynamic program in Table 1. The expected makespan under the optimal policy is f _(M,0). However, it is difficult to analytically characterize the structure of the optimal policy because of its complexity in general. Thus, it is hard to implement the optimal policy in practice, which motivates us to study simpler and more intuitive policies. In the following sections, we first determine the expected makespan of a general non‐idling policy. We then focus on three specific non‐idling policies, and benchmark their performance against the optimal policy.

The Expected Makespan of a General Non‐Idling Policy for Buffer Size B = 1

In this section, we determine the expected makespan under a general non‐idling policy for buffer size B = 1. Suppose jobs k and l are at stations 1 and 2 respectively. There are two possible cases. In case (i), job k finishes service at station 1 before job l at station 2. Let π(k ≺ l) denote the probability of case (i), and let τ ₁(k ≺ l) denote the expected service time of job k at station 1 conditioned on this case. In case (ii), job l finishes service at station 2 before job k at station 1. Let π(k ≻ l) denote the probability of case (ii), and let τ ₂(k ≻ l) denote the expected service time of job l at station 2 conditioned on this case. Define an indicator function δ ^I(k,l) for assignment I described in section 3 such that δ ^I(k,l) = 1, if assignment I is chosen; and δ ^I(k,l) = 0, otherwise. We define indicator functions δ ^II(k,l), δ ^III(k,l), and δ ^IV(k,l) for assignments II, III, and IV, respectively, in a similar manner. Since we choose one of the four server assignments to serve jobs k and l at stations 1 and 2 respectively, one and only one of the four indicator functions equals 1. According to the above definitions and using Lemma 3 in the online supplement, it is straightforward to derive the following equations:

π ( k ≺ l ) = δ I ( k , l ) + μ 1 , 1 ( k ) μ 1 , 1 ( k ) + μ 2 , 2 ( l ) δ III ( k , l ) + μ 2 , 1 ( k ) μ 1 , 2 ( l ) + μ 2 , 1 ( k ) δ IV ( k , l ) , π ( k ≻ l ) = δ II ( k , l ) + μ 2 , 2 ( l ) μ 1 , 1 ( k ) + μ 2 , 2 ( l ) δ III ( k , l ) + μ 1 , 2 ( l ) μ 1 , 2 ( l ) + μ 2 , 1 ( k ) δ IV ( k , l ) , τ 1 ( k ≺ l ) = 1 μ 1 , 1 ( k ) + μ 2 , 1 ( k ) δ I ( k , l ) + 1 μ 1 , 1 ( k ) + μ 2 , 2 ( l ) δ III ( k , l ) + 1 μ 1 , 2 ( l ) + μ 2 , 1 ( k ) δ IV ( k , l ) , τ 2 ( k ≻ l ) = 1 μ 1 , 2 ( l ) + μ 2 , 2 ( l ) δ II ( k , l ) + 1 μ 1 , 1 ( k ) + μ 2 , 2 ( l ) δ III ( k , l ) + 1 μ 1 , 2 ( l ) + μ 2 , 1 ( k ) δ IV ( k , l ) .

We adopt a methodology similar to Wang et al. (2014). Let T _m denote the time point when job m finishes service at station 1. Let R _m denote the number of jobs at the buffer and station 2 at time T _m . Since the buffer size B = 1, R _m can be as large as 2. Let p _m,i  = Pr{R _m  = i} denote the probability that job m, upon its service completion at station 1, finds i jobs at the buffer and station 2, for i = 0,1,2. Since job 1, upon its service completion at station 1, always finds the buffer and station 2 empty, we have p _1,0 = 1 and p _1,i  = 0, for i = 1,2. The following lemma determines p _m,i , for m = 2,…,M.

Lemma

For m = 2, p _2,0 = π(2 ≻ 1), p _2,1 = π(2 ≺ 1), and p _2,2 = 0.

For m = 3,…,M,

p m , 0 = π ( m ≻ m − 1 ) p m − 1 , 0 + π ( m ≻ m − 2 ) π ( m ≻ m − 1 ) ( p m − 1 , 1 + p m − 1 , 2 ) ; p m , 1 = π ( m ≺ m − 1 ) p m − 1 , 0 + π ( m ≻ m − 2 ) π ( m ≺ m − 1 ) ( p m − 1 , 1 + p m − 1 , 2 ) ; p m , 2 = π ( m ≺ m − 2 ) ( p m − 1 , 1 + p m − 1 , 2 ) .

Using the equations in Lemma 1, we can determine all p _m,i recursively from m = 1. We calculate the expected makespan using the probabilities p _m,i for the rest of this section.

The expected makespan E[D _M ] under a general non‐idling policy can be represented as the sum of the following four components:

E [ D M ] = E [ W M ] + E [ X M ] + E [ Y M ] + E [ Z M ] ,

where the random variable of each component is defined in Table .

OPEN IN VIEWER

Table 2

Time Durations of Job m = 1,…,M

W m : Duration of job m staying at the initial position (before entering station 1)

X m : Duration of job m staying at station 1

Y m : Duration of job m staying at the buffer (before entering station 2)

Z m : Duration of job m staying at station 2

Duration at station 1

The following proposition determines the expected duration of job m staying at station 1.

Proposition

For m = 1,

E [ X 1 ] = 1 μ 1 , 1 ( 1 ) + μ 2 , 1 ( 1 ) .

For m = 2,

E [ X 2 ] = τ 1 ( 2 ≺ 1 ) p 2 , 1 + τ 2 ( 2 ≻ 1 ) + 1 μ 1 , 1 ( 2 ) + μ 2 , 1 ( 2 ) p 2 , 0 .

For m = 3,…,M,

E [ X m ] = τ 1 ( m ≺ m − 2 ) + 1 μ 1 , 2 ( m − 2 ) + μ 2 , 2 ( m − 2 ) p m , 2 + τ 1 ( m ≺ m − 1 ) p m , 1 + ( τ 2 ( m ≻ m − 1 ) + 1 μ 1 , 1 ( m ) + μ 2 , 1 ( m ) ) p m , 0 + τ 2 ( m ≻ m − 2 ) π ( m ≻ m − 2 ) ( p m − 1 , 2 + p m − 1 , 1 ) .

Duration at the initial position

For m = 1, E[W ₁] = 0. For m = 2,…,M, the expected duration of job m staying at the initial position equals the sum of the expected durations of job m−1 staying at the initial position and at station 1. That is, E[W _m ] = E[W _m−1] + E[X _m−1]. After obtaining E[X _m ], m = 1,…,M, from Proposition 1, we can determine E[W _m ] recursively, starting from m = 1.

Duration at station 2

The following proposition determines the expected duration of job m staying at station 2.

Proposition

For m = 1,…,M − 2,

E [ Z m ] = τ 1 ( m + 2 ≺ m ) + 1 μ 1 , 2 ( m ) + μ 2 , 2 ( m ) π ( m + 2 ≺ m ) + τ 2 ( m + 2 ≻ m ) π ( m + 2 ≻ m ) ( p m + 1 , 2 + p m + 1 , 1 ) + τ 1 ( m + 1 ≺ m ) p m + 1 , 1 + τ 2 ( m + 1 ≻ m ) p m + 1 , 0 .

For m = M − 1,

E [ Z M − 1 ] = 1 μ 1 , 2 ( M − 1 ) + μ 2 , 2 ( M − 1 ) ( p M , 2 + p M , 1 ) + τ 1 ( M ≺ M − 1 ) p M , 1 + τ 2 ( M ≻ M − 1 ) p M , 0 .

For m = M,

E [ Z M ] = 1 μ 1 , 2 ( M ) + μ 2 , 2 ( M ) .

Duration at the buffer

The following proposition determines the expected duration of job m staying at the buffer.

Proposition

For m = 1, E[Y ₁] = 0. For m = 2,

E [ Y 2 ] = τ 2 ( 3 ≻ 1 ) π ( 3 ≻ 1 ) + τ 1 ( 3 ≺ 1 ) + 1 μ 1 , 2 ( 1 ) + μ 2 , 2 ( 1 ) π ( 3 ≺ 1 ) p 2 , 1 .

For m = 3,…,M − 1,

E [ Y m ] = [ τ 2 ( m + 1 ≻ m − 1 ) π ( m + 1 ≻ m − 1 ) + τ 1 ( m + 1 ≺ m − 1 ) + 1 μ 1 , 2 ( m − 1 ) + μ 2 , 2 ( m − 1 ) π ( m + 1 ≺ m − 1 ) ] ( p m , 2 + p m , 1 ) .

For m = M,

E [ Y M ] = 1 μ 1 , 2 ( M − 1 ) + μ 2 , 2 ( M − 1 ) ( p M , 2 + p M , 1 ) .

After determining all the four time durations, the expected makespan under a general non‐idling policy can be obtained as E[D _M ] = E[W _M ] + E[X _M ] + E[Y _M ] + E[Z _M ].

Three Specific Non‐Idling Policies

We analyze three specific non‐idling policies: the summation‐myopic policy, the product‐myopic policy, and the teamwork policy. We derive the expected makespan under each policy using the results in section 4.

Summation‐myopic policy: If station 2 is starved, then both servers work at station 1. If station 1 is blocked or job M has finished its service at station 1, then both servers work at station 2. If both of the above conditions do not hold, then let k and l denote the indices of the jobs currently at stations 1 and 2, respectively, and one of the following conditions holds:

If

μ 1 , 1 ( k ) ≥ μ 1 , 2 ( l )

and

μ 2 , 1 ( k ) ≥ μ 2 , 2 ( l )

, then both servers work at station 1.

If

μ 1 , 1 ( k ) < μ 1 , 2 ( l )

and

μ 2 , 1 ( k ) < μ 2 , 2 ( l )

, then both servers work at station 2.

If

μ 1 , 1 ( k ) ≥ μ 1 , 2 ( l )

and

μ 2 , 1 ( k ) < μ 2 , 2 ( l )

, then servers 1 and 2 work at stations 1 and 2, respectively.

If

μ 1 , 1 ( k ) < μ 1 , 2 ( l )

and

μ 2 , 1 ( k ) ≥ μ 2 , 2 ( l )

, then servers 1 and 2 work at stations 2 and 1 respectively.

The summation‐myopic policy chooses the assignment that maximizes the sum of the service rates of the two servers for the system's current state. For case I, the maximum rate is

μ 1 , 1 ( k ) + μ 2 , 1 ( k )

, so the policy chooses assignment I. For case II, the maximum rate is

μ 1 , 2 ( l ) + μ 2 , 2 ( l )

, so the policy chooses assignment II. For case III, the maximum rate is

μ 1 , 1 ( k ) + μ 2 , 2 ( l )

, so the policy chooses assignment III. For case IV, the maximum rate is

μ 1 , 2 ( l ) + μ 2 , 1 ( k )

, so the policy chooses assignment IV. Note that under this policy, each server independently chooses to work on the job that he is good at. The indicator functions under this policy can be defined as follows:

δ I ( k , l ) = 1 , if μ 1 , 1 ( k ) ≥ μ 1 , 2 ( l ) and μ 2 , 1 ( k ) ≥ μ 2 , 2 ( l ) ; 0 , otherwise . δ II ( k , l ) = 1 , if μ 1 , 1 ( k ) < μ 1 , 2 ( l ) and μ 2 , 1 ( k ) < μ 2 , 2 ( l ) ; 0 , otherwise . δ III ( k , l ) = 1 , if μ 1 , 1 ( k ) ≥ μ 1 , 2 ( l ) and μ 2 , 1 ( k ) < μ 2 , 2 ( l ) ; 0 , otherwise . δ IV ( k , l ) = 1 , if μ 1 , 1 ( k ) < μ 1 , 2 ( l ) and μ 2 , 1 ( k ) ≥ μ 2 , 2 ( l ) ; 0 , otherwise .

Product‐myopic policy: If station 2 is starved, then both servers work at station 1. If station 1 is blocked or job M has finished its service at station 1, then both servers work at station 2. If both of the above conditions do not hold, then let k and l denote the indices of the jobs currently at stations 1 and 2, respectively, and one of the following conditions holds:

If

μ 1 , 1 ( k ) μ 2 , 2 ( l ) ≥ μ 2 , 1 ( k ) μ 1 , 2 ( l )

, then servers 1 and 2 work at stations 1 and 2 respectively.

If

μ 1 , 1 ( k ) μ 2 , 2 ( l ) < μ 2 , 1 ( k ) μ 1 , 2 ( l )

, then servers 1 and 2 work at stations 2 and 1 respectively.

The product‐myopic policy chooses the assignment that maximizes the product of the service rates at the two stations for the system's current state. If the maximum product is

μ 1 , 1 ( k ) μ 2 , 2 ( l )

, then the policy chooses assignment III. If the maximum product is

μ 1 , 2 ( l ) μ 2 , 1 ( k )

, then the policy chooses assignment IV. Note that the two servers work at different stations unless the system is starved or blocked. Under the product‐myopic policy, we have the following: δ ^I(k,l) = δ ^II(k,l) = 0.

δ III ( k , l ) = 1 , if μ 1 , 1 ( k ) μ 2 , 2 ( l ) ≥ μ 2 , 1 ( k ) μ 1 , 2 ( l ) ; 0 , otherwise . δ IV ( k , l ) = 1 , if μ 1 , 1 ( k ) μ 2 , 2 ( l ) < μ 2 , 1 ( k ) μ 1 , 2 ( l ) ; 0 , otherwise .

If the jobs are homogeneous (that is,

μ i , j ( m ) = μ i , j

, for all m), then the product‐myopic policy is equivalent to the policy in Theorem 4.1 by Andradóttir et al. (2001). The authors showed that this policy is optimal for maximizing the long‐run average throughput of a system with an infinite number of homogeneous jobs. We will show that this policy is also optimal for minimizing the expected makespan of a system with a finite number of homogeneous jobs.

Using the above indicator functions, we can then obtain π(k ≺ l), π(k ≻ l), τ ₁(k ≺ l), τ ₂(k ≻ l), and follow the procedure in section 4 to derive the expected makespan E[D _M ] under the summation‐myopic policy and the product‐myopic policy.

Teamwork policy: The two servers work together on the same job all the time. They serve each job at station 1, and then complete the job at station 2, before they initiate a new job.

The teamwork policy is proposed by Van Oyen et al. (2001). It is straightforward to calculate the expected makespan under the teamwork policy without using the indicator functions. That is,

E [ D M ] = ∑ m = 1 M ( 1 μ 1 , 1 ( m ) + μ 2 , 1 ( m ) + 1 μ 1 , 2 ( m ) + μ 2 , 2 ( m ) ) .

It is worth noting that we do not need the service rates of all the jobs at t = 0 in order to implement the three policies above. Furthermore, although the summation‐myopic policy considers more flexible server assignments than the other two policies, it is not clear whether the former can always outperform the latter policies. We discuss their relative performance in the next section.

Performance Evaluation

We first prove that some of the policies above are optimal for some special cases. For general cases, we compare numerically the performance of these policies against the optimal policy derived from the dynamic program in Table .

Optimality for some Special Cases

Theorem 1

If

μ 1 , 1 ( m ) / μ 2 , 1 ( m ) = μ 1 , 1 ( m + 1 ) / μ 2 , 1 ( m + 1 )

and

μ 1 , 2 ( m ) / μ 2 , 2 ( m ) = μ 1 , 2 ( m + 1 ) / μ 2 , 2 ( m + 1 )

, for m = 1,…,M − 1, then the product‐myopic policy is optimal.

Theorem 1 shows that if the servers maintain the same service‐rate ratio at each station over all the jobs, then the product‐myopic policy is optimal.

Corollary 1

If

μ i , j ( m ) = μ i , j

, for m = 1,…,M, then the product‐myopic policy is optimal.

Recall that if the jobs are homogeneous, then the product‐myopic policy is equivalent to the policy in Theorem 4.1 by Andradóttir et al. (2001). In contrast to Theorem 4.1 by Andradóttir et al. (2001) (which studies a system with an infinite number of homogeneous jobs), Corollary 1 shows that the product‐myopic policy is also optimal for minimizing the expected makespan of a system with a finite number of homogeneous jobs.

Theorem 2

If

μ 1 , 1 ( m ) / μ 2 , 1 ( m ) = μ 1 , 2 ( n ) / μ 2 , 2 ( n )

, for all jobs n and m, 0 < m − n ≤ B + 1, then the teamwork policy is optimal.

Theorem 2 shows that the teamwork policy is optimal if the servers maintain the same service‐rate ratio at different stations for all jobs n and m, 0 < m − n ≤ B + 1.

Theorem 3

The expected makespan of the summation‐myopic policy is no larger than that of the teamwork policy.

It is worth noting that the server assignments under the summation‐myopic policy combine the server assignments under the teamwork policy and the product‐myopic policy. Theorem 3 shows that the summation‐myopic policy is no worse than the teamwork policy. On the other hand, our numerical study in section 6.2 below suggests that the summation‐myopic policy can be better or worse than the product‐myopic policy.

It is straightforward to show that the conditions in Theorem 2:

μ 1 , 1 ( m ) / μ 2 , 1 ( m ) = μ 1 , 2 ( n ) / μ 2 , 2 ( n )

, for all jobs n and m, 0 < m − n ≤ B + 1, imply that the conditions in Theorem 1 hold. Under these conditions, the product‐myopic policy assigns server 1 to station 1 and server 2 to station 2, unless station 1 is blocked or station 2 is starved. It is surprising to find that the product‐myopic and the teamwork policies, though using very different server assignments, both generate the minimum expected makespan. Combining this result with Theorem 3 leads to the following corollary.

Corollary 2

If

μ 1 , 1 ( m ) / μ 2 , 1 ( m ) = μ 1 , 2 ( n ) / μ 2 , 2 ( n )

, for all jobs n and m, 0 < m − n ≤ B + 1, then the summation‐myopic policy, the product‐myopic policy, and the teamwork policy are all optimal.

Numerical Study for General Service Rates

We conduct a numerical study to compare the policies for general cases. Figure  benchmarks the expected makespan under the summation‐myopic, the product‐myopic, and the teamwork policies against the optimal expected makespan (from the dynamic program in Table ).

OPEN IN VIEWER

Figure 2

Expected Makespan

In Figure a, we set

μ 1 , 1 ( m ) = μ 2 , 1 ( m ) = 0.5 + m − 1 M − 1

,

μ 1 , 2 ( m ) = 1

, and

μ 2 , 2 ( m ) = 3

, for m = 1,2,3,…. Note that the servers are initially less familiar with the work at station 1, but their rate at station 1 increases as they serve more jobs. Under this setting, we have

μ 1 , 1 ( m ) / μ 2 , 1 ( m ) = μ 1 , 1 ( m + 1 ) / μ 2 , 1 ( m + 1 )

and

μ 1 , 2 ( m ) / μ 2 , 2 ( m ) = μ 1 , 2 ( m + 1 ) / μ 2 , 2 ( m + 1 )

, for m = 1,…,M − 1. According to Theorem 1, the product‐myopic policy is optimal. Note that under this parameter setting, the summation‐myopic policy behaves as the teamwork policy when m is small, but behaves as the product‐myopic policy when m is large. Thus, the expected makespan of the summation‐myopic policy lies between that of the teamwork and the product‐myopic policies.

We set

μ 1 , 1 ( m ) = μ 2 , 1 ( m ) = 0.5 + m − 1 M − 1

,

μ 1 , 2 ( m ) = 1

, and

μ 2 , 2 ( m ) = 1

, for m = 1,2,3,…, in Figure b. Under this setting, we have

μ 1 , 1 ( m ) / μ 2 , 1 ( m ) = μ 1 , 2 ( n ) / μ 2 , 2 ( n )

, for all jobs n and m, 0 < m − n ≤ 2. According to Corollary 2, the summation‐myopic policy, the product‐myopic policy, and the teamwork policy are all optimal. Figure b confirms this result.

Figure c shows an example where none of the three non‐idling policies is optimal. We set

μ 1 , 1 ( m ) = 10

and

μ 2 , 1 ( m ) = 1

, for m = 1,3,5,…,

μ 1 , 1 ( m ) = 1

and

μ 2 , 1 ( m ) = 10

, for m = 2,4,6,…,

μ 1 , 2 ( m ) = 1

and

μ 2 , 2 ( m ) = 10

, for m = 1,2,3,…. In this setting, there are two different types of jobs that are sequenced in an alternative manner. At station 1, server 1 is good at one type and server 2 is good at another type. This causes each server's rate at station 1 to oscillate between a high value and a low value. Note that the summation‐myopic policy and the product‐myopic policy have the same expected makespan under this setting.

Figure d shows another example where none of the three non‐idling policies is optimal. We set

μ 1 , 1 ( m ) = 20

, for m = 1,3,5,…,

μ 1 , 1 ( m ) = 1

, for m = 2,4,6,…,

μ 2 , 1 ( m ) = 1

, for m = 1,5,9,…,

μ 2 , 1 ( m ) = 5

, for m ≠ 1,5,9,…,

μ 1 , 2 ( m ) = 20

and

μ 2 , 2 ( m ) = 1

, for m = 1,2,3,…. In this setting, there are four different types of jobs that arrive in a rotating manner. At station 1, server 1 is good at the first and the third types, whereas server 2 is slow for the first type. Note that the summation‐myopic policy leads to a smaller expected makespan than the product‐myopic policy, and is very close to the optimal policy.

Among all the parameter settings in Figure , the summation‐myopic policy outperforms the teamwork policy, which is consistent with Theorem 3. However, the summation‐myopic policy can be better (see Figure d) or worse (see Figure a) than the product‐myopic policy. We believe that these different parameter settings cover a wide range of situations that may happen in practice. As shown in Figure , each policy performs differently in different situations.

Extension: General Buffer Size

In this section, we extend the analysis to a system with a general buffer size

B ∈ N

. We first describe the dynamic program to determine the optimal policy. We also derive the expected makespan of a general non‐idling policy. We then discuss the expected makespan of the three specific policies and their performance.

The Optimal Policy

Recall that V(t) denote the number of jobs that are finished at station 1 but not yet finished at station 2 at time t. For a system with a general buffer size B, we have V(t) ∈ {0,…,B + 2}. Note that V(t) = B + 2 if station 1 is blocked at time t. Table  describes the dynamic program for the system with a general buffer size B. The expected makespan under the optimal policy is f _(M,0).

OPEN IN VIEWER

Table 3

Dynamic Programming Formulation for a System with a General Buffer Size B

f (0,0) = 0.

For u = 1,…,M,

f ( u , 0 ) = 1 μ 1 , 1 ( M − u + 1 ) + μ 2 , 1 ( M − u + 1 ) + f ( u − 1 , 1 ) .

For u = 1,…,M−B−2,

f ( u , B + 2 ) = 1 μ 1 , 2 ( M − u − B − 1 ) + μ 2 , 2 ( M − u − B − 1 ) + f ( u , B + 1 ) .

For v = 1,…,B + 2,

f ( 0 , v ) = 1 μ 1 , 2 ( M − v + 1 ) + μ 2 , 2 ( M − v + 1 ) + f ( 0 , v − 1 ) .

For u = 1,…,M−v; v = 1,…,B+1,

f ( u , v ) = min { f ( u , v ) I , f ( u , v ) II , f ( u , v ) III , f ( u , v ) IV } ,

where

f ( u , v ) I = 1 μ 1 , 1 ( M − u + 1 ) + μ 2 , 1 ( M − u + 1 ) + f ( u − 1 , v + 1 ) ;

f ( u , v ) II = 1 μ 1 , 2 ( M − u − v + 1 ) + μ 2 , 2 ( M − u − v + 1 ) + f ( u , v − 1 ) ;

f ( u , v ) III = 1 μ 1 , 1 ( M − u + 1 ) + μ 2 , 2 ( M − u − v + 1 ) + μ 1 , 1 ( M − u + 1 ) μ 1 , 1 ( M − u + 1 ) + μ 2 , 2 ( M − u − v + 1 ) f ( u − 1 , v + 1 ) + μ 2 , 2 ( M − u − v + 1 ) μ 1 , 1 ( M − u + 1 ) + μ 2 , 2 ( M − u − v + 1 ) f ( u , v − 1 ) ;

f ( u , v ) IV = 1 μ 2 , 1 ( M − u + 1 ) + μ 1 , 2 ( M − u − v + 1 ) + μ 2 , 1 ( M − u + 1 ) μ 2 , 1 ( M − u + 1 ) + μ 1 , 2 ( M − u − v + 1 ) f ( u − 1 , v + 1 ) + μ 1 , 2 ( M − u − v + 1 ) μ 2 , 1 ( M − u + 1 ) + μ 1 , 2 ( M − u − v + 1 ) f ( u , v − 1 ) .

The Expected Makespan of a General Non‐Idling Policy

To derive the expected makespan of a general non‐idling policy, we first calculate p _m,i , for i = 0,…,m − 1 and m = 1,…,M. Given the buffer size B, we have p _m,i  = 0 for i > B + 1. Since job 1, upon its service completion at station 1, always finds the buffer and station 2 empty, we have p _1,0 = 1. The following lemma determines p _m,i , for m = 2,…,M. For notational convenience, we define π(k ≺ l) = 1 and

τ 1 ( k ≺ l ) = 1 μ 1 , 1 ( k ) + μ 2 , 1 ( k )

, if k = l; and π(k ≻ l) = 1 and

τ 2 ( k ≻ l ) = 1 μ 1 , 2 ( l ) + μ 2 , 2 ( l )

if k = l + B + 2.

Lemma

For m = 2,…,M,

p m , i = ∑ j = max { 0 , i − 1 } m − 2 p m − 1 , j Pr { R m = i | R m − 1 = j } ,

where

Pr { R m = i | R m − 1 = j } = π ( m ≺ m − i ) ∏ l = m − j − 1 m − i − 1 π ( m ≻ l ) , if j ≤ B ; π ( m ≺ m − i ) ∏ l = m − B − 1 m − i − 1 π ( m ≻ l ) , if j = B + 1 .

Similar to section 4, to determine the expected makespan E[D _M ], we need to derive the four components E[W _M ], E[X _M ], E[Y _M ], and E[Z _M ].

Duration at station 1

We first calculate E[X _m ]: the expected duration of job m staying at station 1. We separate the duration of job m staying at station 1, X _m , into two parts: the duration of job m staying at station 1 before its service at the station finishes, X _1,m , and the duration of job m staying at station 1 after its service at the station finishes, X _2,m . Note that X _1,m may be longer than the actual service duration of job m at station 1 because job m could be idle at station 1 while both servers work at station 2 (depending on the specific policy used). Furthermore, X _2,m represents the duration when job m is blocked at station 1. Thus, we have E[X _m ] = E[X _1,m ] + E[X _2,m ].

To derive E[X _1,m ] and E[X _2,m ], let S _m denote the number of jobs at the buffer and station 2 found by job m upon entering station 1, for m = 2,…,M. Recall that R _m denote the number of jobs at the buffer and station 2 found by job m upon its service completion at station 1. Obviously, we have R _m ≤ S _m . For m = 1, job 1 is first served by both servers at station 1. After that it leaves station 1 without waiting. Thus, we have

E [ X 1 , 1 ] = 1 μ 1 , 1 ( 1 ) + μ 2 , 1 ( 1 )

and E[X _2,1] = 0. For m = 2,…,M, we have

E [ X 1 , m ] = ∑ j = 1 m − 1 ∑ i = 0 j E [ X 1 , m | R m = i , S m = j ] Pr { R m = i | S m = j } Pr { S m = j } ,

and

E [ X 2 , m ] = ∑ i = 0 m − 1 E [ X 2 , m | R m = i ] Pr { R m = i } .

Recall that Pr{R _m =i}=p _m,i is given in Lemma 2. Given the buffer size B, we have

Pr { S m = j } = Pr { R m = i | S m = j } = 0

, for j > B + 1. The following proposition determines Pr{S _m  = j},

Pr { R m = i | S m = j }

,

E [ X 1 , m | R m = i , S m = j ]

, and

E [ X 2 , m | R m = i ]

, for m = 2,…,M.

Proposition

For j = 1,…,B + 1, i = 0,…,j,

Pr { S m = j } = p m − 1 , j − 1 , if 1 ≤ j ≤ B ; p m − 1 , B + p m − 1 , B + 1 , if j = B + 1 ; Pr { R m = i | S m = j } = π ( m ≺ m − i ) ∏ l = m − j m − i − 1 π ( m ≻ l ) ; E [ X 1 , m | R m = i , S m = j ] = ∑ l = m − j m − i − 1 τ 2 ( m ≻ l ) + τ 1 ( m ≺ m − i ) .

For i = 0,…, m − 1,

E [ X 2 , m | R m = i ] = 1 μ 1 , 2 ( m − B − 1 ) + μ 2 , 2 ( m − B − 1 ) , if i = B + 1 ; 0 , otherwise .

Duration at the initial position

Similar to the case with B = 1, we have E[W ₁] = 0 and E[W _m ] = E[W _m−1] + E[X _m−1], for m = 2,…,M. After obtaining E[X _m ], m = 1,…,M, from Proposition 4, we can determine E[W _m ] recursively, starting from m = 1.

Duration at station 2

We now calculate E[Z _m ]: the expected duration of job m staying at station 2. Let O _m denote the number of jobs at the buffer found by job m upon entering station 2, and let Q _m denote the number of jobs at the buffer and station 2 immediately after job m leaves station 2, for m = 1,…,M − 1. Obviously, we have O _m ≤Q _m . For m = M, job M is served by both servers at station 2 when it enters the station. Thus, we have

E [ Z M ] = 1 μ 1 , 2 ( M ) + μ 2 , 2 ( M )

. For m = 1,…,M − 1, we have

E [ Z m ] = ∑ i = 0 M − m ∑ j = i M − m E [ Z m | O m = i , Q m = j ] Pr { Q m = j | O m = i } Pr { O m = i } .

Given the buffer size B, we have Pr{O _m  = i} = 0, for i > B, and

Pr { Q m = j | O m = i } = 0

, for i > B or j > B + 1. The following proposition determines Pr{O _m  = i},

Pr { Q m = j | O m = i }

, and

E [ Z m | O m = i , Q m = j ]

, for m = 1,…,M − 1.

Proposition

For m = 1,…,M − B,

Pr { O m = i } = p m + 1 , 0 + p m + 1 , 1 , if i = 0 ; ∑ j = 0 i + 1 p m + i + 1 , j − ∑ j = 0 i p m + i , j , if 1 ≤ i ≤ B − 1 ; p m + B , B + 1 , if i = B .

For m = M − B + 1,…,M − 1,

Pr { O m = i } = p m + 1 , 0 + p m + 1 , 1 , if i = 0 ; ∑ j = 0 i + 1 p m + i + 1 , j − ∑ j = 0 i p m + i , j , if 1 ≤ i ≤ M − m − 1 ; ∑ j = M − m + 1 B + 1 p M , j , if i = M − m .

For m = 1,…,M − 1, i = 0,…,M − m,

Pr { Q m = j | O m = i } = π ( m + j + 1 ≻ m ) ∏ k = m + i + 1 m + j π ( k ≺ m ) , if i ≤ j ≤ M − m − 1 ; = ∏ k = m + i + 1 M π ( k ≺ m ) , if j = M − m ;

E [ Z m | O m = i , Q m = j ] = ∑ k = m + i + 1 m + j τ 1 ( k ≺ m ) + τ 2 ( m + j + 1 ≻ m ) , if i ≤ j ≤ M − m − 1 ; ∑ k = m + i + 1 M τ 1 ( k ≺ m ) + 1 μ 1 , 2 ( m ) + μ 2 , 2 ( m ) , if j = M − m .

Duration at the buffer

To calculate the duration of job m staying at the buffer, Y _m , let Γ _m denote the time point when job m enters station 2, for m = 1,…,M. Let ϒ _m denote the duration from the time point when job m − 1 leaves station 2 to the time point when job m enters station 2, for m = 2,…,M.

We first derive E[ϒ _m ]. If job m finishes service at station 1 before job m−1 finishes service at station 2 (that is, R _m  > 0), then ϒ _m  = 0. Thus, we have

E [ Υ m | R m > 0 ] = 0

. Otherwise, we have R _m  = 0. In this case, upon job m − 1 completes its service at station 2, station 2 becomes starved, and both servers work at station 1 on job m. After job m finishes its service at station 1, it enters station 2 immediately (because the buffer is empty). Thus, we have

E [ Υ m | R m = 0 ] = 1 μ 1 , 1 ( m ) + μ 2 , 1 ( m )

. Combining the two cases, we have

E [ Υ m ] = E [ Υ m | R m > 0 ] Pr { R m > 0 } + E [ Υ m | R m = 0 ] Pr { R m = 0 } = p m , 0 μ 1 , 1 ( m ) + μ 2 , 1 ( m )

, for m = 2,…,M.

We now derive E[Γ _m ]. For m = 1,

E [ Γ 1 ] = 1 μ 1 , 1 ( 1 ) + μ 2 , 1 ( 1 )

. For m = 2,…,M, we have E[Γ _m ] = E[Γ _m−1] + E[Z _m−1] + E[ϒ _m ]. After determining E[Γ _m ], the expected duration of job m staying at the buffer can be calculated as E[Y _m ] = E[Γ _m ] − (E[W _m ] + E[X _m ]), where E[W _m ] + E[X _m ] represents the expected duration for job m to enter the buffer.

After finding all the four time components, the expected makespan can be obtained as E[D _M ] = E[W _M ] + E[X _M ] + E[Y _M ] + E[Z _M ].

The Expected Makespans of the Three Specific Non‐Idling Policies

We revisit the three specific non‐idling policies: the summation‐myopic policy, the product‐myopic policy, and the teamwork policy for the system with a general buffer size B. Note that the indicator functions δ ^I(k,l), δ ^II(k,l), δ ^III(k,l), and δ ^IV(k,l) under the summation‐myopic policy and the product‐myopic policy remain the same as in section 5. Using these indicator functions, we can obtain π(k ≺ l), π(k ≻ l), τ ₁(k ≺ l), τ ₂(k ≻ l) in section 4, and follow the procedure in section 2 to derive the expected makespan E[D _M ] under the summation‐myopic policy or the product‐myopic policy. Note that the expected makespan under the teamwork policy is given in section 5 and is independent of the buffer size.

Performance Evaluation

For the system with a general buffer size B, we have the same results as in section 6 on the optimality of the three non‐idling policies under certain conditions on the service rates.

Theorem 4

All the results in Theorems 1‐3 and Corollaries 1‐2 hold for the system with a buffer size

B ∈ N

.

A numerical study comparing the summation‐myopic, the product‐myopic, and the teamwork policies against the optimal policy (from the dynamic program in Table ) based on general service rates gives very similar results as in Figure . Thus, we do not show the results here.

Extensions: Moving Costs and Service Defects of a General Non‐Idling Policy

Since we characterize the servers’ movements between the stations in our analysis, we can incorporate the costs for the servers to transfer between the stations and the probability of creating defects at each station in the model. In this section, we develop methods to calculate the moving costs and the number of perfect jobs under a general non‐idling policy. We then compare the three specific non‐idling policies in terms of these performance measures. For illustration purposes, we focus on the case with B = 1. To the best of our understanding, moving costs and service defects are generally under studied in the literature. See Andradóttir et al. (2012) for an analysis of a system incurring setup costs when servers move between stations. They consider that the system serves an infinite number of jobs.

Incorporating Moving Costs

Our methodology enables us to calculate the expected total moving cost, which serves as a separate objective besides the expected makespan. We assume that a moving costc ₁ (c ₂) is incurred every time server 1 (server 2) moves from one station to another. Suppose servers 1 and 2 are currently at stations s ₁ and s ₂, respectively, where s ₁,s ₂ = 1,2. If we choose server assignment I in section 3, then a moving cost c ^I(s ₁,s ₂) = (s ₁ − 1)c ₁ + (s ₂ − 1)c ₂ is incurred. Similarly, we have c ^II(s ₁,s ₂) = (2 − s ₁)c ₁ + (2 − s ₂)c ₂, c ^III(s ₁,s ₂) = (s ₁−1)c ₁ + (2 − s ₂)c ₂, and c ^IV(s ₁,s ₂) = (2 − s ₁)c ₁ + (s ₂−1)c ₂, for server assignments II, III, and IV, respectively.

Suppose in the current state, neither station 1 is blocked nor station 2 is starved, jobs k and l are at stations 1 and 2 respectively, and servers 1 and 2 are at stations s ₁ and s ₂, respectively. For a system with M jobs, let C _(M)(k,l,s ₁,s ₂) denote the expected moving cost from the current state until the completion of all the jobs under a general non‐idling policy. For notational convenience, let k = 0 represent the case when station 1 is blocked or job M has finished its service at station 1, and let l = 0 represent the case when station 2 is starved.

Suppose in the current state, station 1 is not blocked, job M has not finished its service at station 1, and station 2 is not starved. Assume jobs k and l are at stations 1 and 2 respectively, and servers 1 and 2 are at stations s ₁ and s ₂ respectively. For a system with M jobs, let C _(M)(k,l,s ₁,s ₂) denote the expected moving cost from the current state until the completion of all the jobs under a general non‐idling policy. For a state in which station 1 is blocked or job M has finished its service at station 1, let C _(M)(0,l,s ₁,s ₂) denote the expected moving cost from the state until the completion of all the jobs under a general non‐idling policy. Similarly, for a state in which station 2 is starved, let C _(M)(k,0,s ₁,s ₂) denote the expected moving cost from the state until the completion of all the jobs under a general non‐idling policy.

Let

C ^ ( M )

denote the expected total moving cost of a system with M jobs under a general non‐idling policy. Since the system always starts with the two servers simultaneously serving job 1 at station 1, we have

C ^ ( M ) = C ( M ) ( 1 , 0 , 1 , 1 )

. To derive C _(M)(1,0,1,1), we calculate C _(M)(k,l,s ₁,s ₂), for k = 0,l + 1,l + 2, and s ₁,s ₂ = 1,2, according to Table 4 in the online supplement by enumerating l from M to 0. Recall that the indicator functions δ ^I(k,l), δ ^II(k,l), δ ^III(k,l), and δ ^IV(k,l) under the summation‐myopic policy and the product‐myopic policy are given in section 5. For the teamwork policy, it is straightforward to derive that the expected total moving cost equals (2M−1)(c ₁ + c ₂), which is the largest among all the policies discussed.

Figure  compares the expected total moving costs of the three policies. We set c ₁ = c ₂ = 1. For each sub‐figure of Figure , we use the same parameter setting as in the corresponding sub‐figure of Figure . Figure a shows that the teamwork policy leads to the largest expected total moving cost, followed by the summation‐myopic policy. The product‐myopic policy has the smallest expected total moving cost. The rankings of the policies are identical to that of Figure a, which is based on the expected makespan. It is interesting to compare Figures b and b. Although the three policies lead to the same expected makespan, they produce very different expected total moving costs. Comparing Figures c and c suggests that the summation‐myopic and the product‐myopic policies yield not only the same expected makespan, but also the same expected total moving cost. This suggests that the two policies are identical under this parameter setting. In contrast to Figures a–d shows that the summation‐myopic policy may lead to a smaller expected total moving cost than the product‐myopic policy.

OPEN IN VIEWER

Figure 3

Expected Total Moving Cost

Incorporating Service Defects

We now consider a system that may generate defects. We assume two types of service defects: Type‐1 (type‐2) defects only occur at station 1 (station 2). These two types of defects occur independently. For each job, the probability of having a type‐j defect depends on who serves the job at station j, j = 1,2. This probability is determined by one of the following scenarios:

The job is finished only by server i at station j (this includes the case in which the job is first served by another server i ^′ and later finished by server i at that station). The probability for the job to have a type‐j defect is d _i,j .

The job is finished by both servers at station j (this includes the case in which the job is first served only by one server and later finished by both servers at that station). The probability for the job to have a type‐j defect is d _j .

Define

d ¯ i , j = 1 − d i , j

and

d ¯ j = 1 − d j

, for i,j = 1,2. A job is called perfect if no defects occur during its services at stations 1 and 2. For a system with M jobs, let Q _(M) denote the expected number of perfect jobs. Define P _(M),m as the probability that job m is perfect, for m = 1,…,M. Thus, we have

Q ( M ) = ∑ m = 1 M P ( M ) , m

. To calculate P _(M),m , we need to know whether the job is finished by only one server or both servers at each station. The following proposition determines P _(M),m , for m = 1,…,M, under a general non‐idling policy.

Proposition

If M = 1, then

P ( 1 ) , 1 = d ¯ 1 d ¯ 2

. If M = 2, then

P ( 2 ) , 1 = d ¯ 1 [ p 2 , 0 ( d ¯ 2 δ II ( 2 , 1 ) + d ¯ 2 , 2 δ III ( 2 , 1 ) + d ¯ 1 , 2 δ IV ( 2 , 1 ) ) + p 2 , 1 d ¯ 2 ] , P ( 2 ) , 2 = d ¯ 2 [ p 2 , 1 ( d ¯ 1 δ I ( 2 , 1 ) + d ¯ 1 , 1 δ III ( 2 , 1 ) + d ¯ 2 , 1 δ IV ( 2 , 1 ) ) + p 2 , 0 d ¯ 1 ] .

If M ≥ 3, for m = 1,…,M − 2, we have

P ( M ) , m = p m , 0 d ¯ 1 K m + [ p m , 1 ( d ¯ 1 δ I ( m , m − 1 ) + d ¯ 1 , 1 δ III ( m , m − 1 ) + d ¯ 2 , 1 δ IV ( m , m − 1 ) ) + p m , 2 ( d ¯ 1 δ I ( m , m − 2 ) + d ¯ 1 , 1 δ III ( m , m − 2 ) + d ¯ 2 , 1 δ IV ( m , m − 2 ) ) ] × [ J m δ I ( m + 1 , m − 1 ) + K m δ II ( m + 1 , m − 1 ) + μ 1 , 1 ( m + 1 ) μ 1 , 1 ( m + 1 ) + μ 2 , 2 ( m − 1 ) J m + μ 2 , 2 ( m − 1 ) μ 1 , 1 ( m + 1 ) + μ 2 , 2 ( m − 1 ) K m δ III ( m + 1 , m − 1 ) + μ 2 , 1 ( m + 1 ) μ 2 , 1 ( m + 1 ) + μ 1 , 2 ( m − 1 ) J m + μ 1 , 2 ( m − 1 ) μ 2 , 1 ( m + 1 ) + μ 1 , 2 ( m − 1 ) K m δ IV ( m + 1 , m − 1 ) ] ,

where

J m = d ¯ 2 δ I ( m + 2 , m ) + d ¯ 2 δ II ( m + 2 , m ) + μ 1 , 1 ( m + 2 ) μ 1 , 1 ( m + 2 ) + μ 2 , 2 ( m ) d ¯ 2 + μ 2 , 2 ( m ) μ 1 , 1 ( m + 2 ) + μ 2 , 2 ( m ) d ¯ 2 , 2 δ III ( m + 2 , m ) + μ 2 , 1 ( m + 2 ) μ 2 , 1 ( m + 2 ) + μ 1 , 2 ( m ) d ¯ 2 + μ 1 , 2 ( m ) μ 2 , 1 ( m + 2 ) + μ 1 , 2 ( m ) d ¯ 1 , 2 δ IV ( m + 2 , m ) , K m = J m δ I ( m + 1 , m ) + d ¯ 2 δ II ( m + 1 , m ) + μ 1 , 1 ( m + 1 ) μ 1 , 1 ( m + 1 ) + μ 2 , 2 ( m ) J m + μ 2 , 2 ( m ) μ 1 , 1 ( m + 1 ) + μ 2 , 2 ( m ) d ¯ 2 , 2 δ III ( m + 1 , m ) + μ 2 , 1 ( m + 1 ) μ 2 , 1 ( m + 1 ) + μ 1 , 2 ( m ) J m + μ 1 , 2 ( m ) μ 2 , 1 ( m + 1 ) + μ 1 , 2 ( m ) d ¯ 1 , 2 δ IV ( m + 1 , m ) .

For m = M − 1, we have

P ( M ) , M − 1 = p M − 1 , 0 d ¯ 1 K M − 1 + [ p M − 1 , 1 ( d ¯ 1 δ I ( M − 1 , M − 2 ) + d ¯ 1 , 1 δ III ( M − 1 , M − 2 ) + d ¯ 2 , 1 δ IV ( M − 1 , M − 2 ) ) + p M − 1 , 2 ( d ¯ 1 δ I ( M − 1 , M − 3 ) + d ¯ 1 , 1 δ III ( M − 1 , M − 3 ) + d ¯ 2 , 1 δ IV ( M − 1 , M − 3 ) ) ] × [ d ¯ 2 δ I ( M , M − 2 ) + K M − 1 δ II ( M , M − 2 ) + μ 1 , 1 ( M ) μ 1 , 1 ( M ) + μ 2 , 2 ( M − 2 ) d ¯ 2 + μ 2 , 2 ( M − 2 ) μ 1 , 1 ( M ) + μ 2 , 2 ( M − 2 ) K M − 1 δ III ( M , M − 2 ) + μ 2 , 1 ( M ) μ 2 , 1 ( M ) + μ 1 , 2 ( M − 2 ) d ¯ 2 + μ 1 , 2 ( M − 2 ) μ 2 , 1 ( M ) + μ 1 , 2 ( M − 2 ) K M − 1 δ IV ( M , M − 2 ) ] ,

where

K M − 1 = d ¯ 2 δ I ( M , M − 1 ) + d ¯ 2 δ II ( M , M − 1 ) + μ 1 , 1 ( M ) μ 1 , 1 ( M ) + μ 2 , 2 ( M − 1 ) d ¯ 2 + μ 2 , 2 ( M − 1 ) μ 1 , 1 ( M ) + μ 2 , 2 ( M − 1 ) d ¯ 2 , 2 δ III ( M , M − 1 ) + μ 2 , 1 ( M ) μ 2 , 1 ( M ) + μ 1 , 2 ( M − 1 ) d ¯ 2 + μ 1 , 2 ( M − 1 ) μ 2 , 1 ( M ) + μ 1 , 2 ( M − 1 ) d ¯ 1 , 2 δ IV ( M , M − 1 ) .

For m=M, we have

P ( M ) , M = d ¯ 2 [ p M , 0 d ¯ 1 + p M , 1 ( d ¯ 1 δ I ( M , M − 1 ) + d ¯ 1 , 1 δ III ( M , M − 1 ) + d ¯ 2 , 1 δ IV ( M , M − 1 ) ) + p M , 2 ( d ¯ 1 δ I ( M , M − 2 ) + d ¯ 1 , 1 δ III ( M , M − 2 ) + d ¯ 2 , 1 δ IV ( M , M − 2 ) ) ] .

To calculate P _(M),m and Q _(M) for the summation‐myopic policy or the product‐myopic policy, we can substitute the corresponding indicator functions δ ^I(k,l), δ ^II(k,l), δ ^III(k,l), and δ ^IV(k,l) from section 5 into Proposition 6. It is straightforward to see that under the teamwork policy, we have

Q ( M ) = M d ¯ 1 d ¯ 2

. If d _j  < d _i,j , for i,j = 1,2 (for example, if the servers help each other to avoid mistakes when they work jointly), then the teamwork policy yields the largest expected number of perfect jobs among all the policies discussed.

We conduct a numerical study to compare the three policies in terms of the expected number of perfect jobs. We consider the following three cases:

d ₁ < d _i,1,d ₂ < d _i,2. d _1,1 < d _1,2,d _2,2 < d _2,1.

d ₁ > d _i,1,d ₂ > d _i,2. d _1,1 < d _1,2,d _2,2 < d _2,1.

d ₁ < d _i,1,d ₂ > d _i,2. d _1,1 = d _2,1,d _1,2 = d _2,2.

Figure a shows the expected percentage of perfect jobs under each policy for case (i). We use the same parameter setting as in Figure a. We set d ₁ = d ₂ = 0.02, d _1,1 = d _2,2 = 0.1, and d _1,2 = d _2,1 = 0.2. Since d _j  < d _i,j , for i,j = 1,2, the teamwork policy yields the largest expected percentage of perfect jobs in Figure a as the servers always work jointly under this policy. The performance of the summation‐myopic policy falls in the middle, producing a larger expected percentage of perfect jobs than the product‐myopic policy. This is because under the product‐myopic policy, the two servers generally work separately (unless the system is blocked or starved), which leads to more defects. In contrast, the summation‐myopic policy mixes the server assignments of the other two policies, producing the expected percentage of perfect jobs that always falls between that of the two policies.

OPEN IN VIEWER

Figure 4

Expected Percentage of Perfect Jobs

Using the same parameter setting as in Figures a and b shows the expected percentage of perfect jobs under each policy for case (ii). We set d ₁ = d ₂ = 0.3, d _1,1 = d _2,2 = 0.1, and d _1,2 = d _2,1 = 0.2. In this case, we have d _j  > d _i,j , for i,j = 1,2. In contrast to case (i), the teamwork policy yields the smallest expected percentage of perfect jobs in this situation. The performance of the summation‐myopic policy remains in the middle, and the product‐myopic policy gives the largest expected percentage of perfect jobs.

Figure  shows the expected percentage of perfect jobs under each policy for case (iii). In this case, the servers are less likely to create defects when they work jointly at station 1, but are more likely to create defects when they work jointly at station 2. For each sub‐figure of Figure , we use the same parameter setting as in the corresponding sub‐figure of Figure . We set d ₁ = d ₂ = 0.1, d _1,1 = d _2,1 = 0.2, and d _1,2 = d _2,2 = 0.02. The teamwork policy yields the same expected percentage of perfect jobs in all the sub‐figures. Figure a shows that the product‐myopic policy outperforms the summation‐myopic policy, whereas we have the opposite result in Figure d. Both policies produce fewer defects than the teamwork policy. In Figure c, the summation‐myopic policy produces the same expected percentage of perfect jobs as the teamwork policy, whereas the product‐myopic policy creates the largest number of defects. Figure  shows that the summation‐myopic and the product‐myopic policies produce the same expected percentage of perfect jobs. This again verifies that these two policies are identical under this parameter setting.

OPEN IN VIEWER

Figure 5

Expected Percentage of Perfect Jobs

Conclusion

We study a two‐station, two‐server tandem system serving a finite number of jobs. There is a finite buffer between the stations. The servers are cross‐trained such that they can work at both stations. The duration for each server to serve a job at each station is exponentially distributed with a rate that depends on the server, the station, and the job. This tandem system is common in the manufacturing and the service industries, where workforce is a major operating cost. In these environments, it is important to maximize the productivity by effectively using the workforce.

We formulate a stochastic dynamic program to identify an optimal policy that dynamically assigns the servers to the stations to minimize the expected makespan. Unfortunately, the optimal policy is too complicated to characterize for a large number of jobs. This motivates us to develop simpler and more intuitive policies. We use the optimal policy as a benchmark when we evaluate the simpler policies.

Since the optimal policy is non‐idling, we focus on non‐idling policies in this study. Using the basic probability theory, we first derive the expected makespan of a system with a buffer size B = 1 under a general non‐idling policy. We then analyze three specific non‐idling policies: the summation‐myopic, the product‐myopic, and the teamwork policies. We prove that the product‐myopic policy is optimal in minimizing the expected makespan if the servers maintain the same service‐rate ratio at each station for all the jobs (see Theorem 1). Furthermore, if the service rates are independent of the jobs (that is, the jobs are homogeneous), then the product‐myopic policy is optimal (see Corollary 1). We also prove that the teamwork policy is optimal if the servers maintain the same service‐rate ratio at different stations for all jobs n and m, 0 < m − n ≤ B + 1 (see Theorem 2). Finally, we prove that the expected makespan of the summation‐myopic policy is no larger than that of the teamwork policy (see Theorem 3). On the other hand, our numerical study based on general service rates suggests that the summation‐myopic policy can be better or worse than the product‐myopic policy.

We extend the analysis to a system with a general buffer size

B ∈ N

. We derive the expected makespan of a general non‐idling policy and the three specific policies. We prove that all the optimality results for the system with a buffer size B = 1 still hold. We also extend the model to incorporate moving costs and service defects, which are under studied in the literature. We derive the expected total moving cost and the expected number of perfect jobs (without service defects) under a general non‐idling policy. A numerical study suggests that in terms of the expected total moving cost, the teamwork policy is always the worst, whereas the relative performance of the summation‐myopic and the product‐myopic policies depends on the service rates. Furthermore, each of the three policies can possibly produce the largest expected number of perfect jobs.

Footnotes

Acknowledgment

The authors thank the senior editor and the two anonymous referees for their valuable comments that have substantially improved the paper. The first author is grateful for the support from the Singapore Management University under the Lee Kong Chian Fellowship and the Ministry of Education, Singapore under the MOE Tier 1 Academic Research Fund.

ORCID

Yun Fong Lim

References

1.

Ahn H.‐S. Duenyas I. Zhang R. . 2004. Optimal control of a flexible server. Adv. Appl. Prob. 36(1): 139–170.

Go to Reference

2.

Andradóttir S. Ayhan H. . 2005. Throughput maximization for tandem lines with two stations and flexible servers. Oper. Res. 53(3): 516–531.

+ Show References

3.

Andradóttir S. Ayhan H. Down D. G. . 2001. Server assignment policies for maximizing the steady‐state throughput of finite queueing systems. Manage. Sci. 47(10): 1421–1439.

+ Show References

4.

Andradóttir S. Ayhan H. Down D. G. . 2003. Dynamic server allocation for queueing networks with flexible servers. Oper. Res. 51(6): 952–968.

+ Show References

5.

Andradóttir S. Ayhan H. Down D. G. . 2007a. Compensating for failures with flexible servers. Oper. Res. 55(4): 753–768.

Go to Reference

6.

Andradóttir S. Ayhan H. Down D. G. . 2007b. Dynamic assignment of dedicated and flexible servers in tandem lines. Prob. Eng. Inform. Sci. 21(4): 497–538.

Go to Reference

7.

Andradóttir S. Ayhan H. Kirkizlar E. . 2012. Flexible servers in tandem lines with setup costs. Queueing Syst. 70(2): 165–186.

Go to Reference

8.

Armbruster D. Gel E. S. . 2006. Bucket brigades revisited: Are they always effective?. Eur. J. Oper. Res. 172(1): 213–229.

Go to Reference

9.

Armony M. Chan C. W. Zhu B. . 2018. Critical care capacity management: Understanding the role of a step down unit. Prod. Oper. Manag. 27(5): 859–883.

Go to Reference

10.

Bartholdi J. J. III Eisenstein D. D. . 1996. A production line that balances itself. Oper. Res. 44(1): 21–34.

Go to Reference

11.

Bartholdi J. J. III Eisenstein D. D. . 2005. Using bucket brigades to migrate from craft manufacturing to assembly lines. Manuf. Serv. Oper. Manag. 7(2): 121–129.

Go to Reference

12.

Bartholdi J. J. III Bunimovich L. A. Eisenstein D. D. . 1999. Dynamics of two‐ and three‐worker “bucket brigade” production lines. Oper. Res. 47(3): 488–491.

Go to Reference

13.

Bartholdi J. J. III Eisenstein D. D. Foley R. D. . 2001. Performance of bucket brigades when work is stochastic. Oper. Res. 49(5): 710–719.

Go to Reference

14.

Bell S. L. Williams R. J. 2001. Dynamic scheduling of a system with two parallel servers in heavy traffic with complete resource pooling: Asymptotic optimality of a threshold policy. Ann. Appl. Prob. 11(3): 608–649.

Go to Reference

15.

Cachon G. Terwiesch C. . 2013. Matching Supply with Demand, 3rd Edition. McGraw‐Hill, New York, NY.

Go to Reference

16.

Duenyas I. Gupta D. Olsen T. L. . 1998. Control of a single server queueing system with setups. Oper. Res. 46(2): 218–230.

Go to Reference

17.

Farrar T. M. 1993. Optimal use of an extra server in a two station tandem queueing network. IEEE Trans. Autom. Control 38(8): 1296–1299.

Go to Reference

18.

Gel E. S. Hopp W. J. Van Oyen M. P. . 2002. Factors affecting opportunity of worksharing as a dynamic line balancing mechanism. IIE Trans. 34(10): 847–863.

Go to Reference

19.

Harrison J. M. López M. J. . 1999. Heavy traffic resource pooling in parallel‐server systems. Queue. Sys. 33(4): 339–368.

Go to Reference

20.

Hopp W. J. Spearman M. C. . 2008. Factory Physics, 3rd Edition. Waveland Press, Inc, Long Grove, IL.

Go to Reference

21.

Hopp W. J. Van Oyen M. P. . 2004. Agile workforce evaluation: A framework for cross‐training and coordination. IIE Trans. 36(10): 919–940.

Go to Reference

22.

Hopp W. J. Tekin E. Van Oyen M. P. . 2004. Benefits of skill chaining in serial production lines with cross‐trained workers. Manage. Sci. 50(1): 83–98.

Go to Reference

23.

Iravani S. M. R. Posner M. J. M. Buzacott J. M. . 1997. A two‐stage tandem queue attended by a moving server with holding and switching costs. Queue. Syst. 26(3‐4): 203–228.

Go to Reference

24.

Kaufman D. L. Ahn H.‐S. Lewis M. E. . 2005. On the introduction of an agile, temporary workforce into a tandem queueing system. Queue. Syst. 51(1‐2): 135–171.

Go to Reference

25.

Kirkizlar E. Andradóttir S. Ayhan H. . 2010. Robustness of efficient server assignment policies to service time distributions in finite‐buffered lines. Naval Res. Logist. 57(6): 563–582.

Go to Reference

26.

Lim Y. F. 2011. Cellular bucket brigades. Oper. Res. 59(6): 1539–1545.

Go to Reference

27.

Lim Y. F. 2017. Performance of cellular bucket brigades with hand‐off times. Prod. Oper. Manag. 26(10): 1915–1923.

Go to Reference

28.

Lim Y. F. Wu Y. . 2014. Cellular bucket brigades on U‐lines with discrete work stations. Prod. Oper. Manag. 23(7): 1113–1128.

Go to Reference

29.

Lim Y. F. Yang K. K. . 2009. Maximizing throughput of bucket brigades on discrete work stations. Prod. Oper. Manag. 18(1): 48–59.

Go to Reference

30.

Mandelbaum A. Stolyar A. L. . 2004. Scheduling flexible servers with convex delay costs: Heavy‐traffic optimality of the generalized cμ‐rule. Oper. Res. 52(6): 836–855.

Go to Reference

31.

Ostolaza J. McClain J. O. Thomas L. J. . 1990. The use of dynamic (state‐dependent) assembly‐line balancing to improve throughput. J. Manuf. Oper. Manag. 3(2): 105–133.

Go to Reference

32.

Rosberg Z. Varaiya P. P. Walrand J. C. . 1982. Optimal control of service in tandem queues. IEEE Trans. Autom. Control 27(3): 600–609.

Go to Reference

33.

Van Oyen M. P. Gel E. S. Hopp W. J. . 2001. Performance opportunity for workforce agility in collaborative and noncollaborative work systems. IIE Trans. 33: 761–777.

+ Show References

34.

Wallace R. B. Whitt W. . 2005. A staffing algorithm for call centers with skill‐based routing. Manuf. Serv. Oper. Manag. 7(7): 276–294.

Go to Reference

35.

Wang R. Jouini O. Benjaafar S. . 2014. Service systems with finite and heterogeneous customer arrivals. Manuf. Serv. Oper. Manag. 16(3): 329–480.

Go to Reference

36.

Williams R. J. 2000. On dynamic scheduling of a parallel server system with complete resource pooling. McDonald D. R. Turner S. R. E. , eds. Analysis of Communication Networks: Call Centers, Traffic and Performance. American Mathematical Society, Toronto, 49–71.

Go to Reference

37.

Zavadlav E. McClain J. O. Thomas L. J. . 1996. Self‐buffering, self‐balancing, self‐flushing production lines. Manage. Sci. 42(8): 1151–1164.

Go to Reference