The sequence-dependent assembly line balancing problem. (English) Zbl 1193.90235
Summary: Assembly line balancing problems (ALBP) arise whenever an assembly line is configured, redesigned or adjusted. An ALBP consists of distributing the total workload for manufacturing any unit of the products to be assembled among the work stations along the line. The sequence-dependent assembly line balancing problem (SDALBP) is an extension of the standard simple assembly line balancing problem (SALBP) which has significant relevance in real-world assembly line settings. SDALBP extends the basic problem by considering sequence-dependent task times. In this paper, we define this new problem, formulate several versions of a mixed-integer program, adapt solution approaches for SALBP to SDALBP, generate test data and perform some preliminary computational experiments. As a main result, we find that applying SALBP-based search procedures is very effective, whereas modelling and solving the problem with MIP standard software is not recommendable.
References:
| [1] | Baybars I (1986) A survey of exact algorithms for the simple assembly line balancing problem. Manage Sci 32:909–932 · Zbl 0601.90081 · doi:10.1287/mnsc.32.8.909 |
| [2] | Becker C, Scholl A (2006) A survey on problems and methods in generalized assembly line balancing. Eur J Oper Res 168:694–715 · Zbl 1083.90013 · doi:10.1016/j.ejor.2004.07.023 |
| [3] | Bockmayr A, Pisaruk N (2001) Solving assembly line balancing problems by combining IP and CP. In: Proceedings of the 6th Annual Workshop of the ERCIM Working Group on Constraints, Prague, Czech Republic |
| [4] | Bowman EH (1960) Assembly-line balancing by linear programming. Oper Res 8:385–389 · Zbl 0093.32805 · doi:10.1287/opre.8.3.385 |
| [5] | Boysen N, Fliedner M, Scholl A (2006) A classification of assembly line balancing problems. Eur J Oper Res (in press) · Zbl 1179.90103 |
| [6] | Erel E, Sarin SC (1998) A survey of the assembly line balancing procedures. Prod Plan Control 9:414–434 · doi:10.1080/095372898233902 |
| [7] | Ghosh S, Gagnon RJ (1989) A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems. Int J Prod Res 27:637–670 · doi:10.1080/00207548908942574 |
| [8] | Hackman ST, Magazine MJ, Wee TS (1989) Fast, effective algorithms for simple assembly line balancing problems. Oper Res 37:916–924 · Zbl 0689.90047 · doi:10.1287/opre.37.6.916 |
| [9] | Hoffmann TR (1992) EUREKA: a hybrid system for assembly line balancing. Manage Sci 38:39–47 · Zbl 0825.90511 · doi:10.1287/mnsc.38.1.39 |
| [10] | Johnson RV (1988) Optimally balancing large assembly lines with ”FABLE”. Manage Sci 34:240–253 · doi:10.1287/mnsc.34.2.240 |
| [11] | Lübke M (2006) Methoden der Präferenzmessung: Formale Analyse, Vergleich und Weiterentwicklung. Diploma Thesis, University of Jena |
| [12] | Patterson JH, Albracht JJ (1975) Assembly-line balancing: Zero-one programming with Fibonacci search. Oper Res 23:166–172 · Zbl 0307.90057 · doi:10.1287/opre.23.1.166 |
| [13] | Peeters M, Degraeve Z (2006) An linear programming based lower bound for the simple assembly line balancing problem. Eur J Oper Res 168:716–731 · Zbl 1083.90028 · doi:10.1016/j.ejor.2004.07.024 |
| [14] | Pinnoi A, Wilhelm WE (1997) A family of hierarchical models for assembly system design. Int J Prod Res 35:253–280 · Zbl 0949.90646 · doi:10.1080/002075497196073 |
| [15] | Rekiek B, Dolgui A, Delchambre A, Bratcu A (2002) State of art of optimization methods for assembly line design. Annu Rev Control 26:163–174 · doi:10.1016/S1367-5788(02)00027-5 |
| [16] | de Reyck B, Herroelen W (1997) Assembly line balancing by resource-constrained project scheduling–A critical appraisal. Found Comput Control Eng 22:143–167 · Zbl 0899.68007 |
| [17] | Saltzman MJ, Baybars I (1987) A two-process implicit enumeration algorithm for the simple assembly line balancing problem. Eur J Oper Res 32:118–129 · Zbl 0622.90043 · doi:10.1016/0377-2217(87)90276-1 |
| [18] | Scholl A (1993) Data of assembly line balancing problems. Schriften zur Quantitativen Betriebswirtschaftslehre 16/93, TU Darmstadt |
| [19] | Scholl A (1999) Balancing and sequencing assembly lines, 2nd edn. Physica, Heidelberg · Zbl 0949.90034 |
| [20] | Scholl A, Becker C (2006) State-of-the-art exact and heuristic solution procedures for simple assembly line balancing. Eur J Oper Res 168:666–693 · Zbl 1083.90019 · doi:10.1016/j.ejor.2004.07.022 |
| [21] | Scholl A, Klein R (1997) SALOME: A bidirectional branch and bound procedure for assembly line balancing. Inf J Comput 9:319–334 · Zbl 0895.90121 · doi:10.1287/ijoc.9.4.319 |
| [22] | Scholl A, Klein R (1999) Balancing assembly lines effectively–a computational comparison. Eur J Oper Res 114:50–58 · Zbl 0949.90034 · doi:10.1016/S0377-2217(98)00173-8 |
| [23] | Scholl A, Voß S (1996) Simple assembly line balancing–Heuristic approaches. J Heuristics 2:217–244 · doi:10.1007/BF00127358 |
| [24] | Sprecher A (1999) A competitive branch-and-bound algorithm for the simple assembly line balancing problem. Int J Prod Res 37:1787–1816 · Zbl 0949.90522 · doi:10.1080/002075499191003 |
| [25] | Talbot FB, Patterson JH, Gehrlein WV (1986) A comparative evaluation of heuristic line balancing techniques. Manage Sci 32:430–454 · doi:10.1287/mnsc.32.4.430 |
| [26] | Thangavelu SR, Shetty CM (1971) Assembly line balancing by zero-one integer programming. AIIE Trans 3:61–68 |
| [27] | Ugurdag HF, Rachamadugu R, Papachristou CA (1997) Designing paced assembly lines with fixed number of stations. Eur J Oper Res 102:488–501 · Zbl 0955.90019 · doi:10.1016/S0377-2217(96)00248-2 |
| [28] | Wee TS, Magazine MJ (1982) Assembly line balancing as generalized bin packing. Oper Res Lett 1:56–58 · Zbl 0491.90049 · doi:10.1016/0167-6377(82)90046-3 |
| [29] | White WW (1961) Comments on a paper by Bowman. Oper Res 9:274–276 · doi:10.1287/opre.9.2.274 |
| [30] | Williams HP (1999) Model building in mathematical programming, 4th edn. Wiley, New York · Zbl 1253.90166 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
