A Branch And Bound Algorithm To Minimize The Total Weighted Flowtime For The Two-stage Assembly Scheduling Problem

Computers & Operations Research 30 (2003) 309 – 320

www.elsevier.com/locate/dsw

A branch and bound algorithm to minimize the total weighted #owtime for the two-stage assembly scheduling problem * Ali Tozkapana , Omer K,rcaa , Chia-Shin Chungb; ∗ a

b

Department of Industrial Engineering, Middle East Technical University, Ankara 06531, Turkey Department of Operations Management and Business Statistics, 1860 East 18th Street, Cleveland State University, Cleveland, OH 44114 3610, USA Received 1 May 2001; received in revised form 1 August 2001

Abstract In this paper, a two-stage assembly scheduling problem is considered with the objective of minimizing the total weighted #owtime. A lower bounding procedure and a dominance criterion are developed and incorporated into a branch and bound procedure. A heuristic procedure is also used to derive an initial upper bound. Computational results of the algorithm are presented. Scope and purpose statement The two-stage assembly scheduling problem is a generalization of the two-machine #owshop problem, which has received attention in the literature recently. In the 3rst stage, there are m−1 machines assigned to produce m − 1 di4erent types of component, which is required for each job. In the second stage, an assembly machine is used to assemble the components. Each machine can process only one job at any time. The objective is to minimize the sum of weighted completion times (total weighted #owtime) of all jobs. We develop a branch and bound algorithm to solve the problem. Lower bounds and a dominance criterion are incorporated in the algorithm to improve its e9ciency. We also conduct computational experiments, which show that the algorithm can solve moderate sized problems in reasonable amount of time. The algorithm could be used to provide a benchmark for the evaluation of heuristics for larger sized problems. This problem appears in many real world situations. Examples are plenty in papers published by prominent researchers. ? 2002 Elsevier Science Ltd. All rights reserved. Keywords: Scheduling; Two-stage assembly #owshop; Branch and bound algorithm; Total weighted #owtime

∗

Corresponding author. Tel.: +1-216-687-4770; fax: +1-216-687-9343. E-mail address: [email protected] (C.-S. Chung).

0305-0548/02/$ - see front matter ? 2002 Elsevier Science Ltd. All rights reserved. PII: S 0 3 0 5 - 0 5 4 8 ( 0 1 ) 0 0 0 9 8 - 3

310

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

1. Introduction The two-stage assembly scheduling problem is a generalization of the two-machine #owshop problem. There are n jobs, J1 ; J2 ; : : : ; Jn , to be processed. Each job requires m − 1 components to be processed in the 3rst stage. There are m − 1 3rst-stage machines assigned to produce a speci3c type of component. These machines are independent of each other. When all of the components are processed at the 3rst stage, a machine at the second stage, namely the assembly machine, assembles the components. Each machine can process only one job at any time. The objective is to minimize the sum of weighted completion times (total weighted #owtime) of all jobs. The problem can be seen commonly in industry. Potts et al. [1] describe an example in the production of personal computers. A customer typically requires a speci3c set of modules: a central processing unit, a hard disk drive, a monitor, a printer, an appropriate keyboard, a set of manuals in the right language, etc. The modules are produced on independent feeder lines. Orders are assembled to customer speci3cation at a packaging station. A large variety of end products can be o4ered to the customer by using di4erent combinations at the packaging station. Lee et al. [2] present another application of the two-stage assembly scheduling problem. In a 3re engine assembly plant, the body and chassis of 3re engine are produced (in parallel) in two di4erent departments, whereas the engine is purchased from outside. When the body and chassis are completed and the engine is received, they are fed to an assembly line where the 3re engine is assembled. Potts et al. [1] show that the two-stage assembly scheduling problem with the makespan objective is NP-hard in the strong sense even when number of the machines in the 3rst stage is equal to two. Hariri and Potts [3] develop a branch and bound algorithm for the same problem. A lower bound based on solving an arti3cial two-machine #owshop problem and several dominance theorems are incorporated into the algorithm. Koulamas and Kyparisis [4] generalize the problem to three-stage assembly scheduling problem. They propose several heuristics to solve the problems. The commonly used objectives for a scheduling problem are the minimization of the make-span, #owtime, tardiness, lateness, and the number of jobs late. Here, unlike the papers cited previously, the objective in this paper is to 3nd a schedule to minimize the sum of completion times for all jobs, that is the objective is to minimize the total #owtime. Flowtime measures the time a job stays in the system. Minimizing it amounts to improving customer service in terms of responsiveness (see [5]). In Section 2, we give a brief description of the problem and show that the problem to minimize the total weighted #owtime can be restricted to the class of permutation schedules. A machine based lower bound similar to the one in Chung and K,rca [6] is derived in Section 3. A dominance criterion is developed in Section 4. In Section 5, heuristics are developed to serve as the initial upper bound in the algorithm. An outline of the algorithm appears in Section 6. Results of computational experiments are presented in Section 7. Finally, we include a short conclusion section. 2. The problem description In the two-stage assembly scheduling problem we assume that there are m machines, m − 1 at the 3rst stage and an assembly machine at the second stage. All machines are open at time zero. There are n independent jobs, which are ready to be processed at time zero. Each machine can process

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

311

at most one job at a time. All processing times are positive. Job preemption is not allowed. (Once started, a job cannot be interrupted before completion.) This paper employs the following additional notation: m n M N pjk p[x]k S U G(S) Lk (S) Et Rtk wj w[x]

number of machines number of jobs set of all machines ={1; 2; : : : ; m} set of all jobs ={1; 2; : : : ; n} processing time of job j on machine k processing time of job in position x on machine k set of scheduled jobs (partial schedule) set of unscheduled jobs, which equals to N − S total #owtime of jobs in the partial schedule S completion time of the last job in S in stage k; k = 1; 2 earliest start time of the tth job on machine m (under estimate) earliest completion time of the tth job on machine k (under estimate) weight of job j weight of job in position x

It turns out that the search for an optimal solution may be restricted to the class of permutation schedules. Theorem 2.1. For the two-stage assembly problem with minimum total weighted 9owtime objective; there exists an optimal solution; which is a permutation schedule. Proof. Suppose that there exists an optimal schedule S in which the processing order for some 3rst-stage machine k = 1; : : : ; m − 1 di4ers from the order for the assembly machine m. Let Ci; k (S) be the completion time of job i on machine k and ri (S) be the starting time of job i on machine m. There exists a pair of jobs i and j; such that job i is sequenced immediately before job j on machine k; but job i follows job j on machine m; perhaps with some intervening operations. Cj; k (S) = (Ci; k (S) + pj; k ) 6 rj (S) 6 ri (S): Construct a new schedule S
by interchanging jobs i and j on machine k; k = 1; 2; : : : ; m − 1, in S. We have Cj; k (S
) 6 Cj; k (S) 6 rj (S)

and

Ci; k (S
) = Cj; k (S
) 6 rj (S) 6 ri (S):

Thus, the jobs in S
will start on machine m at least as early as the same jobs in S, hence the schedule S
must also be optimal. Repeating the same argument for any inconsistent job ordering between the two stages proves the theorem. Note that the above result is also true for the makespan objective.

312

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

3. Lower bounds Branch and bound algorithms are commonly applied to the #owshop problem, see, for example, Bansal [7], Chung and K,rca [6] and Hariri and Potts [3]. The e4ectiveness of a branch and bound algorithm is heavily in#uenced by its lower bounds. Such bounds are useful when they are tight and easy to compute. In this section, we develop a useful machine based lower bound. To derive our bound, we assume each machine has unit capacity except for the last assembly machine, which we assume has in3nite capacity. (A machine’s capacity equals the number of jobs that it can handle simultaneously.) Jobs need not wait at in3nite capacity machines. Hence, one can obtain a lower bound on the total #owtime by solving a single-machine scheduling problem. The computations are easy, since the weighted shortest processing time rule (WSPT) is optimal. For any job assigned to position t, we begin with estimating its earliest start time Et on machine m and the earliest completion time Rtk on machine k; k = 1; 2; : : : ; m − 1. The estimated times Et and Rtk provide the lower bound for values for the actual times of the unscheduled jobs. They are derived by applying the WSPT rule for the unscheduled jobs for each machine. For k = 1; 2; : : : ; m − 1 Rtk = Rt −1; k + p[t]k
Et = Max Rt −1; m ;

for t = s + 1; : : : ; n:  Max {Rtk } for t = s + 1; : : : ; n:

k=1;2;:::; m−1

(1)

After job rearrangements, p[j]k satis3es, p[s+1]m =w[s+1] 6 p[s+2]m =w[s+2] 6 · · · 6 p[n]m =w[n]

for j ∈ U:

Then the following mathematical program is used to 3nd a lower bound for the total #owtime of all unscheduled jobs: Min

n 

wj Cjt

(2)

j ∈U t=s+1

subject to Cjt ¿ (Et + pjm )xjt Cjt ¿



for j ∈ U; t = s + 1; : : : ; n;

Ci; t −1 + pjm xjt − M (1 − xjt )

for j ∈ U; t = s + 1; : : : ; n;

(3) (4)

i ∈U n 

xjt = 1

for j ∈ U;

(5)

t=s+1



xjt = 1

for t = s + 1; : : : ; n:

(6)

j ∈U

Here, the variable Cjt represents the completion time of job j on machine m if assigned to position t. In addition, xjt is equal to 1 if job j is assigned to position t, and 0 otherwise. Constraint (4) implies that if job j is not assigned to position t, then Cjt = 0.

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

313

By relaxing constraint (3), the problem becomes a single-machine weighted total #owtime problem for which the WSPT rule has been shown to be optimal. First type of lower bound is obtained from this rule for the total #owtime of all unscheduled jobs for #owshop problem with n jobs and m machines. It is computed as follows:   n   n n    LB1 = w[t] Es+1 + w[r] p[t]m ; (7) t=s+1

t=s+1

r=t

where p[s+1]m =w[s+1] 6 p[s+2]m =w[s+2] 6 · · · 6 p[n]m=w[n]. By relaxing constraint (4), there exists an optimal solution, such that Constraint (3) holds with equality. Substituting Cjt in the objective function with the right-hand side of Constraint (3), the problem becomes an assignment problem with the following objective: Min Since

n

n  j ∈U t=s+1

t=s+1

Min

wj (Et + pjm )xjt = Min

n  j ∈U t=s+1

wj Et xjt +

n 

wj pjm xjt :

(8)

j ∈U t=s+1

xjt = 1 for j ∈ U , Eq. (8) becomes

n 

wj Et xjt +

j ∈U t=s+1



wj pjm :

(9)

j ∈U

A second lower bound for the total #owtime of jobs can be obtained by using the largest weight rule (LWR). Theorem 3.1. The LWR rule minimizes the objective in (9). Proof. Consider any assignment that does not satisfy LWR rule. There exists a t ∈ {s + 1; : : : ; n − 1} such that w(t+1) ¿ w(t) ; where (t) and (t + 1); respectively; denote the jobs in positions t and t + 1. By interchanging jobs (t) and (t + 1); the objective is decreased by (w(t) Et + w(t+1) Et+1 ) − (w(t+1) Et + w(t) Et+1 ) = (w(t+1) − w(t) )(Et+1 − Et ); which is positive. The second lower bound can be computed as follows: LB2 =

n 

w[t] Et +

t=s+1



wj pjm ;

(10)

j ∈U

where w[s+1] ¿ w[s+2] ¿ · · · ¿ w[n] . By combining the two lower bounds developed above, we have the following overall lower bound: LB(S) = Max{LB1 ; LB2 } + G(S): 4. A dominance criterion In this section, we develop a dominance criterion, which will be shown to be e4ective in pruning nodes in the branch and bound algorithm.

314

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

Denition 4.1. Let 1 and 2 be two partial schedules for the same subset of jobs. We say 1 dominates 2 if G(1 ) 6 G(2 ); for every permutation  of the jobs in N − S. The following theorem describes dominance conditions between two schedules. Theorem 4.1 (Set Dominance). Let 1 and 2 be two partial schedules for the same set of jobs S. If i: ii:

G(2 ) ¿ G(1 );





G(2 ) − G(1 ) ¿

 wr

(L2 (1 ) − L2 (2 ));

(11)

r ∈N −S

then 1 dominates 2 . Proof. Let  = j1 j2 · · · jn−s denote any permutation of the jobs in N − S; and let i = j1 j2 · · · ji ; for 1 6 i 6 n − s. First; we prove that for i = 1; 2; : : : ; n − s; L2 (1 i ) − L2 (2 i ) 6 L2 (1 ) − L2 (2 ):

(12)

(Recall that L2 (1 i ) and L2 (2 i ); respectively; are the completion times of the last job in 1 i and 2 i in stage 2.) It is well known that L2 (1 i ) = max{L1 (1 i ) + pji m ; L2 (1 i−1 ) + pji m }; L2 (2 i ) = max{L1 (2 i ) + pji m ; L2 (2 i−1 ) + pji m }; where 0 denotes the null sequence. Since L1 (1 i ) = L1 (2 i ); these results imply that L2 (1 i ) − L2 (2 i ) 6 L2 (1 i−1 ) − L2 (2 i−1 ):

n−s wji L2 (j i ) for j = 1; 2. Use an induction argument to get (12). Finally; G(j ) = G(j ) + i=1 n−s Hence; G( ) − G( ) = G( ) − G( ) − w (L (  ) − L (  2 1 2 1 ji 2 1 i 2 2 i )) ¿ G(2 ) − G(1 ) − i=1  ( r ∈N −S wr )(Lk (1 ) − Lk (2 )); which is non-negative by (11); as required. Using Theorem 4.1 directly in the algorithm is impractical, since it will require excessive memory requirement. We present a special case of the dominance property below. Corollary 4.1 (Job Dominance). If i: ii:

G(ji ) ¿ G(ij ) G(ji ) − G(ij ) ¿





 wr

(L2 (ij ) − L2 (ji ))

(13)

r ∈N − S

then ij dominates ji . Corollary 4.1 will be incorporated in the branch and bound algorithm described in Section 6.

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

315

5. Upper bounds In this section, two di4erent heuristic procedures are presented to obtain initial upper bound. The 3rst heuristic procedure is based on the weighted shortest processing time rule (WSPT). The second heuristic procedure is derived from three indices, which are de3ned below. The two upper bounding procedures are run consecutively and the one that gives better solution is selected as the initial upper bound. 5.1. The >rst upper bounding procedure For each machine k =1; 2; : : : ; m, the WSPT rule is applied to obtain a job sequence. The weighted total #owtime is calculated for each sequence. The smallest #owtime will then be chosen as a candidate for the upper bound. 5.2. The second upper bounding procedure The second upper bounding procedure is derived from using three indices. Three schedules will be obtained by sequencing the jobs in non-decreasing order of each index. 1. The minimum processing time MPTIi = min{pik =wi } k

for i = 1; 2; : : : ; n:

2. The average processing time m

APTIi =

1 (pik =wi ) m

for i = 1; 2; : : : ; n:

k=1

3. The maximum processing time MPTIi = max {pik =wi } k

for i = 1; 2; : : : ; n:

The best solution from the above two procedures provides the upper bound for the algorithm. 6. A branch and bound algorithm The branch and bound algorithm is commonly applied to smaller or moderately sized scheduling problems. Our algorithm employs an adaptive depth->rst plus backtracking search strategy. The advantages of a depth-3rst strategy are: (1) the number of active nodes is always less than or equal to n, (2) the bottom of the tree is reached faster so good upper bounds can be found earlier, (3) a stack can be used to reduce computations. Consider the search tree for our algorithm. The root node ? represents the null schedule. Every other node represents a partial schedule  = ((1); : : : ; (s)), indicating that job (j) occupies the jth position on each machine, for 1 6 j 6 s, where 1 6 s 6 n. Any permutation P of the set of

316

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

unscheduled jobs de3nes a complete schedule P = ((1); : : : ; (s); (1); P : : : ; (n P − s)). By placing any unscheduled job i in position (s + 1), we produce a descendant node i = ((1); : : : ; (s); i). Our search strategy incorporates a dominance and a best bound rule. Given the current node r = (r (1); : : : ; r (r)), let  = (r (1); : : : ; r (r − 1)) and i = r (r). (Note that i ≡ r .) For each job j not in the set {r (1); : : : ; r (r)}, our algorithm dictates the following. If node ij has not been previously fathomed, use the dominance test of Theorem 4:2 to determine whether ij strictly dominates ij . If so, then fathom ij and assign to it the lower bound ∞; otherwise compute a lower bound for ij . Finally, branch on the job j with the smallest lower bound. Calculating all these lower bounds costs additional time. However, our computational experience suggests that the bene3ts outweigh the costs. The outline of the algorithm is as follows: Step 1. Initialization: 1.1 Let r = 0; Sr = ∅; Ur = N; LBr (j) = 0 for all j ∈ Ur . 1.2 Compute upper bound (Z ∗ ; S ∗ ) from the proposed heuristic procedure. Step 2. First Level Lower Bound Computation: Set r = 1, for all j ∈ Ur , compute LB1 (j) for the set {j}. Step 3. Branching: If r = 1, go to step 3.1 If |Ur | = 1 go to step 5 Otherwise Let k = minj∈U {j} r ← r + 1, Sr = Sr −1 + {k}, Ur = Ur −1 − {k}, LBr −1 (k) = ∞. 3.1 Let k = argminj∈Ur {LBr (j)} r ← r + 1, Sr = Sr −1 + {k}, Ur = Ur −1 − {k}, LBr −1 (k) = ∞. Step 4. Dominance criteria and lower bound computation: 4.1 Let Ji be the last element of set Sr . For all j ∈ Ur , apply the dominance criteria for the pair ( i; j). If sequence {j; i} dominates {i; j} set LBr (j) = ∞. 4.2 For Sr compute a lower bound LBr (j). If LBr (j) ¿ Z ∗ , go to Step 6. Otherwise go to step 3. Step 5. Update upper bound: 5.1 Set S = Sr + {Ur }. 5.2 Compute LBr (S). 5.3 If LBr (S) 6 Z ∗ , set S ∗ = S and Z ∗ = LBr (S). Step 6. Fathoming: 6.1 Set r ← r − 1. 6.2 If r ¿ 0, go to Step 3; otherwise stop with the optimal solutions S ∗ and Z ∗ .

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

317

Table 1 The ranges of the uniform distribution due to type of data Type of data A B C

Stage 1

Stage 2

a

b

a

b

1 1 20

100 80 100

1 20 1

100 100 80

7. Computational experiments This section reports on computational experiments that evaluate the e4ectiveness of the optimal branch and bound algorithm, assess the performance of the lower bound and the dominance test. Our results suggest that our algorithm can handle test problems with n 6 20 for both the unweighed and weighted objectives. It also seems capable of dealing with even larger problems for the unweighed objective. The problems were run on computers with 350 MHz PII processor and 64-MB memory. The program is coded in C and run on Turbo C 2.0 version. The performance measures are the percentage deviation of initial upper bound (UB%) from optimal percentage, the deviation of the lower bound at the 3rst level of the branch and bound tree (LB%) from optimal, the number of nodes visited, and the computation time. The processing times are generated from uniform distributions on [a; b]. There are three types of data generated, which uses di4erent values of a and b. The reason for having three types of data was to incorporate domination between the two stages in computation times. In type A data, there is no domination between the stages. In type B, stage 2 dominates; while in type C, stage 1 dominates. Table 1 shows the values of a and b used in our experiments. The weights are generated from a uniform distribution on [1; 10]. In addition, we applied our algorithm for unweighed case (all weights are equal to one). To study the weighted and unweighed objective, we use the following combinations of m and n values: (m; n) = (5; 10); (10; 10); (5; 15), and (10; 15). For each (m; n), we generate 10 problems. Table 2 reports on the mean, maximum, and minimum of the node count, computation time, UB (in percent) and LB (in percent) vary with n and m, while Table 3 does the same for test. As expected, the means of the node count and computation times tend to increase with n and m. Our branch and bound algorithm performs adequately for all test problems. It is evident from Tables 2 and 3 that the weighted problems are harder to solve in general for type A and type C problems, but are easier for type B problems. For example it took an average of 13:16 min to solve an unweighed type A problem with 15 jobs and 10 machines. The amount of time needed for an equivalent weighted problem was 24:80 min. To see why this is the case, we examine the e4ectiveness of the lower bounds. The lower bound percentages for the unweighed problems are signi3cantly smaller than those of the weighted problems for type A and type C problems and are similar in magnitude for type B problems. The lower bound e4ectiveness is clearly crucial to the performance of the algorithm.

318

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

Table 2 Summary of unweighed computational results Job, Machine UB%

LB%

Number of Nodes

Min Ave

Max

Min Ave

Type A 10; 5 10; 10 15; 5 15; 10 20; 5

0.47 5.76 4.50 7.02 4.23 9.25 3.64 5.94 5.17 10.76

10.07 13.26 14.76 9.32 20.01

2.45 6.46 11.16 4.73 10.53 13.53 1.41 8.75 17.12 4.42 10.01 14.93 5.99 11.18 17.94

Type B 10; 5 10; 10 15; 5 15; 10

1.06 2.46 3.12 3.83

6.06 11.69 1.09 6.26 8.95 0.20 7.01 9.34 0.89 8.88 16.44 1.48

6.01 16.38 3.39 8.26 6.79 13.70 6.08 12.47

79 67 491 380

668 523 35,545 38,222

2152 2522 89,709 162,886

0.00 0.00 0.11 0.66

0.09 0.23 7.83 62.21

0.27 1.10 20.44 281.92

Type C 10; 5 10; 10 15; 5 15; 10

1.68 2.09 2.64 4.77

3.11 3.34 4.47 5.69

5.50 8.02 6.30 8.72 5.73 11.68 7.80 11.35

59 915 1705 49,297

1687 2762 253,691 809,677

3801 4660 1,161,653 2,312,510

0.00 0.38 0.88 86.65

0.24 11.62 154.43 1457.95

0.55 33.41 683.30 4163.52

5.59 5.63 7.87 7.37

0.57 4.99 1.45 4.65

Max

Min

Ave

CPU time Max

Min

Ave

Max

166 874 3550 0.00 0.13 0.49 335 2910 7727 0.16 1.43 3.46 2400 78,800 211,479 1.04 32.14 80.71 18,470 446,152 1,467,729 32.64 789.87 2614.51 710,854 27,186,512 79,182,653 559.73 22682.36 73683.42

Table 3 Summary of weighted computational results Job, Machine UB%

LB%

Number of Nodes

Min Ave Max

Min

Ave

Max

Type A 10,5 10,10 15,5 15,10

0.00 0.00 2.51 1.01

3.15 6.45 2.81 7.53 4.22 7.03 4.76 10.65

7.70 6.62 12.95 5.79

20.67 18.30 25.91 20.99

34.58 26.96 35.02 31.04

188 411 53,909 10,692

1961 3005 444,272 778,997

6040 8451 2,358,605 3,107,525

Type B 10, 5 10, 10 15, 5 15, 10 20, 5 20, 10

0.55 1.15 2.88 2.76 2.08 4.01

3.17 10.81 3.88 8.57 5.91 9.53 5.84 10.53 5.74 9.55 6.37 11.60

0.00 0.00 0.00 0.00 0.40 0.45

7.01 16.02 4.72 10.14 5.48 14.38 3.82 9.83 3.97 9.10 5.60 8.79

10 10 15 15 39 480

284 216 2837 2298 33,441 153,735

975 707 15,442 8902 122,358 836,089

Type C 10, 5 10, 10 15, 5 15, 10

0.00 0.11 0.75 1.13

0.78 1.25 2.03 2.64

214 1290 26,375 203,001

1234 5166 308,618 1,030,425

2.19 2.69 3.54 5.36.

13.05 16.36 14.09 15.18

18.53 19.22 19.98 21.70

25.37 24.35 27.23 28.83

Min

Ave

CPU time Max

Min

Ave

Max

0.05 0.43 1.37 0.71 4.92 14.89 48.08 377.53 1988.35 20.66 1488.11 5942.42 0.00 0.00 0.00 0.00 0.05 1.70

0.06 0.16 0.15 0.49 0.95 5.16 2.36 9.23 39.55 146.04 362.60 1433.13

3524 0.05 0.27 0.77 14,675 1.15 8.72 25.88 1218,295 16.81 185.20 672.91 3,168,267 397.20 1975.18 5903.24

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

319

Table 4 The results of the dominance criterion Job, Machine

Number of nodes Without DC

CPU time With DC

Without DC

With DC

A Type 10; 5 10; 10 15; 5 15; 10

3633 5755 1,566,811 3,462,947

1961 3005 444,272 778,997

0.53 2.61 716.82 4475.23

0.43 4.92 377.53 1488.11

B Type 10; 5 10; 10 15; 5 15; 10

410 284 5748 4239

284 216 2837 2298

0.06 0.13 3.15 2.92

0.06 0.15 0.95 2.36

C Type 10; 5 10; 10 15; 5 15; 10

2527 15,545 2,183,749 4,913,253

1234 5166 308,618 1,030,425

0.37 7.01 1253.25 6423.16

0.27 8.72 185.20 1975.18

The performance of the algorithm is a4ected by the type of lower bound. For the unweighed case, LB2 is more e4ective. On the other hand, LB1 for which WSPT is used to compute is more e4ective for the weighted case. Moreover, for type B problems, because of larger processing times on the average at the second stage, LB1 becomes increasingly e4ective. Hence, the lower bound for type B problems are tighter for the weighted case seen in Table 3. It also can be seen in Tables 2 and 3 that the upper bounding procedure seems to be more e4ective for the weighted case. The average upper bound deviation ranged from 3.11% to 10.76% for unweighed case and from 0.78% to 6.37% for weighted case. However, its e4ect seems to be less signi3cant than that of the lower bound deviation. We have also tested the e4ectiveness of the dominance criterion. The results are shown in Table 4. We 3nd that the dominance criterion reduces the number of nodes visited by 56% and the CPU time by 23%. The results seemed to be more signi3cant for large sized problems, which is more realistic. There is conclusive evidence to show that the dominance criterion is e4ective. It needs to be pointed out that the CPU times for the (10,10) case is longer for the problems with dominance criterion than for the one without. This is due to extra computational e4ort in implementing the dominance criterion. This e4ect is especially signi3cant for smaller problems. In order to have some idea about the size of the problem the algorithm can handle, we have also tested two larger sized unweighed problems. The 3rst one is a type B problem with 25 jobs and 10 machines. It took an average of 22:99 min to solve. The second one is a Type A problem with 20 jobs and 5 machines. The amount of times needed was 6:3 h on the average. This indicates the e4ect of exponential growth in computation times is beginning to take place. Hence, to solve larger sized problems, we have to resort to heuristics.

320

A. Tozkapan et al. / Computers & Operations Research 30 (2003) 309 – 320

8. Conclusion In this paper, we study the two-stage assembly scheduling problem with the objective of minimizing the total weighted #owtime. The problem is NP-hard indicating that 3nding an optimal solution is di9cult. In this paper, we develop a branch and bound algorithm to solve the problem, which seemed to work well for reasonable sized problems. For larger sized problems, however, a heuristic is more practical. The algorithm developed in this paper can be used to provide a benchmark for the evaluation of heuristics. The problem can be found in many real world situations. There are plenty of examples in papers published by prominent researchers. We feel that the objective of minimizing the total #owtime in this paper is at least as important as the makespan. Some potential research topics are worth mentioning. Di4erent performance measures can also be considered as an objective, for instance, lateness and tardiness. Recent development in simulated annealing and genetic algorithm provides interesting approaches for 3nding good heuristic solutions. However, the amount of time needed tends to be too long to be practical. References [1] Potts CN, Sevast’janov SV, Strusevich VA, Van Wassenhove LN, Zwaneveld CM. The two-stage assembly scheduling problem: complexity and approximation. Operations Research 1995;43(2):346–55. [2] Lee C-Y, Cheng TCE, Lin BMT. Minimizing the makespan in the 3-machine assembly-type #owshop scheduling problem. Management Science 1993;39(5):616–25. [3] Hariri AMA, Potts CN. A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational Research 1997;103:547–56. [4] Koulamas C, Kyparisis GJ. The three stage assembly #owshop scheduling problem. Computers and Operations Research 2001;28:689–704. [5] Allahverdi A. Minimizing mean #owtime in a two machine #owshop with sequence independent setup times. Computers and Operations Research 2000;27:111–27. [6] Chung C, K,rca O. A branch and bound algorithm to minimize the total weighted #owtime for m-machine #owshop problems. Middle East Technical University Industrial Engineering Department Technical Report, 1996. [7] Bansal SP. Minimizing the sum of completion times of n jobs over m machines in a #owshop—a branch and bound approach. AIIE Transactions 1977;9:306–11. Ali Tozkoparan received BS from Gazi University and MS from Middle East Technical University, Ankara, Turkey in Industrial Engineering. He now works for a private company as Industrial Engineer. , Omer K/rca is a professor in the department of Industrial Engineering, Middle East Technical University. He received his Ph.D. degree from the Industrial and Systems Engineering Department, Georgia Institute of Technology. His main research interests are production planning and scheduling, mathematical modeling=programming applications, and vehicle routing and scheduling. Chia-Shin Chung is a professor in the department of Operations Management and Business Statistics. He received his Ph.D. degree from the department of Industrial Engineering and Operations Research, University of California, Berkeley. His main research interests are inventory management, scheduling, reliability and supply chain management.