A New Heuristic Approach to Solving U-shape Assembly Line Balancing Problems Type-1
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.
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:62337", author = "M. Fathi and M. J. Alvarez and V. RodrÃguez", title = "A New Heuristic Approach to Solving U-shape Assembly Line Balancing Problems Type-1", 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", volume = "5", number = "11", pages = "2480-9", }
