یک الگوریتم فراابتکاری ترکیبی برای مسئله زمان‌بندی کار کارگاهی منعطف با منابع دوگانه محدود انسان و ماشین

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

نویسندگان

1 * دانشگاه آزاد اسلامی، واحد علوم‌ و‌ تحقیقات، گروه مهندسی صنایع، تهران، ایران

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

3 * استاد، دانشکده مهندسی صنایع، پردیس دانشکده های فنی، دانشگاه تهران، تهران، ایران

چکیده

در این مقاله مسئله زمان‌بندی کار کارگاهی منعطف با در‌نظر‌گرفتن منابع دوگانه محدود انسان و ماشین با هدف کمینه‌سازی معیار حداکثر زمان تکمیل کارها مورد بررسی قرار گرفته‌است. مسئله مورد‌مطالعه از گروه مسائل NP-hardاست و از ۳ زیر‌مسئله تشکیل شده‌است. مسئله اول تخصیص هر عملیات به یک ماشین از میان ماشین‌های موجود برای انجام آن عملیات، مسئله دوم تخصیص هر عملیات به یک کارگر از میان کارگرهای قادر به انجام آن عملیات و مسئله دیگر تعیین توالی عملیات‌ها روی ماشین‌ها با توجه به کارگران در‌نظر گرفته‌شده به‌منظور بهینه‌سازی معیار عملکرد می‌باشد. ما در این مقاله مدل ریاضی مسئله مورد‌نظر را تهیه و در ادامه یک الگوریتم فراابتکاری ترکیبی را برای حل آن ارائه کرده‌ایم. الگوریتم ترکیبی توسعه داده‌شده از الگوریتم‌های جستجوی همسایگی متغیر و شبیه‌سازی تبرید برای جستجوی فضای جواب استفاده می‌کند. به‌منظور ارزیابی عملکرد الگوریتم ارائه‌شده، مطالعات محاسباتی با در‌نظر‌گرفتن مسائل نمونه ایجاد‌شده انجام خواهد‌شد. نتایج نشان می‌دهد که الگوریتم ارائه‌شده روشی مؤثر برای حل مسئله زمان‌بندی کار کارگاهی منعطف با منابع دوگانه محدود انسان و ماشین است. 

کلیدواژه‌ها


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

A hybrid meta-heuristic algorithm for dual resource constrained flexible job shop scheduling problem

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

  • Mehdi Yazdani 1
  • Mostafa Zandieh 2
  • Reza Tavakkoli-Moghaddam 3
1 - Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
2 ** Associate professor, Department of Industrial Management, Management and Accounting Faculty, Shahid Beheshti University, G.C., Tehran, Iran
3 *** Professor, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
چکیده [English]

     In this paper, the dual-resource constrained flexible job-shop scheduling problem (DRCFJSP) with objective of minimizing the makespan is investigated. Under studied problem is NP-hard and mainly includes three sub-problems. The first one is to assign each operation to a machine out of a set of capable machines, the second one is to determine a worker among a set of skilled workers for processing each operation on the selected machine and the third one deals with sequencing the assigned operations on the machines considering workers in order to optimize the performance measure. In this paper, we provide a mathematical model for this problem and then propose a hybrid meta-heuristic algorithm for solving the problem. The proposed hybrid algorithm uses variable neighborhood search and simulated annealing algorithms to search in the solution space. Computational study with randomly generated test problems is performed to evaluate the performance of the proposed algorithm. The results show the proposed algorithms are effective approaches for solving the DRCFJSP.
  

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

  • Scheduling
  • Dual-resource constrained
  • Flexible job shop
  • Mathematical Modeling
  • Simulated Annealing
  • Variable neighborhood search
Bokhorst, J.A.C. and Gaalman, G.J.C., (2009). Cross-training workers in dual resource constrained systems with heterogeneous processing times. International Journal of Production Research, Volume 47, Issue 22, Pages 6333-6356.

 ElMaraghy, H., Patel, V., and Ben Abdallah, I., (1999). Genetic algorithm based approach for scheduling of dual-resource constrained manufacturing systems. CIRP Annals Manufacturing Technology; Volume 48, Issue 1, Pages 369-372.

ElMaraghy, H., Patel, V., and Ben Abdallah, I., (2000). Scheduling of manufacturing systems under dual-resource constraints using genetic algorithms. Journal of Manufacturing Systems; Volume 19 Issue 3, Pages 186-198.

Gao, J., Sun, L., and Gen, M., (2008). A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research, Volume 35, Issue 9, Pages 2892–2907.

Garey, M.R., Johnson, D.S., and Sethi, R., (1976). The complexity of flowshop and jobshop scheduling scheduling. Mathematical Operation Research; Volume 1, Issue 2, Pages 117-129.

Hansen, P. and Mladenovic, N., (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, Volume 130, Issue 3, Pages 449–467.

Huiyuan, R., Lili, J., Xiaoying, X., and Muzhi, L., (2009). Heuristic optimization for dual-resource constrained job shop scheduling. International Asia Conference on Informatics in Control, Automation and Robotics, IEEE Explore; Pages 485-488.

Jaber, M.Y. and Neumann, W.P., (2010). Modelling worker fatigue and recovery in dual-resource constrained systems. Modelling worker fatigue and recovery in dual-resource constrained systems; Volume 59, Issue 1, Pages 75-84.

Jingyao, L., Shudong, S., and Yuan, H., Ganggang, N., (2010). Research on Double-Objective Optimal Scheduling Algorithm for Dual Resource Constrained Job Shop. Artificial Intelligence and Computational Intelligence; Lecture Notes in Computer Science, Volume 6319/2010, Pages 222-229.

Jingyao, L., Shudong, S., and Yuan, H., (2011). Adaptive Hybrid Ant Colony Optimization for Solving Dual Resource Constrained Job Shop Scheduling Problem, Journal OF Software; Volume 6, Issue 4, Pages 584-594.

Kacem, I., Hammadi, S., and Borne, P.,) 2002(. Approach by localization and Multi-objective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man, and Cybernetics, Part C, Volume 32, Issue1, Pages 1-13.

Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P., (1983). Optimization by simulated annealing. Science, Volume 220, Pages 671–680.

Lei, D. and Guo, X., (2014). Variable neighbourhood search for dual-resource constrained flexible job shop scheduling”, International Journal of Production Research, 52(9), pp. 2519-2529.

Liu, X.X., Lio, Ch., and Tao, Z., (2011). Research on Bi-Objective Scheduling of Dual-Resource Constrained Flexible Job Shop, Advanced Materials Research; Volume 211-212, Pages 1091-1095.

Lobo, B.J., Hodgson, T.J., King, R.E., and Thoney, K.A., and Wilson, J.R., (2013). An effective lower bound max L in a worker-constrained job shop. Computers and Operations Research, Volume 40, Issue 1, Pages 328-343.

Mati, Y. and Xie, X., (2004). The complexity of two-job shop problems with multi-purpose unrelated machines. European Journal of Operational Research, Volume 152, Pages 159-169.

Metropolis, N., Rosenbluth, A.W., Rosenbloth, M.N., Teller, A. H., & Teller, E. (1953). Equation of state calculation by fast computing machines. Journal of Chemical Physics, 21.

Mladenovic, N. (1995). A variable neighborhood algorithm—a new metaheuristic for combinatorial optimization. Abstracts of papers presented at Optimization Days: Montre´ al, 112–112.

Mladenovic, N. and Hansen, P. (1997). Variable neighborhood search. Computers and Operations

Research, Volume 24, Issue 11, Pages 1097–1100.

Nelson, R.T., (1967). Labor and machine limited production systems, Management Science, Volume 13, Issue 9, Pages 648–671.

Pezzella F., Morganti G., and Ciaschetti G., (2008). A genetic algorithm for the Flexible Job-shop Scheduling Problem. Computers & Operations Research; Volume 35, Issue 10, Pages 3202-3212.

Pinedo, M., (1995). Scheduling: Theory, Algorithms and Systems, Prentice-Hall. New Jersey, Englewood Cliffs.

Ruiz, R. and Allahverdi, A. (2007). Some effective heuristics for no-wait flowshops with setup times to minimize total completion time. Annals of Operations Research, Volume 156, Issue 1, Pages 143-171.

Xianzhou, C. and Zhenhe, Y.,  (2011). An Improved Genetic Algorithm for Dual-Resource Constrained Flexible Job Shop Scheduling, Intelligent Computation Technology and Automation (ICICTA);  Volume 1, Pages 42-45.

Yazdani, M., Amiri, M., and Zandieh, M., (2010). Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Systems with Applications, 37(1), Pages 678–687.

ZhiGang, L. Yan, L., and Shujuan, L., (2007). Multi-resource constrained job shop optimization scheduling based on ant colony algorithm. Journal of System Simulation, Volume 19, Pages 200-216.

Zhijun S. and Jianying, Zh., (2005). Intelligent optimization for job shop scheduling of dual-resources. Journal of Southeast University (Natural Science Edition), Volume 35, Pages 376-381.