zbMATH — the first resource for mathematics

Balancing assembly lines effectively – a computational comparison. (English) Zbl 0949.90034
Summary: We report on results of a numerical experiment including the most effective branch and bound procedures for solving type I of the simple assembly line balancing problem (SALBP-1), namely Johnson’s (1988) FABLE, Nourie and Venta’s (1991) OptPack, Hoffmann’s (1992) Eureka and Scholl and Klein’s (1997) SALOME. It appears that SALOME clearly outperforms the other procedures with respect to hard instances of a new challenging data set. Beyond that, it is shown that the performance of SALOME can greatly be improved by adding some further features including dynamic renumbering and dominance rules.

90B30 Production models
90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI
[1] Baybars, I., A survey of exact algorithms for the simple assembly line balancing problem, Management science, 32, 909-932, (1986) · Zbl 0601.90081
[2] Demeulemeester, E.; Herroelen, W.S., New benchmark results for the resource-constrained project scheduling problem, Management science, 43, 1485-1492, (1997) · Zbl 0914.90160
[3] Hackman, S.T.; Magazine, M.J.; Wee, T.S., Fast, effective algorithms for simple assembly line balancing problems, Operations research, 37, 916-924, (1989) · Zbl 0689.90047
[4] Hoffmann, T.R., Assembly line balancing with a precedence matrix, Management science, 9, 551-562, (1963)
[5] Hoffmann, T.R., Assembly line balancing: A set of challenging problems, International journal of production research, 28, 1807-1815, (1990)
[6] Hoffmann, T.R., Eureka: A hybrid system for assembly line balancing, Management science, 38, 39-47, (1992) · Zbl 0825.90511
[7] Hoffmann, T.R., Response to note on microcomputer performance of ‘FABLE’ on Hoffmann’s data sets, Management science, 39, 1192-1193, (1993)
[8] Johnson, R.V., Assembly line balancing algorithms: computation comparisons, International journal of production research, 19, 277-287, (1981)
[9] Johnson, R.V., Optimally balancing large assembly lines with FABLE, Management science, 34, 240-253, (1988)
[10] Johnson, R.V., Note: microcomputer performance of ‘FABLE’ on Hoffmann’s data sets, Management science, 39, 1190-1193, (1993)
[11] Nourie, F.J.; Venta, E.R., The packing heuristic for assembly line balancing, Journal of applied business research, 3, 122-128, (1987)
[12] Nourie, F.J.; Venta, E.R., Finding optimal line balances with optpack, Operations research letters, 10, 165-171, (1991) · Zbl 0738.90038
[13] Nourie, F.J.; Venta, E.R., Microcomputer performance of optpack on Hoffmann’s data sets: comparison with eureka and FABLE, Management science, 42, 304-306, (1996) · Zbl 0884.90099
[14] Saltzman, M.J.; Baybars, I., A two-process implicit enumeration algorithm for the simple assembly line balancing problem, European journal of operational research, 32, 118-129, (1987) · Zbl 0622.90043
[15] A. Scholl, Balancing and Sequencing of Assembly Lines, Physica, Heidelberg, 1995
[16] Scholl, A.; Klein, R., SALOME: A bidirectional branch-and-bound procedure for assembly line balancing, INFORMS journal on computing, 9, 319-334, (1997) · Zbl 0895.90121
[17] Schrage, L.; Baker, K.R., Dynamic programming solution of sequencing problems with precedence constraints, Operations research, 26, 444-459, (1978) · Zbl 0383.90054
[18] Talbot, F.B.; Patterson, J.H., An integer programming algorithm with network cuts for solving the assembly line balancing problem, Management science, 30, 85-99, (1984) · Zbl 0554.90055
[19] Talbot, F.B.; Patterson, J.H.; Gehrlein, W.V., A comparative evaluation of heuristic line balancing techniques, Management science, 32, 430-454, (1986)
[20] Van Assche, F.; Herroelen, W.S., An optimal procedure for the single-model deterministic assembly line balancing problem, European journal of operational research, 3, 142-149, (1979) · Zbl 0392.90035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.