نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانش‌آموخته کارشناسی‌ارشد مهندسی صنایع، دانشگاه صنعتی شیراز، شیراز، ایران

2 دانشیار دانشکده مهندسی صنایع، دانشگاه صنعتی شیراز، شیراز، ایران

3 دانشیار گروه مهندسی صنایع، مرکز آموزش عالی فیروزآباد، فیروزآباد، ایران

چکیده

شکل متمرکز است که در آن توابع -U این مقاله بر ارائه یک مدل جدید برای مسئله بالانس خط مونتاژ
هدف از جنس هزینه، ظرفیت و کیفیت به طور هم زمان در قالب یک مسئله بررسی می شود. بهعلاوه فرض
شده هر وظیفه به مجموعه ای از ابزارآلات نیاز دارد و کیفیت انجام وظایف توسط کارگرها نیز متفاوت
است؛ بنابراین هدف مدل این است که تجهیزات و کارگران بهنحوی به ایستگاه ها تخصیص یابند که
مجموع هزینهی تجهیزات حداقل شود و کیفیت انجام کار در بالاترین سطح ممکن قرار گیرد. علاوه بر این
دو هدف، تعداد ایستگاه ها نیز کمینه میشوند. به این منظور، ابتدا یک مدل برنامهریزی چندهدفه غیرخطی
آمیخته عدد صحیح ارائه می شود. سپس مدل، خطیسازی شده و برای حل مسئله، الگوریتم فراابتکاری
شبیهسازی تبرید و نیز دو حالت بهبودیافته ی آن به کارگیری می شود. دو الگوریتم پیشنهادی شامل یک
برنامه رمزگذاری و رمزگشایی جدید و نیز جستجوی محلی برای تخصیص کارگر به هر ایستگاه است.
برای تعیین حدود پارامترها در این سه الگوریتم از روش طراحی آزمایش استفاده شده و به ازاء ترکیب
پارامترها، حالت های مختلفی برای حل مسئله ایجاد شده است. سپس، بر اساس گراف های موجود در
ادبیات تحقیق مثال های عددی ایجاد و نتایج حل آنها با سه الگوریتم مقایسه و کارایی الگوریتم ها سنجش
می شوند. به علاوه، برای ارزیابی کارایی مدل و الگوریتم پیشنهادی در مسائل واقعی، مطالعه موردی در خط
مونتاژ قطعه نازل انجام گردید که در پالایشگاه های نفت کاربرد دارد. نتایج حل مطالعه موردی و بررسی
شاخص های عملکرد برای آن، بیانگر کارایی و عملکرد بهتر حالتهای بهبودیافته الگوریتم شبیهسازی
تبرید است.

کلیدواژه‌ها

عنوان مقاله [English]

Providing a multi-objective programming model for U-shaped assembly line balancing with equipment assignment and task performing quality level

نویسندگان [English]

  • Morteza Khorram 1
  • Mahmood Eghtesadifard 2
  • Sadegh Niroomand 3

1 MSc. in Industrial Engineering, Faculty of Industrial Engineering, Shiraz University of Technology, Shiraz, Iran

2 Associate Professor, Faculty of Industrial Engineering, Shiraz University of Technology, Shiraz, Iran (Corresponding Author)

3 Associate Professor, Department of Industrial Engineering, Firouzabad Institute of Higher Education, Firouzabad, Fars, Iran

چکیده [English]

This paper focuses on a novel model of the U-shaped assembly line balancing problem, in which the objective functions include cost, capacity, and quality. It is assumed that each task requires a set of equipment. In addition, the quality of tasks performed by each worker varies. Hence, the purpose of the model is that the total cost of the equipment is minimized and the quality of the work is maximized. Additionally, the number of workstations is minimized. At first, a multi-objective non-linear mixed-integer programming model is provided. Then, the model is linearized, and simulated annealing (SA) algorithm and two of its modified modes have been proposed to solve the problem. The proposed algorithm includes a new encoding/decoding scheme, as well as a local search for assigning the worker to each station. To determine the parameters in three algorithms, the experimental design has been used and various modes have been created by combining the parameters. Moreover, numerical examples were established based on the graphs found in the literature and the solution is compared with three algorithms, revealing the efficiency of each algorithm. Additionally, a case study on the nozzle assembly line in oil refineries was conducted to evaluate the efficiency of the proposed model and algorithm. Results from the case study show that the modified SA algorithms performed better.
Introduction
Nowadays, assembly lines play a crucial role in the production of standardized and high-volume products. If task allocation to workstations is done without considering the balance of the assembly line, it can lead to high levels of idle time in some workstations and decreased line efficiency. Therefore, assembly line balancing is an important stage in the production process to enhance production line productivity. This study focuses on the single-model U-shaped assembly line balancing problem. Assembly lines can be divided into four categories based on their layout, and in this research, the U-shaped assembly lines are specifically considered. The objectives of this problem include minimizing the number of workstations, minimizing equipment costs, and minimizing the level of work quality deviation at each workstation (equivalent to maximizing work quality). Additionally, constraints related to occurrence, precedence, and capacity, as well as limitations on tool and worker allocations, have been considered in the problem model. In terms of research gaps in this field, it should be noted that in previous studies on U-shaped assembly line balancing problems, objective functions combining cost, capacity, and quality have not been simultaneously addressed within a single problem. Furthermore, simultaneous allocation of workers (based on skill levels) and tools has not been studied in the context of U-shaped assembly line balancing problems.
Materials and Methods
In this study, a nonlinear mixed-integer multi-objective programming model is proposed for balancing a single-model U-shaped assembly line. The problem modeling assumes realistic conditions where each task requires a set of tools, and in this regard, the quality of task execution by workers is considered to be different. The modeling of quality in the assembly line balancing problem (as one of the objective functions) is approached differently compared to previous studies in this field, aiming to minimize the level of work quality deviation in all workstations. Additionally, for solving the problem, the allocation of workers and tools to the workstations is performed based on a neighborhood algorithm, which is a notable innovation in the research. In this study, a modified simulated annealing metaheuristic algorithm is developed with innovations in encoding and decoding procedures to solve the proposed model in three optimization scenarios. To compare the results of these algorithms, numerical examples based on graphs available in the research literature are solved using the three algorithms. Furthermore, a case study is conducted on the assembly line of component δ, which is used in oil refineries, to evaluate the efficiency of the proposed model and algorithm in real assembly lines.
Discussion and Results
In this study, to validate the proposed algorithms, 10 numerical examples of different sizes (small, medium, and large) were designed based on valid graphs available in the research literature. Then, for various parameter values, each problem was solved 10 times using each algorithm, and the results of each algorithm were analyzed. In these examples, the costs of tools and the data related to task quality were randomly generated. Additionally, workers with different skills were defined to perform the tasks. Furthermore, the cycle time proportional to the activity durations was considered. It is observed that in all solved examples, the values of the third objective function (quality objective function) obtained from the third algorithm are better than the values obtained from the first and second algorithms. These results are not unexpected because in the third algorithm, due to the presence of an improvement loop for the third objective function, its value decreases compared to the other two algorithms, resulting in a reduction in the overall objective function and its improvement compared to the other two algorithms. For the cost minimization objective function (first objective function) and the number of workstations minimization objective function (second objective function), the values obtained from the three algorithms are approximately the same, and the difference in the obtained values for the overall objective function is primarily dependent on the value of the quality objective function (third objective function). Additionally, the results of solving the numerical examples show that the third algorithm achieves the best values for the overall objective function (compared to the other two algorithms) on examples with more than 25 activities, indicating that employing a local search for worker allocation in the modified simulated annealing algorithm makes the algorithm stronger and more efficient compared to its classical form.
Conclusion
In this research, the modeling and problem-solving of the U-shaped assembly line balancing problem were investigated considering tool allocation constraints and quality conditions. To this end, a mixed integer nonlinear programming model was presented for the problem, where equipment and workers were simultaneously considered as two objectives in terms of minimizing equipment cost and the level of task quality. In addition to these two objectives, the number of workstations was also minimized. To solve the problem, a metaheuristic algorithm called simulated annealing was employed, as well as two improved versions of it (by introducing innovations in the random allocation of workers to workstations and applying a local search for improving worker allocation). The proposed model was solved using well-known graphs in the literature of assembly line balancing problems (as numerical examples) with the proposed algorithms, and the results obtained from the algorithms were compared and the performance of these algorithms was analyzed and examined.

کلیدواژه‌ها [English]

  • U-shaped assembly line balancing problems (UALBPs)
  • simulated annealing algorithm
  • non-linear mixed-integer programming
  • equipment allocation
  • work quality
 
Ajenblit, D. A., & Wainwright, R. L. (1998, May). “Applying genetic algorithms to the U-shaped assembly line balancing problem”, In 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence (Cat. No. 98TH8360) (pp. 96-101). IEEE.
Alavidoost, M. H., Zarandi, M. F., Tarimoradi, M., & Nemati, Y. (2017). “Modified genetic algorithm for simple straight and U-shaped assembly line balancing with fuzzy processing times”, Journal of intelligent manufacturing, 28(2), 313-336.
Aydoğan, B. İ., Ceyhan, K., Şahin, M., & Çorapçıoğlu, D. (2019). “Are thyroid nodules with spongiform morphology always benign?” Cytopathology, 30(1), 46-50.
Baykasoglu, A. (2006). “Multi-rule multi-objective simulated annealing algorithm for straight and U type assembly line balancing problems”, Journal of Intelligent Manufacturing, 17(2), 217-232.
Bowman, E. H. (1960). “Assembly-line balancing by linear programming” Operations Research, 8(3), 385-389.
Campana, N. P., Iori, M., & Moreira, M. C. O. (2021). Mathematical models and heuristic methods for the assembly line balancing problem with hierarchical worker assignment. International Journal of Production Research, 1-19.
Chang, C. T., & Chang, C. C. (2000). “A linearization method for mixed 0–1 polynomial programs”, Computers & Operations Research, 27(10), 1005-1016.
Charnes, A., & Cooper, W. W. (1962). “Programming with linear fractional functionals”, Naval Research logistics quarterly, 9(3‐4), 181-186.
Corominas, A., García-Villoria, A., & Pastor Moreno, R. (2016). Improving the resolution of the simple assembly line balancing problem type E. SORT1, 227-242.
Costa, N. R., & Pereira, Z. L. (2010). “Multiple response optimization: a global criterion‐based method”, Journal of chemometrics, 24(6), 333-342.
Deckro, R. F., & Rangachari, S. (1990). “A goal approach to assembly line balancing”, Computers & operations research, 17(5), 509-521.
Delice, Y., Aydoğan, E. K., Özcan, U., & İlkay, M. S. (2017). Balancing two-sided U-type assembly lines using modified particle swarm optimization algorithm. 4or15(1), 37-66.
Delice, Y., Kızılkaya Aydoğan, E., & Özcan, U. (2016). Stochastic two-sided U-type assembly line balancing: a genetic algorithm approach. International Journal of Production Research54(11), 3429-3451.
Dong, J., Zhang, L., & Xiao, T. (2018). A hybrid PSO/SA algorithm for bi-criteria stochastic line balancing with flexible task times and zoning constraints. Journal of Intelligent Manufacturing29(4), 737-751.
Eghtesadifard, M., Khalifeh, M., & Khorram, M. (2020). A systematic review of research themes and hot topics in assembly line balancing through the web of science within 1990–2017. Computers & Industrial Engineering139, 106182.
Fang, Y., Ming, H., Li, M., Liu, Q., & Pham, D. T. (2020). Multi-objective evolutionary simulated annealing optimisation for mixed-model multi-robotic disassembly line balancing with interval processing time. International Journal of Production Research58(3), 846-862.
Fathi, M., Á lvarez, M. J., & Rodríguez, V. (2016). “A new heuristic-based bi-objective simulated annealing method for U-shaped assembly line balancing”, European Journal of Industrial Engineering, 10(2), 145-169.
Fathi, M., Nourmohammadi, A., Ng, A. H., Syberfeldt, A., & Eskandari, H. (2019). An improved genetic algorithm with variable neighborhood search to solve the assembly line balancing problem. Engineering Computations.
Fattahi, P., Roshani, A., & Roshani, A. (2011). “A mathematical model and ant colony algorithm for multi-manned assembly line balancing problem”, International Journal of Advanced Manufacturing Technology, 53(1-4), 363-378.
Glover, F., & Woolsey, E. (1974). “Converting the 0-1 polynomial programming problem to a 0-1 linear program”, Operations research, 22(1), 180-182.
Gökçen, H., & Agˇpak, K. (2006). “A goal programming approach to simple U-line balancing problem”, European Journal of Operational Research, 171(2), 577-585.
Gökçen, H., Ağpak, K., & Benzer, R. (2006). “Balancing of parallel assembly lines”, International Journal of Production Economics, 103(2), 600-609.
Kalayci, C. B., Polat, O., & Gupta, S. M. (2016). A hybrid genetic algorithm for sequence-dependent disassembly line balancing problem. Annals of Operations Research242(2), 321-354.
Kellegöz, T. (2017). Assembly line balancing problems with multi-manned stations: a new mathematical formulation and Gantt based heuristic method. Annals of Operations Research253(1), 377.
Khorram, M., Eghtesadifard, M., & Niroomand, S. (2021). Hybrid meta-heuristic algorithms for U-shaped assembly line balancing problem with equipment and worker allocations. Soft Computing, 1-18.
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). “Optimization by simulated annealing”, Science, 220(4598), 671-680.
Kucukkoc, I., & Zhang, D. Z. (2015). “Type-E parallel two-sided assembly line balancing problem: Mathematical model and ant colony optimisation based approach with optimised parameters”, Computers & Industrial Engineering, 84, 56-69.
Kucukkoc, I., & Zhang, D. Z. (2017). Balancing of mixed-model parallel U-shaped assembly lines considering model sequences. International Journal of Production Research55(20), 5958-5975.
Li, Z., Janardhanan, M. N., Ashour, A. S., & Dey, N. (2019). Mathematical models and migrating birds optimization for robotic U-shaped assembly line balancing problem. Neural Computing and Applications31(12), 9095-9111.
Li, Z., Kucukkoc, I., & Tang, Q. (2017). “New MILP model and station-oriented ant colony optimization algorithm for balancing U-type assembly lines”, Computers & Industrial Engineering, 112, 107-121.
Li, Z., Kucukkoc, I., & Zhang, Z. (2018). Branch, bound and remember algorithm for U-shaped assembly line balancing problem. Computers & Industrial Engineering124, 24-35.
Li, Z., Kucukkoc, I., & Zhang, Z. (2020). Branch, bound and remember algorithm for two-sided assembly line balancing problem. European Journal of Operational Research284(3), 896-905.
Make, M. R. A., Rashid, M. F. F. A., & Razali, M. M. (2017). “A review of two-sided assembly line balancing problem”, International Journal of Advanced Manufacturing Technology, 89(5-8), 1743-1763.
Manavizadeh, N., Hosseini, N. S., Rabbani, M., & Jolai, F. (2013). “A Simulated Annealing algorithm for a mixed model assembly U-line balancing type-I problem considering human efficiency and Just-In-Time approach”, Computers & Industrial Engineering, 64(2), 669-685.
McMullen, P. R., & Frazier, G. V. (1998). “Using simulated annealing to solve a multiobjective assembly line balancing problem with parallel workstations”, International Journal of Production Research, 36(10), 2717-2741.
Miltenburg, G. J., & Wijngaard, J. (1994). “The U-line line balancing problem”, Management science, 40(10), 1378-1388.
Mukund Nilakantan, J., & Ponnambalam, S. G. (2016). Robotic U-shaped assembly line balancing using particle swarm optimization. Engineering Optimization48(2), 231-252.
Norouzi, N., Tavakkoli-Moghaddam, R., Ghazanfari, M., Alinaghian, M., & Salamatbakhsh, A. (2012). A new multi-objective competitive open vehicle routing problem solved by particle swarm optimization. Networks and Spatial Economics12(4), 609-633.
Ogan, D., & Azizoglu, M. (2015). “A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements”, Journal of Manufacturing Systems, 36, 46-54.
Ogan, D., & Azizoglu, M. (2015). A branch and bound method for the line balancing problem in U-shaped assembly lines with equipment requirements. Journal of Manufacturing Systems36, 46-54.
Özcan, U., & Toklu, B. (2009). “Balancing of mixed-model two-sided assembly lines”, Computers & Industrial Engineering, 57(1), 217-227.
Patterson, J. H., & Albracht, J. J. (1975). “Assembly-line balancing: zero-one programming with Fibonacci search”, Operations Research, 23(1), 166-172.
Pereira, J., & Álvarez-Miranda, E. (2018). “An exact approach for the robust assembly line balancing problem”, Omega, 78, 85-98.
Pınarbaşı, M. (2021). New chance-constrained models for U-type stochastic assembly line balancing problem. Soft Computing, 1-15.
Pitakaso, R., & Sethanan, K. (2016). Modified differential evolution algorithm for simple assembly line balancing with a limit on the number of machine types. Engineering Optimization48(2), 253-271.
Proos, K. A., Steven, G. P., Querin, O. M., & Xie, Y. M. (2001). “Multicriterion evolutionary structural optimization using the weighting and the global criterion methods”, AIAA journal, 39(10), 2006-2012.
Rashid, M. F. F., Hutabarat, W., & Tiwari, A. (2012). “A review on assembly sequence planning and assembly line balancing optimisation using soft computing approaches”, International Journal of Advanced Manufacturing Technology, 59(1-4), 335-349.
Roshani, A., & Giglio, D. (2017). Simulated annealing algorithms for the multi-manned assembly line balancing problem: minimising cycle time. International Journal of Production Research55(10), 2731-2751.
Saif, U., Guan, Z., Wang, B., Mirza, J., & Huang, S. (2014). “A survey on assembly lines and its types”, Frontiers of Mechanical Engineering, 9(2), 95-105.
Scholl, A. (1995). Data of assembly line balancing problems. Techn. Hochsch., Inst. für Betriebswirtschaftslehre.
Sivasankaran, P., & Shahabudeen, P. (2014). “Literature review of assembly line balancing problems”, International Journal of Advanced Manufacturing Technology, 73(9-12), 1665-1694.
Sparling, D., & Miltenburg, J. (1998). “The mixed-model U-line balancing problem”, International Journal of Production Research, 36(2), 485-501.
Suman, B., & Kumar, P. (2006). “A survey of simulated annealing as a tool for single and multiobjective optimization”, Journal of the operational research society, 57(10), 1143-1160.
Suresh, G., & Sahu, S. (1994). “Stochastic assembly line balancing using simulated annealing”, International Journal of Production Research, 32(8), 1801-1810.
Talbi, E. G. (2009). “Metaheuristics: from design to implementation” (Vol. 74). John Wiley & Sons.
Torabi, S. M. (1993). Theoretical Analysis of the Alignment of the Assembly Line with the Aim of Comparing and Presenting an Optimal Balancing Algorithm in the Engine Assembly Unit of the Iran Khodro Factory. Master Thesis, Tehran: Tarbiat Modarres University, (In Persian)
Vilarinho, P. M., & Simaria, A. S. (2002). “A two-stage heuristic method for balancing mixed-model assembly lines with parallel workstations”, International Journal of Production Research, 40(6), 1405-1420.
Wang, K., Li, X., Gao, L., Li, P., & Gupta, S. M. (2021). A genetic simulated annealing algorithm for parallel partial disassembly line balancing problem. Applied Soft Computing107, 107404.
Zhang, H., Yan, Q., Liu, Y., & Jiang, Z. (2016). An integer-coded differential evolution algorithm for simple assembly line balancing problem of type 2. Assembly Automation.
Zhang, Z., Tang, Q., & Zhang, L. (2019). Mathematical model and grey wolf optimization for low-carbon and low-noise U-shaped robotic assembly line balancing problem. Journal of Cleaner Production215, 744-756.
Zhang, Z., Tang, Q., Han, D., & Li, Z. (2019). Enhanced migrating birds optimization algorithm for U-shaped assembly line balancing problems with workers assignment. Neural Computing and Applications31(11), 7501-7515.
Zhang, Z., Tang, Q., Li, Z., & Zhang, L. (2019). Modelling and optimisation of energy-efficient U-shaped robotic assembly line balancing problems. International Journal of Production Research57(17), 5520-5537.
Zhang, Z., Tang, Q., Ruiz, R., & Zhang, L. (2020). Ergonomic risk and cycle time minimization for the U-shaped worker assignment assembly line balancing problem: A multi-objective approach. Computers & Operations Research118, 104905.
Zhong, Y. G., & Ai, B. (2017). A modified ant colony optimization algorithm for multi-objective assembly line balancing. Soft Computing21(22), 6881-6894.