A Branch And Bound Algorithm To Minimize The Total Flow Time For M-machine Permutation Flowshop Problems

Int. J. Production Economics 79 (2002) 185–196

A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems Chia-Shin Chunga, James Flynna,*, Omer Kircab a

Department of Operations Management and Business Statistics, Cleveland State University, Cleveland, OH 44115, USA b Department of Industrial Engineering, Middle East Technical University, Ankara 06531, Turkey Received 12 January 2001; accepted 12 March 2002

Abstract The m-machine permutation flowshop problem with the total flow-time objective is a common scheduling problem, which is known to be NP-hard for mX2: In this article, we develop a branch and bound algorithm to solve both the weighted and unweighted version of this problem. Our algorithm incorporates a new machine-based lower bound and a dominance test for pruning nodes. Computational experiments suggest that the algorithm can handle test problems with np15: It also seems capable of dealing with larger problems for the unweighted objective, especially when the processing times are correlated. r 2002 Elsevier Science B.V. All rights reserved. Keywords: Scheduling theory; Permutation flowshop; Flow time; Machine-based lower bounds; Branch and bound

1. Introduction In the permutation flowshop problem, each of n jobs has to be processed on machines 1; y; m in that order. The processing times of each job on each machine are known. At any time, each machine can process at most one job and each job can be processed on at most one machine. Once the processing of a job on a machine has started, it must be completed without interruption. Furthermore, each job must be processed in the same order at every machine. The usual objectives are the minimization of the make-span, flow time, tardiness, lateness, and the number of jobs late. For a review of the general flowshop problem, see *Corresponding author. Tel.: +216-621-6349. E-mail address: j.fl[email protected] (J. Flynn).

[1,2], and more recently [3]. In this article, the objective is to minimize the total flow time. Flow time measures the time a job stays in the system. Minimizing it amounts to maximizing the utilization of resources. Schedules where each job must be processed in the same order at every machine are called permutation schedules. When mp2; the restriction to permutation schedules is harmless; however, when m > 3; there may exist a schedule whose total flow is strictly less than the total flow of any permutation schedule (see [1, Chapter 6]). Finding such a schedule is often computationally impractical; so, most approaches to the m-machine flowshop problem restrict attention to permutation schedules. The single-machine case has been studied extensively and it is well known that the SPT rule

0925-5273/02/$ - see front matter r 2002 Elsevier Science B.V. All rights reserved. PII: S 0 9 2 5 - 5 2 7 3 ( 0 2 ) 0 0 2 3 4 - 7

186

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

minimizes the total flow time and the WSPT rule minimizes the weighted total flow time. Most of the research in this area deals with special variations of the basic problem. For example, Sidney [4] and Potts [5] developed branch and bound algorithms to solve a problem with precedence constraints. Bansal [6] and Potts and van Wassenhove [7] considered weighted flow-time problems with constraints that require jobs to meet their deadlines. Mason and Anderson [8] included job classes and setup times in their model. There is also considerable interest in problems which allow unequal release time for all jobs (see [9–11]). Ignall and Schrage [12] developed a branch and bound algorithm for the two-machine case, which was extended to the m-machine case by Bansal [13]. Ahmadi and Bagchi [14] derived a new machine-based lower bound for the m-machine case and conducted computational experiments where their bound was strictly better than Bansal’s in 75–95% of the time. These experiments did not show that the new bound improved the branch and bound algorithm’s performance. Note that all these papers assume unweighted flow time. Recently, other lower bounds have been developed for the two-machine case. Van de Velde [15] proposed a bound based on the Lagrangean relaxation method. Hoogeveen and van de Velde [16] improved this bound by introducing slack variables. Della Croce et al. [17] conducted experiments that compare five lower bounding methods with one of their own. They concluded that, by combining van de Verde’s lower bound with theirs, one can solve problems with up to 30 jobs effectively. There are only a few known solvable cases for the m-machine total flow-time problem. Most of the research attempts to find conditions under which well-known rules such as SPT and WSPT are optimal. Panwalkar and Khan [18] show that for the m-machine case, the optimality of the SPT rule can be extended to an ordered flowshop where the order of the processing times on different machines is the same for each job. Szwarc [19] develops sufficient conditions for policies to be optimal. (His conditions are automatically satisfied by ordered flowshops.) Aderi and Amit [20]

show that the SPT rule is optimal for problems that satisfy a machine dominance condition. Note that almost all solvable cases are for the unweighted objective. The general m-machine flow-time problem with the total flow-time objective is known to be NP-hard for mX2 [21]. (For a thorough coverage of the complexity issues of machine scheduling problems, see [22,23].) Because of the difficulty of finding optimal solutions to large-size problems, there is considerable interest in developing efficient heuristics. For recent developments, see [24,25]. Here, we first develop a branch and bound algorithm to solve the unweighted m-machine permutation flowshop problem. (The basic structure of the algorithm is similar to the one developed by Potts [26] for the make-span objective.) Then we extend our algorithm to the weighted case. The possibility of assigning weights to jobs makes the model more practical. Jobs can be assigned weights based on their cost and priorities. For example, more expensive jobs should be given larger weights, since the longer they stay in the system, the higher is the cost. In Section 2, we briefly describe the problem and derive a new machine-based lower bound for the unweighted case, which dominates Bansal’s lower bound. Our bound employs estimates of the earliest start time for jobs assigned to each position in the job sequence. Section 3 presents a dominance test, which helps to prune nodes. Section 4 extends the lower bound and the dominance test to weighted problems. An outline of the algorithm appears in Section 5. Section 6 reports on computational experiments, which evaluate our algorithm and compare our lower bound with the one using the lower bound of Ahmadi and Bagchi [14]. Finally, Section 7 states our conclusions.

2. The problem description and a lower bound Branch and bound algorithms are commonly applied to the permutation flowshop problem, which is known to be NP-hard for mX2: The

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

effectiveness of a branch and bound algorithm is heavily influenced by its lower bounds. Such bounds are more useful when they are tighter and easier to compute. In this section, we develop a useful machine-based lower bound. To derive our bound, we assume that one machine has unit capacity and the others have infinite capacity. (A machine’s capacity equals the number of jobs that it can handle simultaneously.) Jobs need not wait at infinite-capacity machines. Hence, one can obtain a lower bound on the total flow time by solving a single-machine scheduling problem. The computations are easy, since the SPT rule is optimal. Consider the search tree for our algorithm (see [27]). The root node + represents the null schedule. Every other node represents a partial schedule s ¼ ðsð1Þ; y; sðsÞÞ; indicating that job sðjÞ occupies the jth position on each machine, for 1pjps; where 1pspn: Any permutation s% of the set of unscheduled jobs defines a complete schedule ss% ¼ ðsð1Þ; y; sðsÞ; sð1Þ; y; sðn % %  sÞÞ: By placing any unscheduled job i in position (s þ 1), we produce a descendant node si ¼ ðsð1Þ; y; sðsÞ; iÞ: This paper employs the following additional notation:

187

have infinite capacity. Our lower bound is based on estimates of the earliest possible start time for any job in U assigned to position t; where s þ 1ptpn: The idea behind these estimates is that a job can be processed at a machine only when both the job and the machine are ready. For 1prpk  1; let q½sþ1;r;k1 denote the smallest qj; r; k1 for jAU: Also, let p½sþ1k ; p½sþ2k ; y; p½nk denote a permutation of the processing times of the jobs in U on machine k; which satisfies p½sþ1k pp½sþ2k p ?pp½nk : The procedure for finding our lower bound is described as follows. Step 1: Set Esþ1;1 ¼ L1 ðsÞ and Rs;1 ¼ L1 ðsÞ; t X p½r1 ; Rt1 ¼ Rt1;1 þ p½t1  Rs;1 þ r¼sþ1

t ¼ s þ 1; y; n; Et1 ¼ Rt1;1 ;

t ¼ s þ 2; y; n:

Step 2: For k ¼ 2; y; m; Esþ1;k ¼ maxfLk ðsÞ; max1prpk1 fEsþ1;r þ q½sþ1;r;k1 gg; ð1Þ Rsk ¼ Esþ1;k ;

N ¼ 1; y; n pjk

The set of all jobs Processing time of job j on machine k Weight of job j Total flow time for jobs in the partial schedule s Total weighted flow time for jobs in the partial schedule s The number of jobs in the partial schedule s The set of jobs that are not included in the partial schedule s Completion time of the last job in s on machine k

wj GðsÞ GW ðsÞ s U Lk ðsÞ ( Pv qjuv ¼

r¼u

0;

pjr ;

for 1pjpn and 1pupvpm; otherwise:

Next, consider our lower bound on the total flow time at node s: Temporarily assume that machine k has unit capacity and the others

Rtk ¼ Rt1;k þ p½tk  Rs;k þ

ð2Þ t X

p½rk ;

r¼sþ1

t ¼ s þ 1; y; n; Etk ¼ maxfRt1;k ; Rt;k1 g;

ð3Þ t ¼ s þ 2; y; n:

ð4Þ

For tXs þ 1; Etk is an underestimate of the earliest start time of the tth job on machine k and Rtk is an underestimate of the earliest completion time of the tth job on machine k: Recursive equation (1) estimates the earliest time to start the first unscheduled job, which is the earliest time that both machine k and the ðs þ 1Þth job are ready. Note that we do not specify what the ðs þ 1Þth job is. Eqs. (2) and (3) estimate the earliest completion times of all unscheduled jobs at machine k: Eq. (4) provides a lower bound for the start time of any job assigned to the tth position on machine k:

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

188

A lower bound LB on the total flow time at node s is computed as follows: LBk ¼

n X

Etk þ

t¼sþ1

X

ð5aÞ

qjkm ;

jAU

LB ¼ GðsÞ þ max1pkpm LBk ;

k ¼ 2; y; m: ð5bÞ

Remark 2.1. One can reduce the computational effort by performing certain preliminary calculations before starting the branch and bound algorithm. For k ¼ 1; 2; y; m; let að1; kÞ; að2; kÞ; y; aðn; kÞ denote a permutation of the integers 1; 2; y; n such that pað1;kÞ;k ppað2;kÞ;k p?ppaðn;kÞ;k : Similarly, for 1pupvpm; let bð1; u; vÞ; bð2; u; vÞ; y; bðn; u; vÞ; denote a permutation of 1; 2; y; n such that qbð1;u;vÞ;uv pqbð2;u;vÞ;uv p?pqbðn;u;vÞ;uv : The aðj; kÞ’s and bðj; u; vÞ’s can be calculated at the beginning and saved for future access, thus saving unnecessary sorting. Given these objects, the calculations of p½sþ1k through p½nk for fixed k and the calculations of q½sþ1;r;k1 for fixed r and k require OðnÞ calculations. Hence, one can evaluate LB for a given node s using Oðm2 nÞ calculations. (Doing m iterations of (1) requires Oðm2 nÞ calculations. The remaining work requires OðmnÞ calculations.) Bansal [13] developed a lower bound for the mmachine problem with unweighted total flow-time objective. There are three basic steps in developing his machine-based bound. First, he uses the following formula to estimate the earliest start time at machine k for every unscheduled job: ESTðs; kÞ ¼ maxfLk ðsÞ; max1prpk1 fLr ðsÞ þ q½sþ1;r;k1g g:

ð6Þ

Second, he assumes infinite capacities at every machine except at machine k: Third, he applies the SPT rule to schedule jobs at machine k: Using this procedure, he develops the lower bound LS below, LSk ¼

n X t¼sþ1

ðESTðs; kÞ þ

t X r¼sþ1

p½rk Þ þ

X

qj;kþ1;m ;

jAU

ð7aÞ

LS ¼ GðsÞ þ max1pkpm LSk :

ð7bÞ

The main difference between LSk and LBk is that the estimated start time for all unscheduled jobs is the same in LSk ; while the estimated start time of a job depends on the position of the job in LB k : One can easily show that Etk > ESTðs; kÞ þ Pt1 r¼sþ1 p½rk for all k: Furthermore, qj;kþ1;m P  pjk þ qj;kþ1;m P and (5a) imply that LBk ¼ nt¼sþ1 ðEtk þ p½tk Þ þ jAU qj;kþ1;m : These results imply that LBk XLSk for all k; which implies the following theorem. Theorem 2.1. LB dominates LS; the lower bound of Bansal. Our computational experiments in Section 6 find that dominance is often strict. Ahmadi and Bagchi [14] developed a lower bound, which also dominates Bansal’s bound. (There is no dominance relationship between Ahmadi and Bagchi’s (A&B’s) bound and our bound.) The calculations for A&B’s bound entail minimizing the total flow time for each of m single-machine problems with preemption and release times. For such problems, the shortest remaining processing time rule (SRPT) is optimal and requires Oðn logðnÞÞ computation time [1], which implies that the time requirement for A&B’s bound is Oðmn logðnÞÞ [14]. Since our bound has time requirement Oðm2 nÞ and since n is much larger than m in most practical situations, this suggests that our bound is typically easier to compute. In the computational experiments of Section 6, our bound tends to prune more nodes and require less time. Note that a major advantage of our bound over A&B’s bound is that only our bound naturally extends to a useful bound for weighted problems. (A&B’s bound does not extend, since the SRPT rule is not optimal for the weighted flow-time problem.)

3. Dominance criteria Here, we define a dominance relation between partial schedules, which can help us to prune nodes.

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

Definition 3.1. Let s1 and s2 be two partial schedules for the same set of jobs S: We say that s1 dominates s2 ; if Gðs1 sÞpGðs2 sÞ for every permutation s of the jobs in N  S: If the previous inequality is strict, we say that s1 strictly dominates s2 : The following theorem develops conditions for one partial schedule to dominate another. Theorem 3.1 (Node dominance). Let s1 and s2 be two partial schedules for the same set of jobs S, and let s ¼ jSj: If Gðs2 Þ  Gðs2 Þ Xðn  sÞmax1pkpm fLk ðs1 Þ  Lk ðs2 Þg

ð8Þ

then s1 dominates s2 : Moreover, dominance is strict if inequality (8) is strict. Proof. Let p ¼ j1 j2 ?jns denote any permutation of the jobs in N  S; and let pi ¼ j1 j2 ?ji ; for 1pipn  s: First, we prove that for i ¼ 1; 2; y; n  s;

189

Use Lu ðs1 pi Þ  Lu ðs2 pi Þpmax1pkpm fLk ðs1 pi1 Þ  Lk ðs2 pi1 Þg and an inductionPargument to get (9). Finally, Gðsj pÞ ¼ Gðsj Þ þ ns for j ¼ 1; 2: i¼1 Lm ðsj pi Þ; Hence, Gðs2 pÞ  Gðs1 pÞ P ¼ Gðs2 ÞGðs1 Þ  ns i¼1 ðLm ðs1 pi Þ  Lm ðs2 pi ÞÞ XGðs2 Þ  Gðs1 Þðn  sÞmax1pkpm fLk ðs1 Þ Lk ðs2 Þg; which is non-negative by (8), as required.

&

Due to excessive memory requirements, it is impractical to apply the above theorem directly. The following corollary applies to the special case of consecutive jobs. Corollary 3.1 (Job dominance). Let s be a partial schedule for the set of jobs S; let s ¼ jSj; and let i and j be distinct jobs in N  S. If GðsijÞ  GðsjiÞ

Lu ðs1 pi Þ  Lu ðs2 pi Þpmax1pkpm fLk ðs1 Þ  Lk ðs2 Þg

Xðn  s  2Þ max1pkpm fLk ðsjiÞ  Lk ðsijÞg; ð10Þ

ð9Þ

then sji dominates sij: Moreover, dominance is strict if inequality (10) is strict.

for all 1pupm:

(Recall that Lu ðs1 pi Þ and Lu ðs2 pi Þ; respectively, are the completion times of the last job in s1 pi and s2 pi at machine u:) It is well known that for 1pupm; Lu ðs1 pi Þ ¼ max1pvpu fLv ðs1 pi1 Þ þ qji vu g  Lv1 ðs1 pi1 Þ þ qji v1 u ; Lu ðs2 pi Þ ¼ max1pvpu fLv ðs2 pi1 Þ þ qji vu g  Lv2 ðs2 pi1 Þ þ qji v2u ; where p0 denotes the null sequence and lpv1 ; v2 pu: These results imply that Lu ðs1 pi Þ  Lu ðs2 pi Þ ¼ ðLv1 ðs1 pi1 Þ þ qji v1 u ÞÞ  ðLv2 ðs2 pi1 Þ þ qji v2 u ÞÞ

4. Extension to the weighted objective Our lower bound and elimination criteria can be extended to the weighted case, where each job is assigned a weight indicating its importance. The possibility of assigning weights to jobs makes the model more practical; however, it also makes it harder to find an optimal solution. A lower bound on the total flow time at node s for the weighted case can be obtained by solving the following assignment problem: n P P P Min wj Etk Xjt þ wj qjkm jAU t¼sþ1 jAU ð11Þ P s:t: xjt ¼ 1; for t ¼ s þ 1; y; n; jAU

pðLv1 ðs1 pi1 Þ þ qji v1 u ÞÞ  ðLv1 ðs2 pi1 Þ þ qji v1 u ÞÞ ¼ Lv1 ðs1 pi1 Þ  Lv1 ðs2 pi1 Þ pmax1pkpm fLk ðs1 pi1 Þ  Lk ðs2 pi1 Þg:

n X

xjt ¼ 1;

for jAU;

t¼sþ1

xjt A1 ¼ f0; 1g

for jAU and t ¼ s þ 1; y; n:

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

190

Here xjt equals 1 if job j is assigned to position t; and xjt ¼ 0 otherwise. The above objective function underestimates the total weighted flow time of all jobs in U: Therefore, GW ðsÞ plus the optimal objective function for the above assignment problem becomes a lower bound on the weighted total flow time at node s: Note that the second term in (11) is a constant, which can be ignored when solving the assignment problem. The following theorem shows that an optimal solution can be obtained by using the largest weight rule (LWR), which arranges the jobs in descending order of their weight. Theorem 4.1. The LWR rule minimizes the objective in (11). Proof. Consider any assignment that does not satisfy LWR rule. There exists a tAfs þ 1; y; n  1g such that wrðtþ1Þ > wrðtÞ ; where rðtÞ and rðt þ 1Þ; respectively, denote the jobs in positions t and t þ 1: By interchanging jobs rðtÞ and rðt þ 1Þ; the objective is decreased by ðwrðtÞ Etk þ wrðtþ1Þ Etþ1;k Þ  ðwrðtþ1Þ Etk þ wrðtÞ Etþ1;k Þ ¼ ðwrðtþ1Þ  wrðtÞ ÞðEtþ1;k  Et;k Þ; which is positive.

&

Next, let w½sþ1 ; w½sþ2 ; y; w½n denote a permutation of the weights of the jobs in U which satisfies w½sþ1 Xw½sþ2 X?Xw½n : Theorem 4.1 implies that WLB below is a lower bound on the weighted flow time at node s: n X X WLBk ¼ w½t Etk þ wj qjkm ; t¼sþ1

jAU

k ¼ 1; y; m;

ð12aÞ

WLB ¼ GW ðsÞ þ max1pkpm WLBk :

ð12bÞ

The dominance results described in Section 3 can be easily extended to the weighted case. Condition (10) of Corollary 3.1 becomes ! X GW ðsijÞ  GW ðsjiÞX wr rAUfi;jg

max1pkpm fLk ðsjiÞ  Lk ðsijÞg:

ð13Þ

The proof is similar to that for the unweighted case and will not be presented here. Note that if

wj ¼ 1 for 1pjpn; then WLBk ¼ LBk ; WLB ¼ LB; and (13) is equivalent to (10). 5. The algorithm Branch and bound is commonly applied to scheduling problems. The algorithm of this paper employs an adaptive depth-first plus backtracking search strategy, which differs from the breadth-first strategy of Bansal [13]. The advantages of a depthfirst strategy are: (1) the number of active nodes is always pn; (2) the bottom of the tree is reached faster so a feasible solution can be found earlier, (3) a stack can be used to reduce computations. Our search strategy incorporates a dominance and a best bound rule. Given the current node sr ¼ ðsr ð1Þ; y; sr ðrÞÞ; let Ur denote the set of all jobs not in the set fsr ð1Þ; y; sr ðrÞg; and for each jAUr ; let Zr ðjÞ denote the lower bound for node sr j: Also, let s ¼ ðsr ð1Þ; y; sr ðr  1ÞÞ and i ¼ sr ðrÞ: (Note that si  sr :) For each jAUr ; our algorithm dictates the following. If node sij has not been previously fathomed, use the dominance test of (10) or (13) to determine whether sji strictly dominates sij: If so, then fathom sij and assign to it the lower bound N; otherwise, compute a lower bound for sij: 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 benefits outweigh the costs. To obtain an initial incumbent node, we use a simple m-machine heuristic. For each u and v with 1pupvpm; consider a schedule which is generated as follows. Compute qjuv for j ¼ 1; 2; y; n and then schedule jobs in ascending order of qjuv ; breaking ties arbitrarily. For each of these mðm þ 1Þ=2 schedules, compute the objective function. Then select the minimum Z as the initial upper bound and a schedule s achieving the minimum as the initial incumbent. The rationale for this is that if one treats machine u through machine v as a single consolidated machine with unit capacity and assumes that the other machines have infinite capacity, then one has a single-machine problem where the SPT rule is optimal. In the computational experiments of Section 6, this heuristic produces tight upper bounds. Our algorithm is outlined below.

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

Step 1: Initialization. Set r :¼ 0; sr :¼ +; Ur :¼ N , and Zr ðjÞ :¼ 0 for all jAUr : Compute an upper bound Z from an initial feasible solution s : Go to Step 3. Step 2: Dominance test. Set Zr ðjÞ :¼ 0 for jAUr : Set s :¼ ðsr ð1Þ; y; sr ðr  1ÞÞ and i :¼ sr ðrÞ: For each jAUr ; apply the dominance test to i; j; and s: Whenever sji strictly dominates sij; set Zr ðjÞ :¼ N: Step 3: Lower bound computation. (a) For each jAUr such that Zr ðjÞoN; compute a lower bound Zr ðjÞ for sr j: (b) If minjAUr Zr ðjÞ X Z then go to Step 5 else continue to Step 4. Step 4: Branch/Update upper bound. (a) If rXn  1 then let j0 be the unique element in Ur ; s :¼ sr j0 ; Z :¼ Zr ðj0 Þ; and go to Step 5. (b) Set j0 :¼ argðminjAUr Zr ðjÞÞ; r :¼ r þ 1; sr :¼ sr1 j0 ; Ur :¼ Ur1  fj0 g; and Zr1 ðj0 Þ :¼ N: Go to Step 2. Step 5: Fathom. (a) r :¼ r  1; if ro0 then stop with the optimal solution s and Z : (b) If minjAUr Zr ðjÞXZ then repeat Step 5, else go to Step 4.

6. Computational experiments This section reports on computational experiments that evaluate the effectiveness of the optimal branch and bound algorithm, compare the performance of our lower bound with A&B’s, and assess the contribution of our dominance test. Our results suggest that our lower bound outperforms A&B’s and that our algorithm can handle test problems with np15 for both the unweighted and weighted objectives. It also seems capable of dealing with even larger problems for the unweighted objective, especially when the processing times are correlated. The algorithm was coded in C and run under Borland C++ version 5.0 on a 1700 MHz Pentium 4 processor under Windows 2000. Our implementation of the branch and bound algo-

191

rithm uses data structures to minimize redundant computations and employs integer variables where practical. All random numbers are generated by the ran1 procedure from [28, Chapter 7]. A simple heuristic described in Section 5 produces the initial incumbent node. Our branch and bound algorithm stops if the node count reaches the upper limit of 4 106 without finding an optimal node. To measure performance, we record the computation time and node count. To evaluate our heuristic for an initial incumbent, we compute UB1(final objective function)/(initial objective function). (Note that if our algorithm stops before finding an optimal node, the final objective function is suboptimal, so UB is artificially small.) Our problem generation procedure outlined below yields test problems encompassing a wide variety of situations. For all problems, the processing times are generated using a scheme like that of Lageweg et al. [27]. Specifically, for i ¼ 1; y; n and k ¼ 1; y; m; pik follows a discrete uniform distribution on ½aik ; bik ; where aik and bik are dependent on a trend and a correlation factor. A positive trend in the processing time for job i indicates that pik increases as k increases, while a negative trend indicates that pik decreases as k increases. Similarly, a correlation between the processing times of job i exists if pi1 ; pi2 ; y; pin are consistently relatively large or relatively small. For problems with correlation, additional integers ri ; i ¼ 1; y; n; are randomly drawn from {0, 1, 2, 3, 4}. Depending on the existence of a trend and/or a correlation, we consider the six ptypes summarized below. (I) Neither correlation nor trend: aik ¼ 1 and bik ¼ 100: (II) Correlation only: aik ¼ 20ri and bik ¼ 20ri þ 20: (III) Positive trend only: aik ¼ 1212ðk  1Þ þ 1; and bik ¼ 1212ðk  1Þ þ 100: (IV) Correlation and positive trend: aik ¼ 212ðk  1Þ þ20ri þ 1; and bik ¼ 212ðk  1Þ þ 20ri þ 20: (V) Negative trend only: aik ¼ 1212ðm  kÞ þ 1; and bik ¼ 1212ðm  kÞ þ 100: (VI) Correlation and negative trend: aik ¼ 212 ðm  kÞþ 20ri þ 1; and bik ¼ 212ðm  kÞ þ 20ri þ 20:

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

192

Table 1 Unweighted case: mean and standard deviation of node count, computation time, and % UB as a function of p-type when n ¼ 15 and m¼4 p-type

Node count

Neither correlation nor trend Correlation only Positive trend only Correlation and positive trend Negative trend only Correlation and negative trend Average

Time (s)

% UB

Mean

s.d.

Mean

s.d.

Mean

s.d.

30671.7 334.3 2947.7 804.9 10,253.8 153.8

43,687.9 305.8 4656.3 1091.2 35,010.6 181.7

1.020 0.012 0.093 0.029 0.351 0.005

1.448 0.013 0.146 0.040 1.129 0.007

8.1 0.2 7.0 0.3 2.5 0.2

3.1 0.2 2.5 0.4 1.4 0.1

7527.7

14,155.6

0.252

0.464

3.1

1.3

Table 2 Unweighted case: mean and standard deviation of node count, computation time, and % UB, and % stopped as a function of n and m n=m

10/2 10/6 10/10 15/2 15/4 15/6 15/8 20/2 20/4

Node count

Time (s)

% UB

% stopped

Mean

s.d.

Mean

s.d.

Mean

s.d.

39.8 175.3 286.4 1353.6 2415.8 16,387.4 29,957.8 184,417.1 441,022.1

48.3 211.2 360.8 2735.9 14,155.0 21,228.6 51,014.1 458,847.0 636,623.0

0.001 0.006 0.018 0.024 0.252 0.875 2.271 4.468 23.178

0.002 0.008 0.022 0.048 0.464 1.104 3.586 10.744 32.600

2.4 1.5 1.0 3.0 3.1 2.3 2.0 3.3 3.7

1.9 0.8 0.5 1.8 1.3 0.9 0.6 1.9 1.3

To study the unweighted objective, we use eleven combinations of m and n values: ðm; nÞ=(2,10), (4,10), (6,10), (8,10), (10,10), (2,15), (4,15), (6,15), (8,15), (2,20), and (4,20). For each ðm; nÞ and p-type (i.e., I–VI above), we produce 50 random problems. This entails generating random pik ’s and ri ’s that meet the specifications described in the previous paragraphs. We use the resulting test bed of 3300 problems for Tables 1–5, which summarize our findings for the unweighted objective. (For some ðm; nÞ and p-types, we also ran experiments based on 500 random problems; however, the results were similar to those reported here.) Table 1 reports on how the mean and standard deviation of the node count, computation time, and UB (in percent) vary with the p-type when

None None None None None None None 2.67 6.67

n ¼ 15 and m ¼ 4: The situation is typical of other n and m values. Problems with neither trend nor correlation tend to be harder while those with correlation tend to be dramatically easier. Similarly, the UB values tend to be higher for problems with neither trend nor correlation and tend to be close to zero for problems with correlation (e.g., see Table 3). The reason correlation makes jobs easier and UB values smaller is that given its presence, some jobs tend to be more dominant than other jobs, which increases the effectiveness of both our bounds and our heuristic for generating initial solutions. Table 2 reports on how the percentage of problems terminated early by our stopping rule nd the mean and standard deviation of the node count, computation time, and UB (in percent) vary

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

193

Table 3 Unweighted case: mean and standard deviation of node count, computation time, and % UB, and % stopped for test problems with correlation as a function of n and m n=m

10/2 10/6 10/10 15/2 15/4 15/6 15/8 20/2 20/4

Node count

Time (s)

% UB

Mean

s.d.

Mean

s.d.

Mean

10.6 36.1 70.8 95.4 431.0 890.3 2832.8 1302.9 13,210.8

7.8 36.9 177.8 210.1 526.2 1585.6 8723.5 3393.0 42,630.4

0.000 0.001 0.004 0.002 0.015 0.048 0.186 0.033 0.704

0.001 0.003 0.010 0.005 0.020 0.083 0.502 0.101 2.391

0.1 0.1 0.0 0.2 0.2 0.2 0.1 0.3 0.3

% stopped s.d. 0.3 0.1 0.0 0.2 0.2 0.2 0.1 0.4 0.2

None None None None None None None None None

Table 4 Unweighted case: mean and standard deviation of node count and computation time, and % stopped for Ahmadi and Bagchi as a function of n and m n=m

10/2 10/6 10/10 15/2 15/4 15/6 15/8 20/2 20/4

Number of nodes

Time (s)

% stopped

Mean

s.d.

Mean

s.d.

60.8 235.4 342.4 3296.8 15,156.3 27,273.7 41,484.8 288,208.1 615,182.1

109.1 250.8 382.2 7287.7 27,143.6 35,573.4 69,393.6 536,202.9 724,178.2

0.001 0.011 0.031 0.142 0.937 2.769 5.808 10.977 62.505

0.003 0.013 0.033 0.282 1.667 3.511 8.580 18.910 69.747

None None None None None None None 3.67 10.30

Table 5 Unweighted case: mean and standard deviation of node count and computation time, and % stopped when dominance test is suspended as a function of n and m n=m

10/2 10/6 10/10 15/2 15/4 15/6 15/8 20/2 20/4

Number of nodes

Time (s)

% stopped

Mean

s.d.

Mean

s.d.

57.9 193.0 301.3 4236.8 11,298.5 19,380.6 34,333.6 430,852.1 577,627.6

77.4 240.0 397.1 10,183.2 21,906.5 25,250.8 19,205.9 726,224.2 785,400.6

0.001 0.006 0.018 0.067 0.360 0.968 2.437 11.764 29.144

0.002 0.008 0.024 0.154 0.688 1.217 4.099 16.343 38.767

None None None None None None None 8.33 9.00

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

194

Table 6 Weighted problems: mean and standard deviation of node count, computation time, and % UB, and % stopped as a function of n and m n=m

10/2 10/6 10/10 15/2 15/4 15/6 15/8 20/2 20/4

Node count

Time (s)

% UB

% stopped

Mean

s.d.

Mean

s.d.

Mean

s.d.

230.9 325.0 344.9 31,995.9 56,871.7 58,601.9 63,134.0 1,789,465.4 2,123,175.0

306.4 355.6 444.9 89,140.9 138,923.4 13,007.3 143,223.0 1,560,441.7 1,459,539.9

0.002 0.010 0.022 0.471 1.984 2.976 4.684 41.153 113.150

0.005 0.012 0.025 1.133 4.685 6.227 9.989 35.445 75.914

12.2 5.8 3.8 15.3 11.4 9.1 7.3 15.5 13.4

5.5 3.1 2.0 5.5 3.9 3.1 2.7 5.9 4.1

with n and m when averaged over all p-type values, while Table 3 does the same for test problems with correlation (i.e., p-type II, IV or VI). 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 with correlation and for most test problems with n ¼ 10 or 15: None of these problems are terminated early by our stopping rule. Some of the others are hard to solve. Among problems without correlation, 5.33% with ðm; nÞ ¼ ð2; 20Þ and 13.33% with ðm; nÞ ¼ ð4; 20Þ are stopped early. One noticeable feature of the results in Tables 1–3 is the high value of the variances of the node counts and computation times. This is due to the presence of some hard problems. Table 4 reports on the performance of the branch and bound algorithm when the lower bound of A&B’s replaces ours. (Everything else is the same, including the dominance test.) The test problems for Table 4 are identical to those for Table 2. For such problems, using A&B’s bound increases the number of problems stopped early and multiplies the average values of the node count and computation time, respectively, by 1.47 and 2.67. (When coding A&B’s bound, we employ a heap to ensure that its computation time achieves its ideal level of Oðmn logðnÞÞ:) As mentioned in Section 2, there is no dominance relationship between A&B’s bound and our bound. Hence, the maximum of these bounds provides a new and tighter lower bound. Extensive computational

None None None None None None None 27.33 36.33

experiments find that replacing our bound with this new bound is not worthwhile, since it leads to an increase in the mean computation time. For the experiments of previous paragraph, the dominance test was activated. In order to gauge the effect of the dominance test, we conducted experiments with the dominance test suspended, using the test problems for Table 2. For these problems, suspending the dominance test increases the number of problems stopped early and multiplies the average values of the node count and computation time, respectively, by around 1.59 and 1.44 (see Table 5). This suggests that the dominance test is very useful. To study the weighted objective, we generate 3300 test problems using the approach described above for unweighted problems. (For each weighted test problem, we also generate weights wj ; 1pjpn; that follow a discrete uniform distribution on [1,10].) In contrast to the unweighted case, the values of the node count, computation time, and UB are not sensitive to the p-type. In particular, our results for problems with correlation are similar to those for problems without correlation. Table 6 reports on how the quantities of interest vary with n and m when averaged over all p-type values. As before, the means of the node count and computation times tend to increase with n and m: Furthermore, weighted problems are harder to solve and have higher UB values than unweighted ones. The differences are greater for larger n: For n ¼ 20;

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

we get the following results: The mean computation time equals 77.152 seconds for weighted problems and 13.383 seconds for unweighted problems; furthermore, 31.83% of the weighted problems and 4.67% of the unweighted problems are stopped early. (No problems with no20 are stopped early.) The main purpose of the paper is to present a lower bound generation scheme and a dominance criterion, which are used to improve a branch and bound algorithm. A limited computational experiment is conducted to test their effectiveness. It is designed to shed some light on the usefulness of the two features. A more general experiment will be needed if one is interested in a full-scale study to find the most efficient algorithm utilizing one or a combination of the existing bounds in the literature.

7. Conclusions The m-machine permutation flowshop problem with the total flow-time objective is a common scheduling problem, which is known to be NPhard for mX2: Here, we develop a branch and bound algorithm to solve both the weighted and unweighted version of this problem. Our algorithm incorporates a new machine-based lower bound and a dominance test for pruning nodes. Computational experiments suggest that the algorithm can handle test problems with np15: It also seems capable of dealing with larger problems for the unweighted objective, especially when the processing times are correlated. Note that our algorithm’s ability to handle the weighted flow-time objective makes it more practical. Jobs can be assigned weights based on their cost and priorities. For example, more expensive jobs should be given larger weights, since the longer they stay in the system, the higher the cost. For future research, we believe that the following topics are potentially useful: (i) the application of other solution techniques to the problem, e.g., Lagrangean relaxation and slack variable decomposition; (ii) extending our branch and bound algorithm to other objectives, e.g., the minimization of total tardiness or total weighted tardiness;

195

(iii) the development of efficient heuristics. Since the problem is NP-hard, it is unlikely that an effective algorithm for solving large problems exists, so (iii) is especially important. Our optimal branch and bound algorithm can play a useful role in evaluating the performance of any heuristic.

References [1] K.R. Baker, Introduction to Sequencing and Scheduling, Wiley, New York, 1974. [2] R.W. Conway, W.L. Maxwell, L.W. Miller, Theory of Scheduling, Addison-Wesley, Reading, MA, 1967. [3] Lawler, E.L., J.K. Lenstra, A.H.G. Rinnooy Kan, D. Shmoys, Sequencing and scheduling: algorithms and complexity, in: S. Graves, A.H.G. Rinnooy Kan, P. Zipkin (Eds.), Handbooks in Operations Research and Management Science, Logistics of Production and Inventory, Vol. 4, North-Holland, Amsterdam, 1993, pp. 445–522. [4] J.B. Sidney, Decomposition algorithms for single-machine sequencing with precedence relations and referral costs, Operations Research 23 (1975) 283–298. [5] C.N. Potts, A Lagrangean based branch and bound algorithm for single-machine sequencing with precedence constraints to minimize total weighted completion-time, Management Science 31 (1985) 1300–1311. [6] S.P. Bansal, Single-machine scheduling to minimize weighted sum of completion times with secondary criterion – a branch and bound approach, European Journal of Operational Research 5 (1980) 177–181. [7] C.N. Potts, L.N. van Wassenhove, An algorithm for single-machine sequencing with deadlines to minimize total weighted, completion time, European Journal of Operational Research 12 (1983) 379–387. [8] A.J. Mason, E.J. Anderson, Minimizing flow time on a single machine with job classes and setup time, Naval Research Logistics 38 (1991) 333–350. [9] L. Bianco, S. Ricciardelli, Scheduling of a single machine to minimize total weighted completion time subject to release dates, Naval Research Logistics Quarterly 29 (1982) 151–162. [10] C. Chu, A branch and bound algorithm to minimize total flow time with unequal release dates, Naval Research Logistics 39 (1992) 859–875. [11] S. Chand, R. Traub, R. Uzsoy, Single machine scheduling with dynamic arrivals: Decomposition results and an improved algorithm, Naval Research Logistics 43 (1996) 705–719. [12] E. Ignall, L. Schrage, Application of the branch and bound technique to some flow-shop scheduling problems, Operations Research 13 (1965) 400–412. [13] S.P. Bansal, Minimizing the sum of completion times of n jobs over m machines in a flowshop – a branch, bound approach, AIIE Transactions 9 (1977) 306–311.

196

C.-S. Chung et al. / Int. J. Production Economics 79 (2002) 185–196

[14] R.H. Ahmadi, U. Bagchi, Improved lower bounds for minimizing the sum of completion times of n jobs over m machines in a flow shop, European Journal of Operational Research 44 (1990) 331–336. [15] S.L. van de Velde, Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation, Annals of Operations Research 26 (1990) 257–268. [16] J.A. Hoogeveen, S.L. van de Velde, Stronger Lagrangian bounds by use of slack variables: Applications to machine scheduling problems, Mathematical Programming 70 (1994) 173–190. [17] F.C. Della Croce, V. Narayan, R. Tadei, The two-machine total completion time flow shop problem, European Journal of Operational Research 90 (1996) 227–237. [18] S.S. Panwalkar, A.W. Khan, An ordered flowshop sequencing problem with mean completion time criterion, International Journal of Production Research 14 (1976) 631–635. [19] W. Szwarc, Solvable cases of the flowshop problem without interruptions in job processing, Naval Research Logistics 30 (1983) 179–183. [20] I. Adiri, N. Amit, Openshop and flowshop scheduling to minimize the sum of completion times, Computers and Operations Research 11 (1984) 275–284.

[21] T. Gonzales, S. Sahni, Flow-shop and job-shop schedules: Complexity and approximation, Operations Research 26 (1978) 36–52. [22] A.H.G. Rinnooy Kan, Machine scheduling problems: Classification, complexity and computations, Nijhoff, The Hague, 1976. [23] J.K. Lenstra, A.H.G. Rinnooy Kan, P. Brucker, Complexity of machine scheduling problems, Annals of Discrete Mathematics 1 (1977) 343–362. [24] J. Ho, Y. Chang, A new heuristic for the n job, m machine flow-shop problem, European Journal of Operational Research 52 (1991) 194–202. [25] C. Rajendran, Heuristic algorithm for scheduling in a flowshop to minimize total flowtime, International Journal of Production Economics 29 (1993) 65–73. [26] C.N. Potts, An adaptive branching rule for the permutation flow-shop problem, European Journal of Operational Research 5 (1980) 19–25. [27] B.J. Lageweg, J.K. Lenstra, A.H.G. Rinnooy Kan, A general bounding scheme for the permutation flow-shop problem, Operations Research 26 (1978) 53–67. [28] W. Press, S. Teukolsky, W. Vetterling, B. Flannery, Numerical Recipes in C: The Art of Scientific Computing, 2nd Edition, Cambridge University Press, Cambridge, 1992.