نوع مقاله : مقاله پژوهشی
نویسندگان
1 گروه مهندسی صنایع، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران.
2 گروه مهندسی صنایع ، واحد قزوین، دانشگاه آزاد اسلامی، قزوین، ایران.
3 گروه مدیریت صنعتی، دانشگاه علامه طباطبایی، تهران، ایران.
چکیده
هدف: یکی از مهمترین مسایل حوزه زمانبندی تولید که اخیرا بسیار موردتوجه محققان قرار گرفته است، مساله زمانبندی کار کارگاهی منعطف با منابع دوگانه محدود انسان و ماشین (DRCFJSP)است. برای مقابله با اختلال‌های غیرمنتظره مانند خرابی ماشین، باید برنامه زمانبندی کارها استوار باشد تا در صورت وقوع اختلال، برنامه زمانی دارای کارایی مناسبی باشد و از راه‌حل بهینه انحراف کمتری داشته باشد. لذا در این تحقیق، مساله زمانبندی کار کارگاهی منعطف با منابع دوگانه محدود انسان و ماشین با در نظر گرفتن سناریوهای محتمل خرابی ماشین‌ها یا اختلال در کارگاه موردمطالعه قرار می‌گیرد.
روش‌شناسی پژوهش: در حل مساله موردمطالعه، نحوه واگذاری مارها به ماشین‌ها و توالی عملیات بر روی هر ماشین باید به‌گونه‌ای صورت پذیرد که تحت هر سناریوی محتمل، حداکثر زمان تکمیل کارها کمینه شود تا ترکیب وزنی مربوط به عملکرد سیستم در حالت متوسط، عملکرد سیستم در حالت بدبینانه، جریمه نقض قیود پنجره‌های زمانی موعدهای تحویل کارها و واریانس مقدار تابع هدف با توجه به سناریوهای مختلف بهینه باشد. به این منظور یک مدل برنامهریزی تصادفی سناریو محور استوار (RSSP) در قالب یک مدل برنامهریزی خطی عدد صحیح مختلط برای این مساله ارایه گردیده است و به‌منظور اعتبار‌سنجی در ابعاد کوچک و متوسط به‌وسیله نرم‌افزار گمز حل شده است. با توجه به Np-hard بودن این مساله، یک روش فراابتکاری مبتنی بر الگوریتم ژنتیک (GA) برای حل مسایل در ابعاد بزرگ ارایه شده است. همچنین، نتایج یک مطالعه موردی در شرکت البرز یدک مرتبط با مساله تحقیق در مقاله گزارش شده است.
یافته‌ها: نتایج اجرای مدل RSSP پیشنهادی نشان می‌دهد که نرم افزار گمز قادر است که مسایل مذکور تا ابعاد متوسط را در یک زمان قابل قبول حل کند و به یک پاسخ کنترل شده و استوار دست یابد. همچنین نتایج عددی نشان‌دهنده عملکرد مناسب الگوریتم GA پیشنهادی به عنوان یک گزینه برای حل مدل RSSP در مسایل با اندازه بزرگ است.
اصالت/ارزش افزوده علمی: در این تحقیق، مساله DRCFJSP با در نظر گرفتن سناریوهای محتمل خرابی ماشین‌ها مورد مطالعه قرار می گیرد. همچنین در این مقاله یک مدل برنامهریزی تصادفی سناریومحور استوار (RSSP) در قالب قاعده برنامهریزی خطی عدد صحیح مختلط و یک روش فراابتکاری برای مساله مورد نظر ارایه گردیده است.
کلیدواژه‌ها
- الگوریتم ژنتیک
- برنامهریزی تصادفی سناریو محور استوار
- خرابی ماشین
- زمانبندی کار کارگاهی منعطف
- منابع دوگانه محدود انسان و ماشین
موضوعات
عنوان مقاله [English]
Modeling and solving dual resource constrained flexible job-shop scheduling problem considering machine breakdown
نویسندگان [English]
- Parham Soofi 1
- Mehdi Yazdani 2
- Maghsoud Amiri 3
- Mohammad Amin Adibi 2
1 Department of Industrial Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.
2 Department of Industrial Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.
3 Department of Industrial Management, Allameh Tabatabai University, Tehran, Iran.
چکیده [English]
Purpose: One of the most important issues in the field of production scheduling, which has recently received much attention from researchers, is Dual Resource Constrained Flexible Job Shop Scheduling Problem (DRCFJSP). To deal with unexpected disruptions such as machine breakdowns, the job schedule must be robust so that in the event of a malfunction, the job schedule works properly and deviate less from the optimal solution. The purpose of this paper is to study the DRCFJSP problem with possible scenarios of machine failure or workshop disruption.
Methodology: In solving the under-studied problem, the assignment of jobs and the sequence of operations on each machine should be done in such a way that under any possible scenario, the maximum completion time is minimized so that the weight combination of system performance in average mode, system performance in worst mode, the penalty for violating the time window constraints of the due dates and the variance of the objective function value is optimal according to different scenarios. For this purpose, a Robust Scenario-based Stochastic Programming (RSSP) model based on a mixed integer linear programming model has been presented for this problem and has been solved by Gams software for validation in small and medium-sized problems. Also, due to the Np-hard nature of this problem, a meta-heuristic method based on Genetic Algorithm (GA) is proposed for solving the large-sized problems. Also, the results of a case study in Alborz Yadak company related to the problem of the research are reported in the article.
Findings: The results of the proposed RSSP model indicate that GAMS software is able to solve these problems up to medium sizes in an acceptable time and achieve a controlled and robust solution. Numerical results also show the proper performance of the proposed GA as an alternative to solve the RSSP model in the large-sized problems.
Originality/Value: In this paper, DRCFJSP problem is studied with possible scenarios of machine failure or disruption in the workshop. Also, a RSSP model according to the mixed integer linear programming formulation and a meta-heuristic Algorithm have been presented for mentioned problem in this article.
کلیدواژه‌ها [English]
- Flexible job-shop scheduling
- Dual-resource constrained
- Machine breakdown
- Robust scenario-based stochastic programming
- Genetic algorithm
- Ahmadi, E., Zandieh, M., Farrokh, M., & Emami, S. M. (2016). A multi objective optimization approach for flexible job shop scheduling problem under random machine breakdown by evolutionary algorithms. Computers & operations research, 73, 56-66.
- Andrade-Pineda, J. L., Canca, D., Gonzalez-R, P. L., & Calle, M. (2019). Scheduling a dual-resource flexible job shop with makespan and due date-related criteria. Annals of operations research, 291, 5-35. https://doi.org/10.1007/s10479-019-03196-0
- Applegate, D., & Cook, W. (1991). A computational study of the job-shop scheduling problem. ORSA journal on computing, 3(2), 149-156.
- Buddala, R., & Mahapatra, S. S. (2019). Two-stage teaching-learning-based optimization method for flexible job-shop scheduling under machine breakdown. The international journal of advanced manufacturing technology, 100(5), 1419-1432.
- Chen, R., Yang, B., Li, S., & Wang, S. (2020). A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem. Computers & industrial engineering, 149, 106778. https://doi.org/10.1016/j.cie.2020.106778
- Dhiflaoui, M., Nouri, H. E., & Driss, O. B. (2018). Dual-resource constraints in classical and flexible job shop problems: a state-of-the-art review. Procedia computer science, 126, 1507-1515.
- Fattahi, P., Mehrabad, M. S., & Jolai, F. (2007). Mathematical modeling and heuristic approaches to flexible job shop scheduling problems. Journal of intelligent manufacturing, 18(3), 331-342.
- Felan, J. T., & Fry, T. D. (2001). Multi-level heterogeneous worker flexibility in a dual resource constrained (DRC) job-shop. International journal of production research, 39(14), 3041-3059.
- Gong, G., Chiong, R., Deng, Q., & Gong, X. (2020). A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility. International journal of production research, 58(14), 4406-4420.
- Kress, D., Müller, D., & Nossack, J. (2019). A worker constrained flexible job shop scheduling problem with sequence-dependent setup times. OR spectrum, 41(1), 179-217.
- Lang, M., & Li, H. (2011). Research on dual-resource multi-objective flexible job shop scheduling under uncertainty. 2011 2nd international conference on artificial intelligence, management science and electronic commerce (AIMSEC)(pp. 1375-1378). IEEE. https://doi.org/10.1109/AIMSEC.2011.6010821
- Lei, D., & Guo, X. (2014). Variable neighbourhood search for dual-resource constrained flexible job shop scheduling. International journal of production research, 52(9), 2519-2529.
- Meng, L., Zhang, C., Ren, Y., Zhang, B., & Lv, C. (2020). Mixed-integer linear programming and constraint programming formulations for solving distributed flexible job shop scheduling problem. Computers & industrial engineering, 142, 106347. https://doi.org/10.1016/j.cie.2020.106347
- Mulvey, J. M., Vanderbei, R. J., & Zenios, S. A. (1995). Robust optimization of large-scale systems. Operations research, 43(2), 264-281.
- Nouiri, M., Bekrar, A., Jemai, A., Trentesaux, D., Ammari, A. C., & Niar, S. (2017). Two stage particle swarm optimization to solve the flexible job shop predictive scheduling problem considering possible machine breakdowns. Computers & industrial engineering, 112, 595-606.
- Sajadi, S. M., Alizadeh, A., Zandieh, M., & Tavan, F. (2019). Robust and stable flexible job shop scheduling with random machine breakdowns: multi-objectives genetic algorithm approach. International journal of mathematics in operational research, 14(2), 268-289.
- Salehi, F., Mahootchi, M., & Husseini, S. M. M. (2019). Developing a robust stochastic model for designing a blood supply chain network in a crisis: a possible earthquake in Tehran. Annals of operations research, 283(1), 679-703.
- Shen, L., Dauzère-Pérès, S., & Neufeld, J. S. (2018). Solving the flexible job shop scheduling problem with sequence-dependent setup times. European journal of operational research, 265(2), 503-516.
- Sun, D.-h., He, W., Zheng, L.-j., & Liao, X.-y. (2014). Scheduling flexible job shop problem subject to machine breakdown with game theory. International journal of production research, 52(13), 3858-3876.
- Sun, J., Zhang, G., Lu, J., & Zhang, W. (2021). A hybrid many-objective evolutionary algorithm for flexible job-shop scheduling problem with transportation and setup times. Computers & operations research, 132, 105263. https://doi.org/10.1016/j.cor.2021.105263
- Xie, J., Gao, L., Peng, K., Li, X., & Li, H. (2019). Review on flexible job shop scheduling. IET collaborative intelligent manufacturing, 1(3), 67-77.
- Xiong, J., Xing, L. N., & Chen, Y. W. (2013). Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns. International journal of production economics, 141(1), 112-126.
- 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, 22(3), 1242-1257.
- Yu, C.-S., & Li, H.-L. (2000). A robust optimization model for stochastic logistic problems. International journal of production economics, 64(1-3), 385-397.
- Zandieh, M., Khatami, A. R., & Rahmati, S. H. A. (2017). Flexible job shop scheduling under condition-based maintenance: improved version of imperialist competitive algorithm. Applied soft computing, 58, 449-464.
- Zhang, G., Hu, Y., Sun, J., & Zhang, W. (2020). An improved genetic algorithm for the flexible job shop scheduling problem with multiple time constraints. Swarm and evolutionary computation, 54, 100664. https://doi.org/10.1016/j.swevo.2020.100664
- Zhang, G., Sun, J., Liu, X., Wang, G., & Yang, Y. (2019). Solving flexible job shop scheduling problems with transportation time based on improved genetic algorithm. Mathematical biosciences and engineering, 16(3), 1334-1347.
)