Mathematical Programming 82 (1998) 255-271

Approximation algorithms for two-machine flow shop scheduling with batch setup times Bo Chen a, Chris N. Potts b,*, Vitaly A. Strusevich ° a Warwick Business School, University of Warwick, Coventry CV4 7AL, UK b Faculty of Mathematical Studies, University of Southampton, Southampton S0117 1BJ, UK c School of Computing and Mathematical Sciences', University of Greenwich, London SE 18 6PF, UK

Received 1 March 1995; accepted 17 July 1996

Abstract In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n log n) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. Keywords: Scheduling; Flow shop; Batch setup times; Approximation algorithm; Performance

analysis

1. Introduction This p a p e r addresses a t w o - m a c h i n e flow s h o p scheduling p r o b l e m with b a t c h setu p times. The t r a d i t i o n a l version o f this p r o b l e m w i t h o u t setups, which is one o f the m o s t w e l l - k n o w n in scheduling theory, can be stated as follows. W e are given two machines A a n d B, a n d a set N = { 1 , 2 , . . . ,n} o f jobs. E a c h j o b m u s t be first p r o cessed on m a c h i n e A a n d then on m a c h i n e B. N e i t h e r o f the m a c h i n e s can process

*Corresponding author. E-mail: [email protected]. S0025-5610/98/$19.00 © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V. PHS0025-56 10(97)00086-5

256

B. Chen et al. / Mathematical Programming 82 (1998) 255-271

more than one job at a time. The objective is to find a schedule that minimizes the makespan Cmax, which is the completion time of all jobs on both machines. Following a standard classification scheme [1], this problem is denoted by F211C~n,x. In some manufacturing environments, it is necessary to perform a setup on a machine before it can start to process a job. The setup cannot be performed while the machine is processing a job. Setup times can be of various types. However, in this paper, we assume that the setup times are sequence-independent, which means that the setup time is dependent only on the job to be processed next and is independent of the previous job, if any; and they are anticipatory, which allows the setup for any job on machine B to be performed concurrently with the setup and processing of this job and of other jobs on machine A. Note that the processing of any job on machine B cannot start until both the processing of this job on machine A and the setup of this job on machine B are completed. This problem is denoted by F21setup[Cm~,x if we again adopt the makespan objective. The model with batch setup times, which we are to investigate, is similar to the F21setuplCmax problem. Practical applications involving batch setup times are given by Monma and Ports [2] and by Potts and Van Wassenhove [3]. In the batch setup times model, the jobs are partitioned into several groups, called batches. No setup time is required between jobs of the same batch. However, a setup on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Note that, once a job is processed on a machine, there is no requirement that all jobs in the same batch should be scheduled next. Consequently, any batch can be split into several sub-batches, where the first job of each sub-batch requires a setup. The same splits are not necessarily adopted on both machines, so sub-batches must be specified for each machine. This model is denoted by F21batch setup[C. . . . Both the F211C .... and F21setuplC .... problems are solvable in O(n log n) time by algorithms which create a schedule with identical job processing orders on each machine [4,5]. However, the F21batch setupICm,x problem is NP-hard [6], although Potts and Van Wassenhove [3] point out that if the number of batches is fixed and processing orders on the two machines are constrained to be identical, then the problem is polynomially solvable by dynamic programming. Potts and Van Wassenhove also review other results in the general area of scheduling with batch setup times. In this paper, two O(n log n) time heuristic algorithms for the F21batch setuplC .... problem are described and their worst-case performance is analyzed. If, for any instance of the problem, the makespan of the schedule generated by some heuristic does not exceed p times the optimal makespan, where p is a constant that is as small as possible, then p is the worst-case performance ratio of the heuristic. We first propose a heuristic in which no batch is split so that all jobs of the same batch are processed consecutively. This approach follows the so-called group technology assumption, and the heuristic has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed for which a reduced worst-case performance ratio of 4/3 is obtained.

B. Chen et aL / Mathematical Programming 82 (1998) 255-271

257

This paper is organized as follows. After providing some preliminary results in Section 2, we present our two heuristic algorithms in Sections 3 and 4. The first heuristic in Section 3 does not allow any batch to be split. A modification to this heuristic, which allows limited splitting of batches, is presented and analyzed in Section 4. Some concluding remarks are given in Section 5.

2. Preliminaries

A formal description of our F2lbatch s e t u p l C m a x is as follows. There is a job set N, and each job j, for j E N, must be first processed on machine A and then on machine B; the processing times are ay and b j, respectively, where aj + bj > 0. Assume that N is partitioned into v batches N1,...,Nu, and IN~l-n~ for l~
~a~(j)+Zb~(j) j=l

I 1 <~u<~n .

(1)

j=u

If the maximum in (1) is attained for u = v, then job ~(v) is critical in ~ and in its associated permutation schedule. If a job is critical in some schedule, then any delay to the starting time of either of its operations causes the makespan to increase. A permutation ~z* which minimizes (1) over all permutations re of jobs is called optimal. For any set Q c N of jobs, we define

Qa = {j c Q t aj <~bj} ,

Qb = {j ~ Q [ aj > bj} ,

(2)

B. Chen et al. / Mathematical Programming 82 (1998) 255 271

258

:

ai,

b(ol : Z

]eQ

jcQ

F o r the F2llCmax problem, an optimal p e r m u t a t i o n can be found by the following algorithm.

Algorithm 1. Step 1. Partition N into the two subsets N ~ and N b according to (2). Step 2. F o r m a p e r m u t a t i o n ~z~ in which all jobs in N ~ precede each of those in N~': the jobs in N ~ are sequenced in non-decreasing order of a/, while the jobs in N b are sequenced in non-increasing order of bj. Stop. Algorithm 1, which is due to J o h n s o n [4], requires O(n log n) time. The permutation ~* found by the algorithm is called a Johnson permutation of the jobs in set N. In our analysis, we also use a p e r m u t a t i o n of jobs which is generated by the following algorithm.

Algorithm 2. Step 1. Partition N into the two subsets N a and N ~' according to (2). Step 2. Define l -- a~gmax{/~i I J c N ~'} if N ~' ¢ (3, and r = argmax{a i [ j ~ N ~} if N t' ¢i (3.

Sty7) 3. F o r m a p e r m u t a t i o n ~r ( l , N ( ' \ { 1 } , N ~ ' \ { r } , r ) , where the jobs in N ~' \ {/} and N t' \ {r} are ordered arbitrarily. ( I f N ~ = (~, then l and N" \ {/} are rem o v e d from the above definition of or; if N t' (3, then N t' \ {r} and r are removed.) Stop. Algorithm 2 can be viewed as a part of the G o n z a l e z - S a h n i algorithm for solving the two machine open shop p r o b l e m [7], and its running time is O(n). The permutation a generated by Algorithm 2 is called a Gonzalez Sahnipermutation. Although a is not an optimal permutation, it has the following property which is exploited in our heuristic algorithms. L e m m a 1. For the F2llCm~x problem, either job 1 or job r is critical in the permutation a that is generated by Algorithm 2. Proof. By definition, a(1) = l i f N a ¢ ~), and or(n) = r i f N b/~ (3. Suppose that some job a(u) is critical in a, so using (1) we have u

jl

n

ju

First, suppose that a(u) ~ N ~. Then, from the definition o f N ~, we have a~(j / ~
259

B. Chen et al. / Mathematical Programming 82 (1998) 2 5 5 ~ 7 1 n

COax ((7) ~ a~(1) -I- Z b~U)' j=l from which we use (1) to deduce that a(1) is a critical job. Alternatively, suppose that cr(u) E N b. The definition of Nb and the choice of job r provide the inequalities b~(j/ < a~(j) for u + 1 ~
which implies that a(n) is a critical job. Thus, we have shown that either job l or job r is critical in a.

[]

We now return to the F21batch setuplCmax problem. Consider a partial schedule formed by the jobs in a single batch N~, for 1 <~z ~
(4)

where, as in (1), ~-~a(~,~(l))+ ~--~b(~,=.(i))l 1 <~u<~n, (5) j=l j=u is the makespan of the permutation schedule for the jobs in N~ with batch setup times disregarded. It is clear that a Johnson permutation ~ for the jobs in set N~ is still optimal for scheduling the jobs in batch N~ in the presence of batch setup times. If C ~ x denotes the makespan of an optimal schedule, then we claim that C0max(7"C-c)= max

Cmax ~> max -c=l

s~+a(N),

"c=l

* t~+b(N), ma X {Cmax(~)} •

(6)

l~
To justify the claim that (6) is a valid lower bound, we note that the first two terms in the maximization are the total loads on machines A and B, while Cmax(rc~) is the makespan obtained by considering only the jobs in batch N~.

3. A non-split heuristic In this section, we analyze the worst-case performance of a special class of heuristic algorithms for the F2 Ibatch setup lC max problem, which generate schedules without splitting any batch. These algorithms are called non-split heuristics. We show that the makespan of a schedule found by any non-split heuristic can be at least 3/2 times the makespan of an optimal schedule in the worst case. On the other hand, we also present such a heuristic which runs in O(n log n) time and generates a schedule with makespan at most 3/2 times the optimal value.

260

B. Chen et al. / Mathematical Programming 82 (1998) 255-271

For a schedule S, its makespan is denoted by Cmax (S). If S is a permutation schedule corresponding to permutation ~, then we also use Cma~(re) to denote its makespan. Lemma 2. There exists an instance of the F21batch setuplCma~ problem, such that if S is a schedule generated by any non-split heuristic for the instance, then Cmax(S)/CLa x ~

3/2.

Proof. Consider the following instance of the problem. The job set N = {1,2,3} is partitioned into two batches: N1 = {1,2} and N2 = {3}. All batch setup times are zero. Also, processing times are ( a l , b l ) = (0,1), ( a z , b 2 ) = (l,0) and (a3,b3) = (1,1). Any non-split heuristic produces a schedule S that is no better than any of the schedules corresponding to the four permutations (1,2,3), (2, 1,3), (3, 1,2) and (3,2, l). Thus, we have Cmax(S ) ) 3 , whereas C,*,~ = Cnlax(TC*)=2, where

~*=(1,3,2).

[]

Lemma 2 implies that the worst-case performance ratio of any non-split heuristic cannot be better than 3/2. We now present a non-split heuristic with a worst-case performance ratio that achieves this lower bound. Our heuristic creates a schedule that is defined by a permutation of the jobs.

Algorithm 3. Step 1. Perform (a), (b) and (c) for z = 1 , . . . , v. (a) Run Algorithm 1 to find a Johnson permutation ~ of the jobs in set N~. (b) Evaluate Cmax(7C*). Define c~ : Cmax(lr~) - t~ - b(N~) a n d / ~ = Cn,ax (:Z~;)-- St -a(S~). (c) Associate with set N~ an artificial job z having processing times at = c~ and Step 2. For the F21lCmax problem with artificial jobs { 1 , . . . , v} defined in Step 1, run Algorithm 2 to find a Gonzalez-Sahni permutation a of these artificial jobs. If necessary, renumber the artificial jobs, and also the corresponding batches, so that

~ = (1,...,v). Step 3. Set ~z~ : (7c~,..., rc~), and output the heuristic permutation 7c1. Stop. Algorithm 3 is a non-split heuristic which runs in O(n log n) time. The algorithm creates the heuristic permutation lr~ of the original jobs in which the batches are ordered according to the sequence of artificial jobs in Step 2, and the jobs within each batch are sequenced according to a Johnson permutation. Consider the schedule corresponding to the Johnson permutation ~ for a single batch N~, with makespan Cmax (::~), where the setup and all processing operations on machine B are scheduled as late as possible, as depicted in Fig. 1. In this schedule, machine B is idle for the first e~ time units, machine A is idle for the last/3~ time units,

B. Chen et al. / Mathematical Programming 82 (1998) 255-271

261

A B ^

~

Fig. 1. Optimal permutation schedule for jobs in N~.

and both machines are simultaneously busy for 7¢ time units. To sequence the batches, an artificial job is created from the schedule for each batch N, by removing the " c o m m o n " segment of length 7¢: the remaining segments on machines A and B with lengths c¢¢and/3,, respectively, correspond to the two operations of the artificial job. We show later in the proof of Theorem 1 that a schedule for the original problem is easily created from a schedule of artificial jobs by reinserting the common segments that are removed during the creation of the artificial jobs. The artificial jobs, and hence the batches, are ordered according to a GonzalezSahni permutation. Although a Johnson permutation could be constructed instead, without detriment to the performance guarantee, a Gonzale~Sahni permutation is faster to compute and is simpler to analyze. In particular, either the first or the last artificial job is critical due to Lemma 1. If the first artificial job is critical, for example, then the makespan of the heuristic schedule corresponding to permutation n I exceeds the total time for all setup and processing operations on machine B by at most cq. The observations c~1 +/31 ~
*

(7)

Cmax ( g ) / C .... ~ 3/2,

and this bound is tight. Proof. We first analyze some features of the schedule created by Algorithm 3. For the artificial F2]]Cmax problem introduced in Step 2, the Gonzalez Sahni permutation a = ( 1 , 2 , . . . , v) determines a schedule S~ of the artificial jobs. F r o m Lemma 1, either artificial job 1 is critical in S~ and cq ~
if co = 1,

-c-1

~

c~ +/3v

(8)

if co = v.

=

We now evaluate Cma x (TO1) for the original F2]bateh setup]Cmax problem in terms of the makespan Cmax(S~) for the artificial F2]lCmax problem. In the optimal

262

B. Chen et al. / Mathematical Programming 82 (1998) 255-271

schedule for batch N, (see Fig. 1), let 7~ = Cmax(n~) - e~ - ~ be the total load on each machine in batch N~, for 1 ~
Cmax (7cl) =

~l+~t~+b(N) r=l

if~o = 1 (9) if

o = u.

I t i s c l e a r t h a t ~ + ~ < ~ C ~ . ~ ( n ~ ) f o r l < ~ < ~ v . Ifco 1, then cq ~
{

C m,~ (n,) * + ~ t~ +

Cmax (7t;1) --~

2 s ~ + a ( N ) + ½ C ..... (n:))

if co = 1, if o9 = v.

(10)

The desired bound (7) now follows from Eqs. (6) and (10). The tightness of the bound is implied by Lemma 2. [~

4. An improved heuristic The results of the previous section show that to design a heuristic with a better worst-case performance than 3/2, it is necessary to split some batches. In this section, we propose a heuristic which improves the schedule generated by Algorithm 3 by allowing limited splitting. It is useful to derive two preliminary results. The first relates to the processing order of jobs within a batch.

Lemma 3. There exists an optimal schedule in which all jobs in the same batch are processed in the same order on both machines.

B. Chen et al. / Mathematical Programming 82 (1998) 255-271

263

Proof. Suppose that, in an optimal schedule S*, the jobs in some batch N,, where 1 ~
(11)

where B0 (S) is the total time for all setup and processing operations on machine B in S. Alternatively, if (11) does not hold, then it is straightforward to deduce that C m a x (S) =

max{Au(S) + a, + b, + B,(S) ] 1 ~
(12)

where Au(S) and B,(S) are the total times for all setup and processing operations performed on machine A before job u is processed, and on B after u is processed, respectively, in S. If (12) holds and the maximum is attained for u = v, then job v is critical in S. For a given non-permutation schedule, some jobs are never critical, even if their processing times are changed arbitrarily. We define k to be a separating job in schedule S if there is no job j that is sequenced after k on machine A and before k on machine B. It is easily verified that a non-separating job cannot be critical. In any

264

B. Chen et al. / Mathematical Programming 82 (1998) 2 5 5 ~ 7 1

schedule, there is at least one separating job, since the last job processed on machine A is always separating. Moreover, all jobs are separating in a permutation schedule. We now concentrate on the design of a heuristic with a better worst-case performance than Algorithm 3. Inequality (10) shows that this heuristic performs badly when C , ~ ( ~ ) is large, where N~ is the first or last batch of a which is constructed in Step 2, and ~ is defined in Step 1. To derive an improved heuristic, we focus on whether the other batches should be scheduled before or after batch N~, or whether they should be split into two sub-batches with one sub-batch scheduled before No~ and one after. If a job of batch N~ is critical in a permutation schedule, and some other batch N~ is not split and is scheduled before the critical job, then batch N~ contributes s~ + a(N~) to the makespan; if batch N~ is not split and is scheduled after the critical job, then it contributes t~ + b(N~); and if batch N: is split into sub-batches N A and N~ that are scheduled before and after the critical job, then batch N, contributes s, + a(N A) and t~ + b(N~). In the latter case, we observe using (2) that the smallest contribution occurs when N A = N~' and N~ = N~. Thus, our decision about batch N~ depends on the value of R~, where R~ = min {s~ + a(N~), t~ + b(N~), s~ + t~ + a(N~) + b(N~)},

(13)

for l ~< ~ ~< v. Batch N: is a front batch if R~ = s~ + a(N~) since it is to be scheduled before N~o in our improved heuristic. Similarly, batch N~ is a rear batch if it is not a front batch and R~ = t~ + b(N~); each such batch is to be scheduled after N,,, Batches which are neither front nor rear batches are split batches. If N~ is a split batch, then sub-batches N~ and N~ are to be scheduled before and after N,,,, respectively. Our second preliminary result establishes a lower bound on the optimal makespan. It is expressed in terms of an arbitrary batch N,,, although it is used when N~,, is the first or last batch of the permutation ~r, which is constructed in Step 2 of Algorithm 3. Lemma 4. For any batch N~,

Cmax ~> C ..... ( ~ ) + ~-]R~,

(14)

where l d oa <~v and ~z~ is an optimal permutation for the jobs in batch N,~. Proof. Consider an optimal schedule S*. By L e m m a 3, we may assume that, in S*, all jobs in the same batch are processed in the same order on both machines. For schedule S*, let zco~ be the processing order for the jobs in batch N,,,. Since Cma× (~,~) ~> Cmax (7"g* ~ ) , it is sufficient to establish that

From (4), there are two alternative values for Cm,× (~,~). First, consider the case that Cm,x (~Z~) = t~ + b(N~). It is clear from (6) that

11. Chen et al. / Mathematical Programming 82 (1998) 255-271

265

v

C~nax >1 E t~ + b(N) = t~ Cmax(~o) + ZR-C, -c=l

"c/Lw

-c/Lo)

where the final inequality is deduced from (13). Thus, in this first case, we have established (15), which implies that (14) is satisfied. For the remainder of the proof, we consider the alternative case that 0 so~ + Cmax (~).

C .... (~,~)

(16)

Without loss of generality, we assume that the jobs are indexed so that ~e, = ((co, 1 ) , . . . , (co, no~)). Let (oo, w) be a critical job for the permutation ~z,owhen setup times are ignored. Thus, we use (5) to obtain C°ma~(~e)) =

a(oj) + Z j--1

b(o,,2-

(17)

j--w

From (12), we have for any job k that Cmax ~ Ak(S*) + ak + bk + Bk(S*).

(18)

In the following analysis, we choose k to be a separating job for schedule S*. Now, for any batch N~, where 1 ~<~ ~
R-c

{

& + a(N-c) t~ + b(N~) st + t-c + a(N A) + b(N~)

if N~ = 0, i f N A = (0,

(19)

otherwise,

where N A and N~ denote the sets of jobs in N-c which are processed in S* before job k on machine A, and after k on B, respectively. Consider any batch N~, where k ¢ N~. Since k is a separating job, each job of batch N~ is included either in N A or in N( (or both). Thus, N~ = N A t3 N~, which together with Eqs. (13) and (19) implies that R-c ~> R-c for k ¢ N-c.

(20)

Our use of (20) depends on how k is selected. First, suppose that (co, w) is a separating job in S*. Then, we choose k to be (co, w). In schedule S*, ~o~ defines the processing order of jobs in batch N,o. Also, for any batch N , where v ¢ ~o, at least one setup is required on machine A for the jobs of N A when N~A ¢ ~) and on machine B for the jobs ofN~e when N( ¢ (3. Thus, we obtain w 1

Ak(S*) >~&, + Za(°>,J) + j--I

Z

(& + a(Nff))'

(21)

.c/Lea' NzA#O

ne)

Bk(S*) >~ Z j=w+l

b(e,j) +

Z

(t-c + b(N~B)).

(22)

z#~o, N~#O

For z ¢ co, let x-c and y-c denote the contribution of batch N-c to the right-hand side of Eqs. ((20) and (21), respectively. If N~ = 0, i.e., if N-c -- N A, then x-c - & + a(N~) and y~ = 0. Similarly, if N A = 0, i.e., if N~ = N~, then x~ = 0 and y~ - t-c + b(N~).

B. Chen et al. / Mathematical Programming 82 (1998) 255~71

266

Moreover, if NA 7~ (3 and N~ 7/ (3, then x~ = s~ + a(N~) and y~ - t~ + b(N~). Therefore, combining Eqs. (21) and (22) and applying (19) yields w

1

n~

A~(S*) + Bk(S*) >~so~ + Za(~,.i) + Z .i-1

b(<,j) + Z R ~ .

] w+l

(23)

~¢~.

Furthermore, since job k is chosen to be (co, w), we combine Eqs. (16), (17) and (23) to obtain

Ak(S*) + Bk(S*) + ak + bk >~ Cmax( ~ , j ) + Z R ~ , "c~o)

which, together with Eqs. (18) and (20), proves (15), and hence (14). Alternatively, suppose that (co, w) is not a separating job in S*. Then there is some separating job that is processed after job (co,w) on machine A and before (co, w) on B. Let (co',w') be the last such separating job to be processed on machine B, and we choose job k to be (co',w'). Observe that oJ # co, i.e., k does not belong to batch N,~, since the jobs in N~ are processed in the same order on both machines. We now establish lower bounds, similar to those in Eqs. (21) and (22), on the total load on machine A before job k is processed and on the total load on machine B after job k is processed. For machine A, we use the observation that job (co, w) precedes job k, and consequently ~ D {(co, 1 ) , . . . , (co, w)}, to obtain w

Ak(S*) >~s~,~+ Z a((,)j) +

Z

(s: + a(N~A)).

(24)

For machine B, noting that job (co, w) is processed after job k, we deduce that N~ _D {(co, w ) , . . . , (co, n~o)} and that no

Z j

+

+

w

+

(25)

r ¢ , , ) , , . , , NrB¢0

where b,,, is the total time for all setup and processing operations of the jobs in set N~, on machine B, in S*. We claim that b~,, >~t~o,+ b(N~,) ifN~, ¢ 0. To justify our claim, we need to show that, ifN~, ¢ 0, then at least one setup time is used on machine B in S* for the jobs of N~,. We note that job (eJ,w') is the last job in batch N~, to be sequenced before (co, w) on machine B: otherwise, due to the identical ordering of jobs in the same batch on the two machines, there is another separating job that is scheduled after (co',w') but before (co,w) on machine B, which contradicts our choice of job (co', w'). Thus, if N~, ¢ 0, the first job of batch N,,,, to be scheduled after (co,w) on machine B starts a sub-batch and requires a setup. We have now established our claim. Hence, we may rewrite (25) as

Bk(S*) >~ ~-~b(~,~j)+ ~ j--w

(t~+b(N~)).

~:¢co, N~ TL~I

As in the derivation of (23), we combine Eqs. (24) and (26) to obtain

(26)

B. Chen et al. / Mathematical Programming 82 (1998) 255-271

w

267

t~a)

Ae(S*) + Bk(S*) >1soo + Z a(~oj) + Z b(~oj) + Z R~, j=l

j=w

%&o

from which, on substitution of Eqs. (16) and (17), we deduce that

Ak(S*) + Bk(S*) + a~ + bk

>~ C°max (reo)) @

~-~Rv @ ak + bk.

(27)

z¢:co

From (20), R~ ~> R, for z ¢ co' because k E No,,. Similarly, each job in batch Noy, with the exception of job k, is included either in N A, or in N~, (or both). Although job k does not contribute to Ro,, due to (19), it contributes to Roy, and that contribution does not exceed ak + bk. Therefore, we deduce that Ro~,+ a~ + bk >~Roj. Use of these observations in (27), together with (18), completes our proof of (15), and hence (14). [] Lemma 4 suggests a method for modifying permutation n l, which is generated by Algorithm 3, to produce a new candidate schedule. First, batch N~ is identified using (9). In this candidate schedule, neither batch No,, nor any front or rear batch, is split. Each front batch is scheduled before N~ and each rear batch is scheduled after N~; for a split batch N~, sub-batches N~ and N~° are formed, with N~" scheduled before N~ and N~ scheduled after N,,. The ordering of the batches and sub-batches scheduled before No, is arbitrary, as is the ordering of the batches and sub-batches scheduled after No,. Thus, we create a permutation schedule in which any batch is split at most once. A formal statement of our procedure is as follows.

Algorithm 4. Step 1. Run Algorithm 3 to renumber the batches and find a permutation =

(<,...,

Step 2. Set 1

v i f Cmax (rel) : o;1 + ~ tz Av b ( N ) , z=l

v

i f c ....

coz

"c=l

Step 3. Set re2 = ~Z~o ., Step 4. Perform (a) and (b) for ~ = 1 , . . . , v, with ~ ¢ co. (a) Evaluate R~ using (13), and hence determine whether N~ is a front, rear or split batch. (b) If N~ is a front batch, then set re2= (re~,~2); if N~ is a rear batch, then set re2 = (re2, 7"C*); if N, is a split batch, then set 7~2 = (7~za, TC2, 7cb), where n~ and reb~are the subsequences of rc~ corresponding to the sets N~ and N~, respectively. Step 5. Choose rd/ c {rex,re2} so that Cmax(nH) = min {Cmax (re'), Cmax(re2)}. Output the heuristic permutation ren. Stop.

268

B. Chen et al. / M a t h e m a t i c a l Programming 82 (1998) 255-271

The running time of Algorithm 4 is O(n log n) since its time complexity is dominated by Step 1. Our main result establishes the worst-case performance ratio of Algorithm 4. Theorem 2. For the permutation 7~Lr generated by Algorithm 4, :I

,

4

Cma x (/'c/ ) / C m a x ~-~ 5,

(28)

and this' bound is' tight. Proof. Let =1 and co be defined as in Algorithm 4. Observe that co is chosen as in the 4 * . proof of Theorem 1 to be consistent with (10). Assume that Cmax(g 1) > ~Cmax, otherwise, the validity of (28) is apparent. From Eqs. (10) and (6), we obtain Cmax(7cl) ~ C*lax 4 - -1C m a x ( ~7l;* o), 2

from which we deduce that 2 , Cmax (/re;) > 3Cmax .

It follows from Lemma 4 that Z

R~ < - 1C*max.

~c¢:co

3

(29)

Let =2 be the permutation found at the end of Step 4 of Algorithm 4. To show that (28) holds, we consider four cases separately. First, suppose that there is a critical job in ~2 which belongs to batch N,o. It follows from the construction of ~z2 by Algorithm 4 that batch N,, is not split and its jobs are ordered according to permutation rt2,. Any other batch N~, where r ¢ co, is sequenced in permutation =2 according to its type. If N, is a front batch, it is scheduled before batch No,. If N~ is a rear batch, it is scheduled after No. If N, is a split batch it is partitioned into two sub-batches N," and N~ which are sequenced before and after batch No,, respectively. Since batch No, contains the critical job, we deduce from Eqs. (12) and (13) that C .... (g2) = C .... ( rr* o ) ) 4- Z R ~ .

Hence, rc2 is an optimal permutation due to Lemma 4, and (28) trivially holds. Second, suppose that there is a critical job in ig2 which is sequenced before batch No,. Let v denote this critical job. We partition the set of batch indices { 1 , . . . , v}\{co} into three subsets: f~l contains indices of front batches, f~2 contains indices of rear batches, and f~3 contains indices of split batches. Using (12), we have Cmax (~2) = Av(=2) 4- a~ 4- by + B~(~z2).

(30)

By the construction of rt2 by Algorithm 4, no job in batch N¢, for z E f~2, and no job in sub-batch N~°, for z c ~3, is scheduled before batch No, and hence before job v. Therefore,

B. Chen et al. / Mathematical Programming82 (1998) 255-271

269

(31)

A~(~2) + av <~ Z ( s ~ + a(Nz)) + Z ( s ~ + a(N~)).

Since there are two setups for each batch N~, where z E ~"~3,and a single setup for all other batches, the total time for all setup and processing operations on machine B yields the inequality v

b~ +

B~(rc2) <~~

t~ +

b(N)+ Z

(32)

tz.

ZG~'3)

17=1

Substituting Eqs. (31) and (32) in (30), we obtain Cmax(Tr2)~ Z ( s . c zCQ1

4-a(N~)) @ Z ( s z @a(Na)) @ £ t z - ~ b(N) @ ~-~ tr "cE~3

z=l

zC~3

Rz' (33) zCeJ where the last inequality is obtained from Eqs. (6) and (13). Substituting (29) into (33) yields the desired inequality (28). Third, for the case that a critical job in ~z is sequenced after batch No, a symmetric argument applies, thereby establishing (28). Fourth, suppose that there is no critical job in rc2. Since there are two setups for each batch N,, where z E f~3, and a single setup for all other batches, using (11), we obtain Cmax 3r- Z

Cmax(7~2)~

£

t~-F b(N) -F Z

~=1

tz-< * x @ ~-~ Rz, -~Cma

zCf~3

(34)

zero

where the last inequality is obtained from Eqs. (6) and (13). The desired inequality (28) follows by substituting (29) into (34). Thus, (28) holds in all cases. To show that the bound (28) is tight, we consider an instance with five jobs and three batches. Setup times and processing times are given in Table 1, where 0 < c < 1. The three batches are defined by N~ = {1}, N2 {2, 3} and N3 = {4, 5}. The permutation schedule corresponding to n* = (2, 1,4, 5, 3) is an optimal solution =

Table 1 Worst-case instance for Theorem 2 N~

N1

N2

N3

st t~ j

0 0 1 1 l+e

0 0

1 0

2 0 1

3 1 0

4 0 l+e

5 2~ 0

270

B. Chen et al. / Mathematical Programming 82 (1998) 255 271

which has makespan Cmax = 3 + 2c. Algorithm 4 first constructs rc1 = (1,2, 3, 4, 5) for which Cmax(7~ 1) = 4 + 2e, and sets co = 1. The permutation ~2 = (4, 2, 1, 3, 5) is then generated, which gives C .... (~c2) = 4 + 2e. Hence, Cmax(~h') = 4 + 2c, where ~H = ~1 or ~H = re2. We deduce that C m a x (7"cH)/Cmax = 4/3 - 2e/(3(3 + 2e)) -+ 4/3 as e ---, 0. []

5. Concluding remarks This paper considers the problem of scheduling a two-machine flow shop with batch setup times. On each machine, a sequence independent setup time is required between jobs of different batches. We propose a non-split heuristic in which all jobs in the same batch are processed consecutively. This heuristic is shown to have a worst-case performance ratio of 3/2, and no other non-split heuristic has a better worst-case behavior. By allowing batches to be split into at most two sub-batches, we design a heuristic with an improved worst-case performance ratio of 4/3. Both of our heuristic algorithms generate permutation schedules in which the processing order of jobs is the same on each machine. Nevertheless, our worst-case analysis is valid irrespective of whether or not there exists an optimal solution that is a permutation schedule. This latter issue remains unresolved. The literature contains other results on the worst-case analysis of heuristics with sequence independent batch setup times. A common feature of these heuristics is that, in each case, batches are split into at most two sub-batches. Zdrzatka [8] proposes a heuristic for minimizing the maximum lateness on a single machine for nonpositive due dates, and shows that it has a worst-case performance ratio of 3/2. Monma and Potts [9] and Chen [10] consider the preemptive scheduling of jobs on identical parallel machines to minimize the makespan. Monma and Ports [9] propose a heuristic which, for an arbitrary number of machines, has a worst-case performance ratio of 2. For a special category of problems in which the total processing time of the jobs in each batch is restricted, Chen designs a heuristic with a worst-case performance ratio of 3/2 for an arbitrary number of machines. The worst-case performance ratio of our second heuristic for the two-machine flow shop compares favourably with these ratios for other problems.

Acknowledgements Discussions with C.L. Monma and L.N. Van Wassenhove during the initial stages of this work are gratefully acknowledged. Some useful suggestions by anonymous referees have helped to improve the presentation. This research was partly supported by the International Association for the Promotion of Cooperation with Scientists from the Independent States of the Former Soviet Union, INTAS-93-257.

B. Chert et al. / Mathematical Programming 82 (1998) 255-271

271

References [1] E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, Sequencing and scheduling: Algorithms and complexity, in: S.C. Graves, A.H.G. Rinnooy Kan, P. Zipkin, (Eds.), Handbooks in Operations Research and Management Science, vol. 4: Logistics of Production and Inventory, NorthHolland, Amsterdam, 1993, pp. 445 522. [2] C.L. Monma, C.N. Potts, On the complexity of scheduling with batch setup times, Operations Research 37 (1989) 798-804. [3] C.N. Potts, L.N. Van Wassenhove, Integrating scheduling with batching and lot-sizing: A review of algorithms and complexity, Journal of the Operational Research Society 43 (1992) 395-406. [4] S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1 (1954) 61-68. [5] T. Yoshida, K. Hitomi, Optimal two-stage production scheduling with setup times separated, AIIE Transactions 11 (1979) 261 263. [6] U. Kleinau, Two-machine shop scheduling problems with batch processing, Mathematical and Computer Modelling 17 (1993) 55-66. [7] T. Gonzalez, S. Sahni, Open shop scheduling to minimize finish time, Journal of the Association for Computing Machinery 23 (1976) 665-679. [8] S. Zdrzatka, Analysis of approximation algorithms for single-machine scheduling with delivery times and sequence independent batch setup times, European Journal of Operational Research 80 (1995) 371 380. [9] C.L. Monma, C.N. Potts, Analysis of heuristics for preemptive parallel machine scheduling with batch setup times, Operations Research 41 (1993) 981 993. [10] B. Chen, A better heuristic for preemptive parallel machine scheduling with batch setup times, SIAM Journal on Computing 22 (1993) 1303-1318.