• Share
  • Email
  • Embed
  • Like
  • Save
  • Private Content
State of art salbp

State of art salbp






Total Views
Views on SlideShare
Embed Views



0 Embeds 0

No embeds



Upload Details

Uploaded via as Adobe PDF

Usage Rights

© All Rights Reserved

Report content

Flagged as inappropriate Flag as inappropriate
Flag as inappropriate

Select your reason for flagging this presentation as inappropriate.

  • Full Name Full Name Comment goes here.
    Are you sure you want to
    Your message goes here
Post Comment
Edit your comment

    State of art salbp State of art salbp Document Transcript

    • European Journal of Operational Research 168 (2006) 666–693 www.elsevier.com/locate/ejor Invited Review State-of-the-art exact and heuristic solution procedures for simple assembly line balancing Armin Scholl *, Christian Becker Fakultat fur Wirtschaftswissenschaften, Friedrich-Schiller-Universitat Jena, Carl-Zeiß-Straße 3, D-07743 Jena, Germany ¨ ¨ ¨ Available online 11 September 2004Abstract The assembly line balancing problem arises and has to be solved when an assembly line has to be conﬁgured or rede-signed. It consists of distributing the total workload for manufacturing any unit of the product to be assembled amongthe work stations along the line. The so-called simple assembly line balancing problem (SALBP), a basic version of thegeneral problem, has attracted attention of researchers and practitioners of operations research for almost half acentury. In this paper, we give an up-to-date and comprehensive survey of SALBP research with a special emphasis on recentoutstanding and guiding contributions to the ﬁeld.Ó 2004 Elsevier B.V. All rights reserved.Keywords: Assembly line balancing; Mass-production; Literature survey; Combinatorial optimization; Branch-and-bound; Heuristics1. Introduction systems, assembly line balancing problems are important tasks in medium-term production Assembly lines are ﬂow-oriented production planning.systems which are still typical in the industrial pro- An assembly line consists of (work) stationsduction of high quantity standardized commodi- k = 1, . . ., m arranged along a conveyor belt or aties and even gain importance in low volume similar mechanical material handling equipment.production of customized products. Among the The workpieces (jobs) are consecutively launcheddecision problems which arise in managing such down the line and are moved from station to sta- tion. At each station, certain operations are repeatedly performed regarding the cycle time * Corresponding author. Fax: +49 3641 943171. (maximum or average time available for each E-mail addresses: a.scholl@wiwi.uni-jena.de (A. Scholl), workcycle). The decision problem of optimallyc.becker@wiwi.uni-jena.de (C. Becker). partitioning (balancing) the assembly work among0377-2217/$ - see front matter Ó 2004 Elsevier B.V. All rights reserved.doi:10.1016/j.ejor.2004.07.022
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 667the stations with respect to some objective is scribed and surveyed in Becker and Scholl (thisknown as the assembly line balancing problem issue).(ALBP). Manufacturing a product on an assembly linerequires partitioning the total amount of work into 2. Simple assembly line balancing problema set of elementary operations named tasks (SALBP)V = {1, . . ., n}. Performing a task j takes a tasktime tj and requires certain equipment of machines Most of the research in assembly line balancingand/or skills of workers. Due to technological and has been devoted to modelling and solving the sim-organizational conditions precedence constraints ple assembly line balancing problem (SALBP). Thisbetween the tasks have to be observed. classical single-model problem contains the follow- These elements can be summarized and visual- ing main characteristics (cf. Baybars, 1986a;ized by a precedence graph. It contains a node Scholl, 1999, Chapter 2.2):for each task, node weights for the task timesand arcs for the precedence constraints. Fig. 1 • mass-production of one homogeneous product;shows a precedence graph with n = 10 tasks having • given production process;task times between 2 and 9 (time units). The prec- • paced line with ﬁxed cycle time c;edence constraints for, e.g., task 5 express that its • deterministic (and integral) operation times tj;processing requires the tasks 1 and 4 (direct prede- • no assignment restrictions besides the prece-cessors) and 3 (indirect predecessor) be completed. dence constraints;The other way round, task 5 must be completed • serial line layout with m stations;before its (direct and indirect) successors 6, 8, 9, • all stations are equally equipped with respect toand 10 can be started. machines and workers; Any type of ALBP consists in ﬁnding a feasible • maximize the line eﬃciency E = tsum/(m Æ c) with Pnline balance, i.e., an assignment of each task to ex- total task time tsum ¼ j¼1 tj .actly one station such that the precedence con-straints and possibly further restrictions are Several problem versions arise from varying thefulﬁlled. The set Sk of tasks assigned to a station objective as shown in Table 1. SALBP-F is a feasi-k (=1, . . ., m) constitutes its station load, the cumu- P bility problem which is to establish whether or notlated task time tðS k Þ ¼ j2S k tj is called station a feasible line balance exists for a given combina-time. When a ﬁxed common cycle time c is given, tion of m and c. SALBP-1 and SALBP-2 have aa line balance is feasible only if the station time dual relationship, because the ﬁrst minimizes m gi-of neither station exceeds c. In case of t (Sk) < c, ven a ﬁxed c, while the second minimizes c (maxi-the station k has an idle time of c À t (Sk) time mizes the production rate) given m. SALBP-E isunits in each cycle. the most general problem version maximizing the In the following, we consider the simple assem- line eﬃciency thereby simultaneously minimizingbly line balancing problem (SALBP). More gen- c and m considering their interrelationship.eral ALBP with additional characteristics like For the example of Fig. 1 with tsum = 48, a fea-cost objectives, paralleling of stations, equipment sible line balance for the SALBP-F instance withselection, and mixed-model production are de- Table 1 Versions of SALBP 6 6 4 Cycle time c 1 2 7 2 9 2 Given Minimize 8 9 10 5 5 4 5 No. m of stations 3 4 5 6 Given SALBP-F SALBP-2 Minimize SALBP-1 SALBP-E Fig. 1. Precedence graph.
    • 668 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693cycle time c = 9 and m = 7 stations is given by the Due to the complexity of SALBP, formulating afollowing sequence of station loads (S1 = {1}, mathematical model and solving it by standardS2 = {2}, S3 = {3,7}, S4 = {4,5}, S5 = {6,8}, optimization software is no realistic choice forS6 = {9}, S7 = {10}). While no idle time occurs ﬁnding an optimal solution in case of real-worldin stations 3, 4, and 6, the other stations have idle instances of ALBP (cf. Section 3.6). Thus, we dotimes of 3, 3, 2, and 7 time units. without describing such models but refer to Scholl One of the optimal solutions to the SALBP-1 (1999, Chapter where diﬀerent models areinstance with c = 11 is ({1,3}, {2,4}, {5,6}, {7,8}, presented. Moreover, see Ugurdag et al. (1997),{9,10}) with the minimal number of m* = 5 sta- Pinnoi and Wilhelm (1997a), Bockmayr and Pis-tions. An optimal SALBP-2 solution given m = 6 aruk (2001), and Peeters and Degraeve (this issue).stations is ({3,4}, {1,5}, {2,7}, {6,8}, {9}, {10}) with In what follows, we describe solution proceduresminimal cycle time c* = 10. Given a SALBP-E in- for the diﬀerent versions of SALBP using the nota-stance with the number of stations restricted to 5 tions of Table 2. SALBP-1 is one of the classicalto 7 stations, the optimal line eﬃciency E* = 48/ optimization problems that has been studied inten-(5 Æ 11) = 0.87 is achieved by the SALBP-1 solu- sively since almost 50 years. The most relevanttion given above. developments are eﬀective branch-and-bound pro- The versions of SALBP may be complemented cedures, including intelligent branching schemesby a secondary objective which consists of smooth- and a variety of bounding procedures (Section 3),ing station loads, i.e., equalizing the station times ﬂexible priority rule based procedures and modern(vertical balancing, cf. Merengo et al., 1999; equal meta-heuristics like tabu search and genetic algo-piles problem, cf. Rekiek et al., 1999). One rithms and their problem-speciﬁc application (Sec-may minimize the smoothness index SX ¼qﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ tion 5). Solution procedures for SALBP-2 and Pm 2 SALBP-E are mostly search methods based on k¼1 ðc À tðS k ÞÞ provided that the combination repeatedly solving SALBP-F instances by(m, c) is optimal with respect to line eﬃciency (see, SALBP-1 procedures (Section 4), others are di-e.g., Moodie and Young, 1965; Rachamadugu and rectly applied heuristics similar to those forTalbot, 1991). SALBP-1 (Section 5). Modifying assumptions of In our example with given combination SALBP leads to generalized problems, solution(m, c) = (5,11), the smoothness index favors the procedures for which are usually based on suchsolution ({3,4}, {1,5}, {2,7}, {6,8}, {9,10}) with for SALBP (cf. Becker and Scholl, this issue).SX = 4.36 versus the other optimal SALBP-1 solu-tions (including the one with SX = 5.39 speciﬁed Table 2for c = 11 above), because the stations of the ﬁrst Notationssolution are more equally loaded. n Number of tasks; index j = 1, . . ., n Since SALBP-F is an NP-complete feasibility V Set of tasks; V = {1, . . ., n}problem, the optimization versions of SALBP, m Number of stations; index k = 1, . . ., mthat may be solved by iteratively examining several m* Optimal number of stationsinstances of SALBP-F, are NP-hard (cf. Wee and LM, UM Lower, upper bound on m c, c* Cycle time, optimal cycle timeMagazine, 1982; Scholl, 1999, Chapter LC, UC Lower, upper bound on cDespite the principal NP-hardness of the problem tj Task time of task j = 1, . . ., nclass, there are considerable diﬀerences concerning tmin, tmax, tsum Minimal, maximal, total task timethe diﬃculty of solving single instances. In order to pj Station requirement of task j; pj = tj/cdistinguish diﬀerent classes with respect to the Pj ðP Ã Þ j Set of direct (all) predecessors of task j Fj ðF Ã Þ Set of direct (all) followers of task jcomplexity of instances, diﬀerent measures like j Sk, t (Sk) Station load, station time of stationthe order strength or the task time variability ratio P k; tðS k Þ ¼ j2S k tj , k = 1, . . ., mhave been developed (for surveys see Scholl, 1999, Ik Idle time of station k; Ik = cÀt (Sk)Chapter; Driscoll and Thilakawardana, aj, nj Head, tail of task j2001). Ej, Lj Earliest, latest station for task j
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 669 Former surveys covering SALBP procedures 3.1.1. Bin packing boundsare given by Buxey et al. (1973), Baybars SALBP-1 reduces to the bin packing problem(1986a), Shtub and Dar-El (1989), Ghosh and BPP-1 (distributing a number of items to a mini-Gagnon (1989), Erel and Sarin (1998), Scholl mum number of ﬁxed-capacity bins; cf. Martello(1999, Chapter 1) as well as Rekiek et al. (2002b). and Toth, 1990) by ignoring the precedence rela- tions. That is, BPP-1 is a relaxation of SALBP-1 and lower bounds for BPP-1 are valid lower3. Exact solution procedures for SALBP-1 bounds for SALBP-1, too. We specify only some of those bounds (further ones can be found in Many operations researchers have been en- Martello and Toth, 1990; Scholl et al., 1997; Fek-gaged with developing eﬀective solution proce- ete and Schepers, 2001; Alvim et al., 2003).dures for exactly solving SALBP-1. This has Total capacity bound (Baybars, 1986a). Theresulted in about two dozens of procedures which most obvious bound LM1 follows from the ine-can be subdivided into branch and bound (B&B) quality m Æ c P tsum, i.e., the total time (total capac-procedures and dynamic programming (DP) ap- ity) available on the line must be no smaller thanproaches. In the following, we summarize the most the total work content:eﬀective key developments without giving closed & ’statements of single procedures. Further (proce- Xn LM1 :¼ dtsum =ce ¼ pj : ð1Þdure oriented) surveys are given by Baybars j¼1(1986a), Ghosh and Gagnon (1989), and Scholl(1999, Chapter 4.1). Simple counting bounds (Johnson, 1988). A Due to their importance for solving SALBP-1 bound LM2 is obtained by counting the numberexactly, we begin with methods for computing of tasks j with tj > c/2 (i.e., pj > 1/2), because alllower bounds on the number of stations (though of those tasks have to be assigned to diﬀerent sta-they are usually not used in DP approaches) tions. LM2 can be strengthened by adding half ofbefore diﬀerent enumeration schemes and possibil- the number of tasks (rounded up to the next inte-ities for reducing the eﬀort of enumeration are ger if necessary) with task time c/2, because two ofdiscussed. them may share one station. A further bound LM3 generalizes LM2 with re-3.1. Lower bounds spect to thirds of the cycle time and is computed by adding up weights which are determined as fol- SALBP-1 is to minimize the number m of sta- lows: All tasks j with pj > 2/3 are given the weighttions given the cycle time c. Due to the integrality 1, because they cannot be combined with any otherof m, only a relatively small number of objective of the tasks considered. Tasks with pj 2 (1/3, 2/3)values are possible. Therefore, it can be expected get the weight 1/2, because two of them may sharethat a large number of line balances is feasible a station. The tasks with pj = 1/3 and pj = 2/3 arefor each feasible value of m. That is, ﬁnding a line weighted with 1/3 and 2/3, respectively.balance given the optimal number m* of stations Extended bin packing bounds. The logic behind(solving the corresponding SALBP-F instance) is the simple counting bounds is combined and ex-often easier than proving a certain number of sta- tended in several manners in order to deﬁne moretions m < m* to be infeasible. As a consequence, sophisticated bound arguments (cf. Martello andknowing sharp lower bounds LM on m* is helpful ´ Toth, 1990; Labbe et al., 1991; Berger et al.,in solving SALBP-1 instances provided that the 1992; Scholl et al., 1997).bounds can be computed eﬃciently. We describe and categorize some of the most 3.1.2. One-machine scheduling boundimportant bound arguments for SALBP-1 (a more The one-machine scheduling bound LM4comprehensive survey is given by Scholl, 1999, (Johnson, 1988) relies on relaxing SALBP-1 to a one-Chapter, and Sprecher, 1999). machine scheduling problem. Tasks are interpreted
    • 670 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693as jobs j = 1, . . ., n with ‘‘processing times’’ pj = tj/c information given by heads and tails provides thewhich have to be successively performed on a sin- overall bound LM4 = max{daj + pj + nje j j =gle machine. After processing job j, a certain 0, . . ., n + 1} which covers Z1 and Z2 for j = 0amount of time (called tail nj) is necessary before and j = n + 1, respectively.the job is terminated. The objective of the one-ma-chine problem is to ﬁnd a sequence of all jobs for 3.1.3. Destructive improvement boundswhich the makespan, i.e., the time interval from the The bound arguments described so far may bestart of the ﬁrst to the termination of the last job, classiﬁed as being constructive, because they ﬁndis minimized. An optimal solution for this problem (construct) optimal solutions to relaxed problems.is achieved by processing the jobs in order of non- A further class of bounds can be deﬁned as beingincreasing tails. Let hh1, . . ., hn] be such a job order- destructive because they try to contradict trialing and tails nj been given, the minimum makespan objective values (numbers of stations) in order tois: successively improve on an initial lower bound. Therefore, this general approach for computingMS ¼ maxfph1 þ nh1 ; ph1 þ ph2 þ nh2 ; . . . ; ph1 lower bounds by a successive process of contra- þ Á Á Á þ phn þ nhn g: ð2Þ dicting potential bound values has been called destructive improvement by Klein and Scholl In the case of SALBP-1, a tail nj of a task j is a (1999).lower bound on the number of stations (not neces- Earliest and latest stations bound LM5 (Saltz-sarily integral) needed by its successors in F Ã . j man and Baybars, 1987; Scholl, 1999, p. 48). ByThus, any bound argument for SALBP-1 can be means of heads and tails (determined as describedapplied to the subproblem deﬁned by F Ã for com- j for LM4), we may compute earliest and latest sta-puting the tails nj (without rounding oﬀ the bound tions to which a task j can be assigned in order notvalues). The computation requires a ﬁctitious to exceed a certain number m of stations:source node j = 0 added to the precedence graph(with t0 = 0 and directed arcs to all original source Ej ¼ daj þ pj e and Lj ðmÞ ¼ m þ 1 À dpj þ nj enodes). The tails are recursively computed in the for j ¼ 1; . . . ; n: ð3Þreverse topological task numbering j = n, . . ., 0.Johnson (1988) proposes to apply LM1, LM2, The destructive improvement concept for com-and LM3 as well as (2) to the subproblem with puting a bound LM5 works as follows: We starttasks F Ã (due to the reverse computation the tails j with a valid lower bound m computed by any con-of those tasks are already known). The largest of structive method. If for any task j the relationthose (unrounded) bound values deﬁnes the tail Ej > Lj (m) holds, j is not assignable to any of thenj of a task j considered. Whenever the conditions m stations and m is increased by 1. This is repeatednj < dnje and pj + nj > dnje are fulﬁlled, task j can- until Ej 6 Lj (m) is true for all tasks. The currentnot share the ﬁrst of the dnje stations required by value of m deﬁnes the bound LM5.its followers such that nj can be rounded up to dnje. SALBP-2 based bound LM6 (Scholl and Klein,This rounding process is the core logic of LM4 1997). Due to the ‘‘duality’’ of SALBP-1 andresponsible for the quality of the computed value. SALBP-2 (cf. Section 2), one may use lowerThe ﬁnal value Z1 = dn0e deﬁnes a ﬁrst lower bounds for SALBP-2 in order to compute boundsbound for SALBP-1. for SALBP-1 in the destructive improvement By applying the same logic in a forward ori- framework: For each trial value m, a lower boundented manner (using heads instead of tails), a sec- c (m) on the cycle time is computed by a boundond bound Z2 = dan+1e may be computed for a argument for SALBP-2 (see Section 4.1). If c (m)ﬁctitious sink node n + 1 (cf. Scholl, 1999, p. 47). is larger than the given cycle time c, m is increasedA head aj is a lower bound on the number of sta- by 1, and the process is repeated. Otherwise, thetions required by all predecessors of task j and is current value of m provides a lower bound LM6computed analogously to tails. Combining the on the number of stations for SALBP-1.
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 671Table 3Heads and tails of tasksj 0 1 2 3 4 5 6 7 8 9 10 11pj 0 0.6 0.6 0.5 0.5 0.4 0.5 0.4 0.2 0.9 0.2 0aj 0 0 1 0 0.5 1.6 2 1.6 3.5 4 5 5.2nj 5.7 4.1 3 4 3.4 3 2.2 2.2 2 1 0 0 Interval bound LM7. A further destructive tsum = 48, tmax = 9, and tmin = 2 as well asbound is proposed by Fleszar and Hindi (2003) c = 10. The following bound values are obtained:who deﬁne station intervals [m1, m2] with1 6 m1 6 m2 6 m for a current lower bound value • LM1 = d48/10e = 5.m. If a solution with m stations exists, the tasks in • LM2 = 3 + d3/2e = 5, because there are threethe set {j 2 VjEj P m1 and Lj (m) 6 m2} must be tasks (1, 2, 9) exceeding half of the cycle timeassigned to at most m2 À m1 + 1 stations. If apply- and three further tasks (3, 4, 6) having task timeing any SALBP-1 bound to this subproblem re- c/2. LM3 = d1 Æ 1 + 1/2 Æ 7e = 5 due to p9 > 2/3veals that this is not possible for any interval and pj 2 (1/3, 2/3) for j 2 VÀ{8, 9, 10}.[m1, m2], m is contradicted as a feasible number • We do without explaining the computation ofof stations and is increased by 1. The process is re- LM4 in detail but give the heads and tails inpeated until no ‘‘destruction’’ of the current m is Table 3. We get LM4 = d5.9e = 6 (deﬁned bypossible which then deﬁnes LM7. task 9). The rounding logic of LM4 becomes Bin packing applications of destructive obvious considering, e.g., task 2 whose headimprovement are also applicable to SALBP-1 as a2 is set to 1 because it is not possible to assignmentioned earlier (cf. Scholl et al., 1997; Alvim 2 to the same station as its direct predecessor 1et al., 2003). though the station requirement of task 1 is only Computational experiments show that among p1 = 0.6.the bound arguments presented so far LM4 is • LM5 is computed starting with, e.g., m =the most powerful one (cf. Scholl, 1999, p. 242). LM1 = 5. Table 4 contains the values for EjHowever, due to the diversity of problem instances and Lj (5). Due to Ej > Lj (5) for j = 8, 9, 10,to be solved applying all arguments available is these tasks cannot be assigned to any of the 5recommendable. stations, and m is increased to 6. Since the con- A further class of bounds is based on solving dition Lj (6) P Ej holds for all tasks jrelaxations of mathematical model formulations (Lj (6) = Lj (5) + 1; cf. Table 4), LM5 gets thefor SALBP-1 by means of standard optimization value 6. Beyond the bound computation, wepackages. Peeters and Degraeve (this issue) present get the information that tasks 8, 9, and 10 musta Dantzig-Wolfe type formulation of SALBP-1 the be assigned to station 4, 5, and 6, respectively,LP-relaxation of which is solved using column in order to ﬁnd a solution with no more thangeneration combined with subgradient optimiza- 6 stations.tion. Computational experiments show that theresulting bound values are close to optimality.However, this must be paid by a high computa-tional eﬀort which is often higher than for exactly Table 4solving the unrelaxed problem. Earliest and latest stations j 1 2 3 4 5 6 7 8 9 103.1.4. Example for bound computation Ej 1 2 1 1 2 3 2 4 5 6 For illustration purposes, we reconsider our Lj (5) 1 2 1 2 2 3 3 3 4 5example of Fig. 1 which is characterized by Lj (6) 2 3 2 3 3 4 4 4 5 6
    • 672 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693• For LM6 we may also start with m = 5. A sim- assignable tasks is built for a station k, before ple bound for SALBP-2 consists of considering the next one k + 1 is considered. the m + 1 largest tasks. Provided that they are- • Task-oriented assignment. Procedures which are sorted in non-increasing order of task times, task-oriented iteratively select a single available c (m) = tm + tm + 1 is a lower bound on the cycle task and assign it to a station, to which it is time given m stations. In our example, we get assignable. c (5) = 5 + 5 = 10 = c and, hence, LM6 = 5.• Starting the computation of LM7 with m = 5, one ﬁnds a contradiction considering the sub- 3.3. Dominance rules problem with station interval [1, 2] and the task set {1, . . ., 5} due to LM1 = d26/10e = 3 > 2. No Most procedures use dominance rules to reduce further contradiction arises for m = 6 such that the enumeration eﬀort. Such a rule compares par- LM7 = 6 is determined. tial solutions (and corresponding residual prob- lems) in order to ﬁnd dominance relationships which allow for excluding (dominated) partial3.2. Construction schemes solutions without explicitly completing them to full solutions. The concept of dominance is based Most exact algorithms are based on enumerat- on the fact that all partial solutions which cannoting feasible solutions by successively assigning be completed to a solution with minimal numbertasks or subsets of tasks to stations. Therefore, of stations and even all of those but one whichthese algorithms consider partial solutions contain- can be completed to an optimal solution coulding a number of already assigned tasks and (par- be eliminated from further consideration. Since ittial) station loads Sk (k = 1, 2, . . .), while the is usually not known in advance into which cate-remaining tasks and station idle times constitute gory the partial solutions fall, a dominance rela-a residual problem. tionship between two partial solutions P1 and P2 For explaining solution procedures we need is established whenever it can be proved that thesome further terms and deﬁnitions: optimal completion of P1 does not require more stations than that of P2. Whenever such a domi-• A yet unassigned task j is available if all preced- nance relationship is found, P2 can be excluded ing tasks h 2 P Ã have already been assigned to a j from further consideration. station. Due to their importance in developing eﬀec-• An available task is assignable to a station k if tive procedures for SALBP-1 we explain some all preceding tasks have already been assigned of the most powerful dominance rules (further- to station k or an earlier station 1, . . ., k À 1 more, see Scholl, 1999, Chapter 4.1, and Sprecher, and the current idle time is suﬃcient. 1999).• A station load Sk is maximal if no available task • Maximum load rule (Jackson, 1956). It excludes is assignable to station k. each partial solution P2 which contains one or• A subset of tasks S  V is feasible if S also more completed but non-maximal station loads, contains the predecessors of each task included. because there exists at least one another partial solution P1 with the same number of maximally Almost every solution procedure for SALBP-1 loaded stations, where additional tasks are as-is based on either of the two following construction signed. In such case the completion of P1 doesschemes, which deﬁne the principle way of assign- not require more stations than that of P2. Theing tasks to stations: maximum load rule does not require explicit com- parisons between several partial solutions, because• Station-oriented assignment. In any step of a sta- it is suﬃcient to examine the maximality of station tion-oriented procedure a complete load of loads while these are constructed (Johnson, 1988).
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 673 Example. Given a cycle time of 10 and the prec- m1 6 m2 stations, P2 is dominated by P1 andedence graph of Fig. 1, S1 = {1} and S1 = {3, 4} excluded.are maximal loads for station 1, while S1 = {3} is In order to apply the feasible set dominancenon-maximal. Provided that S1 = {3, 4} has al- rule, it is necessary to store all feasible subsets ofready been built, S2 = {1, 5} is the only maximal tasks already enumerated together with their min-load available for station 2. imum station requirements in an eﬃcient manner• Jackson dominance rule (Jackson, 1956, strength- with respect to storage space and retrieval speed.ened by Scholl and Klein, 1997). This rule is ap- For this purpose several approaches are available:plied to reduce the number of alternative loads Held et al. (1963) propose a recursive addressingwhich have to be considered for a certain station algorithm which assigns a unique address to eachk. It is based on potential dominance. feasible subset using the address space compactly. A task h potentially dominates a task j that is not Because this addressing algorithm is very time-related to h by precedence, if F j  F Ã and tj 6 th h consuming, Schrage and Baker (1978) develop ahold. If tj = th and Fj = Fh, the lower-numbered simpler procedure based on task labels which havetask is deﬁned to be dominating. to be summed up to quickly compute the address The Jackson rule excludes a maximal station of a subset. However, this addressing is not com-load Sk from consideration if at least one task pact and therefore requires a lot of storage space.j 2 Sk can be replaced by an available not yet as- In order to overcome this disadvantage, Nouriesigned task h which potentially dominates j, and and Venta (1991) deﬁne a tree structure for eﬃ-the resulting station time t (Sk) À tj + th does not ciently storing all feasible subsets which outper-exceed the cycle time c. forms the previous approaches. A similar This rule utilizes the fact that all successors of approach is proposed by Sprecher (1999). Alltask j are successors of h as well and cannot start those methods are restricted to examining thebefore h is ﬁnished. Hence, the sequence of j dominance relation for the special case T2 = T1,and h is not important for the successors of j such the more general case T2  T1 is examined in athat replacing h by j does not exclude later task solution procedure for the related resource con-assignments which would be possible when j re- strained scheduling problem (cf. Klein and Scholl,mained. The condition tj 6 th guarantees that the 2000).station utilization will not decrease if h replaces j Example. The partial solution P1 = ({3, 4},in Sk. {1, 5}, {2, 7}) assigns the feasible set T1 = {1, . . ., Example. In Fig. 1, the following pairs of poten- 5, 7} to m1 = 3 stations. Another partial solutiontial dominance (h, j) are present: (1, 4), (2, 6), (3, 7), P2 = ({1}, {3, 4}, {2, 5}) corresponds to(4, 7), (5, 7), (6, 7). This results, e.g., in the par- T2 = {1, . . ., 5} and requires m2 = 3 stations, too.tial solution P1 = ({1}, {3, 4}, {2, 5}) dominating Thus, P2 is dominated by P1.P2 = ({1}, {3, 4}, {2, 7}) and also P3 = ({1}, {3, 4}, • Station ordering rules. Because ﬁnding a single{5, 6}). optimal solution is suﬃcient, it is not necessary• Feasible set dominance rule (Schrage and Baker, to consider diﬀerent partial solutions which have1978; Nourie and Venta, 1991; Scholl and Klein, the same station loads but diﬀer only in the se-1999). It extends the logic of the maximal load rule quence these loads are assigned to stations. Severalto feasible subsets of tasks. Provided that a partial rules which attempt to ﬁnd respective dominancesolution P2 is constructed in forward direction relationships in an eﬃcient manner are proposed(from early to late stations) and the maximum load by Johnson (1988), Scholl and Klein (1997) as wellrule is applied to all m2 stations already loaded, the as Sprecher (1999).corresponding feasible subset T2 of tasks is as- Example. The partial solutions P1 = ({1},signed to these m2 stations. Whenever another par- {2, 7}, {3, 4}) and P2 = ({1}, {3, 4}, {2, 7}) are iden-tial solution P1 has already been considered which tical except for the sequence of the second andassigns a feasible task set T1 (with T2  T1) to third load. Thus, one can be excluded.
    • 674 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 Computational experience reveals that applying • Additional precedence relations (Fleszar and Hin-(computationally inexpensive) dominance rules is di, 2003). Consider two tasks h and j which are notvery important for the computation times of exact related by precedence. If m (j, h) = daj + pj +procedures (cf. Johnson, 1988; Nourie and Venta, ph + nhe > UM À 1, an additional arc (h, j) is1991, 1996; Scholl and Klein, 1997; Scholl, 1999, p. added to the precedence graph, because perform-242). ing j before h cannot lead to an improved solution. If m (h, j) > UM À 1 is additionally true, no solu- tion with less than UM stations exists. That is,3.4. Reduction rules examining precedence relations in both directions is a means that may be applied within destructive Besides dominance rules several procedures use improvement bounds (cf. Klein and Scholl, 1999).reduction rules to lower the computational eﬀort Example. Again starting with UM = 7, we canfor solving SALBP-1. Such rules try to modify add the arc (3, 2) due to m (2, 3) = d6.1e > 6 andproblem data, i.e., task times or precedence rela- m (3, 2) = d4.1e < 6 (cf. Table 3). Trying to contra-tions, such that the number of solution alternatives dict m = 5 or, equivalently, trying to improve oncan be reduced or bounds may get improved val- UM = 6, a contradiction is found consideringues. However, the reduced problem must have at the tasks 1 and 3 because of m (1,3) > 5 andleast one optimal solution in common with the m (3,1) > 5.original problem. • Task conjoining rule (Fleszar and Hindi, 2003). If• Task time incrementing rule (Johnson, 1988; all (potential) maximal loads containing a particu-Scholl, 1999, p. 117). The task times of all tasks lar task j also contain another task h, both nodeswhich cannot share a station with any other task can be merged into one node thereby uniting theare set to c. A simple suﬃcient condition for incre- sets of predecessors and successors.menting the time tj of a task j to c is tj + tmin > c. Example. Provided that the arc (3, 2) has beenImproved conditions are given by Talbot and Pat- added as described in the rule above, the only max-terson (1984), Sprecher (1999), and Fleszar and imal load containing task 3 is {3, 4} such that bothHindi (2003). tasks can be merged. Example. In the instance given by Fig. 1 and Fleszar and Hindi (2003) deﬁne further rulesc = 10, we ﬁnd that the time of task 9 can be in- which may allow for decomposing the prece-creased to 10. Inspecting the precedence structure dence graph and improving on lower bounds byreveals that the time of task 10 can be set to 10, successively adding dummy tasks and increasingtoo. Doing so, immediately leads to the improved task times. Their computational experimentsLM1 = d57/10e = 6. show that reduction rules have a great potential• Preﬁxing (Scholl and Klein, 1999). Whenever it for improving solutions found by any heuristic ifbecomes clear that a task can only be assigned to they are applied prior to the heuristic. Further-one speciﬁc station in order to ﬁnd an improved more, they allow for computing sharper lowersolution (or one with a predeﬁned number of sta- bounds.tions) this task can be assigned (preﬁxed) to therespective station. Provided that UM denotes a va-lid upper bound on the number of stations, 3.5. Dynamic programming proceduresEj = Lj (UM À 1) is a suﬃcient condition which al-lows for preﬁxing task j to station Ej because an As already mentioned, exact solution proce-improved solution must not have more then dures for SALBP-1 are based either on dynamicUM À 1 stations. programming or branch and bound. Example. Let us assume that a feasible solution The ﬁrst dynamic programming (DP) procedurewith UM = 7 stations is already known. Then the developed by Jackson (1956) and modiﬁed by Heldtasks 8, 9, and 10 can be preﬁxed to the stations 4, et al. (1963) subdivides the solution process in5, and 6, respectively (cf. Table 4). stages which correspond to stations, i.e., it follows
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 675the station-oriented construction scheme. States Table 5are given by the feasible subsets of tasks already Possible componentsassigned at a given stage. The optimal solution LMi Lower bound LMi (i = i, . . ., 6)is searched for stage-by-stage in a forward recur- ML Maximum load rule FS Feasible set dominance rulesion, i.e., the procedure enumerates all ﬁrst station JD Jackson dominance ruleloads before it considers all additional second sta- SO Station ordering dom. ruletion loads and so on (breadth-ﬁrst search). In or- TI Task time incrementing ruleder to restrict the enumeration eﬀort, only PF Preﬁxingmaximal station loads not being dominated by RN Task renumbering HS Additional heuristicthe Jackson dominance rule (cf. Section 3.3) are FW/BW Constructing solutions inbuilt. forward/backward direction If in JacksonÕs approach the states are repre-sented by nodes and the station loads, by arcswhich are weighted with the corresponding stationidle times, SALBP-1 is transformed to an equiva- 3.6.1. Search strategieslent shortest path problem. Each path in this graph Besides the construction scheme (station- orcorresponds to a feasible solution and each short- task-oriented), the B&B procedures diﬀer with re-est path to an optimal solution of SALBP-1 (cf. spect to search strategy.Gutjahr and Nemhauser, 1964). Since the number • In a depth-ﬁrst search (DFS), a single branch ofof nodes grows exponentially with the number of the tree is developed until a leaf node is reachedtasks, it is generally not possible to construct the or the current node is fathomed. On its way backcomplete graph. Therefore, Easton et al. (1989) to the root, the search follows the ﬁrst possibleincorporate lower and upper bounds as well as alternative branch, i.e., each node is completelydominance rules to reduce the size of the graph. developed before its ancestor nodes are revisited.Furthermore, their procedure is designed to be ap- Most commonly, DFS is organized as laser searchplied in forward and backward direction, (LS), i.e., in each node of the current branch, onlyrespectively. one descending node is built and developed at a Further DP procedures apply task-oriented time. Alternatively, all descending nodes may beconstruction schemes. The procedures of Held generated and sorted by a priority rule (e.g.,et al. (1963) and Schrage and Baker (1978) per- according to non-decreasing lower bound values).form a forward recursion and store states together The one with the highest priority is branched ﬁrst.with their minimum station requirement in a The remaining nodes are stored in a candidate listmemory using diﬀerent addressing schemes (see and are developed according to the priority orderfeasible set dominance rule; cf. Section 3.3). at each revisit of the node. This derivative is calledHowever, both procedures have large memory DFS with complete node development (DFSC).requirements because they do not strictly work • A minimal lower bound strategy (MLB) alwaysstage-by-stage. The procedures of Lawler (1979) chooses a not yet developed node which has theand Kao and Queyranne (1982) improve on this minimum value of a lower bound (see Sectiondrawback and get by with considerably less 3.1) from a candidate list. This node is completelymemory. branched by constructing all descending nodes. The latter are stored in the list which is sorted3.6. Branch and bound procedures according to non-decreasing bound values, while the current node is dropped. At the beginning, In the last decades, a considerable number of the list only contains the root node.branch and bound (B&B) approaches have been Irrespective of the strategy used, a node is fath-proposed in the literature. Table 6 gives a survey omed when its (local) lower bound (computedof these procedures and characterizes them brieﬂy explicitly or inherited from the father node) isby means of the notation in Table 5. not smaller than the global upper bound UM
    • 676 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693(number of stations in the currently best known earlier. In order to reduce this negative eﬀect, mostsolution), because it does not have an optimal procedures using LS renumber the tasks concern-solution with less than UM stations. ing some priority rule such that the ﬁrst subprob- While DFS considers (and stores) only a small lems generated contain promising taskpart of the enumeration tree at a time, MLB has assignments which have the potential of being partto manage a large number of not yet developed of an improved solution.nodes considerably restricting its applicability to DFSC explicitly tries to avoid the drawback ofSALBP-1 and other combinatorial optimization LS by generating all subproblems of a currentproblems. Therefore, the most eﬀective algorithms node before they are examined in order of non-for SALBP-1 presented recently are based on some decreasing lower bound values. So, promisingtype of DFS strategy. partial solutions are considered ﬁrst, but all sub- However, both extreme versions of DFS dis- problems have to be generated irrespective of thecussed above have potential disadvantages, too: diﬃculty in ﬁnding an improved UM value. ThatLS considers the diﬀerent subproblems in an (arbi- is, even in case of ﬁnding the optimal solution totrary) sequence induced by the task labeling taking a node in the ﬁrst branch followed, all subprob-the risk to examine large subtrees before promising lems have been generated before.parts of the enumeration tree are entered and im- The so-called local lower bound method (LLBM)proved solutions (with decreased UM) are found. aims at ﬁnding a reasonable compromise betweenThat is, LS tends to spend a lot of time in investi- these extreme positions (cf. Scholl and Klein,gating many solutions which could have been fath- 1997). The subproblems of a current node are sub-omed if an improved UM value was determined divided into two classes: class I contains all sub-Table 6Survey of branch and bound procedures for SALBP-1Station-oriented Task-orientedDFS• Mertens (1967): FW, LS, LM1, RN • Talbot and Patterson (1984), based on additive• Johnson (1981): FW, DFSC, LM1, modiﬁed LM2,3, ML algorithm of Balas (1965): FW, LS, reduction• Betts and Mahmoud (1989): similar to Johnson (1981), tests based on LM1, TI enumeration based on Hoﬀmann (1963) • Saltzman and Baybars (1987): parallel FW-BW,• Berger et al. (1992): similar to Hackman et al. (1989) LS, RN, LM1,5, LM2,3 modiﬁed like Johnson restricted to out-tree type precedence graphs, (1981), TI, HS LM1 and extended bin packing bound • FABLE, Johnson (1988, 1993): FW, LS, RN,• EUREKA, Hoﬀmann (1992, 1993): FW-BW (successively), LM1-4, ML, JD, FS (restricted), TI, SO LS, LM1; lower bound method: repeated application for • Nourie and Venta (1991, 1996): branching like increasing trial numbers of stations; application of heuristic FABLE, FW, LS, RN, LM1, ML, FS, HS of Hoﬀmann (1963) if no feasible solution is found • Sprecher (1999): branching like FABLE, FW-BW (static direction switching), LS, RN, LM1-6, ML, JD, FS, TI, SO • Sprecher (2003): distributed version of Sprecher (1999) for parallel computersMLB• Jaeschke (1964): FW, LM1, ML• Van Assche and Herroelen (1979): FW, LM1, ML, FS (restricted)• Hackman et al. (1989): FW, LM1, ML, FS (restricted), HSLLBM• SALOME-1, Scholl and Klein (1997, 1999): FW-BW (bidirectional), RN, LM1-6, ML, JD, FS (Nourie and Venta, 1991), PF, TI, SO• Bock and Rosenberg (1998), Bock (2000): distributed version of SALOME-1
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 677 6 {3,4} 6 6 7 {9} 7 {5,6} {8} {10} 2 3 4 5 6 7 7} 6 {2 , UM=7 6 {6,7} 6 {8} 7 1 } ,5 } 9 10 11 16 {1 {3 {2 ,4 } 6 6 {5,6} 6 {8} 7 LM1=5 {2,7} 8 12 13 14 19 0 {5 7 {3 ,6} 6 {2,7} 6 {8} ,4 15 16 17 22 } 5 18 5 {6,8} 6 {9} 6 {10} {1 ,5} 5 {2,7} 20 21 22 23 UM=6 19 6 {6} 24 29 Fig. 2. Enumeration tree with laser search and bound LM1.problems which have the same local lower bound precedence graph of Fig. 1. In order to concen-value LLB as the current node, class II contains trate on these strategies, we only apply the simpleall remaining subproblems which have an in- lower bound LM1 and do without dominance andcreased LLB. Following the basic principle of reduction rules except for the maximum load rule.DFSC, the subproblems of the ﬁrst class are As construction scheme, we use the station-ori-branched before those of the second class. This is ented assignment. Fig. 2 shows the enumerationimplemented as follows: the subproblems are gen- tree obtained by applying the LS strategy, whereerated following a task renumbering as in case of the node numbering indicates the sequence of nodeLS. Each subproblem is judged concerning its generation (the tree is developed from left to rightmembership to class I or II. Class II-problems and from top to bottom). The initial bound of theare dropped and re-enumerated later if necessary, root node 0 is given by LM1 = d48/10e = 5, the lo-class I-problems are chosen for branching. After cal lower bounds of the other nodes are given ashaving examined the corresponding subtrees, the node weights. In the ﬁrst branch, a feasible solu-following situations may occur in the current node: tion with UM = 7 is found. This upper bound allows for fathoming the shaded nodes 11, 14,(1) If an improved upper bound UM = LLB has and 17. been found, the current node can be fathomed In node 23, an improved solution with UM = 6 immediately without generating further stations is found, such that node 24 can be fath- subproblems. omed. Since all nodes with LM1 = 5 are now com-(2) If an improved upper bound UM = LLB + 1 pletely branched, the procedure stops with the has been found, all class II-problems can be optimal solution S* = ({3, 4}, {1, 5}, {2, 7}, {6, 8}, dropped, i.e., the search stops after having {9}, {10}) with 6 stations. Solving this problem in- examined all class I-problems. stance to optimality requires examining 25 nodes(3) If all class I-problems have been examined, of the enumeration tree. LLB is increased by 1 (the current node has The DFSC strategy starts with completely no solution with at most LLB stations) start- branching node 0 thereby building (and storing) ing the examination of the class II-problems if the nodes 1 and 18. Computing LM1 for both LLB remains smaller than UM. Otherwise, nodes indicates that the search should continue the current node is fathomed. with branching node 18. This generates only node 19 whose branching results in the nodes 20 and 24 with lower bound values 5 and 6, respectively.3.6.2. Comparison of search strategies Therefore, the search continues with node 20 We compare the diﬀerent search strategies by ﬁnally leading to the optimal solution with 6 sta-means of our example deﬁned by c = 10 and the tions. Backtracking leads to fathoming the nodes
    • 678 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–69324 and 1 and the procedure stops. In total, DFSC completed even in cases where the ﬁnished stationhas to consider 9 nodes. load is recognized as being inferior due to much The LLBM only builds the branch leading to the idle time. That is, the search can less strictly be di-optimal solution (nodes 0 and 18–23) without stor- rected to ﬁnding promising partial solutions sooning the nodes 1 and 24. After having found the as in case of other search strategies.solution with UM = 6, no further branching is re- Similarly to station-oriented LS procedures (seequired because the loads {1} in node 0 and {6} in above), additionally applying bound argumentsnode 19 would lead to class II-subproblems. So, and dominance rules partially removes this disad-LLBM requires the minimal number of 7 nodes. vantage. However, this comes along with addi- The MLB strategy might produce the same tree tional expense in computation time and storageas DFSC. However, due to several nodes having space. This tradeoﬀ can best be seen comparingthe same bound value at a time it might perform FABLE (Johnson, 1988) and EUREKA (Hoﬀ-much worse. For example, the following sequence mann, 1992), because the ﬁrst performs a task-ori-of selecting nodes for further development or fat- ented LS with a lot of bounding, dominance andhoming is possible which requires examining 23 reduction rules, while the latter performs a sta-nodes: 0, 18, 19, 20, 1, 2, 3, 4, 8, 9, 10, 12, 13, tion-oriented LS almost without such rules. Exper-15, 16, 21, 22, 23, 24, 5, 11, 14, 17. That is, the per- imental tests show that both procedures whichformance of the procedure depends on resolving were the benchmark procedures in the early nine-such tie break situations. ties get similar results when EUREKA is restricted Of course, one may ﬁnd other problem in- to the forward direction (Johnson, 1993; Hoﬀ-stances where MLB or DFSC or even LS per- mann, 1993; Scholl, 1999, p. 238) despite their veryform better than LLBM but experimental results diﬀerent approaches. The tests have been per-indicate that LLBM is the most eﬀective formed using benchmark data sets of Talbotscheme in many situations (cf. Scholl and Klein, et al. (1986), Hoﬀmann (1990, 1992), and Scholl1997). (1993) that are downloadable from http:// When these basic strategies are enriched with www.assembly-line-balancing.de and described inadditional bound arguments, dominance and Scholl (1999, p. 234).reduction rules the diﬀerences between the search Some improvements are obtained by includingstrategies are reduced. For example, the nodes 12 the static backward planning of EUREKAand 15 are avoided by the Jackson dominance rule, (Scholl, 1999, p. 239) which indicates that somebecause task 7 is potentially dominated by task 5 problem instances are easier solved in the reverseand task 6 by task 2. Moreover, node 11 would direction. Signiﬁcant further improvements arebe avoided by the feasible set dominance rule due to the LLBM connected with the ﬂexible bidi-due to node 5 and node 24 due to node 15. Never- rectional branching of SALOME-1, which at-theless, 17 nodes remain for LS. tempts to ﬁnd the preferable planning direction in any node of the tree by some type of priority3.6.3. Comparison of construction schemes and rule (Scholl and Klein, 1997). Additional compo-complete procedures nents like dynamic preﬁxing and dynamic task Comparing the diﬀerent construction schemes renumbering as well as the FS rule together with(task- versus station-oriented assignment) reveals the storage scheme of Nourie and Venta (1991,a methodical drawback of the task-oriented ap- 1996) considerably speed up SALOME-1 (Schollproach, because it successively ﬁlls stations with and Klein, 1999).tasks without controlling their ﬁnal idle times. This The only (serial) procedure which seems to bedrawback becomes apparent most clearly when the competitive to SALOME-1 is that of Sprechertask-oriented assignment is connected with LS (as (1999) who applies many of the components alsois the case with all task-oriented procedures cur- contained in SALOME-1 but performs a task-ori-rently on hand; cf. Table 6), because each partial ented LS. The potential disadvantage of such typestation load and the following subtree must be of enumeration (see above) is compensated by
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 679utilizing improved knowledge on characteristics of for SALBP-2 is given by LC1 := max{tmax, dtsum/optimal solutions. me}. Signiﬁcant speed ups are obtained by parallel- Bound LC2 (Klein and Scholl, 1996). SALBP-2ized versions of SALOME-1 and the Sprecher passes into a parallel machine problem with thealgorithm (cf. Bock and Rosenberg, 1998; Bock, objective of minimizing the makespan by omitting2000; Sprecher, 2003). This is due to the fact that the precedence relations. A lower bound for thesimultaneously searching in diﬀerent parts of the parallel machine problem and, thus, for SALBP-solution space enlarges the probability of ﬁnding 2 is obtained as follows provided that the tasksan optimum soon. are renumbered according to non-increasing task SALBP-1 can be formulated as a special case times, i.e., tj P tj+1 for j = 1, . . ., n. Consider theof the generalized resource-constrained project m + 1 largest tasks 1, . . ., m + 1. A lower boundscheduling problem (GRCPSP) as shown in De on the cycle time for this reduced problem isReyck and Herroelen (1997) and Sprecher (1999). tm + tm+1, the sum of the two smallest task times,However, applying exact procedures for GRCPSP because at least one station contains two tasks.is not competitive to specialized SALBP proce- For the 2m + 1 largest tasks, a lower bound is gi-dures (cf. De Reyck and Herroelen, 1997). ven by the sum of the three smallest operation Recently, Bockmayr and Pisaruk (2001) devel- times, t2mÀ1 + t2m + t2m+1. In general, a loweroped a branch and cut procedure based on integer bound LC2 is deﬁned asprogramming formulations with additional valid ( ) Xkinequalities and constraint programming tech- LC2 :¼ max tkÁmþ1Ài j k ¼ 1; . . . ; bðn À 1Þ=mcniques. Pinnoi and Wilhelm (1997a,b, 1998) also i¼0propose branch and cut procedures for SALBP-1 ð4Þconnected with vertical balancing (cf. Section 2)as well as for more general problems. Bound LC3 (Scholl, 1999, p. 56). This bound is Though these researchers invest a lot of work in based on earliest and latest stations and destruc-ﬁnding sharp valid inequalities, their computa- tive improvement. Given an initial lower bound ctional experiments clearly show that such proce- on the cycle time, earliest and latest stations aredures cannot compete with state-of-the-art obtained from heads and tails (depending on c)enumeration based B&B algorithms. The same is as follows (cf. Section 3.1):true for DP procedures (cf. Section 3.5). Ej ðcÞ :¼ daj ðcÞ þ pj ðcÞe and Lj ðcÞ :¼ m þ 1 À dpj ðcÞ þ nj ðcÞe for j ¼ 1; . . . ; n:4. Exact solution procedures for SALBP-2 and ð5ÞSALBP-E LC3 is computed by successively increasing c4.1. Lower bounds for SALBP-2 until Ej (c) 6 Lj (c) is obtained for all j = 1, . . ., n. Bound LC4 (Scholl, 1999, p. 57). By subdividing In what follows, we describe only a few argu- the interval [1, m] of all stations into two subinter-ments for computing lower bounds for SALBP-2, vals [1, i] and [i + 1,m], we obtain two aggregatefurther ones are proposed by Scholl (1999, Chap- ‘‘stations’’. For a valid lower bound c, these ‘‘sta-ter As in case of SALBP-1, these bounds tions’’ have to observe the ‘‘cycle times’’ i Æ c andutilize relationships to other problems and the (m À i) Æ c, respectively. This modiﬁed problem isdestructive improvement approach (Section 3.1). solved as follows: Bound LC1 (McNaughton, 1959). By analogy All tasks with Lj (c) 6 i are assigned to the ﬁrstwith LM1, a simple lower bound on the cycle time ‘‘station’’ and those with Ej (c) > i are assigned tofollows from the necessary feasibility condition the second one. The remaining tasks and them Æ c P tsum. Furthermore, the indivisibility of remaining idle times of the two aggregate ‘‘sta-tasks requires that c P tmax. Hence, a lower bound tions’’ constitute a residual problem. This problem
    • 680 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693can be formulated as the feasibility version of the tsum = 51 and tmax = 9, we get LC1 = max{9,bin packing problem with two bins and capaci- d51/5e} = 11. Because the six largest tasks are 9,ties equal to the remaining idle times of the two 1, 2, 3, 4, and 6, LC2 = t4 + t6 = 10 is obtained.aggregate ‘‘stations’’ (2Bin-F for short). The ques- Taking c = max{LC1,LC2} = 11 as initialtion of this feasibility problem reads as: ‘‘Does bound for computing LC3, we get the correspond-there exist a partition of the remaining tasks (items) ing station requirements, heads and tails given ininto at most two bins with given capacities?’’ Even the ﬁrst rows of Table 7. Due to a11 (11) > 5, it isthough 2Bin-F is NP-complete, it can often be clear that c = 11 is no feasible cycle time and is in-solved in a reasonable computation time, because creased to c = 12. The further rows of Table 7 con-the residual problem is usually much smaller than tain the respective station requirements, heads andthe original SALBP-2 instance and only two bins tails as well as earliest and latest stations. Obvi-are considered. The problem may be solved by ously, the condition Ej (12) 6 Lj (12) holds forany exact procedure for the bin packing problem j = 1, . . ., 10 and LC3 = 12 cannot be ‘‘destroyed’’(cf., e.g., Martello and Toth, 1990, Chapter 8; as a potential cycle time.Scholl et al., 1997). If the remaining idle times of For computing LC4, we start with the bestthe two ‘‘stations’’ are diﬀerent, equal-sized bins known lower bound c = max{LC1, LC2, LC3} =are obtained by pre-assigning a ﬁctitious item, 12 and use the values Ej (12) and Lj (12) of Table 7.whose weight is equal to the idle time diﬀerence, For i = 1 we get two ‘‘stations’’ with ‘‘cycleto form a bin with smaller capacity as required. times’’ c1 = 12 and c2 = 48. The tasks 5–10 are as- Following the destructive improvement ap- signed to ‘‘station’’ 2 ðS 02 ¼ f5; . . . ; 10gÞ and task 1proach, LC4 is given by the minimal trial value c to ‘‘station’’ 1 ðS 01 ¼ f1gÞ. The two bins have resid-for which 2Bin-F has a positive outcome for all ual capacities j1 = 6 and j2 = 19, and the tasks 2,possible subdivisions of [1, m] into two aggregate 3, and 4 remain. A feasible solution of 2Bin-F is‘‘stations’’ [1, i] and [i + 1,m], i.e., for i = 1, . . ., given by the sets S 00 ¼ f2g and S 00 ¼ f3; 4g. 1 2m À 1. Example. We consider a SALBP-2 instance with i = 2. c1 ¼ 24; c2 ¼ 36; S 01 ¼ f1; 3; 4g; S 02 ¼ f6; 8;the precedence graph of Fig. 3 and m = 5. With 9; 10g; j1 ¼ 8; j2 ¼ 15; S 00 ¼ f2g; S 00 ¼ f5; 7g. 1 2 i = 3. c1 = 36, c2 = 24, S 01 ¼ f1; . . . ; 7g; S 02 ¼ 6 6 4 f8; 9; 10g; no residual problem. 1 2 7 i = 4. c1 = 48, c2 = 12, S 01 ¼ f1; . . . ; 9g; S 02 ¼ f10g; 2 9 5 8 9 10 no residual problem. 5 5 4 5 3 4 5 6 Since no infeasibility is found, LC4 = 12 cannot be Fig. 3. Precedence graph. disproved as a feasible cycle time.Table 7Heads and tails of tasks for c = 11 and c = 12j 0 1 2 3 4 5 6 7 8 9 10 11pj (11) 0 0:54 0:54 0:45 0:45 0:36 0:45 0:36 0:18 0:81 0:45 0aj (11) 0 0 1 0 0:45 1:45 2 1:54 3:18 4 5 5:45nj (11) 5 4 3 4 3:36 3 2:18 2:18 2 1 0 0pj (12) 0 0.5 0.5 0:41 6 0:41 6 0:33 0:41 6 0:33 0:1 6 0.75 0:41 6 0aj (12) 0 0 0.5 0 0:41 6 1:33 2 1 3 3:1 6 4 4:41 6nj (12) 4:91 6 3:58 3 2:33 3:41 6 3 2:41 6 2 2 1.75 1 0 0Ej (12) – 1 1 1 1 2 3 2 4 4 5 –Lj (12) – 1 3 2 2 3 3 3 4 4 5 –
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 6814.2. Exact solution procedures for SALBP-2 to c + 1. The search stops with the optimal cycle time UC when UC = LC. While a large variety of exact solution proce-dures exist for SALBP-1, only a few have been Two further search methods are the Fibonaccideveloped which directly solve SALBP-2. Most re- binary search and the upper bound search. Com-search has been devoted to considering search putational experiments indicate that the binarymethods which are based on repeatedly solving search is the best compromise in case of restrictedSALBP-1. computation time (cf. Scholl, 1999, p. 256). When the SALBP-F instances are solved heuris-4.2.1. Iterated search methods tically, the whole search procedure becomes a heu- Following our argumentation in Section 2, ristic (cf. Section 5.1).SALBP-2 (minimize c for given m) can be formu-lated as the problem of ﬁnding the smallest cycletime c for which the corresponding SALBP-F in- 4.2.2. Direct solution approachesstance (m, c) has a feasible solution. Hence, In recent years, only two B&B proceduresSALBP-2 can be solved by successively solving which directly solve SALBP-2 have beenSALBP-F instances with m stations and various developed.trial cycle times. The latter are restricted to an • Scholl (1994) proposes the task-oriented B&Binterval [LC, UC] which is bounded by a lower procedure TBB-2 which is based on a successiveand an upper bound on the cycle time. While lower reduction of the precedence graph to a stationbounds may be computed by means of the argu- graph (for extensions see Scholl, 1999, Chapterments described in Section 4.1, upper bounds are 4.2.3). At the beginning, the precedence graph isderived from any heuristic solution for SALBP-2 complemented by an initial station graph contain-(cf. Section 5). ing an empty node Nk for the stations k = 1, . . ., m. Any exact procedure for SALBP-1 (cf. Section The nodes N1 and Nm serve as ﬁctitious source and3) can easily be modiﬁed for SALBP-F instances sink node of the combined graph, respectively.(m, c) by considering the given cycle time c and Each task which is assigned to a station k byby excluding (fathoming) all solutions which have branching, preﬁxing or another logical test isa larger number of stations than m. This is merged into the station node Nk. A complete solu-achieved by setting UM = m + 1. tion is obtained when only the station graph re- The eﬃciency of solving a SALBP-2 instance mains. The graph representation of partialdepends on the sequence in which the trial cycle solutions allows for applying logical tests which re-times are examined. Therefore, several search duce the B&B tree greatly.methods have been proposed and tested by, e.g., • Klein and Scholl (1996) develop an adaptationDar-El and Rubinovitch (1979), Hackman et al. of SALOME-1 to SALBP-2 which is called SAL-(1989), Klein and Scholl (1996). Two common OME-2. It also utilizes the LLBM, a bidirectionalmethods are the following: branching strategy, and several dominance and reduction rules which have to be modiﬁed to ﬁt• Lower bound search. Starting with the lower the conditions of SALBP-2. A distributed version bound LC, the trial cycle time c is successively of SALOME-2 is examined by Bock (2000, Chap- increased by 1 until the respective SALBP-F ter 6.2). instance (m, c) is feasible. In opposite to SALOME-1, more than two• Binary search. The search interval [LC, UC] is classes of subproblems have to be considered in successively subdivided into two subintervals each node of the enumeration tree depending on by choosing the mean element c = b(LC + the current value of the local lower bound LLC UC)/2c. If SALBP-F is feasible for c, the upper on the cycle time. After examining all maximal sta- bound UC is set to the maximal station time in tion loads feasible for the lower bound cycle time the corresponding solution. Otherwise, LC is set LLC, its value is increased such that at least one
    • 682 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693further load becomes feasible. This process of examined by Zapfel (1975, p. 53), Klenke (1977, ¨branching a node terminates when a feasible com- p. 47) as well as Scholl and Voß (1995). A similarplete solutions with cycle time LLC has been approach is given for a cost-oriented problem byfound or no further load is available. Rosenblatt and Carlson (1985). Computational experiments indicate that SAL- The lower bound search of Scholl and VoßOME-2 gets much better results than TBB-2 when (1995) starts with a list L of combinationsapplied to standard benchmark data sets (cf. (m, LC (m)) with m 2 [mmin, mmax]. That is, for eachScholl, 1999, p. 258). Comparing SALOME-2 with feasible value of m the smallest possible cycle timea binary search applying SALOME-1 to each trial (given by a lower bound LC (m); cf. Section 4.1) iscycle time shows that the search method is compet- considered. In case of LC(m) > cmax, m is removeditive (cf. Klein and Scholl, 1996). This gives a cer- from the station interval. If LC (m) < cmin, we havetain foundation for the concentration on ﬁnding to use LC (m) = cmin. The (m, c)-combinations in Leﬀective procedures for SALBP-1 in the past 50 are sorted in non-decreasing order of their lineyears though SALBP-2 is a problem which may capacities T = m Æ c. The search examines theeven have the greater practical relevance, because SALBP-F instances in this order, where ties areit arises whenever an existing line has to be rebal- broken in favor of the smaller m because the cor-anced, while SALBP-1 is relevant mainly in case of responding SALBP-F instances are often easierthe ﬁrst installation of a line. to solve than those with larger m. If the combina- tion (m, c) is identiﬁed as being infeasible, m is re-4.3. Search methods for SALBP-E moved from the station interval in case of c = cmax. Otherwise, the next possible cycle time As is the case with SALBP-2, instances of the c 0 (normally c 0 : = c + 1) is deﬁned for m and themore general SALBP-E may be solved by some resulting combination is sorted into the list L. Thissearch method. Such a method has to ﬁnd a feasi- process continues until a feasible (=optimal) com-ble combination (m, c) of the number m of stations bination is found.and the cycle time c such that the line eﬃciency is Examination of the SALBP-F instances may bemaximized or, equivalently, the required line done by applying a (correspondingly modiﬁed)capacity T = m Æ c is minimized (cf. Section 2). SALBP-1 or SALBP-2 procedure. The latter have A SALBP-E instance is deﬁned by an interval the advantage that larger increments than 1 may[cmin, cmax] of possible cycle times and/or an inter- be identiﬁed accelerating the search (cf. Scholl,val [mmin, mmax] of possible numbers of stations. 1999, Chapter 4.3). Furthermore, they more oftenThe intervals have to observe the feasibility condi- ﬁnd feasible solutions in case of restricted compu-tions T = m Æ c P tsum and cmin P tmax as well as tation time (cf. Scholl, 1999, p. 272).space and productivity constraints. Procedures directly solving SALBP-E are not An obvious solution procedure for SALBP-E available. This may be due to the diﬃculty to di-consists of considering all possible SALBP-F in- rect the search in promising regions of the solutionstances (=(m, c)-combinations with m 2 [mmin, space when neither m nor c is ﬁxed.mmax] and c 2 [cmin, cmax]) and examining their fea-sibility. A feasible combination with minimal valueof T is optimal. This may be done with modiﬁed 5. Heuristic approaches for diﬀerent versions ofprocedures for SALBP-1 or SALBP-2, respec- SALBPtively. However, usually a lot of (m, c)-combina-tions exist. Furthermore, the SALBP-F instances A large variety of heuristic approaches to diﬀer-to be considered are NP-complete. Thus, the out- ent versions of SALBP have been proposed in thelined approach is usually very ineﬃcient. last decades. While constructive procedures con- In order to ﬁnd an optimal (m, c)-combination structing one or more feasible solution(s) weremore eﬃciently, search methods similar to those developed until the mid nineties, improvementdeﬁned for SALBP-2 (Section 4.2) have been procedures using metastrategies like tabu search
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 683and genetic algorithms have been in the focus of For the rule MaxPW, this procedure is calledresearchers in the last decade. ranked positional weight technique by Helgeson and Birnie (1961).5.1. Constructive procedures • Task-oriented procedures. Among all available tasks, one with highest priority is chosen and The majority of constructive procedures have assigned to the earliest station to which it isbeen proposed for SALBP-1 and are based on pri- assignable.ority rules, others are restricted enumerative pro- Depending on whether the set of available taskscedures. The most recent comprehensive surveys is updated immediately after assigning a task orof those approaches are given by Talbot et al. after assigning all currently available tasks,(1986) and Scholl (1999, Chapter 5.1.1). Further- task-oriented methods can be subdivided intomore, see Boctor (1995) and Ponnambalam et al. immediate-update-ﬁrst and general-ﬁrst-ﬁt(2000). methods (cf. Wee and Magazine, 1982; Hack- man et al., 1989).5.1.1. Priority rule based procedures for SALBP-1 Those procedures use priority values computed Theoretical analyses show that both schemesfor the diﬀerent tasks based on the task times and obtain the same solution when the used prioritythe precedence relations given. Some of the most rule is strongly monotonous, i.e., the priority valueeﬀective ones are given in Table 8 (cf. Talbot of any task j is smaller than that of each predeces-et al., 1986; Hackman et al., 1989; Scholl and sor h 2 Pj. This is, e.g., true for MaxPW, MaxF,Voß, 1996). In any case, the tasks are sorted and MaxCPW (cf. Scholl, 1999, p. 182). Computa-according to non-increasing priority values to get tional experiments indicate that, in general, sta-a priority list. tion-oriented procedures get better results than By analogy with exact solution procedures (cf. task-oriented ones though no theoretical domi-Section 3.2), two construction schemes are relevant nance exists (cf. Scholl and Voß, 1996). This sup-for priority rule based approaches. They diﬀer ports the analogous ﬁnding in case of exactwith respect to the manner in which the tasks to procedures (cf. Section 3.6).be assigned are selected out of the set of available These classical priority rule based procedurestasks (cf. Talbot et al., 1986; Hackman et al., 1989; work unidirectionally in forward direction andScholl and Voß, 1996): construct a single feasible solution. Improvements are obtained by following approaches.• Station-oriented procedures. They start with the • Flexible bidirectional construction. The stations ﬁrst station (k = 1). The following stations are to be loaded are considered in forward and back- considered successively. In each iteration, a task ward direction, simultaneously (Scholl and Voß, with highest priority which is assignable to the 1996). That is, a station-oriented procedure con- current station k is selected and assigned. When siders the earliest and the latest unloaded station station k is loaded maximally, it is closed, and at a time. Besides selecting a (forward or backward the next station k + 1 is opened. assignable) task by some priority rule the (earliest or latest) station to be considered next is chosen.Table 8 Task-oriented procedures simultaneously considerPriority values forward and backward available tasks and alwaysName Priority value choose the one with highest priority. Both ap- proaches require deﬁning reversed priority rulesMaxT Task time tj PMaxPW Positional weight pwj ¼ tj þ h2F Ã th (cf. Scholl, 1999, p. 184).MaxF Ã Number of followers j F j j j • Dynamic priority rules iteratively adapt the prior-MaxTL Task time over latest station tj/Lj ities depending on the current partial solutions (cf.MaxTS Task time over slack tj/(LjÀEj + 1) P Boctor, 1995; Scholl and Voß, 1996). For example,MaxCPW Cumulated positional weight pwÃ ¼ tj þ h2F Ã pwÃ j j h MaxTS can be applied dynamically (in a uni- or
    • 684 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693bidirectional procedure) by modifying the earliest Nevertheless, it may require considerable com-and latest stations according to the assignments putation times, because it has to examine all possi-made. ble station loads of a current subproblem.• Multi-pass heuristics repeatedly apply diﬀerent or Therefore, Gehrlein and Patterson (1975, 1978)stochastic priority rules in order to ﬁnd several propose a modiﬁcation of the procedure which ac-solutions the best of which is taken (cf. Talbot et cepts a load for the currently considered station ifal., 1986; Arcus, 1966; Bonney et al., 1976; Scho- a certain amount of idle time is not exceeded. Theﬁeld, 1979). accepted portion of idle time depends on the bal-• Flexible rule application. Such procedures try to ance delay time (total available idle time) for theidentify priority rules best suited to solving a cer- theoretical minimum number LM1 of stationstain problem instance. This is done randomly, on and can be controlled by a parameter.the basis of experiences with former rule applica- An extension of the Hoﬀmann heuristic whichtions and by exploiting problem structures (cf., works bidirectionally is proposed by Fleszar ande.g., Tonge, 1965; Bennett and Byrd, 1976; Go ¨rke Hindi (2003). This heuristic is combined with aand Lentes, 1976; Raouf et al., 1980). number of bound arguments and reduction tech-• Reduction techniques. Baybars (1986b) proposes niques (cf. Sections 3.1 and 3.4) and, thus, has be-a priority based procedure which involves heuristi- come one of the most eﬀective available heuristicscally reducing the problem size by some logical for SALBP-1.tests. Furthermore, see Tonge (1960), Freeman • Truncated enumeration. Each B&B (or DP) pro-and Swain (1986), and Fleszar and Hindi (2003). cedure can be applied as a heuristic by adding• Combined solutions. As stated in Section 3.5, heuristic fathoming rules or imposing a time limit.SALBP-1 can be interpreted as a shortest path For example, subproblems may be fathomed if itproblem with exponential numbers of nodes and is not likely that the current incumbent solutionarcs. Each feasible solution can be represented by can be improved. This may be examined by com-a path in such a graph. Therefore, Pinto et al. paring the average idle time of already loaded sta-(1978) describe a two-stage solution approach. In tions with the average idle time being available inthe ﬁrst step, a number of feasible solutions is an improved solution to be found. Furthermore,determined by a multi-pass heuristic. These solu- the number of descending nodes chosen fortions are used to construct a subgraph of the com- branching in a current subproblem can be re-plete graph in the second step of the procedure. stricted or partial solutions can be completed heu-For this subgraph, a shortest path problem is ristically (cf. Hackman et al., 1989, Scholl, 1999, p.solved. That is, the outlined approach tries to com- 126).bine parts of several feasible solutions in order toobtain an improved complete solution. 5.1.3. Search methods for SALBP-2 and SALBP-E As already mentioned in Sections 4.2 and 4.3,5.1.2. Incomplete enumeration procedures solutions for SALBP-2 or SALBP-E may be ob- A class of heuristic procedures (for SALBP-1 or tained by iteratively solving SALBP-F instancesSALBP-2) consists of incomplete enumeration through SALBP-1 procedures. If heuristic proce-techniques. Generally, such methods are based dures are applied within such search methods,on exact enumeration schemes (cf. Section 3), one gets heuristic solutions for SALBP-2 orwhich are modiﬁed by heuristically restricting the SALBP-E. Respective procedures are described,search space. among others, by Hackman et al. (1989), Scholl• Heuristic of Hoﬀmann (1963). The procedure and Voß (1996), and Ugurdag et al. (1997).works unidirectionally in a station-oriented man-ner. In each iteration k = 1,2, . . . a load with min- 5.2. Genetic algorithmsimal idle time is generated for station k. That is, asingle branch of a station-oriented B&B procedure Genetic algorithms (GA) are a general conceptis constructed. for solving complex optimization problems which
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 685is based on manipulating a population of solutions C1 = h1, 2j3, 3, 4, 4, 5, 5, 6, 7i and C2 = h2, 3j1, 1, 2,by genetic operators like selection, recombination 4, 3, 4, 5, 6i. Applying a one-point crossover whichand mutation (cf. Goldberg, 1989). In order to cuts both chromosomes after the second task andadapt the general approach to SALBP (or a gener- combines them crosswise yields C3 = h1, 2, 1, 1, 2,alized ALBP), two main diﬃculties have to be 4, 3, 4, 5, 6i and C4 = h2, 3, 3, 3, 4, 4, 5, 5, 6, 7i, tworesolved: highly infeasible solutions.• For manipulating solutions by means of genetic • Order encoding. The chromosomes are deﬁnedoperators, they have to be encoded in form of as precedence feasible sequences of tasks (cf. Leuso-called chromosomes each of which consists of et al., 1994; Ajenblit and Wainwright, 1998; Sab-a sequence of genes. Several encoding schemes uncuoglu et al., 2000; Thilakawardana et al.,are possible each having pros and cons concerning special issue). They are decoded to feasiblethe type of applicable genetic operators. In partic- SALBP-1 solutions, e.g., by applying the task- orular, pertaining feasibility of manipulated solu- station-oriented construction scheme (cf. Sectiontions is a critical issue. 3.2) following the encoded sequence of tasks.• The objective function of SALBP-1 is not opera- However, the mapping is not unique, because sev-tional for guiding the search to promising parts of eral feasible sequences may lead to the same solu-the solution space, because it does not give a strong tion. Furthermore, several solutions may bedistinction between the solutionsÕ ﬁtness: Usually derived from one sequence by constructing solu-there are a few optimal solutions which require tions in diﬀerent directions (forwards, backwards,the minimal number m* of stations and many oth- bidirectionally; cf. Ajenblit and Wainwright,ers ‘‘around them’’ most of which may require 1998).m* + 1 (or some more) stations. That is, a popula- The recombination of chromosomes C1 and C2tion might consist of solutions all having the same is usually performed by a two-point order crosso-or a few diﬀerent objective value(s) such that select- ver, which cuts each of them into three parts (cf.ing the most promising ones is not obvious. This Leu et al., 1994). One oﬀspring C3 keeps the ﬁrstproblem is usually less relevant for SALBP-2 or and the last part of C1. The middle part of the se-SALBP-E. Because the GA procedures proposed quence is ﬁlled by adding the missing tasks in thefor diﬀerent SALBP versions and generalized prob- order in which they are contained in C2. The otherlems in the literature do not diﬀer in many aspects, oﬀspring C4 is built analogously based on the ﬁrstwe summarize the approaches concerning their res- and the last part of C2 and added tasks of C1. Botholution of the above mentioned diﬃculties. oﬀspring are feasible due to ﬁlling in the middle part in a precedence feasible order. Further cross-5.2.1. Encoding schemes and genetic operators over and mutation operators are described by• Standard encoding. The chromosome is deﬁned Rubinovitz and Levitin (1995) and Thilakawar-as a vector containing the labels of the stations dana et al. (special issue).to which the tasks 1, . . ., n are assigned (Anderson Example. Let C1 = h1, 2, 3j4, 5, 6, 7j8, 9, 10i andand Ferris, 1994, Kim et al., 2000). When standard C2 = h3, 1, 2j4, 7, 5, 6j8, 9, 10i be two feasible se-crossovers or mutations are applied to such chro- quences for our example instance. Decoding themmosomes, the resulting solutions are often infeasi- with the task-oriented construction scheme (withble. This aspect must be dealt with by penalizing maximal load rule) they represent the solutionsinfeasibilities or rearranging the solution by cer- ({1}, {2,7}, {3,4}, {5,6}, {8}, {9}, {10}) with 7 sta-tain heuristic strategies. Kim et al. (2000) achieve tions and ({3,4}, {1,5}, {2,7}, {6,8}, {9}, {10}) withpopulations without infeasible solutions by decod- 6 stations. Cutting them as indicated by verticaling chromosomes using a procedure similar to that lines and recombining them by the two-pointof Helgeson and Birnie (1961). crossover results in C3 = h1, 2, 3, 4, 7, 5, 6, 8, 9, 10i Example. For our SALBP-1 example with the and C4 = h3, 1, 2, 4, 5, 6, 7, 8, 9, 10i. Though the se-precedence graph of Fig. 1 and c = 10, two chro- quences are diﬀerent from the mates, C3 (C4) corre-mosomes representing feasible solutions may be sponds to the same solution as C1 (C2). As a
    • 686 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693consequence, there is no real change in genetic • Indirect encodings. Further encodings representinformation. the solutions in an indirect manner by coding pri-• Group encoding. The encoding of each solution ority values of tasks (cf. Goncalves and Almeida,consists of two parts (cf. Falkenauer and Del- 2002) or a sequence of priority rules and corre-chambre, 1992, Falkenauer, 1996, 1997; Rekiek sponding construction schemes to be applied foret al., 2001, 2002a): The ﬁrst one is task-oriented generating (decoding) the solutions (cf. Bautistaand identical to the standard encoding. The sec- et al., 2000; Baykasoglu et al., 2002). This hasond one is group-oriented, i.e., it contains a the advantage that feasibility can be achieved with-gene for each station. The genetic operators are out diﬃculties. Furthermore, local search heuris-only applied to the second part in order to get tics may be applied to improve on the currenta more direct inﬂuence on the structure of a solution as a means of increasing the ﬁtness, i.e.,solution. For reproduction a modiﬁed two-point only local optima are contained in the populationcrossover is used. The middle part of the sec- (cf. Goncalves and Almeida, 2002).ond parent C2 is injected into the ﬁrst parent C1 An encoding which is based on the degree ofafter the ﬁrst crossing position leading to separation of two adjacent tasks h and j in theduplicates of tasks. Each original station of C1 precedence graph (0 = assigned to the same sta-containing such duplicates and/or tasks which vio- tion, 1 = assigned to two adjacent stations, 2 = as-late precedence constraints are removed. Now signed to non-adjacent stations) is proposed bysome tasks may be missing completely and are Watanabe et al. (1995). For reproduction a simplereassigned by some heuristic (priority rule based) 1-point crossover is used. The possible infeasibilityprocedure. The mutation operator randomly de- of solutions is handled via the ﬁtness function (seeletes some stations and reassigns the tasks below).accordingly. Example. We consider chromosomes C1 = h1, 2, 5.2.2. Fitness functions3, 3, 4, 4, 5, 5, 6, 7:1, 2, 3j4, 5j6, 7i for a solution with In order to get a more diversiﬁed evaluation of7 stations labeled by numbers 1–7 and C2 = a solutionÕs ﬁtness than by using the number ofhb, c, a, a, b, d, c, d, e, f:a, bjc, dje, fi for a solution stations or the cycle time required, several ap-with 6 stations labeled by lower case letters a–f. proaches have been presented. They are based onThe colons separate the two parts of the enco- measuring the distribution of station times (verti-dings; the vertical lines indicate the crossing posi- cal balancing; cf. Section 2):tions, respectively. Injecting hc, di into C1 resultsin h1,2/c, 3,3, 4, 4/d, 5/c, 5/d, 6, 7:1, 2, 3, c, d, 4,5, 6,7i • Falkenauer and Delchambre (1992) and Falk-where the tasks 2, 6, 7, and 8 are contained twice: enauer (1996) deﬁne the ﬁtness f (S) of anS1 = {1}, S2 = {2}, S3 = {3,4}, Sc = {2, 7}, Sd = SALBP-1 solution S = (S1, . . ., SUM) which{6, 8}, S4 = {5, 6}, S5 = {7, 8}, S6 = {9}, S7 = requires UM stations as a mean score measur-{10}. Deleting the stations 2, 4, and 5 results in ing the squared average relative deviation fromh1,c,3, 3, ?, d, c, d, 6, 7:1, 3, c, d, 6, 7i with task 5 as- a full station load:signed not any longer. Reassigning it by the task- P UM 2oriented construction scheme leads to h1, c, 3, 3, x, ðtðS k Þ=cÞ k¼1d, c, d, 6, 7:1, 3, x, c, d, 6, 7i which requires an addi- f ðSÞ ¼ : ð6Þtional station x and corresponds to the line bal- UMance: S1 = {1}, S3 = {3, 4}, Sx = {5}, Sc = {2, 7}, • Sabuncuoglu et al. (2000) use the following ﬁt-Sd = {6, 8}, S6 = {9}, S7 = {10}. ness function, where tSmax denotes the maximal A similar group oriented encoding is used by station time (tSmax 6 c). The ﬁrst part aims atSuresh et al. (1996) who apply a one-point crosso- reducing the imbalance, the second one at min-ver with subsequent rearrangements of the solu- imizing the number of stations (SALBP-1). Thetions to achieve feasibility. factor 2 is set arbitrarily.
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 687 vﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ uUM straints or further objectives (cf. Bautista et al., uP u ðtS max À tðS k ÞÞ2 2000; Ponnambalam et al., 2000) and may be com- tk¼1 f ðSÞ ¼ 2 bined with other heuristics in hybrid approaches UM (cf. Goncalves and Almeida, 2002; Falkenauer, 1996). P UM ðtS max À tðS k ÞÞ 5.3. Local search and metastrategies þ k¼1 : ð7Þ UM Local search (or improvement) procedures try• Bautista et al. (2000) propose the following ﬁt- to improve a given feasible solution by iteratively ness function for SALBP-1 which considers transforming it into other feasible solutions. Such the degree of imbalance in the ﬁrst term and transformations are referred to as moves. Solutions the absolute deviation of the number UM of which may be obtained from a given solution S by stations used to the lower bound LM1: qﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ means of a single move are called neighbouring PUM 2 k¼1 ðc À tðS k ÞÞ solutions or neighbourhood of S. Traditionally, lo- f ðSÞ ¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃ þ LM1 À UM: ð8Þ cal search heuristics try to ﬁnd a sequence of c Á UM moves which produces a trajectory of successively• Anderson and Ferris (1994) construct a GA for improved solutions and terminate in a local opti- SALBP-2 and use a ﬁtness function which sums mum which might be far from optimality. up the maximal station time (deﬁning the real- This diﬃculty is overcome by modern meta- ized cycle time) and a penalty term for prece- strategies like tabu search (TS; cf. Glover and Lag- dence violations. In order to minimize the una, 1997) and simulated annealing (SA; cf. Aarts cycle time, the ﬁtness function is to be mini- and Korst, 1989). In the following, we discuss mized, too. The GA of Watanabe et al. (1995) the main components of such procedures when ap- is also designed for SALBP-2 and takes the line plied to SALBP-1 and SALBP-2. eﬃciency reduced by a penalty term for infeasi- ble surplus stations as ﬁtness values. 5.3.1. Moves and neighborhood deﬁnition All local search procedures for SALBP are based on shifts and swaps (cf. Moodie and Young,5.2.3. Further components and computational 1965; Rachamadugu and Talbot, 1991), which canresults be explained using the following notation: Besides the encoding schemes and the ﬁtnessfunctions, all GA procedures proposed for LPj: latest station to which a predecessor of task jSALBP-1 or SALBP-2 in the literature (see the ref- is currently assigned.erences given above) apply standard approaches ESj: earliest station to which a successor of task j isfor generating the initial population, setting cross- currently assigned.over and mutation probabilities, etc. Unfortu-nately, the computational testing of most GA Two types of moves are relevant in local searchhas been done ignoring existing test beds and procedures for SALBP:state-of-the-art solution methods or using the mostsimple test data available such that most results • A shift (j, k1, k2) describes the movement of aare not meaningful. At least, GA seem to be com- task j from station k1 to station k2 withpetitive to the best known constructive methods k1 5 k2. This move is feasible if k2 2 [LPj, ESj].(cf. Sabuncuoglu et al., 2000; Thilakawardana et al., • A swap (j1, k1, j2, k2) exchanges tasks j1 and j2,special issue) and some type of tabu search (cf. which are not related by precedence, betweenGoncalves and Almeida, 2002; Baykasoglu et al., diﬀerent stations k1 and k2. This move is feasi-2002). Furthermore, they allow for including addi- ble if the two corresponding shifts (j1, k1, k2)tional problem characteristics like assignment con- and (j2, k2, k1) are feasible.
    • 688 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 In order to restrict our presentation to swap Intensiﬁcation and diversiﬁcation. In order tomoves, we interpret shifts as swaps which ex- intensify the search in certain regions or to directchange a real task j1 and a ﬁctitious task j2 with the search into yet unvisited parts of the solutionzero operation time and no precedence relations. space, a frequency based memory is used. In this Two basic local search strategies are best ﬁt memory, the relative number of iterations, any(ﬁnd and perform the most improving move) task j belongs to any station k, is stored (denotedand ﬁrst ﬁt (perform the ﬁrst improving move as zjk). Several phases of the search are either usedfound). for collecting frequency information, ﬁxing tasks j in a station k where they have a high zjk value5.3.2. Tabu search for SALBP-2 (intensiﬁcation) or avoiding that tasks j reenter a An elementary TS procedure for SALBP-2 is station k where they have a high zjk valueproposed by Heinrici (1994). Scholl and Voß (diversiﬁcation).(1996) develop and thoroughly examine a TS pro- Conﬂict management. A conﬂict occurs when nocedure with a lot of optional components. We re- admissible move is available, i.e., the attributesstrict the presentation to the essential features: stored in TL prevent all possible moves from being Initial solution. It may be determined by any performed. Among several strategies, Scholl andconstructive procedure for SALBP-2 or randomly Voß (1996) recommend one which systematically(cf. Section 5.1). Experiments show that the qual- moves predecessors and successors away from crit-ity of the initial solution is not very important ical tasks (those assigned to stations with maximalfor the overall solution quality (cf. Scholl, 1999, station time).p. 263). Computational experiments of Scholl and Voß Local search strategy. The best ﬁt strategy is ap- (1996) show that the TS procedure outlined aboveplied, i.e., in each iteration, the most improving or gets much better results than constructive proce-least deteriorating (if no improving is available) dures. In particular, it is well suited to ﬁnding im-move is performed. proved initial upper bounds for B&B procedures Tabu management. In order to avoid cycling, at- (see Section 4.2) such that their performance is im-tributes of moves just performed are set tabu for a proved. A similar result has been obtained bynumber of iterations TD (=tabu duration) and Scholl et al. (1997) for the related bin packingstored in a tabu list TL (recency based memory). problem.When a swap (j1, k1, j2, k2) is performed the attri- An extension of the described TS procedure to abutes (j1, k1) and (j2, k2) are added to TL such that mixed-model balancing problem with additionalremoving j1 to k1 and j2 to k2 is temporarily forbid- objectives is given by Pastor et al. (2002).den for TD iterations. Since TD is the most criticalparameter concerning the performance of (static) 5.3.3. Tabu search for SALBP-1TS, diﬀerent strategies have been tested by Scholl Developing a TS procedure for SALBP-1 is notand Voß (1996) showing that a dynamic modiﬁca- as straightforward as in case of SALBP-2. This istion of TD (randomly or systematically) is better due to the fact that only three situations can occurthan using a ﬁxed value. Furthermore, a moving after a move (cf. our discussion at the beginninggap strategy which cyclically activates only parts of Section 5.2): (1) the number m of stations is un-of the tabu list at a time is recommendable. In case changed (swapping two real tasks), (2) an additionalof a move which leads to an improved overall solu- station m is required (shirting a task in an empty sta-tion, the tabu status is ignored (global aspiration tion), (3) one station is empty (shifting the only taskcriterion). in this station to another one). No problem arises in Stopping criteria. The search is stopped when- case (3). However, in most iterations a large numberever a prespeciﬁed number of iterations have been of (1) or (2) moves have to be evaluated which haveperformed, a prespeciﬁed time limit is reached or only two diﬀerent objective function values m andthe solution is identiﬁed as being optimal by means m + 1. In this situation ﬁnding a promising searchof lower bounds. direction is rather complicated.
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 689 Scholl and Voß (1996) conclude that applying solutions. The second stage improves on the initialtheir TS procedure for SALBP-2 within a lower solution by a simplex-like improvement procedurebound search (called dual strategy; cf. Section solving a relaxation of the mathematical model4.2) is the best way out of this dilemma. with the nice property of having only integer ex- Chiang (1998) proposes a TS procedure similar treme points.to the SALBP-2 approach of Scholl and Voß(1996) but uses a surrogate objective function that 5.3.6. Ant colony optimization approachmaximizes the sum over the squared station times. Bautista and Pereira (2002) present an ant algo-While minimizing the number of stations, it addi- rithm for SALBP-1 which is based on priority ruletionally favors solutions containing some heavily based procedures. McMullen and Tarasewichloaded stations to those solutions having more (2003) propose an ant algorithm for a generaliza-smoothly loaded ones. This eﬀect successively di- tion of SALBP with respect to parallel stations,rects the search to solutions where saving a station stochastic task times, multiple objectives andin a single move is probable. mixed-model production. Computational experiments indicate that bothapproaches are successful on principle. However,Chiang (1998) reports only limited results for thesimplest data set on hand which are not very 6. Conclusions and further researchmeaningful. Scholl and Voß (1996) ﬁnd out thattheir dual strategy is competitive to exact proce- The survey given shows that research has madedures (applied as a restricted enumeration) in case signiﬁcant algorithmic developments in solvingof short computation times but is not superior to simple assembly line balancing problems (SALBP).SALOME-1 in ﬁnding good feasible solutions Though SALBP is a class of NP-hard optimizationquickly. In opposite to SALBP-2, the quality of problems, eﬀective exact and heuristic proceduresthe initial solution seems to be important for the are available which solve medium-sized instancesquality of the best solution found. in a quality suﬃcient for use in practice. However, A further TS procedure for SALBP-1 is pro- further algorithmic improvement is necessary forposed by Lapierre et al. (this issue) and tested on solving large-scale instances.an arbitrary subset of the test problems available. More recently, assembly line balancing researchFor these instances it compares favorably with evolved towards formulating and solving general-ChiangÕs approach. ized problems (GALBP) with diﬀerent additional characteristics such as cost functions, equipment5.3.4. Simulated annealing (SA) procedures selection, paralleling, U-shaped line layout and Heinrici (1994) proposes an SA procedure for mixed-model production. Reviewing the literatureSALBP-2 which is based on shifts and swaps. An on GALBP (cf. Becker and Scholl, this issue)SA approach for a stochastic variant of SALBP- shows that a lot of relevant problems have been1 is proposed by Suresh and Sahu (1994). McMul- identiﬁed and modelled but development oflen and Frazier (1998) propose a SA procedure for sophisticated solution procedures has just begun.a generalization of SALBP-1 with respect to paral- Thus, additional research is necessary to adoptlel stations, stochastic task times and alternative state-of-the-art solution concepts for SALBP toobjectives. the variety of GALBP. Furthermore, standardized and realistic test beds are required for testing and5.3.5. LP-based improvement procedure comparing methodical enhancements. Ugurdag et al. (1997) develop a two-stage heu- Despite of having available eﬀective solutionristic for SALBP-2 (with additional vertical bal- procedures for diﬀerent assembly line balancingancing) which is based on an integer program. problems their use in practice is limited. BesidesThe procedure starts with a priority rule based imposing restrictive assumptions for deﬁning com-search method that generates one or more initial putationally tractable models, this is due to a lack
    • 690 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693of commercial software that includes state-of-the- Berger, I., Bourjolly, J.-M., Laporte, G., 1992. Branch-and-art solution procedures. bound algorithms for the multi-product assembly line balancing problem. European Journal of Operational Research 58, 215–222. Betts, J., Mahmoud, K.I., 1989. A method for assembly lineReferences balancing. Engineering Costs and Production Economics 18, 55–64.Aarts, E.H.L., Korst, J.H.M., 1989. Simulated annealing and Bock, S., 2000. Modelle und verteilte Algorithmen zur Planung Boltzmann machines: A stochastic approach to combinato- getakteter Fließlinien: Ansatze zur Unterstutzung eines ¨ ¨ rial optimization and neural computing. Wiley, Chichester. eﬃzienten Mass Customization, Gabler, Wiesbaden.Ajenblit, D.A., Wainwright, R.L., 1998. Applying genetic Bock, S., Rosenberg, O., 1998. A new distributed fault-tolerant algorithms to the U-shaped assembly line balancing prob- algorithm for the simple assembly line balancing problem. lem. In: Proceedings of the 1998 IEEE International In: Kischka, P. et al. (Eds.), Operations Research Proceed- Conference on Evolutionary Computation, Anchorage, ings 1997. Springer, Berlin, pp. 474–480. AK, pp. 96–101. Bockmayr, A., Pisaruk, N., 2001. Solving assembly lineAlvim, A.C.F., Ribeiro, C.C., Glover, F., Aloise, D.J., 2003. A balancing problems by combining IP and CP. In: Proceed- hybrid improvement heuristic for the one-dimensional bin ings of the 6th Annual Workshop of the ERCIM Working packing problem. Working Paper, Catholic University of Group on Constraints, Prague, Czech Republic. Rio de Janeiro, Brazil. Boctor, F.F., 1995. A multiple-rule heuristic for assembly lineAnderson, E.J., Ferris, M.C., 1994. Genetic algorithms for balancing. Journal of the Operational Research Society 46, combinatorial optimization: The assembly line balancing 62–69. problem. ORSA Journal on Computing 6, 161–173. Bonney, M.C., Schoﬁeld, N.A., Green, A., 1976. Assembly lineArcus, A.L., 1966. COMSOAL: A computer method of balancing and mixed model line sequencing. In: Proceedings sequencing operations for assembly lines. International of the Fifth INTERNET World Congress, Birmingham, pp. Journal of Production Research 4, 259–277. 112–121.Balas, E., 1965. An additive algorithm for solving linear Buxey, G.M., Slack, N.D., Wild, R., 1973. Production ﬂow line programs with zero–one variables. Operations Research system design––A review. AIIE Transactions 5, 37–48. 13, 517–546. Chiang, W.-C., 1998. The application of a tabu searchBautista, J., Pereira, J., 2002. Ant algorithms for assembly line metaheuristic to the assembly line balancing problem. balancing. In: Dorigo, M., Di Caro, G., Sampels, M. (Eds.), Annals of Operations Research 77, 209–227. Ant Algorithms, Third International Workshop, ANTS Dar-El, E.M., Rubinovitch, Y., 1979. MUST––A multiple 2002, Brussels, Belgium, 2002, Proceedings, Lecture Notes solutions technique for balancing single model assembly in Computer Science, 2463. Springer, Berlin, pp. 65–75. lines. Management Science 25, 1105–1114.Bautista, J., Suarez, R., Mateo, M., Companys, R., 2000. Local De Reyck, B., Herroelen, W., 1997. Assembly line balancing by search heuristics for the assembly line balancing problem resource-constrained project scheduling––A critical apprai- with incompatibilities between tasks. In: Proceedings of the sal. Foundations of Computing and Control Engineering 2000 IEEE International Conference on Robotics and 22, 143–167. Automation, San Francisco, CA, 2404–2409. Driscoll, J., Thilakawardana, D., 2001. The deﬁnition ofBaybars, I., 1986a. A survey of exact algorithms for the simple assembly line balancing diﬃculty and evaluation of balance assembly line balancing problem. Management Science 32, solution quality. Robotics and Computer Integrated Man- 909–932. ufacturing 17, S81–S86.Baybars, I., 1986b. An eﬃcient heuristic method for the simple Easton, F., Faaland, B., Klastorin, T.D., Schmitt, T., 1989. assembly line balancing problem. International Journal of Improved network based algorithms for the assembly line Production Research 24, 149–166. balancing problem. International Journal of Production ¨Baykasoglu, A., Ozbakir, L., Telcioglu, M.B., 2002. Multiple- Research 27, 1901–1915. rule based genetic algorithm for simple assembly line Erel, E., Sarin, S.C., 1998. A survey of the assembly line balancing problems (MRGA-SALBP-I). In: Proceedings balancing procedures. Production Planning and Control 9, of the 5th International Conference on Managing Innova- 414–434. tions in Manufacturing (MIM) 2002, Milwaukee, WI, USA, Falkenauer, E., 1996. A hybrid grouping algorithm for bin pp. 402–408. packing. Journal of Heuristics 2, 5–30.Becker, C., Scholl, A., this issue. A survey on problems and Falkenauer, E., 1997. A grouping genetic algorithm for line methods in generalized assembly line balancing. European balancing with resource dependent task times. In: Proceed- Journal of Operations Research. doi:10.1016/ ings of the Fourth International Conference on Neural j.ejor.2004.07.023. Information Processing 1997, University of Otago, Dun-Bennett, G.B., Byrd, J., 1976. A trainable heuristic procedure edin, New Zealand, pp. 464–468. for the assembly line balancing problem. AIIE Transactions Falkenauer, E., Delchambre, A., 1992. A genetic algorithm for 8, 195–201. bin packing and line balancing. In: Proceedings of the 1992
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 691 IEEE International Conference on Robotics and Automa- Jackson, J.R., 1956. A computing procedure for a line tion, Nice, France, pp. 1186–1192. balancing problem. Management Science 2, 261–271.Fekete, S.P., Schepers, J., 2001. New classes of fast lower Jaeschke, G., 1964. Branching and Bounding: Eine allgemeine bounds for bin packing problems. Mathematical Program- Methode zur Losung kombinatorischer Probleme. Ablauf- ¨ ming 91, 11–31. und Planungsforschung 5, 133–155.Fleszar, K., Hindi, K.S., 2003. An enumerative heuristic and Johnson, R.V., 1981. Assembly line balancing algorithms: reduction methods for the assembly line balancing problem. Computation comparisons. International Journal of Pro- European Journal of Operational Research 145, 606–620. duction Research 19, 277–287.Freeman, D.S., Swain, R.W., 1986. A heuristic technique for Johnson, R.V., 1988. Optimally balancing large assembly lines balancing automated assembly lines. Research Report No. with ‘‘FABLE’’. Management Science 34, 240–253. 86-6, Industrial and Systems Engineering Department, Johnson, R.V., 1993. Note: Microcomputer performance of University of Florida, Gainesville. ‘‘FABLE’’ on HoﬀmannÕs data sets. Management ScienceGehrlein, W.V., Patterson, J.H., 1975. Sequencing for assembly 39, 1190–1193. lines with integer task times. Management Science 21, 1064– Kao, E.P.C., Queyranne, M., 1982. On dynamic programming 1070. methods for assembly line balancing. Operations ResearchGehrlein, W.V., Patterson, J.H., 1978. Balancing single model 30, 375–390. assembly lines: Comments on a paper by E.M. Dar-El Kim, Y.K., Kim, Y., Kim, Y.J., 2000. Two-sided assembly line (Mansoor). AIIE Transactions 10, 109–112. balancing: A genetic algorithm approach. Production Plan-Ghosh, S., Gagnon, R.J., 1989. A comprehensive literature ning and Control 11, 44–53. review and analysis of the design, balancing and scheduling Klein, R., Scholl, A., 1996. Maximizing the production rate in of assembly systems. International Journal of Production simple assembly line balancing––A branch and bound Research 27, 637–670. procedure. European Journal of Operational Research 91,Glover, F., Laguna, M., 1997. Tabu search. Kluwer Academic 367–385. Publishers, Boston. Klein, R., Scholl, A., 1999. Computing lower bounds byGorke, M., Lentes, H.-P., 1976. Leistungsabstimmung von ¨ destructive improvement––An application to resource-con- Montagelinien. Arbeitsvorbereitung 13, 71–77, 106–113, strained project scheduling. European Journal of Opera- and 147–153. tional Research 112, 322–346.Goldberg, D.E., 1989. Genetic algorithms in search, optimiza- Klein, R., Scholl, A., 2000. PROGRESS: Optimally solving the tion and machine learning. Addison-Wesley, Reading, MA. generalized resource-constrained project scheduling prob-Goncalves, J.F., Almeida, J.R., 2002. A hybrid genetic lem. Mathematical Methods of Operations Research 52, algorithm for assembly line balancing. Journal of Heuristics 467–488. 8, 629–642. Klenke, H., 1977. Ablaufplanung bei Fließfertigung. Gabler,Gutjahr, A.L., Nemhauser, G.L., 1964. An algorithm for the Wiesbaden. line balancing problem. Management Science 11, 308–315. ´ Labbe, M., Laporte, G., Mercure, H., 1991. Capacitated vehicleHackman, S.T., Magazine, M.J., Wee, T.S., 1989. Fast, eﬀective routing on trees. Operations Research 39, 616–622. algorithms for simple assembly line balancing problems. Lapierre, S.D., Ruiz, A., Soriano, P., this issue. Balancing Operations Research 37, 916–924. assembly lines with tabu search. European Journal ofHeinrici, A., 1994. A comparison between simulated annealing Operational Research. doi:10.1016/j.ejor.2004.07.031. and tabu search with an example from the production Lawler, E.L., 1979. Eﬃcient implementation of dynamic planning. In: Dyckhoﬀ, H. et al. (Eds.), Operations programming algorithms for sequencing problems, Research Proceedings 1994. Springer, Berlin, pp. 498–503. Report BW 106/79, Stichting Mathematisch Centrum,Held, M., Karp, R.M., Shareshian, R., 1963. Assembly line Amsterdam. balancing––Dynamic programming with precedence con- Leu, Y.Y., Matheson, L.A., Rees, L.P., 1994. Assembly line straints. Operations Research 11, 442–459. balancing using genetic algorithms with heuristic-generatedHelgeson, W.B., Birnie, D.P., 1961. Assembly line balancing initial populations and multiple evaluation criteria. Decision using the ranked positional weight technique. Journal of Sciences 25, 581–606. Industrial Engineering 12, 394–398. Martello, S., Toth, P., 1990. Knapsack problems––AlgorithmsHoﬀmann, T.R., 1963. Assembly line balancing with a prece- and computer implementations. Wiley, New York. dence matrix. Management Science 9, 551–562. McMullen, P.R., Frazier, G.V., 1998. Using simulated anneal-Hoﬀmann, T.R., 1990. Assembly line balancing: A set of ing to solve a multiobjective assembly line balancing challenging problems. International Journal of Production problem with parallel workstations. International Journal Research 28, 1807–1815. of Production Research 36, 2717–2741.Hoﬀmann, T.R., 1992. EUREKA: A hybrid system for McMullen, P.R., Tarasewich, P., 2003. Using ant techniques to assembly line balancing. Management Science 38, 39–47. solve the assembly line balancing problem. IIE TransactionsHoﬀmann, T.R., 1993. Response to note on microcomputer 35, 605–617. performance of ‘‘FABLE’’ on HoﬀmannÕs data sets. Man- McNaughton, R., 1959. Scheduling with deadlines and loss agement Science 39, 1192–1193. functions. Management Science 6, 1–12.
    • 692 A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693Merengo, C., Nava, F., Pozetti, A., 1999. Balancing and Rekiek, B., Dolgui, A., Delchambre, A., Bratcu, A., 2002b. sequencing manual mixed-model assembly lines. Interna- State of art of optimization methods for assembly line tional Journal of Production Research 37, 2835–2860. design. Annual Reviews in Control 26, 163–174.Mertens, P., 1967. Fließbandabstimmung mit dem Verfahren Rosenblatt, M.J., Carlson, R.C., 1985. Designing a production der begrenzten Enumeration nach Muller-Merbach. Ablauf- ¨ line to maximize proﬁt. IIE Transactions 17, 117–121. und Planungsforschung 8, 429–433. Rubinovitz, J., Levitin, G., 1995. Genetic algorithm forMoodie, C.L., Young, H.H., 1965. A heuristic method of assembly line balancing. International Journal of Produc- assembly line balancing for assumptions of constant or tion Economics 41, 343–354. variable work element times. Journal of Industrial Engi- Sabuncuoglu, I., Erel, E., Tanyer, M., 2000. Assembly line neering 16, 23–29. balancing using genetic algorithms. Journal of IntelligentNourie, F.J., Venta, E.R., 1991. Finding optimal line balances Manufacturing 11, 295–310. with OptPack. Operations Research Letters 10, 165–171. Saltzman, M.J., Baybars, I., 1987. A two-process implicitNourie, F.J., Venta, E.R., 1996. Microcomputer performance enumeration algorithm for the simple assembly line balanc- of OptPack on HoﬀmannÕs data sets: Comparison with ing problem. European Journal of Operational Research 32, Eureka and FABLE. Management Science 42, 304–306. 118–129.Pastor, R., Andres, C., Duran, A., Perez, M., 2002. Tabu search Schoﬁeld, N.A., 1979. Assembly line balancing and the appli- algorithms for an industrial multi-product and multi-objec- cation of computer techniques. Computers and Industrial tive assembly line balancing problem, with reduction of the Engineering 3, 53–69. task dispersion. Journal of the Operational Research Scholl, A., 1993. Data of assembly line balancing problems. Society 53, 1317–1323. Schriften zur Quantitativen Betriebswirtschaftslehre 16/93,Peeters, M., Degraeve, Z., this issue. An linear programming TU Darmstadt. based lower bound for the simple assembly line balancing Scholl, A., 1994. Ein B&B-Verfahren zur Abstimmung von problem. European Journal of Operational Research. Einprodukt-Fließbandern bei gegebener Stationsanzahl. In: ¨ doi:10.1016/j.ejor.2004.07.024. Dyckhoﬀ, H. et al. (Eds.), Operations Research ProceedingsPinnoi, A., Wilhelm, W.E., 1997a. A branch and cut approach 1993, Springer, Berlin, pp. 175–181. for workload smoothing on assembly lines. INFORMS Scholl, A., 1999. Balancing and sequencing assembly lines, 2nd Journal on Computing 9, 335–350. ed. Physica, Heidelberg.Pinnoi, A., Wilhelm, W.E., 1997b. A family of hierarchical Scholl, A., Klein, R., 1997. SALOME: A bidirectional branch models for assembly system design. International Journal of and bound procedure for assembly line balancing. Production Research 35, 253–280. INFORMS Journal on Computing 9, 319–334.Pinnoi, A., Wilhelm, W.E., 1998. Assembly system design: A Scholl, A., Klein, R., 1999. Balancing assembly lines eﬀec- branch and cut approach. Management Science 44, 103– tively––A computational comparison. European Journal of 118. Operational Research 114, 50–58.Pinto, P.A., Dannenbring, D.G., Khumawala, B.M., 1978. A Scholl, A., Voß, S., 1995. Kapazitatsorientierte Leistungsab- ¨ heuristic network procedure for the assembly line balancing stimmung in der Fließfertigung. Zeitschrift fur betrie-bs- ¨ problem. Naval Research Logistics Quarterly 25, 299–307. wirtschaftliche Forschung 47, 919–935.Ponnambalam, S., Aravindan, G., Mogileeswar Naidu, G., Scholl, A., Voß, S., 1996. Simple assembly line balancing–– 2000. A multi-objective genetic algorithm for solving Heuristic approaches. Journal of Heuristics 2, 217–244. assembly line balancing problem. International Journal of Scholl, A., Klein, R., Jurgens, C., 1997. BISON: A fast hybrid ¨ Advanced Manufacturing Technology 16, 341–352. procedure for exactly solving the one-dimensional binRachamadugu, R., Talbot, B., 1991. Improving the equality of packing problem. Computers and Operations Research 24, workload assignments in assembly lines. International 627–645. Journal of Production Research 29, 619–633. Schrage, L., Baker, K.R., 1978. Dynamic programming solu-Raouf, A., Tsui, C.L., El-Sayed, E.A., 1980. A new heuristic tion of sequencing problems with precedence constraints. approach to assembly line balancing. Computers and Operations Research 26, 444–449. Industrial Engineering 4, 223–234. Shtub, A., Dar-El, E.M., 1989. A methodology for the selectionRekiek, B., de Lit, P., Pellichero, F., Falkenauer, E., Delcham- of assembly systems. International Journal of Production bre, A., 1999. Applying the equal piles problem to balance Research 27, 175–186. assembly lines. In: Proceedings of the ISATP 1999, Porto, Sprecher, A., 1999. A competitive branch-and-bound algorithm Portugal, pp. 399–404. for the simple assembly line balancing problem. Interna-Rekiek, B., de Lit, P., Pellichero, F., LÕEglise, T., Fouda, P., tional Journal of Production Research 37, 1787–1816. Falkenauer, E., Delchambre, A., 2001. A multiple objective Sprecher, A., 2003. Dynamic search tree decomposition for grouping genetic algorithm for assembly line balancing. balancing assembly lines by parallel search. International Journal of Intelligent Manufacturing 12, 467–485. Journal of Production Research 41, 1413–1430.Rekiek, B., de Lit, P., Delchambre, A., 2002a. Hybrid assembly Suresh, G., Sahu, S., 1994. Stochastic assembly line balancing line design and userÕs preferences. International Journal of using simulated annealing. International Journal of Pro- Production Research 40, 1095–1111. duction Research 32, 1801–1810.
    • A. Scholl, C. Becker / European Journal of Operational Research 168 (2006) 666–693 693Suresh, G., Vinod, V.V., Sahu, S., 1996. Genetic algorithm for Ugurdag, H.F., Rachamadugu, R., Papachristou, C.A., 1997. assembly line balancing. Production Planning and Control Designing paced assembly lines with ﬁxed number of 7, 38–46. stations. European Journal of Operational Research 102,Talbot, F.B., Patterson, J.H., 1984. An integer programming 488–501. algorithm with network cuts for solving the assembly line Van Assche, F., Herroelen, W.S., 1979. An optimal procedure balancing problem. Management Science 30, 85–99. for the single-model deterministic assembly line balancingTalbot, F.B., Patterson, J.H., Gehrlein, W.V., 1986. A com- problem. European Journal of Operational Research 3, parative evaluation of heuristic line balancing techniques. 142–149. Management Science 32, 430–454. Watanabe, T., Hashimoto, Y., Nishikawa, L., Tokumaru, H.,Thilakawardana, D., Driscoll, J., Deacon, G. An eﬃcient 1995. Line balancing using a genetic evolution model. genetic algorithm application in assembly line balancing. Control Engineering Practice 3, 69–76. European Journal of Operational Research. Balancing of Wee, T.S., Magazine, M.J., 1982. Assembly line balancing as Automated Assembly and Transfer Lines (Special issue). generalized bin packing. Operations Research Letters 1/2,Tonge, F.M., 1960. Summary of a heuristic line balancing 56–58. procedure. Management Science 7, 21–39. Zapfel, G., 1975. Ausgewahlte fertigungswirtschaftliche Opti- ¨ ¨Tonge, F.M., 1965. Assembly line balancing using probabilistic mierungsprobleme von Fließfertigungssystemen. Beuth, combinations of heuristics. Management Science 11, 727–735. Berlin.