A Branch And Bound Algorithm For The Two-stage Assembly Scheduling Problem

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH ELSEVIER

European Journal of Operational Research 103 (1997) 547-556

Theory and Methodology

A branch and bound algorithm for the two-stage assembly

scheduling problem A . M . A . H a r i r i a'*, C . N . P o t t s b a Department of Statistics, King Abdul-Aziz University, P.O. Box 9028, Jeddah 21413, Saudi Arabia b Faculty of Mathematical Studies, University of Southampton, Southampton SO17 1BJ, UK Received 1 September 1995; accepted 1 August 1996

Abstract

This paper develops a branch and bound algorithm for the two-stage assembly scheduling problem. In this problem, there are m machines at the first stage, each of which produces a component of a job. When all m components are available, a single assembly machine at the second stage completes the job. The objective is to schedule the jobs on the machines so that the maximum completion time, or makespan, is minimized. A lower bound based on solving an artificial two-machine flow shop problem is derived. Also, several dominance theorems are established and incorporated into the branch and bound algorithm. Computational experience with the algorithm is reported for problems with up to 8000 jobs and 10 first-stage machines. © 1997 Published by Elsevier Science B.V.

1. Introduction

The two-stage assembly scheduling problem may be described as follows. There are n jobs, J l . . . . . Jn, to be processed. Each job requires m components to be manufactured at the first stage, which are then assembled at the second stage, thus completing the job. There are m dedicated first-stage machines, M1 . . . . . Mm, each producing a specific type of component. When all of the components of a job have completed processing at the first stage, they become available for processing on a single assembly machine, MA, at the second stage. The processing time of job Jj ( j = 1 . . . . . n) on machine Mi ( i = 1 . . . . . m ) is P i j , and on machine MA is PA.j. Each machine can process at most one job at a time. The objective is to construct a schedule for

* Corresponding author.

which the maximum completion time, or makespan, is minimized. et al. [ 3] describe an application of the twostage assembly scheduling problem in a fire engine assembly plant, where there are two machines at the first stage. The body and chassis of fire engines are produced (in parallel) in two different departments, whereas the engine is purchased from outside. When the body and chassis are completed and the engine has been delivered, they are fed to an assembly line where the fire engine is assembled. Requests for deliveries of engines are planned so as not to cause any unnecessary delay at the assembly line. A second example, which arises in the manufacture of personal computers, is given by Potts et al. [4]. In this application, the components produced at the first stage include central processing units, hard disks, monitors, keyboards, etc. A packaging machine uses different types of each component to produce a variety of end products.

0377-2217/97/$17.00 (~) 1997 Published by Elsevier Science B.V. All rights reserved. PH S 0 3 7 7 - 2 2 1 7 ( 9 6 ) 0 0 3 1 2 - 8

548

A.M.A. Hariri, C.N. Potts /European Journal of Operational Research 103 (1997) 547-556

For the special case that m --- 1, the resulting problem is a standard two-machine flow shop which is solved in O(n log n) time using Johnson's algorithm [2]. Lee et al. [3] and Potts et al. [4] independently derive several results for the two-stage assembly scheduling problem with m = 2 and with arbitrary m, respectively. In particular, the problem is strongly NP-hard, and there exists an optimal permutation schedule in which the same processing order of jobs is used on all machines. Also, any arbitrary permutation schedule has makespan which does not exceed twice the optimal makespan. Moreover, by considering an artificial two-machine flow shop in which the pronl cessing times of job Jj ( j = 1 . . . . . n) are ~i=I pi,j/m and PA,j, respectively, the resulting permutation that is obtained from Johnson's algorithm yields a schedule with makespan which does not exceed 2 - 1/m times the optimal makespan. Potts et al. also uses geometric techniques to design heuristics with guarantees on the heuristic makespan minus the optimal makespan. In this paper, we develop a branch and bound algorithm for the two-stage assembly scheduling problem. Although a branch and bound algorithm of Lee et al. [3] is available, there is no report on computational experience with the algorithm. By performing extensive computational tests with our algorithm, we provide an insight into the difficulty of the problem, in practice. The remaining sections of this paper are organized as follows. In Section 2, we derive the lower bounds that are used in the branch and bound algorithm. Section 3 establishes various dominance rules that are effective in restricting the size of the branch and bound search tree. A comlblete description of the branch and bound algorithm is given in Section 4. Section 5 reports on computational experience with the algorithm. Finally, some concluding remarks are contained in Section 6.

2. L o w e r bounds

In this section, we derive the lower bounds that are used in our branch and bound algorithm. As indicated in Section 1, it is sufficient to restrict our attention to permutation schedules. Potts et al. [4] show that the makespan for the schedule defined by an arbitrary permutation o- = (tr( 1 ) . . . . . o-(n) ) is

Cmax(O') = max ~ max {Ciu(O-)}~, u=l ,...,nki=l ,...,m

'

(1)

J

where

Ci,u( Or) = £

pi,tr(h) -'[- ~-~pa,o~(h).

(2)

h=u

h=l

Let permutation ~* define an optimal schedule. From (1), we observe that Cmax(Tr*) ~> max {Ci,u(Tr*)} u=l,...,n

f o r / = 1. . . . . m.

(3) However, the right-hand side of (3) is the makespan for a two-machine flow shop in which the processing times of job Jj (j = 1 . . . . . n) are Pi.j and PA,j, respectively. Let 7r* denote an optimal permutation for this flow shop problem, where zrT is obtained in O (n log n) time using Johnson's algorithm [ 2 ]. Thus we obtain the lower bound LBi=

max {Ciu(71"T) u=l,..., n '

}

fori=l

, • •

.,m.

(4)

In the computation of LBi, the processing time on all first-stage machines, except for Mi, is relaxed. We now derive another lower bound which considers all of the processing times. By replacing the second maximization in ( 1 ) by an average, we obtain for permutation zr* that m Cmax(77"*)

/>

~ZCiu(~*)/m[. u=l ,...,n k " max

)

(5)

i=1

The right-hand side of (5) is the makespan for a two machine flow shop in which the processing times of m job Jj (j = 1 . . . . . n) are ~-~i=1Pi,j/m and PA,j, respectively. By applying Johnson's algorithm to this two-machine flow shop problem, we obtain an optimal permutation ~r~,+l in O(n log n) time, and hence compute the lower bound m

(ZCi LBm+I -- um.~..,n

* ,u(lrm+l)/m

).

(6)

i=1

Note that, by taking weighted averages to derive expressions similar to (5), a family of lower bounds can be derived. For use within our branch and bound algorithm, however, the lower bounds given in (4) and (6) are satisfactory.

A.M.A. Hariri, C.N. Ports~European Journal of Operational Research 103 (1997) 547-556 Also, we used the following lower bound proposed by Lee et al. [3]:

549

then there exists an optimal permutation schedule in which job Jj is sequenced before job Jk.

t/

LB0= m i n ( m a x {Pi,j}~ "r E P A , j " .]=l,...,llkl=l,...,m ) j=t

(7)

We can regard LB0 as a bound based on machine Mr which includes an idle time contribution that is incurred while the first job is processed at the first stage. From (4), (6) and (7) we obtain the overall lower bound LB = max{LB1 . . . . . LBm+l, LB0}.

B

-

, ....

~

j=l

mill {PA,j}"

j=l,...,n

Note that LBm+2 is a bound based on the most heavily loaded first-stage machine. From (4) and (2), we observe that max{LBl . . . . . LBm} ~> LBm+2.

11

Cmax(Tr) = Ci,u(7"r) = EPi,lr(h) q- EPA,lr(h), h=l h=u

(11)

for some i ( i = 1. . . . . m) and u (u = 1. . . . . n). Similarly, a lower bound on the makespan for 7r* is Cmax(7"g*) ~ Ci,u(77"*) 12

n

= EPiar*(h ) + EPA,Ir.(h). h--I h=u

(12)

We prove that rr is an optimal permutation by showing, that Cmax(~') ~< Cmax(r*). First, we observe from the construction of 7r, that {Tr*(1) . . . . . r * ( u ) } = {zr(1) . . . . . 7r(u)}, and conu u sequently ~h=l pi,~r*(h) = ~'-~h=lPi,~r(h), for u < f and for u >/ U. Moreover, for j' <~ u < U, we obtain { ~ * ( 1 ) . . . . . ~r*(u)} = ( { ~ ( 1 ) . . . . . ~ ( u ) } u { ~ } ) {j}. Therefore, E~=1 pi,~r*(h) = Eh=l Pi,~r(h) + Pi,k -u Pi,j ~ ~--~h=lPi,~r(h) for j ' ~< u < k', where the inequality is obtained from (9). Thus, in both cases,

3. Dominance rules In this section, we derive four dominance rules that are used to restrict the search in our branch and bound algorithm. The first of these gives sufficient conditions for job Jj to precede job Jk in an optimal permutation schedule. The other results establish which jobs are candidates for appending to the initial partial permutation schedule that is currently under consideration.

Theorem 1. For any two jobs Jj and Jk, where j k, if pi,j ~ Pi,k f o r i = 1. . . . . m,

u

(8)

Our branch and bound algorithm uses a forward sequencing branching rule in which nodes at level l of the search tree correspond to initial partial permutations in which jobs are sequenced in the first l positions. The lower bounds described above are easily adapted to account for the jobs in an initial partial permutation. To conclude this section, we compare our lower bounds to the other lower bound of Lee et al. [ 3 ], which is given by

LBm+2=i=l~..~...n{EPi,j}-~

Proof. Suppose that 7r* is an optimal permutation in which job Jk is sequenced before job Jj. Let zr be obtained from 7r* by interchanging jobs Jj and Jk. Also, we define positions f and U in zr so that ¢r(j I) = j and 7r(k') = k. We show that 7r is also an optimal permutation. From (1) and (2), we can express the makespan f o r ~ as

(9)

and

/4

U

EPi,rr*(h) >/ EPi,~r(h). h=l

(13)

h=l

Using similar arguments to above, {rr*(u) . . . . . ~r*(n)} = {Tr(u) . . . . . 7r(n)}, and consequently n n ~h=uPa,Tr*(h) = ~h.._upA,lr(h), for u ~< jr and for u > U. For jr < u ~< U, the observation that {~*(u) ..... ~*(~)} = ({~(u) ..... ~(~)}u {j}){k} yields Eh=uPA,~r*(h) n , = Eh=uPA,~'(h) "~- PA,y _

Pa,k ~ ~-~h=l pa,lr(h), where the inequality is obtained from (10). Therefore, in both cases, n

n

(14)

PA,j >/ PA,k,

(10)

h=u

h=u

A.M.A. Hariri, CN. Potts/European Journal of Operational Research 103 (1997) 547-556

550

Substituting (13) and (14) into the right-hand side of (12), we obtain the expression in (11), which establishes the desired result that Cmax(~') ~< Cmax('/7"*). [] For the following dominance theorems, we assume that machine Mi (i = 1. . . . . m) becomes available for processing at time T/ and that machine MA becomes available at time TA. These machine availabilities reflect the time that is incurred to process jobs of an initial partial permutation which is fixed in the branch and bound search tree. (To apply these theorems, we discard jobs of the initial partial permutation, reset n accordingly, and number the remaining jobs as 1. . . . . n.) Also, let L denote any valid lower bound on the minimum makespan for the node of the search tree under consideration. Since our dominance rules are applied before a lower bound is computed, we set L to be the lower bound at the parent node (which in our implementation is computed from ( 8 ) ) . When there are machine availability times, expression ( 1 ) for the makespan requires modification. Specifically, the makespan for the schedule defined by an arbitrary permutation o- becomes

Proof. Suppose that 7r* is an optimal permutation in which job Jj is sequenced in position f , where f > 1. Let ~r be obtained from ~* by removing jobs Jj from position f and inserting it in the first position. Thus, 7r = (j,~-*(1) . . . . . ~ * ( f - 1 ) , ~ r * ( f + 1) . . . . . ~r*(n)). We show that ~ is also an optimal permutation. From (15), the makespan for 7r is n

Cmax(qT")=max{Ti-~Ci,u(77"),ZA-k'ZPA,h } , h=l for some i (i = 1. . . . . m) and u (u = 1 . . . . . n). If n Cmax(qr) = TA "q- ~--]~h--IPa,h, then clearly 7r is an optimal permutation. Thus, in our subsequent analysis, we assume that

Cmax(Cr)=T/+ G,.(~r) u

tl

=Ti+ ZPi,~r(h) + EpA,Ir(h ) . h=l h=u

For the case that u = 1, we use (18) and then substitute (17) to obtain n

Cmax(o') = max" max ~

(18)

n

Cmax(~)=Ti+Pi,j+EPa,h < ~ m a X { T A + Z P a , h , L } , h=l h=l

max {Ti-~Ci,u(O')}~,)

I.u=l,...,n I.i=l,...,m n

r A "~- E p A , h }, h=l where

Ci,u(ly )

(15)

is defined in (2).

Cm~(~'*) for u > 1.

Theorem 2. Give~ machine availability times Ti and TA for machines Mi (i = 1. . . . . m) and MA, respectively, and a lower bound L, if there exists a job Jj such that Pi.j <<.PAd for i = 1 . . . . . m,

(16)

For 1 < u ~
Cmax(Tr* ) ~ T/-{- Ci,u_ 1(7T*) u--I

= Ti q- Epi,~r*(h) + PA,~r*(h). (19) h=1 h=u- 1 We observe from the construction of 7r, that {Tr*(1) . . . . . 7 r * ( u - 1)} = {Tr(1) . . . . . 7r(u) } - { j } , and { z r * ( u - 1) . . . . . ¢r*(n)} = {Tr(u) . . . . . 7r(n)} t5 {j}. Using these relationships in (19), we obtain

and

Ti + Pi,j <~ max (TA, L -- ~'~PA,h } h=l f o r i = 1. . . . . m,

which again shows that 7r is an optimal permutation. In the remainder of the proof, we show that ~ is an optimal permutation by establishing that Cmax(Tr) ~<

(17)

then there exists an optimal permutation schedule in which job Jj is sequenced first.

lg

R

Cmax('n'*) t> T/+ Z pi,~r(h)+E PA,~r(h)--Pi,j +PA,j. h=l h=u (20)

A.M.A. Hariri, C.N. Ports~EuropeanJournalof OperationalResearch 103 (1997)547-556 Substituting (16) into (20) and then using (18) yields the desired inequality Cmax(rr) ~< Cmax(~'*). For f < u ~< n, we use (15) and (2) to obtain the lower bound Crnax(Tr*) ~ T/--~

Cmax(Tr*)>/max{Ti +Ci, l(~*),TA+ ~'~PA,h} h=l n

= max{T/q-Pi,k,TA}

h=l

Substituting (23) into (25) yields

n

= T~ q- ~pi,cr*(h) -4- ZpA,~r*(h). h=l h=u

(21) Cmax(¢r*) ~>max{T/+ Pi,j "4-Pa,j, T~ + Pi,j + Pi,k,

Since the construction of 7r shows that {or*(1) . . . . . 7r*(u)} = {Tr(1) . . . . . or(u)}, and {~r*(u) . . . . . 7r*(n)} = {Tr(u) . . . . . 7r(n)}, we obtain from (21) and (18) that Cmax(~') ~< Cmax(Cr*) in this case also. [] Theorem 3. Given machine availability times T~ and TA for machines Mi (i = 1. . . . . m) and MA, respectively, if there exist two jobs Jj and Jk, where j ~ k, such that

Pi,j <~PA,j f o r i = 1 . . . . . m,

TA + PA,j} n

4- Z PA,Tr*(h) -- PA,j.

Using the relationship between 7r and ¢r*, we can write (26) as n

CmaxOr*)/> m a x { T / + P i , c t ( I ) q - Z p A , z r ( h ) , h=l

Ti -+- pi,Tr(l) "t- pi,~-(2)

(22)

pi,j + PA,.i, T~ q- Pi,j q- Pi,k, TA + Pa,j}

(26)

h=l

and max{T/+

-t- ~-'~pA,lr*(h). (25)

Ci,u(Tr*) U

551 n

n

n

h=2

h=l

which is equivalent to

--max{Ti+Pi,k,TA} <~PA,j f o r i = 1. . . . . m, Cmax(q'r*) ~ m a x { T / +

Ci, l(qT"),Ti + Ci,2 ('/7"),

(23)

TA + ~-'~Pt,h }.

then there exists an optimal permutation schedule in which job Jk is not sequenced first. Proof. Suppose that or* is an optimal permutation in which job Jk is sequenced first and job Jj is sequenced in position j', where j ' > 1. Let ¢r be obtained from 7r* by removing jobs Jj from position j ' and inserting it in the first position. Thus, ~- = (j, Tr*(1) . . . . . 7r* (j' - 1),7r*(j' + 1) . . . . . 7r*(n)), where 7r* ( l ) = k. We show that 7r is also an optimal permutation. Using (15), the makespan for ~r is n

Cmax(qT')

=max{Ti+Ci,u(qr),ZA ~- Z P A , h } , (24) h=l

for some i (i = 1. . . . . m) and u (u = 1 . . . . . n). For u = 1 or u = 2, we use (15) and (2) to obtain the lower bound

(27)

h=l

We deduce from (27) and (24) that Cmax(~r) <~ Cmax(Cr*) f o r u = 1 o r u = 2 . If Cmax(Tr) = TA + ~-~=1Pa,h in (24), then clearly ¢r is an optimal permutation. Thus, in our subsequent analysis for u > 2, we assume that Cmax ("/7") =

Zi -}- flu (~)

= Ti "~ ~'~Pi,~r(h) q- ~-~pa,cr(h). h=l h=u

(28)

Note that (28) is identical to (18) of Theorem 2. Also, condition (22) is identical to (16), and the construction of 7r from or* is the same as in Theorem 2. Thus, for the cases 2 < u ~< f and f < u ~< n, the analysis of Theorem 2 can be applied to show that Cmax(Cr) ~< Cmax(¢r*) f o r 2 < u < ~ n . []

552

A.M.A. Hariri, C.N. Potts /European Journal of Operational Research 103 (1997) 547-556

Lastly, we establish a result that is often called a dynamic programming dominance theorem.

Theorem 4. I f o" and ~rI are initial partial permutations containing the same jobs, and

Cmax(O') ~ Cmax(O't),

(29)

then there exists an optimal permutation schedule which does not start with tr I.

For nodes that remain after the dominance theorems are applied, the lower bound LB is computed using (8). Moreover, the permutations that correspond to LBI . . . . . LBm+I are each evaluated to give corresponding upper bounds UB1 . . . . . UBm+l, from which we select min{UBl . . . . . UBm+l } as an upper bound. Potts et al. [4] show that UBm+I, and hence this upper bound, does not exceed 2 - 1/m times the optimal makespan.

Proof. Suppose that ,r* is an optimal permutation which starts with o J. Let zr* = o"o-', where 0"1I is a final partial permutation of jobs. Consider the permutation 7r which is of the form ~ = 0"0-II. Each job of tr/I is processed at the same time on machine Mi (i = 1. . . . . m) in both permutations. Moreover, (29) shows that each job of tr" is processed on machine MA no later in 7r than in 7r*. Therefore, 7r is also an optimal permutation, and it does not start with 0-I. [] Dynamic programming dominance is useful for a variety of scheduling problems in which a solution is defined by a permutation of jobs [ 1,5,6]. Theorem 4 is usually implemented as follows. For an initial partial permutation ort that is generated in the branch and bound search tree, form the initial partial permutation o- by interchanging the last two jobs of 0-I. If (29) holds as a strict inequality, then o-' is dominated and the corresponding node of the search tree is discarded. However, if (29) holds with equality, then some convention is used to decide which ofo" or o"~is discarded and which is retained.

4. The branch and bound algorithm In this section, we give a description of our branch and bound algorithm. As indicated in Section 2, a forward sequencing branching rule is used in which nodes at level l of the search tree fix the job that is sequenced in position l of the permutation. For each node of the search tree, the dominance rules of Section 3 are applied in the order Theorem 2, Theorem 1, and then Theorem 3. Also, Theorem 4 is applied (except at the first level of the search tree), where 0 -I is the initial partial permutation for the search tree node under consideration, and o- is obtained from o" by interchanging the final two jobs.

5. Computational experience In this section, we report on the results of computational tests to assess the effectiveness of our branch and bound algorithm. It was coded in Fortran and run on a PC with a Pentium processor and 166MHz clock speed. For any problem instance, computation is abandoned if a time limit of 100 seconds is exceeded. Test problems with between 20 and 8000jobs, and with 3, 5 and 10 first-stage machines were generated as follows. For each combination of n and m, there are 40 problems with uncorrelated processing times and 40 problems with correlated processing times. For the uncorrelated problems, the processing times Pi,j (i = 1. . . . . m) and PA,j for each job Jj are random integers from the uniform distribution [ 1,100]. For correlated problems, a value pj from the uniform distribution [ 1,100] was generated for each job Jj, and processing times Pi,j ( i = 1 . . . . . m) and PA,j are random integers from the uniform distribution [pj + 1, pj + 20]. Table 1 gives computational results for the uncorrelated test problems. For each combination of n and m, average computation times in seconds (ACT), average numbers of nodes that remain after the dominance rules are applied (ANR), average numbers of times that elimination of one (or several in the case of Theorem 2) node is achieved using one of the dominance rules (ANE), numbers of problems solved at the root node of the search tree with the lower bound equal to the upper bound (NSR), numbers of unsolved problems (NU), and for the successful application of the dominance rules the percentage of times that nodes are eliminated by Theorems 1, 2, 3 and 4 (PE1, PE2, PE3, PE4, respectively); in each case, the relevant values are computed from 40 test problems. When there are unsolved problems, the values listed under ACT, ANR and ANE are lower bounds on the true averages

A.M.A. Hariri, C.N. Ports~European Journal of Operational Research 103 (1997) 547-556

since the values at the time of abandonment are used in computing the averages. Analogous results for the correlated test problems are given in Table 2. We observe from Table 1 that the branch and bound algorithm is capable of solving fairly large instances using modest computational resources, provided that there is no correlation between processing times. For most of our test problems, computation times are very small. Also, many problems are either solved at the root node of the search tree (on average, the lower and upper bounds are equal for more than 35 of the 40 test problems), or only a few search tree nodes are generated. It is only for the largest instances (with 7000 or 8000 jobs and 10 machines) that problems cannot be solved with our 100-second time limit. The success of the branch and bound algorithm is largely attributed to strength of the lower bounds and to the dominance rules. The large number of successful applications of the dominance rules demonstrates their major contribution towards pruning the search trees. The results in Table 2 show the more challenging nature of the correlated problems. For both the smaller instances (with up to 250 jobs) and the larger instances (with 5000 or more jobs), there are 19 unsolved problems, although all problems with between 500 and 4000 jobs are solved within the 100-second time limit. The difficulty in solving the larger instances is understandable. However, the reason for the 13 unsolved problems with 50 jobs and 10 first-stage machines is puzzling, in view of the apparent straightforward nature of the 500- and 1000-job problems. We now attempt a partial explanation as to why correlated problems are harder to solve. It is beneficial to generate queues of component types that have been processed by the first-stage machines and are waiting for assembly. Such queues help to avoid idle time on the assembly machine, and are created by scheduling jobs with small first-stage processing times and a large processing time on the assembly machine. However, for correlated problems, jobs with these characteristics are unlikely to exist. Consequently, idle time may occur on the assembly machine because queues of components are not created, and our lower bounds are unable to account for all of this idle time. For both the uncorrelated and correlated problems, large numbers of nodes are eliminated using our dominance rules. From the last four columns of Tables 1 and 2, we observe that Theorems 1 and 4 are the most

553

effective. Since the number of conditions that must be satisfied before Theorems 1, 2 and 3 can be applied is dependent on m, it is not surprising that these three resuits become less effective as m increases. Since Theorem 4 only requires a single condition to be satisfied, its usefulness is maintained as m increases. We now comment on the performance of our proposed branch and bound algorithm relative to that of Lee et al. [3]. For this comparison, we change our lower bounding scheme and dominance rules so that the resulting algorithm closely resembles that of Lee et al. More precisely, the maximum of the lower bounds LB0 and LBm+2 of Section 2 which are based on machine loads replaces LB, and the first three dominance rules are removed so that only the dynamic programming dominance rule remains. Average computation times and numbers of unsolved problems for the instances with 20, 100, 1000 and 5000 jobs are shown in Table 3: a similar pattern of results is observed for the other test problems. From Table 3, the superiority of the proposed algorithms over that of is Lee et al. [3] is immediately apparent. For the uncorrelated problems, the proposed algorithm solves all instances within the 100-second time limit, whereas 12 remain unsolved for the algorithm of Lee et al. More striking is the contrast in the numbers of unsolved correlated problems; 5 for the proposed algorithm and 168 for the algorithm of Lee et al. The poor relative performance of the algorithm of Lee et al. is explained by the inability of the lower bound to eliminate nodes that would be removed by Theorems 1, 2 and 3 if they were applied. For this algorithm, most problems are either solved at the root node of the search tree, or cannot be solved within the time limit.

6. Concluding remarks This paper develops a branch and bound algorithm for the problem of scheduling a two-stage assembly problem to minimize the makespan. This problem is a generalization of the classical two-machine flow shop. Therefore, it is not surprising that the algorithm of Johnson is useful in developing lower and upper bounding schemes. Also, the structure of the problem allows various dominance rules to be developed. A report on extensive computational tests shows that opti-

A.M.A. Hariri, C.N. Ports~European Journal of Operational Research 103 (1997) 547-556

554

Table 1 Computational results for uncorrelated problems n 20

50

100

250

500

1000

2000

3000

4000

5000

6000

7000

8000

m

ACT

ANR

ANE

3 5

0.00 0.01

4 6

7 4

l0 3 5 l0 3 5 l0 3 5 l0 3 5 10 3 5 l0 3 5 l0 3 5 l0 3 5 10 3 5 10 3 5 10 3 5 l0 3 5 10

0.00 0.01 0.01 0.01 0.01 0.01 0.03 0.02 0.03 0.09 0.05 0.07 0.19 0.07 0.19 0.58 0.18 0.49 2.02 0.34 0.99 1.83 0.33 1.40 0.93 0.72 1.07 0.83 0.39 1.60 1.00 0.63 2.46 13.12 0.80 3.52 4.25

4 3 4 7 2 5 18 4 15 29 6 13 40 3 24 84 5 36 160 l0 58 74 l 64 4 4 31 0 3 40

NSR

NU

PEI

PE2

PE3

PE4

31 27

34 28

14 12

l0 13

42 47

l 7 5 4 l0 l0 17 9 34 33 67 46 48 30 221 86 116 242 150 377 455 92 17 669 2 206 344 0 215 630

30 35 36 32 36 36 34 35 35 35 33 37 35 37 37 36 36 36 35 34 32 38 38 33 39 35 38 40 37 37

2 54 40 18 90 47 6 96 63 6 95 78 16 100 69 29 100 81 43 93 86 32 100 89 100 100 86 100 85

0 15 10 3 0 5 6 0 2 5 5 0 3 0 2 6 0 7 7 5 6 0 0 3 0 0 6 0 4

6 8 10 17 5 II 24 4 17 32 0 12 25 0 20 14 0 0 0 0 0 66 0 4 0 0 0

0

0

40

-

3 57 298 7 66 53

182 744 189 477 1617 30

38 36 35 35 35 39

100 91 100 100 86 100

0 4 0 0 4 0

0 0 0 0 6 0

92 23 40 62 5 37 64 0 18 57 0 10 56 0 9 51 0 12 50 2 8 2 0 4 0 0 8 0 6 0 5 0 0 4 0

4

1

ACT: average computation time in seconds on a PC with a Pentium processor. ANR: average number of nodes remaining in the search tree after the dominance roles are applied. ANE: average number of times that a dominance role eliminates one or more nodes. NSR: number of problems solved at the root node (out of a total of 40). NU: number of unsolved problems (out of a total of 4 0 ) . PEk: for eliminated nodes, the percentage removed using Theorem k, for k = l, 2, 3, 4.

0 5

A.M.A. Hariri, C.N. Potts /European Journal of Operational Research 103 (1997) 547-556

555

Table 2 Computational resultsfor correlated problems

n 20

50

100

250

500

1000

2000

3000

4000

5000

6000

7000

8000

m

ACT

ANR

ANE

NSR

NU

PEI

PE2

PE3

PFA

3

0.95

4496

5833

11

-

16

I

0

83

5

4.30

18542

23135

6

1

14

1

1

84

10

13.45

39132

1

4

2

8

0

0

92

3

0.34

1064

3186

21

-

33

1

3

63

5

3.08

9380

20728

20

1

9

0

1

90

10

35.57

80688

4

16

13

5

0

0

95

3

2.52

2325

75974

25

1

28

0

0

72

5

0.03

28

121

30

-

41

3

1

55

10

0.04

27

17

34

-

34

2

5

59

3

2.56

939

53054

33

1

35

0

0

65

5

0.05

37

97

32

-

66

2

2

30

l0

0.13

50

33

33

-

40

3

2

55

3

0.10

38

235

27

-

75

11

0

14

5

0.10

29

92

32

-

73

6

1

20

10 3

0.17 0.14

33 29

48 166

34 34

-

53 98

2 0

1 0

44 2

5

0.17

21

67

37

-

80

7

0

13

10

0.28

19

86

37

-

58

9

0

33

3

0.39

45

489

33

-

0

4

5

0.22

0

0

40

.

10

2.74

219

150

26

-

79

4

0

17

3

0.29

8

67

38

-

100

0

0

0

5

0.69

43

166

36

-

100

0

0

0

10

9.54

440

92

25

-

67

6

1

26

3

0.69

37

551

35

-

98

0

0

2

5

1.56

76

524

35

-

84

7

0

9

10

10.60

353

2

30

-

71

5

1

23

3 5

0,93 0,85

36 29

746 154

35 36

-

88 100

9 0

0 0

3 0

10

19.26

545

0

26

1

75

5

1

19

3

1.38

72

1217

29

-

99

0

0

1

5

1.51

59

322

35

-

100

0

0

0

10

30.12

758

0

23

5

82

2

1

15

3

1.59

61

1091

31

-

100

0

0

0

5

1.50

32

188

36

-

100

0

0

0

10

20.26

426

189

27

5

99

0

0

1

3

1.36

36

683

35

-

I00

0

0

0

93 .

3 .

.

5

3.59

76

867

36

-

83

9

0

8

10

28.93

551

30

25

8

98

0

0

2

ACT: average computation time in seconds on a PC with a Pentium processor. ANR: average number of nodes remaining in the search tree after the dominance rules are applied. ANE: average number of times that a dominance rule eliminates one or more nodes. NSR: number of problems solved at the root node (oat of a total of 40). NU: number of unsolved problems (out of a total of 40). PEk: for eliminated nodes, the percentage removed using Theorem k, for k = 1,2, 3, 4.

A.M.A. Hariri, C.N. Ports/European Journal of Operational Research 103 (1997) 547-556

556

Table 3 Comparison of proposed algorithm and that of Lee et al. [ 3 ] Uncorrelated problems Proposed n 20

100

1000

5000

Correlated problems Lee et al.

Proposed

Lee et al.

m

ACT

NU

ACT

NU

ACT

NU

ACT

NU

3 5

0.00 0.01

-

2.51 10.01

1 4

0.95 4.30

1

97.55 97.51

10

0.00

-

2.52

1

13.45

2

100.00

39 39 40

3

0.01

-

5.02

2

2.52

1

5 10 3 5 10 3 5 10

0.01 0.03 0.07 0.19 0.58 0.72 1.07 0.83

-

2.51 5.05 0.13 2.85 1.00 2.72 5.00 0.97

1 2 1 -

0.03 0.04 0.14 0.17 0.28 0.93 0.85 19.26

1

32.52 25.02 22.52 0.37 7.83 8.29 6.14 6.34 30.27

10 9 3 3 1 11

13

ACT: average computation time in seconds on a PC with a Pentium processor. NU: number of unsolved problems (out of a total of 40). mal s o l u t i o n s o f large i n s t a n c e s c o n t a i n i n g up to 8000 j o b s can be o b t a i n e d w i t h the p r o p o s e d b r a n c h and b o u n d a l g o r i t h m . T h e r e s u l t s also d e m o n s t r a t e the sup e r i o r i t y o f t h e p r o p o s e d a l g o r i t h m o v e r a b r a n c h and b o u n d a l g o r i t h m o f L e e et al. [ 3 ]. S c h e d u l i n g p r o b l e m s w h i c h r e q u i r e an a s s e m b l y o p e r a t i o n in the last s t a g e o f t h e p r o d u c t i o n p r o c e s s have b o t h t h e o r e t i c a l i n t e r e s t a n d practical i m p o r t a n c e . A w o r t h w h i l e t o p i c f o r f u t u r e r e s e a r c h is to d e s i g n alg o r i t h m s f o r p r o b l e m s w i t h o t h e r o b j e c t i v e s , and to c o n s i d e r m o d e l s w i t h m o r e stages.

References

[1] Hariri, A.M.A., and Ports, C.N. (1983), An algorithm for single machine sequencing with release dates to minimize total weighted completion time, Discrete Applied Mathematics 5, 99-109.

[2] Johnson, S.M. (1954), Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1, 61-68. [3] Lee, C.-Y., Cheng, T.C.E., and Lin, B.M.T. (1993), Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, ManagementScience 39, 616625. [4] Potts, C.N., Sevast'janov, S.V., Strusevich, V.A., Van Wassenhove, L.N., and Zwaneveld, C.M. (1995), The two-stage assembly scheduling problem: complexity and approximation, Operations Research 43, 346-355. [5] Potts, C.N., and Van Wassenhove, L.N. (1983), An algorithm for single machine sequencing with deadlines to minimize total weighted completion time, European Journal of Operational Research 12, 379-387. [6] Potts, C.N., and Van Wassenhove, L.N. (1985), A branch and bound algorithm for the total weighted tardiness problem, Operations Research 33, 363-377.