A New Heuristic Approach to Solving U-shape Assembly Line Balancing Problems Type-1

Authors: M. Fathi, M. J. Alvarez, V. Rodríguez

Abstract:

Assembly line balancing is a very important issue in mass production systems due to production cost. Although many studies have been done on this topic, but because assembly line balancing problems are so complex they are categorized as NP-hard problems and researchers strongly recommend using heuristic methods. This paper presents a new heuristic approach called the critical task method (CTM) for solving U-shape assembly line balancing problems. The performance of the proposed heuristic method is tested by solving a number of test problems and comparing them with 12 other heuristics available in the literature to confirm the superior performance of the proposed heuristic. Furthermore, to prove the efficiency of the proposed CTM, the objectives are increased to minimize the number of workstation (or equivalently maximize line efficiency), and minimizing the smoothness index. Finally, it is proven that the proposed heuristic is more efficient than the others to solve the U-shape assembly line balancing problem.

Keywords: Critical task method, Heuristic, Line balancingproblem, U-shape

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080892

References:

[1] A. Scholl, and R. Klein, "ULINO: Optimally balancing U-shaped JIT assembly lines," Int J of Prod Res. vol. 37, no. 4, pp. 721-736, Mar. 1999.
[2] S. Ghosh, and R. J. Gagnon, "A comprehensive literature review and analysis of the design, balancing and scheduling of assembly systems," Int J of Prod Res. vol. 27, no. 4, pp. 637-670, Apr. 1989.
[3] M. E. Salveson, "The assembly line balancing problem," J Ind Eng. Vol. 6, no. 3, pp. 18-25, May-Jun. 1955.
[4] A. L. Gutjahr, and G. L. Nemhauser, "An algorithm for the line balancing problem," Manag Sci, vol. 11, no. 2, pp. 308-315, Nov. 1964.
[5] D. A. Ajenblit, and R. L. Wainwright, "Applying genetic algorithms to the U-shaped assembly line balancing problem," IEEE Int. Conf. Evolutionary Computation, ICEC, Anchorage, AK, USA 1998, pp. 96- 101.
[6] S. G. Ponnambalam, P. Aravindan, and G. Mogileeswar Naidu, "Multiobjective genetic algorithm for solving assembly line balancing problem," Int J Adv Manuf Technol. vol. 16, no. 5, pp. 341-352, Apr. 2000.
[7] A. Baykasoglu, "Multi-rule multi-objective simulated annealing algorithm for straight and U type assembly line balancing problems," J Intell Manuf. vol. 17, no. 2, pp. 217-232, Apr. 2006.
[8] N. Kriengkorakot, and N. Pianthong, "The Assembly Line Balancing Problem," KKU Enginieering Journal. vol. 34, no. 2, pp. 133-140, Mar.- Apr. 2007.
[9] A. Pinnoi, A branch and cut approach for certain problems in assembly systems, Texas A&M University, United States, Texas, Unpublished Ph.D. thesis.
[10] K. H. Oh, "Expert Line Balancing System (ELBS)," Comput Indu Eng, vol 33, no. 1-2, pp. 303-306, Oct. 1997.
[11] D. H. Yeh, and H. H. Kao, "A new bidirectional heuristic for the assembly line balancing problem," Comput Indu Eng, vol. 57, no. 4, pp. 1155-1160, Nov. 2009.
[12] W. B. Helgeson, and D. P. Birnie, "Assembly line balancing using the ranked positional weight technique," J Ind Eng. vol. 12, no. 6, pp. 394- 398, Nov.-Dec. 1961.
[13] A. Scholl, and C. Becker, "State-of-the-art exact and heuristic solution procedures for simple assembly line balancing," Eur J Oper Res. vol. 168, no. 3, pp. 666-693, Feb. 2006.
[14] Tonge, F. M., "Summary of a heuristic line balancing procedure," Manag Sci, vol. 7, no. 1, pp. 21-42, Oct. 1960.
[15] C. L. E. Khaw, and S. G. Ponnambalam, "Multi-rule multi-objective ant colony optimization for straight and U-type assembly line balancing problem," 2009 Int. Conf. Automation Science and Engineering, CASE 2009, Bangalore, pp. 177-182.
[16] .Baykasoglu A, Dereli T, "Two-sided assembly line balancing using an ant-colony-based heuristic," Int J Adv Manuf Technol, vol 36, no. 5-6, pp. 582-58, Mar. 2008.
[17] R. Kolisch, "Efficient priority rules for the resource-constrained project scheduling problem," J Oper Manag, vol 14, no.3, pp. 179-192, Sep. 1996.
[18] J. Bautista, and J. Pereira, "Ant algorithms for assembly line balancing," Lecture Notes in Computer Science. Vol. 2463, pp. 65-75, Sep. 2002.
[19] U. Ozcan, and B. Toklu, "A new hybrid improvement heuristic approach to simple straight and U-type assembly line balancing problems," J Intell Manuf. vol. 20, no.1, pp. 123-136, Feb. 2009.
[20] F. B. Talbot, J. H. Patterson, and W. V. Gehrlein, "A comparative evaluation of heuristic line balancing techniques," Manag Sci, Vol. 32, no.4, pp. 430-454, Apr. 1986.
[21] T. R. Hoffmann, Eureka, "A hybrid system for assembly line balancing," Manag Sci, vol. 38, no.1, pp. 39-47, Jan. 1992.
[22] A. Scholl, "Data of assembly line balancing problems," (Working paper), Schriften zur Quantitativen Betriebswirtschaftslehre, vol 16, no.93, pp.1-32, Nov. 1993.