مدل‌سازی ریاضی و الگوریتم رقابت استعماری برای مسئله خط مونتاژ جریان کارگاهی

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

نویسندگان

1 دانشجوی دکتری، دانشگاه آزاد اسلامی، قزوین.

2 دانشیار، دانشگاه آزاد اسلامی، قزوین.

3 دانشیار، دانشگاه خوارزمی.

چکیده

مونتاژ جریان کارگاهی دومرحله‌ای با در­نظر­گرفتن زمان آماده‌سازی، یکی از مسائل جدید زمان‌بندی تولید است. در این مسئله، قطعات در مرحله نخست در یک سیستم جریان کارگاهی تولید و در مرحله دوم، قطعات تولیدی مونتاژ می‌شوند. هدف از حل این مسئله، ارائه توالی بهینه تولید قطعات و مونتاژ آن‌ها است؛ به‌طوری‌که زمان تکمیل آخرین سفارش کمینه شود. با توجه به جدید­بودن موضوع، تاکنون مدل مناسبی برای حل این مسئله ارائه نشده است. این پژوهش ابتدا به بررسی مدل موجود می‌پردازد و سپس یک مدل برنامه‌ریزی خطی عدد صحیح مختلط برای حل مسئله ارائه می‌دهد؛ سپس برای حل مؤثر این مسئله، دو الگوریتم فراابتکاری رقابت استعماری و ژنتیک ارائه می‌شود. در ادامه عملکرد مدل و الگوریتم‌ها ارزیابی می‌شوند. نتایج نشان می‌دهد الگوریتم رقابت استعماری عملکرد بهتری دارد.

کلیدواژه‌ها

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

Algorithm for Assembly Flowshops

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

  • Habib Reza Gholami 1
  • Esmaeil Mehdizadeh 2
  • Bahman Naderi 3
1 PhD student, Islamic Azad University, Qazvin.
2 Associate Professor, Islamic Azad University, Qazvin.
3 Associate Professor, Kharazmi University.
چکیده [English]

Assembly flowshop with setup times is one of the newset production scheduling problems. In this problem, parts in the first stage that is a flow shop system are produced. Then, in the second stage, they are assembled. The objective is to sequence the parts production and assembly to minimize makespan. There is not an effective mathematical model for this problem. This paper first reviews the available model and then proposes a mixed integer linear programming model. To solve the model, it proposes two metaheuristics, imperialist competitive and genetic algorithms. Finally, the performance of the model and algorithms are evaluated, and the results show that imperialist competitive algorithm performs well.

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

  • Mixed Integer Linear Programming
  • Assembly Flow Shops
  • Setup Times
  • Imperialist Competitive Algorithm
  • Genetic Algorithm

مراجع

1. Allahverdi, A., & Al-Anzi, F.S. (2006). A PSO and a tabu search heuristics for assembly scheduling problem of the two-stage. Computers & Operations Research, 33, 1056-1080.
2. Asadzadeh, L., & Zamanifar, K. (2010). An agent-based parallel approach for the job shop scheduling problem with genetic algorithms. Mathematical and Computer Modelling, 52, 1957-1965.
3. Atashpaz-Gargari, E., & Lucas, C. (2007). Imperialist competitive algorithm: an algorithm for optimization inspired by imperialistic competition. IEEE Congress, 4661-4670.
4. Attar, S.F., Mohammadi, M., & Tavakkoli-Moghaddam, M. (2011). A novel imperialist competitive algorithm to solve flexible flow shop scheduling problem in order to minimize maximum completion time, International Journal of Computer Applications, 28, 27-32.
5. Caraffa, V., Ianes S.P., Bagchi, T., & Sriskandarajah, C. (2001). Makespan Minimizing makespan in a blocking flowshop using genetic algorithms. International Journal of Production Economics, 70(2), 101-115.
6. Forst, F. (1983). Minimizing total expected costs in the two-machine, stochastic flow shop. Operations Research Letters, 2(2), 58-61.
7. Hariri, A.M.A., & Potts, C.N. (1997). A branch and bound algorithm for the two-stage assembly scheduling Problem. European Journal of Operational Research, 103, 547-556.
8. Hatami, S., Ebrahimnejad, S., Tavakkoli-Moghaddam R., & Maboudian, Y. (2010). Two meta-heuristics for three stage assembly flowshop scheduling with sequence-dependent setup times. International Journal ofAdvanced Manufacturing Technology, 50, 1153-1164.
9. Hendizadeh, S.H., ElMekkawy, T.Y., & Wang, G.G. (2007). Bi-criteria scheduling of a flowshop manufacturing cell with sequence dependent setup times. European Journal of Industrial Engineering, 1, 391-413.
10. Khakbiz, M., Rezaei Pendari, A., Dehghan Niri, M., (2017). Mathematical model for diversifying stock portfolio and solving with genetic algorithm, Industrial Management Prespective, 24, 173-196 (In Persian).
11. Kazemi, H., Mahdavi Mazdeh M., & Rostami, M. (2017). The two stage assembly flow-shop scheduling problem with batching and delivery, Engineering Applications of Artificial Intelligence, 63, 98-107.
12. Komaki G.M., Kayvanfar V., (2015). Grey Wolf Optimizer algorithm for the two-stage assembly flow shop scheduling problem with release time, Journal of Computational Science, 8, 109-120.
13. Koulamas, C., & Kyparisis, G.J. (2001). The three-stage assembly flowshop scheduling problem. Computers & Operations Research, 28, 689-704.
14. Javadian, N., Mozdgir, A., Gazani Koohi, E., Davallo Qajar, M.R., & Shiraqai M.E. (2009). Solving assembly flowshop scheduling problem with parallel machines using variable neighborhood search. In Proceedings of 39th International Conference of Computers and Industrial Engineering, University ofTechnology of Troyes, Paris, France, 102-107.
15. Lee, C.Y., Cheng, T.C.E., & Lin, B.M.T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem, Management Science, 39, 616-625.
16. Lin J.., Wang Z.J., Li X. (2017). A backtracking search hyper-heuristic for the distributed assembly flow-shop scheduling problem, Swarm and Evolutionary Computation, 36, 124-135.
17. Navaei J., Ghomi S.M.T.F., Jolai F., Shiraqai M.E., & Hidaji H., (2013). Two-stage flow-shop scheduling problem with non-identical second stage assembly machines. International Journal of Advanced Manufacturing Technology, 69, 2215-2226.
18. Navaei, J., Fatemi Ghomi, S.M.T., Jolai, F., & Mozdgir, A. (2014). Heuristics for an assembly flow-shop with non-identical assembly machines and sequence dependent setup times to minimize sum of holding and delay costs. Computers & Operations Research, 44, 52-65.
19. Navaei, J., Mozdgir, A., & Hidaji, H. (2010). Two-stage assembly flow-shop scheduling problem with bi-objective of number of tardy and makespan minimization. In: Proceedings of the 2010 International Conferenceon Artificial Intelligence, Las Vegas, Nevada, USA, 704-709.
20. Potts, C.N., Sevastjanov, S.V., Strusevich, V.A., Van Wassenhove, L.N., & Zwaneveld, C.M. (1995). The two-stage assembly scheduling problem: complexity and approximation, Operations Research, 43, 346-355.
21. Rahimi Shekh, H, Sharifi, M, & Shahriari M.R, A model for resialent supply chain: Case study in National healthcare organization, Industrial Management Prespective, 27, 127-150 (In Persian).
22. Ruiz, R, & Allahverdi, A. (2007). No-wait flowshop with separate setup times to minimize maximum lateness. International Journal of Advanced Manufacturing Technology, 35, 551-565.
23. Soke, A., & Bingul, Z. (2006). Hybrid genetic algorithm and simulated annealing for two-dimensional nonguillotine rectangular packing problems. Engineering Applications of Artificial Intelligence, 19, 557-567.
24. Sung, C.S., & Juhn, J. (2009). Makespan minimization for a 2-stage assembly scheduling problem subject to component available time constraint. International Journal of Production Economics, 119, 392- 401.
25. Torabzadeh, E., & Zandieh. M. (2010). Cloud Theory-Based Simulated Annealing Approach for Scheduling in the Two-Stage Assembly Flowshop. Advances in Engineering Software, 41, 1238-1243.
26. Tozkapan, A., Kirca, O., and Chung, C.S. (2003). A branch and bound algorithm to minimize the total weighted flow time for the two-stage assembly scheduling problem, Computers & Operations Research, 30, 309-320.
27. Wu C.C., Chen J.Y., Lin W.C., Lai K., Liu S.C., & Yu P.W., (2018). A two-stage three-machine assembly flow shop scheduling with learning consideration to minimize the flowtime by six hybrids of particle swarm optimization, Swarm and Evolutionary Computation, doi.org/10.1016/j.swevo.2018.01.012.
28. Zandieh, M., Fotovat, A. (2015). A general flow shop scheduling problem with consideration of position- based learning effect and multiple availability constraints. Industrial Management Prespective, 20, 41-58 (In Persian).

فایل ها

هم رسانی

ارجاع به این مقاله

آمار