zbMATH — the first resource for mathematics

A branch-and-bound based solution approach for the mixed-model assembly line-balancing problem for minimizing stations and task duplication costs. (English) Zbl 1116.90035
Summary: A common assumption in the literature on mixed-model assembly line balancing is that a task that is common to multiple models must be assigned to a single station. In this paper, we relax this restriction, and allow a common task to be assigned to different stations for different models. We seek to minimize the sum of costs of the stations and the task duplication. We develop an optimal solution procedure based on a backtracking branch-and-bound algorithm and evaluate its performance via a large set of experiments. A branch-and-bound based heuristic is then developed for solving large-scale problems. The heuristic solutions are compared with a lower bound and experiments show that the heuristic provides much better solutions than those obtained by traditional approaches.

90B30 Production models
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI
[1] Baybars, I., A survey of exact algorithm for the simple assembly line balancing problem, Management science, 32, 909-932, (1986) · Zbl 0601.90081
[2] Becker, C., Scholl, A., in press. A survey on problems and methods in generalized assembly line balancing. European Journal of Operational Research. · Zbl 1083.90013
[3] Berger, I.; Bourjolly, J.M.; Laporte, G., Branch-and-bound algorithm for the multi-product assembly line balancing problem, European journal of operational research, 58, 215-222, (1992) · Zbl 0757.90029
[4] Bukchin, J.; Tzur, M., Design of flexible assembly line to minimize equipment cost, IIE transactions, 32, 7, 585-598, (2000)
[5] Bukchin, J.; Dar-El, E.M.; Rubinovitz, J., Mixed model assembly line design in a make-to-order environment, Computers & industrial engineering, 41, 4, 405-421, (2002)
[6] Erel, E.; Gokcen, H., Shortest-route formulation of mixed-model assembly line balancing problem, European journal of operational research, 116, 194-204, (1999) · Zbl 1009.90120
[7] Erel, E.; Sarin, S.C., A survey of the assembly line balancing procedures, Production planning & control, 9, 5, 414-434, (1998)
[8] Ghosh, S.; Gagnon, R.J., A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems, International journal of production research, 27, 637-670, (1989)
[9] Gokcen, H.; Erel, E., Binary integer formulation for mixed-model assembly line balancing problem, Computers and industrial engineering, 34, 2, 451-461, (1998)
[10] Johnson, J.R., Optimally balancing large assembly lines with FABLE, Management science, 34, 240, (1988)
[11] Karabati, S.; Sayin, S., Assembly line balancing in a mixed-model sequencing environment with synchronous transfers, European journal of operational research, 149, 2, 417-429, (2003) · Zbl 1033.90042
[12] Karp, R.M., Reducibility among combinatorial problems, (), 85-103 · Zbl 0366.68041
[13] Mansoor, E.M.; Yadin, M., On the problem of assembly line balancing, (), 361 · Zbl 0284.90039
[14] Matanachai, S.; Yano, C.A., Balancing mixed-model assembly lines to reduce work overload, IIE transactions, 33, 29-42, (2001)
[15] Merengo, C.; Nava, F.; Pozzetti, A., Balancing and sequencing manual mixed-model assembly lines, International journal of production research, 37, 12, 2835-2860, (1999) · Zbl 0949.90570
[16] Roberts, S.D.; Villa, C.D., On a multiproduct assembly line-balancing problem, AIIE transactions, 2, 4, 361-364, (1970)
[17] Scholl, A., Balancing and sequencing of assembly lines, (1999), Physica-Verlag Heidelberg, Germany
[18] Scholl, A., Becker, C., in press. State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. European Journal of Operational Research. · Zbl 1083.90019
[19] Scholl, A.; Klein, R., SALOME: A bi-directional branch-and-bound procedure for assembly line balancing, INFORMS journal on computing, 9, 4, 319-334, (1997) · Zbl 0895.90121
[20] Thomopoulos, N.T., Line balancing-sequencing for mixed-model assembly, Management science, 14, 59-75, (1967)
[21] Thomopoulos, N.T., Mixed model line balancing with smoothed station assignments, Management science, 16, 593-603, (1970) · Zbl 0194.19801
[22] Van Zante-de Fokkert, J.I.; De Kok, T.G., The mixed and multi model line-balancing problem: A comparison, European journal of operational research, 100, 399-412, (1997) · Zbl 0921.90085
[23] Vilarinho, P.M.; Simaria, A.S., A two-stage heuristic method for balancing mixed-model assembly lines with parallel workstations, International journal of production research, 40, 6, 1405-1420, (2002) · Zbl 1063.90533
[24] Xhao, X.; Ohno, K.; Lau, H.S., A balancing problem for mixed model assembly lines with a paced moving conveyor, Naval research logistics, 51, 446-464, (2004) · Zbl 1054.90026
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.