×

zbMATH — the first resource for mathematics

A versatile algorithm for assembly line balancing. (English) Zbl 1152.90412
Summary: This paper discusses a two stage graph-algorithm, which was designed to solve line balancing problems including practice relevant constraints (GALBP), such as parallel work stations and tasks, cost synergies, processing alternatives, zoning restrictions, stochastic processing times or U-shaped assembly lines. Unlike former procedures, the presented approach can be easily modified to incorporate all of the named extensions. It is not only possible to select and solve single classes of constraints, but rather any combination of them with just slight modifications.

MSC:
90B30 Production models
90C09 Boolean programming
Software:
Knapsack
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aase, G.R.; Schniederjahn, M.J.; Olson, J.R., U-OPT: an analysis of exact U-shaped line balancing procedures, International journal of production research, 41, 4185-4210, (2003) · Zbl 1069.90059
[2] Aase, G.R.; Olson, J.R.; Schniederjahn, M.J., U-shaped assembly line layouts and their impact on labor productivity: an experimental study, European journal of operational research, 156, 698-711, (2004) · Zbl 1107.90342
[3] Akagi, F.; Osaki, H.; Kikuchi, S., A method for assembly line balancing with more than one worker in each station, International journal of production research, 21, 755-770, (1983)
[4] Amen, M., An exact method for cost-oriented assembly line balancing, International journal of production economics, 64, 187-195, (2000)
[5] Amen, M., Heuristic methods for cost-oriented assembly line balancing: A survey, International journal of production economics, 68, 1-14, (2000)
[6] Amen, M., Heuristic methods for cost-oriented assembly line balancing: A comparison on solution quality and computing time, International journal of production economics, 69, 255-264, (2001)
[7] Arcus, A.L., COMSOAL: A computer method of sequencing operations for assembly lines, International journal of production research, 4, 259-277, (1966)
[8] Bard, J.F., Assembly line balancing with parallel workstations and dead time, International journal of production research, 27, 1005-1018, (1989)
[9] Bautista, J.; Pereira, J., Ant algorithm for assembly line balancing, (), 65-75
[10] Baybars, I., A survey of exact algorithms for the simple assembly line balancing problem, Management science, 32, 909-932, (1986) · Zbl 0601.90081
[11] Becker, C.; Scholl, A., A survey on problems and methods in generalized assembly line balancing, European journal of operational research, 168, 694-715, (2006) · Zbl 1083.90013
[12] Boctor, F.F., A multiple-rule heuristic for assembly line balancing, Journal of the operational research society, 62-69, (1995) · Zbl 0829.90068
[13] Bowman, E.H., Assembly-line balancing by linear programming, Operations research, 8, 385-389, (1960) · Zbl 0093.32805
[14] Boysen, N., Fliedner, M., Scholl, A., 2006. A classification of assembly line balancing problems. European Journal of Operational Research, in press, doi:10.1016/j.ejor.2006.10.010. · Zbl 1179.90103
[15] Buffa, E.S.; Sarin, R.K., Modern production, operations management, (1987), Wiley New York
[16] Bukchin, J.; Tzur, M., Design of flexible assembly line to minimize equipment cost, IIE transactions, 32, 585-598, (2000)
[17] Buxey, G.M., Assembly line balancing with multiple stations, Management science, 20, 1010-1021, (1974)
[18] Carnahan, B.J.; Norman, B.A.; Redfern, M.S., Incorporating physical demand criteria into assembly line balancing, IIE transactions, 33, 875-887, (2001)
[19] Carraway, R.L., A dynamic programming approach to stochastic assembly line balancing, Management science, 35, 459-471, (1989) · Zbl 0674.90045
[20] Dar-El, E.M.; Rubinovitch, Y., MUST - A multiple solutions technique for balancing single model assembly lines, Management science, 25, 1105-1114, (1979)
[21] Dorigo, M.; Di Caro, G.; Gambardella, L.M., Ant algorithms for discrete optimization, Artifical life, 5, 137-172, (1999)
[22] Dudzinski, K.; Walukiewicz, S., Exact methods for the knapsack problem and its generalization, European journal of operational research, 28, 3-21, (1987) · Zbl 0603.90097
[23] Erel, E.; Sabuncuoglu, I.; Aksu, B.A., Balancing of u-type assembly systems using simulated annealing, International journal of production research, 39, 3003-3015, (2001) · Zbl 1060.90552
[24] Fleszar, K.; Hindi, K.S., An enumerative heuristic and reduction methods for the assembly line balancing problem, European journal of operational research, 145, 606-620, (2003) · Zbl 1011.90039
[25] 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)
[26] Goncalvez, J.F.; de Almeida, J.R., A hybrid genetic algorithm for assembly line balancing, Journal of heuristics, 8, 629-642, (2002)
[27] Graves, S.C.; Lamar, B.W., An integer programming procedure for assembly system design problems, Operations research, 31, 522-545, (1983) · Zbl 0517.90053
[28] Hackman, S.T.; Magazine, M.J.; Wee, T.S., Fast, effective algorithms for simple assembly line balancing, Operations research, 37, 916-924, (1989) · Zbl 0689.90047
[29] Helgeson, W.B.; Birnie, D.P., Assembly line balancing using ranked positional weight technique, Journal of industrial engineering, 12, 394-398, (1961)
[30] Hoffman, T.R., EUREKA: A hybrid system for assembly line balancing, Management science, 38, 39-47, (1992) · Zbl 0825.90511
[31] Hoffmann, T.R., 1959. Generation of permutations and combinations, Engineering Experiment Station Report Nr. 13, University of Wisconsin, Madision.
[32] Ignall, E.J., A review of assembly line balancing, Journal of industrial engineering, 16, 244-254, (1966)
[33] Inman, R.R.; Leon, M., Scheduling duplicate serial stations in transfer lines, International journal of production research, 32, 2631-2644, (1994) · Zbl 0896.90122
[34] Iskander, W.H.; Chou, J., Unbalanced production line scheduling with partial job specialization, Naval research logistics, 37, 789-805, (1990) · Zbl 0707.90039
[35] Jackson, J.R., A computing procedure for a line balancing problem, Management science, 2, 261-271, (1956)
[36] Johnson, R.V., A branch and bound algorithm for assembly line balancing problems with formulation irregularities, Management science, 29, 1309-1324, (1983) · Zbl 0526.90051
[37] Johnson, R.V., Optimally balancing large assembly lines with “FABLE”, Management science, 34, 240-253, (1988)
[38] Johnson, E.L.; Padberg, M.W., A note on the knapsack problem with special ordered sets, Operations research letters, 1, 18-22, (1981) · Zbl 0493.90062
[39] Kao, E.P.C., A preference order dynamic program for stochastic assembly line balancing, Management science, 22, 1097-1104, (1976) · Zbl 0345.90017
[40] Klein, M., On assembly line balancing, Operations research, 11, 274-281, (1963)
[41] Kottas, J.F.; Lau, H.-S., A stochastic line balancing procedure, International journal of production research, 19, 177-193, (1981)
[42] Lapierre, S.D.; Ruiz, A.B., Balancing assembly lines: an industrial case study, Journal of the operational research society, 55, 589-597, (2004) · Zbl 1060.90686
[43] Martello, S., Toth, P., 1990. Knapsack Problems - Algorithms and Computer Implementations. Chichester. · Zbl 0708.68002
[44] Miltenburg, J., Balancing u-lines in a multiple u-line facility, European journal of operational research, 109, 1-23, (1998) · Zbl 0949.90032
[45] Miltenburg, J., The effect of breakdowns on u-shaped production lines, International journal of production research, 38, 353-364, (2000) · Zbl 0944.90513
[46] Miltenburg, J., One-piece flow manufacturing on u-shaped production lines: A tutorial, IIE transactions, 33, 303-321, (2001)
[47] Miltenburg, J., Balancing and scheduling mixed-model u-shaped production lines, International journal of flexible manufacturing systems, 14, 119-151, (2002)
[48] Miltenburg, J.; Wijngaard, J., The u-line balancing problem, Management science, 40, 1378-1388, (1994) · Zbl 0822.90077
[49] Monden, Y., Toyota production system: an integrated approach to just-in-time, (1998), Kluwer Doderecht
[50] Nakade, K.; Ohno, K., Separate and carousel type allocation of workers in a u-shaped production line, European journal of operational research, 145, 403-424, (2003) · Zbl 1011.90015
[51] Nauss, R.M., The 0-1 knapsack problem with multiple choice constraints, European journal of operational research, 2, 125-131, (1978) · Zbl 0383.90078
[52] Nicosia, G.; Pacciarelli, D.; Pacifici, A., Optimally balancing assembly lines with different workstations, Discrete applied mathematics, 118, 99-113, (2002) · Zbl 0995.90082
[53] Nkasu, M.M.; Leung, K.H., A stochastic approach to assembly line balancing, International journal of production research, 33, 975-991, (1995) · Zbl 0915.90135
[54] Park, K.; Park, S.; Kim, W., A heuristic for an assembly line balancing problem with incompatibility, range, and partial precedence constraints, Computers and industrial engineering, 32, 321-332, (1997)
[55] Patterson, J.H.; Albracht, J.J., Assembly-line balancing: zero – one programming with Fibonacci search, Operations research, 23, 166-172, (1975) · Zbl 0307.90057
[56] Pinnoi, A.; Wilhelm, W.E., A family of hierarchical models for the design of deterministic assembly systems, International journal of production research, 35, 253-280, (1997) · Zbl 0949.90646
[57] Pinnoi, A.; Wilhelm, W.E., Assembly system design: A branch and cut approach, Management science, 44, 103-118, (1998) · Zbl 0989.90049
[58] Pinto, P.A.; Dannenbring, D.G.; Khumawala, B.M., A branch and bound algorithm for assembly line balancing with paralleling, International journal of production research, 13, 183-196, (1975)
[59] Pinto, P.A.; Dannenbring, D.G.; Khumawala, B.M., Branch and bound and heuristic procedures for assembly line balancing with paralleling stations, International journal of production research, 19, 565-576, (1981)
[60] Pinto, P.A.; Dannenbring, D.G.; Khumawala, B.M., Assembly line balancing with processing alternatives, Management science, 29, 817-830, (1983)
[61] Pisinger, D., A minimal algorithm for the multiple-choice knapsack problem, European journal of operational research, 83, 394-410, (1995) · Zbl 0904.90143
[62] Ponnambalam, S.G.; Aravindan, P.; Naidu, G.M., A multi-objective genetic algorithm for solving assembly line balancing problem, International journal of advanced manufacturing technology, 16, 341-352, (2000)
[63] Queyranne, M., Bounds for assembly line balancing heuristics, Operations research, 33, 1353-1359, (1985) · Zbl 0579.90054
[64] Rekiek, B.; de Lit, P.; Pellichero, F.; L’Eglise, T.; Fouda, P.; Falkenauer, E.; Delchambre, A., A multiple objective grouping genetic algorithm for assembly line design, Journal of intelligent manufacturing, 12, 467-485, (2001)
[65] Rekiek, B.; de Lit, P.; Delchambre, A., Hybrid assembly line design and user’s preferences, International journal of production research, 40, 1095-1111, (2002) · Zbl 1064.90534
[66] Rosenberg, O.; Ziegler, H., A comparison of heuristic algorithms for cost oriented assembly line balancing, Zeitschrift für operations research, 6, 477-495, (1992) · Zbl 0765.90053
[67] Salveson, M.E., The assembly line balancing problem, The journal of industrial engineering, 6, 3, 18-25, (1955)
[68] Sarin, S.C.; Erel, E., Development of cost model for the single-model stochastic assembly line balancing problem, International journal of production research, 28, 1305-1316, (1990)
[69] Sarker, B.R.; Shantikumar, J.G., A generalized approach for serial or parallel line balancing, International journal of production research, 21, 109-133, (1983)
[70] Sawik, T., Monolithic vs. hierarchical balancing and scheduling of a flexible assembly line, European journal of operational research, 143, 115-124, (2002) · Zbl 1073.90514
[71] Scholl, A., Balancing and sequencing of assembly lines, (1999), Physica Heidelberg
[72] Scholl, A.; Becker, C., State-of-the-art exact and heuristic solution procedures for simple assembly line balancing, European journal of operational research, 168, 666-693, (2006) · Zbl 1083.90019
[73] Scholl, A.; Klein, R., ULINO: optimally balancing U-shaped JIT assembly lines, International journal of production research, 37, 721-736, (1999) · Zbl 0939.90527
[74] Scholl, A.; Voß, S., Simple assembly line balancing – heuristic approaches, Journal of heuristics, 2, 217-244, (1996)
[75] Shtub, A., The effect of incompletion cost on line balancing with multiple Manning of work stations, International journal of production research, 22, 235-245, (1984)
[76] Silverman, F.N.; Carter, J.C., A cost-based methodology for stochastic line balancing with intermitted line stoppages, Management science, 32, 455-463, (1986)
[77] Sinha, P.; Zolters, A.A., The multiple-choice knapsack problem, Operations research, 27, 503-515, (1979)
[78] Sniedovich, M., Analysis of a preference order assembly line problem, Management science, 27, 1067-1080, (1981) · Zbl 0466.90034
[79] Sparling, D., Balancing JIT production units: the n u-line balancing problem, Information systems and operational research, 36, 215-237, (1998)
[80] Sparling, D.; Miltenburg, J., The mixed-model u-line balancing problem, International journal of production research, 36, 485-501, (1998) · Zbl 0951.90527
[81] Stützle, T.; Dorigo, M., ACO algorithms for the quadratic assignment problem, (), 33-50
[82] Suresh, G.; Sahu, S., Stochastic assembly line balancing using simulated annealing, International journal of production research, 32, 1801-1810, (1994) · Zbl 0906.90087
[83] 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
[84] Talbot, F.B.; Patterson, J.H.; Gehrlein, W.V., A comparative evaluation of heuristic line balancing techniques, Management science, 32, 430-454, (1986)
[85] Thangavelu, S.R.; Shetty, C.M., Assembly line balancing by zero – one integer programming, AIIE transactions, 3, 61-68, (1971)
[86] Tonge, F.M., A heuristic program for assembly line balancing, (1961), Prentice Hall Englewood Cliffs
[87] Tonge, F.M., Assembly line balancing using probabilistic combinations of heuristics, Management science, 11, 727-735, (1965)
[88] Urban, T.L., Optimal balancing of U-shaped assembly lines, Management science, 44, 738-741, (1998) · Zbl 0989.90055
[89] Wilhelm, W.E., A column-generation approach for the assembly system design problem with tool changes, International journal of flexible manufacturing systems, 11, 177-205, (1999)
[90] Zemel, E., The linear multiple choice knapsack problem, Operations research, 28, 1412-1423, (1980) · Zbl 0447.90064
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.