×

Rules-based heuristic approach for the U-shaped assembly line balancing problem. (English) Zbl 1480.90122

Summary: The type-2 U-shaped assembly line balancing problem is important for many just-in-time manufactures, but an efficient algorithm is not available at present. Thus, in this study, a novel heuristic approach based on multiple rules and an integer programming model is proposed to address this problem. In the proposed approach, three rules are systematically grouped together, i.e., task selection, task assignment, and task exchange rules. The sufficient conditions for implementing the exchange rules are proposed and proved. Thirteen small or medium scale benchmark issues comprising 63 instances were solved, where the computational results demonstrate the efficiency and effectiveness of the proposed method compared with integer programming. The computational results obtained for 18 examples comprising 121 instances demonstrate that the task exchange rules significantly improve the computational accuracy compared with the traditional heuristic. Finally, 30 new standard instances produced by a systematic data generation process were also solved effectively by the proposed approach. The proposed heuristic approach with multiple rules can provide a theoretical basis for other local search algorithms, especially for addressing issues such as the U-Shaped assembly line balancing problem.

MSC:

90B30 Production models

Software:

SALBPGen
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gökcen, H.; Ağpak, K., A goal programming approach to simple U-line balancing problem, Eur. J. Oper. Res., 171, 577-585 (2006) · Zbl 1090.90061
[2] Hwang, R.; Katayama, H., A multi-decision genetic approach for workload balancing of mixed-model U-shaped assembly line systems, Int. J. Prod. Res., 47, 14, 3797-3822 (2009)
[3] Kara, Y.; Paksoy, T.; Chang, C. T., Binary fuzzy goal programming approach to single model straight and U-shaped assembly line balancing, Eur. J. Oper. Res., 195, 2, 335-347 (2009) · Zbl 1175.90356
[4] Toksarı, M. D.; İsleyen, S. K.; Güner, E.; Baykoc, Ö. F., Simple and U-type assembly line balancing problems with a learning effect, Appl. Math. Model., 32, 12, 2954-2961 (2008)
[5] Baykasoğlu, A.; Dereli, T., Simple and U-type assembly line balancing by using an ant colony based algorithm, Math. Comput. Appl., 14, 1, 1-12 (2009) · Zbl 1186.90126
[6] Özcan, U.; Toklu, B., A new hybrid improvement heuristic approach to simple straight and U-type assembly line balancing problems, J. Intell. Manuf., 20, 123-136 (2009)
[7] Kara, Y.; Özgüven, C.; Yalçın, N.; Atasagun, Y., Balancing straight and U-shaped assembly lines with resource dependent task times, Int. J. Prod. Res., 49, 21, 6387-6405 (2011)
[8] Miltenburg, G. J.; Wijngaard, J., The U-line balancing problem, Manag. Sci., 40, 10, 1378-1388 (1994) · Zbl 0822.90077
[9] Becker, C.; Scholl, A., A survey on problems and methods in generalized assembly line balancing, Eur. J. Oper. Res., 168, 694-715 (2006) · Zbl 1083.90013
[10] Hamzadayi, A.; Yildiz, G., A genetic algorithm based approach for simultaneously balancing and sequencing of mixed-model U-lines with parallel workstations and zoning constraints, Comput. Ind. Eng., 62, 206-215 (2012)
[11] Kazemi, S. M.; Ghodsi, R.; Rabbani, M.; Tavakkoli-Moghaddam, R., A novel two-stage genetic algorithm for a mixed-model U-line balancing problem with duplicated tasks, Int. J. Adv. Manuf. Technol., 55, 1111-1122 (2011)
[12] Manavizadeh, N.; Hosseini, N.; Rabbani, M.; Jolai, F., A simulated annealing algorithm for a mixed model assembly U-line balancing type-1 problem considering human efficiency and just-in-time approach, Comput. Ind. Engineering, 64, 2, 669-685 (2013)
[13] Rabbani, M.; Kazemi, S. M.; Manavizadeh, N., Mixed model U-line balancing type-1 problem: a new approach, J. Manuf. Syst., 31, 131-138 (2012)
[14] Bagher, M.; Zandieh, M.; Farsijani, H., Balancing of stochastic U-type assembly lines: an imperialist competitive algorithm, Int. J. Adv. Manuf. Technol., 54, 1-4, 271-285 (2011)
[15] Baykasoğlu, A.; Özbakrı, L., Stochastic U-line balancing using genetic algorithms, Int. J. Adv. Manuf. Technol., 32, 1-2, 139-147 (2007)
[16] Özcan, U.; Kellegöz, T.; Toklu, B., A genetic algorithm for the stochastic mixed-model U-line balancing and sequencing problem, Int. J. Prod. Res., 49, 6, 1605-1626 (2011)
[17] Urban, T. L.; Chiang, W. C., An optimal piecewise-linear program for the U-line balancing problem with stochastic task times, Eur. J. Oper. Res., 168, 3, 771-782 (2006) · Zbl 1083.90029
[18] Alavidoost, M. H.; Babazadeh, H.; Sayyari, S. T., An interactive fuzzy programming approach for bi-objective straight and U-shaped assembly line balancing problem, Appl. Soft Comput. J., 40, 221-235 (2016)
[19] Nourmohammadi, A.; Zandieh, M.; Tavakkoli-Moghaddam, R., An imperialist competitive algorithm for multi-objective U-type assembly line design, J. Comput. Sci., 4, 393-400 (2013)
[20] Kucukkoc, I.; Zhang, D. Z., Coping with model variations on parallel u-shaped assembly line configurations, IFAC Proc. Vol. (IFAC-Papers Online), 48, 3, 2030-2035 (2015)
[21] Kucukkoc, I.; Zhang, D. Z., Balancing of parallel U-shaped assembly lines, Comput. Oper. Res., 64, C, 233-244 (2015) · Zbl 1349.90285
[22] Fattahi, A.; Elaoud, S.; Azer, S.; Turkay, M., A novel integer programming formulation with logic cuts for the U-shaped assembly line balancing problem, Int. J. Prod. Res., 52, 5, 1318-1333 (2014)
[23] Sabuncuoglu, I.; Erel, E.; Alp, A., Ant colony optimization for the single model U-type assembly line balancing problem, Int. J. Prod. Econ., 120, 2, 287-300 (2009)
[24] Avikal, S.; Jain, R.; Mishra, P. K.; Yadav, H. C., A heuristic approach for U-shaped assembly line balancing to improve labor productivity, Comput. Ind. Eng., 64, 4, 895-901 (2013)
[25] Gökcen, H.; Ağpak, K.; Gencer, C.; Kizilkaya, E., A shortest route formulation of simple U-type assembly line balancing problem, Appl. Math. Model., 29, 373-380 (2005) · Zbl 1077.90022
[26] Hamta, N.; Ghomi, S. M.T. F.; Jolai, F.; Bahalke, U., Bi-criteria assembly line balancing by considering flexible operation times, Appl. Math. Model., 35, 12, 5592-5608 (2011) · Zbl 1228.90034
[27] Lapierre, S. D.; Ruiz, A.; Soriano, P., Balancing assembly lines with tabu search, Eur. J. Oper. Res., 168, 3, 826-837 (2006) · Zbl 1083.90017
[28] Otto, C.; Otto, A., How to design effective priority rules: example of simple assembly line balancing, Comput. Ind. Eng., 69, 43-52 (2014)
[29] Qiaoxian, Z.; Ming, L.; Yuanxiang, L.; Qiuhua, T., Station ant colony optimization for the type 2 assembly line balancing problem, Int. J. Adv. Manuf. Technol., 66, 1859-1870 (2013)
[30] Helgeson, W. B.; Birnie, D. P., Assembly line balancing using the ranked positional weight technique, J. Ind. Eng., 12, 6, 394-398 (1961)
[31] Scholl, A., Balancing and Sequencing of Assembly Lines (1999), Physica: Physica Heidelberg
[32] Scholl, A.; Becker, C., State-of-the-art exact and heuristic solution procedures for simple assembly line balancing, Eur. J. Oper. Res., 168, 666-693 (2006) · Zbl 1083.90019
[33] Otto, A.; Otto, C.; Scholl, A., Systematic data generation and test design for solution algorithms on the example of SALBPGen for assembly line balancing, Eur. J. Oper. Res., 228, 1, 33-45 (2013) · Zbl 1332.90176
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.