زمان‌بندی تولید کارگاهی انعطاف‌پذیر با منابع دوگانه‌ی محدود و اهداف لکزیکوگراف

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

نویسندگان

1 استادیار، گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه قم، قم، ایران

2 کارشناسی ارشد، مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه قم، قم، ایران

چکیده

در این تحقیق، مسئله‌ی زمان‌بندی تولید کارگاهی انعطاف‌پذیر با محدودیت منابع دوگانه در نظر گرفته شده است. مسئله‌ی زمان‌بندی تولید کارگاهی انعطاف‌پذیر، حالت گسترده‌تری از مسائل زمان‌بندی تولید کارگاهی کلاسیک است و هر عملیات می‌تواند توسط چند ماشین پردازش شود. در زمان‌بندی تولید کارگاهی انعطاف‌پذیر با محدودیت منابع دوگانه، علاوه بر تخصیص ماشین به هر عملیات و تعیین توالی عملیات بر روی ماشین‌ها، لازم است تخصیص کارگر به عملیات را نیز مشخص کنیم. دو هدف حداقل‌سازی مجموع موزون تأخیرها و حداکثر زمان تکمیل کارها به‌صورت لکزیکوگراف مورد بررسی قرار گرفته است که مجموع موزون تأخیرها، اولویت اول است. با توجه به NP-Hard بودن این مسئله، یک الگوریتم ترکیبی کلونی زنبور عسل مصنوعی با عملگرهای الگوریتم ژنتیک و چندین الگوریتم‌ ابتکاری، ارائه می‌شود. به‌منظور اعتبارسنجی و ارزیابی عملکرد الگوریتم ارائه شده، مطالعات محاسباتی با در نظر گرفتن مسائل نمونه، انجام شده و با نتایج نرم‌افزار GAMS مقایسه شده است. نتایج نشان می‌دهد که الگوریتم ترکیبی پیشنهادی، روشی مؤثر برای حل مسئله‌ی زمان‌بندی تولید کارگاهی انعطاف‌پذیر با محدودیت منابع دوگانه است.

کلیدواژه‌ها

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

Dual Resource Constrained Flexible Job-Shop Scheduling with Lexicograph Objectives

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

  • Ghasem Mokhtari 1
  • Mina Abolfathi 2
1 Assistant Professor, Department of Industrial Engineering, Faculty of Engineering, Qom University, Qom, Iran
2 M.A., Industrial Engineering, Faculty of Engineering, Qom University, Qom, Iran
چکیده [English]

In this research, the dual resource constrained flexible job-shop scheduling problem (DRCFJSP) is considered. Compared to the flexible job-shop scheduling, there is a limited research on DRCFJSP. The flexible job-shop scheduling problem is an extension of the classical job-shop scheduling problem by allowing an operation to be assigned to one of a set of eligible machines during scheduling. Hence, solving DRCFJSP not only needs to determine the processing sequences on machines and assign each operation to a machine, but also needs to determine a worker among a set of skilled workers for processing operation on the selected machine. The problem in this study was investigated to minimize two objectives consisting of total weighted tardiness and maximum completion time. The lexicographic approach is applied to compare the solutions and select the optimum solution. The first objective function is total weighted tardiness. DRCFJSP is strongly NP-hard, so a hybrid artificial bee colony algorithm is proposed to solve medium and large instances. In order to evaluate the performance of the proposed algorithm, computational studies have been conducted and compared with the results of the GAMS software. The results show that proposed hybrid algorithm has an appropriate performance for solving the DRCFJSP.

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

  • Dual resource constrained flexible
  • job-shop scheduling problem
  • Artificial bee colony algorithm
  • Total weighted tardiness
  • Maximum completion time

مراجع

[1]    Yazdani, M., Zandieh, M., Tavakkoli-Moghaddam, R., & Jolai, F. (2015). Two meta-heuristic algorithms for the dual-resource constrained flexible job-shop scheduling problem. Scientia Iranica. Transaction E, Industrial Engineering, 22(3): 12-42.
[2]    Gao, L., & Pan, Q. K. (2016). A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem. Information Sciences, 372: 655-676.
[3]    Gonzalez, T., & Sahni, S. (1978). Flow shop and job shop schedules: complexity and approximation. Operations research, 26(1): 36-52.
[4]    Du, J., & Leung, J.Y.T. (1990).  Minimizing Total Tardiness on One Machine Is NP-Hard. Mathematics of Operations Research, 15(3): 483-495.
[5]    Baker, K. R. (1974). Introduction to sequencing and scheduling. John Wiley & Sons.
[6]    Brucker, P., & Schlie, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45(4): 369-375.
[7]    Shahsavari-Pour, N., & Ghasemishabankareh, B. (2013). A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling. Journal of Manufacturing Systems, 32(4): 771-780.
[8]    Sobeyko, O., & Mönch, L. (2016). Heuristic approaches for scheduling jobs in large-scale flexible job shops. Computers & Operations Research, 68: 97-109.
[9]    Rooyani, D., & Defersha, F. M. (2019). An Efficient Two-Stage Genetic Algorithm for Flexible Job-Shop Scheduling. IFAC PapersOnLine, 52(13): 2519–2524.
[10] Fakhrzad, M.B., & Alinezhad, E. (2013). Advanced planning and scheduling with a learning effect in the flexible job shop manufacturing system. Journal of Industrial Engineering Research in Production Systems, 1(1): 13-24.
[11] Nelson, R. T. (1967). Labor and machine limited production systems. Management Science, 13(9): 648-671.
[12] Jaber, M. Y., & Neumann, W. P. (2010). Modelling worker fatigue and recovery in dual-resource constrained systems. Computers & Industrial Engineering, 59(1): 75-84.
[13] Li, J., Sun, S., Huang, Y., & Wang, N. (2010, June). A hybrid algorithm for scheduling of dual-resource constrained job shop. Computing, Control and Industrial Engineering (CCIE), 2010 International Conference on, 1: 235-238.
[14] Lobo, B. J., Hodgson, T. J., King, R. E., Thoney, K. A., & Wilson, J. R. (2013). An effective lower bound on Lmax in a worker-constrained job shop. Computers & Operations Research, 40(1): 328-343.
[15] Lei, D., & Guo, X. (2014). Variable neighborhood search for dual-resource constrained flexible job shop scheduling. International Journal of Production Research, 52(9): 2519-2529.
[16] Liu, X. X., Liu, C. B., & Tao, Z. (2011). Research on Bi-Objective Scheduling of Dual-Resource Constrained Flexible Job Shop. Advanced Materials Research, 211: 1091-1095.
[17] Lang, M., & Li, H. (2011). Research on dual-resource multi-objective flexible job shop scheduling under uncertainty. 2nd International Conference on Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC), Dengleng, China, 8-10 Aug. 2011, 1375-1378.
[18] Xianzhou, C., & Zhenhe, Y. (2011, March). An improved genetic algorithm for dual-resource constrained flexible job shop scheduling. Intelligent Computation Technology and Automation (ICICTA), 2011 International Conference on, 1: 42-45.
[19] Li, J.Q., Pan, S. Xie, S. Wang. (2011). A Hybrid Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problems. International Journal of Computers, Communications & Control, 2: 286-296.
[20] Lian, Z., Jiao, B., & Gu, X. (2006). A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan. Applied mathematics and computation, 183(2): 1008-1017.
[21] Udaiyakumar, K. C., & Chandrasekaran, M. (2014). Application of firefly algorithm in job shop scheduling problem for minimization of makespan. Procedia Engineering, 97: 1798-1807.
[22] Yuan, Y., & Xu, H. (2013). An integrated search heuristic for large-scale flexible job shop scheduling problems. Computers & Operations Research, 40(12): 2864-2877.
[23] Pasandideh, S. H. R., Niaki, S. T. A., & Hajipour, V. (2013). A multi-objective facility location model with batch arrivals: two parameter-tuned meta-heuristic algorithms. Journal of Intelligent Manufacturing, 1-18.
[24] Bagheri, A., & Zandieh, M. (2011). Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—variable neighborhood search approach. Journal of Manufacturing Systems, 30(1): 8-15.
[25] Huang, R. H., & Yu, T. H. (2017). An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting. Applied Soft Computing, 57, 642-656.
[26] Zheng, F., & Wang, Zh. (2019). Bi-objective Flexible Job Shop Scheduling with Operation Overlapping Costs. IFAC PapersOnLine, 52(13): 893–898.
[27] Farahani, R. Z., SteadieSeifi, M., & Asgari, N. (2010). Multiple criteria facility location problems: A survey. Applied Mathematical Modelling, 34(7): 1689-1709.
[28] Mandow, L., & de la Cruz, J. P. (2001). A heuristic search algorithm with lexicographic goals. Engineering Applications of Artificial Intelligence, 14(6): 751-762.
[29] Dhouib, E., Teghem, J., & Loukil, T. (2013). Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints. International Transactions in Operational Research, 20(2): 213-232.
[30] Sawik, T. (2007). A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing. European Journal of Operational Research, 180(3): 1060-1075.
[31] Palacios, J. J., González-Rodríguez, I., Vela, C. R., & Puente, J. (2015). Swarm lexicographic goal programming for fuzzy open shop scheduling. Journal of Intelligent Manufacturing, 26(6): 1201-1215.
[32] Li, X., Peng, Z., Du, B., Guo, J., Xu, W., Zhuang, K. (2017). Hybrid artificial bee colony algorithm with a rescheduling strategy for solving flexible job shop scheduling problems. Computers & Industrial Engineering, 113: 10-26.
[33] Gao, K.Z., Suganthan, P.N., Chua, T.J. Chong, C.S., Cai, T.X., Pan, Q.K. (2015). A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion. Expert Systems with Applications, 42 (21): 7652-7663.
[34] Li, J.Q., Pan, Q.K., Tasgetiren M.F. (2014). A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Applied Mathematical Modelling, 38(3): 1111-1132.
[35] Thammano, A., Phu-ang, A. (2013). A Hybrid Artificial Bee Colony Algorithm with Local Search for Flexible Job-Shop Scheduling Problem. Procedia Computer Science, 20: 96–101.
[36] Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization [J]. Technical Report TR06. Turkey: Computer Engineering Department, Erciyes University.
[37] Gao, J., Gen, M., Sun, L. (2006). Scheduling jobs and maintenance in flexible job shop with a hybrid genetic algorithm, Journal of Intelligent Manufacturing, 17(4): 493-507.
[38] Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 35(10): 3202-3212.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 8، شماره 17
اسفند 1399
صفحه 295-309

فایل ها

هم رسانی

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

آمار