زما‌ن‌بندی ماشین‌های موازی یکسان با درنظر گرفتن عملیات مشترک به‌منظور کمینه‌ نمودن مجموع انرژی‌های مصرفی و مجموع زمان‌های دیرکرد

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

نویسندگان

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

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

3 استاد گروه مهندسی صنایع، دانشکده مهندسی، دانشگاه کردستان، سنندج، ایران

چکیده

مدیریت مصرف انرژی هم‌زمان با زما‌ن‌بندی عملیات تولید ازاهمیت ویژه‌ای برخوردار است چراکه با زما‌ن‌بندی بهینه می‌توان به‌کاهش مصرف انرژی نیز کمک نمود. دراین پژوهش، مسأله‌ زما‌ن‌بندی در محیط ماشین‌های موازی یکسان با درنظر گرفتن عملیات مشترک به‌منظور کمینه نمودن هم‌زمان مجموع انرژی‌های مصرفی و مجموع زمان‌های دیرکرد مورد مطالعه قرار می‌گیرد. بدین‌منظور ابتدا برای مسأله مورد بررسی، یک مدل برنامه‌ریزی خطی عددصحیح آمیخته دوهدفه ارائه می‌گردد و برای حل مسائل باابعاد کوچک از روش محدودیت اپسیلون تکامل‌یافته جهت دستیابی به مجموعه نقاط پارتو بهینه استفاده می‌شود. درادامه باتوجه به پیچیدگی محاسباتی مسأله، الگوریتم ژنتیک مرتب‌سازی نامغلوب (NSGA-II) و الگوریتم ژنتیک رتبه‌بندی نامغلوب (NRGA) به‌منظور حل مسائل باابعاد متوسط و بزرگ توسعه داده می‌شوند. کارایی و عملکرد الگوریتم‌های حل ارائه شده باانجام آزمایش‌های محاسباتی برروی مسائل نمونه، مورد ارزیابی قرار می‌گیرد. براساس نتایج به‌دست آمده، الگوریتم NSGA-II منجربه ارائه جبهه‌های پارتوی تقریبی با همگرایی بهتر می‌شود به‌گونه‌ای که عملکرد این الگوریتم در مقایسه با الگوریتم NRGA به‌لحاظ درصد انحراف نسبی (RPD) در شاخص‌های Q و MID به‌ترتیب 30% و 22% بهتر است. از سوی دیگر، الگوریتم NRGA درزمانی کمتر، جواب‌های نامغلوب بیشتر و با تنوع بهتر را ارائه می‌دهد به‌گونه‌ای که عملکرد این الگوریتم در مقایسه با الگوریتم NSGA-II به‌لحاظ درصد انحراف نسبی (RPD) در شاخص‌های  Dو NPS به‌ترتیب 12% و 8% بهتر است.

کلیدواژه‌ها


  • Fang, K., Uhan, N., Zhao, F., & Sutherland, J. W. (2011). A new approach to scheduling in manufacturing for power consumption and carbon footprint reduction. Journal of Manufacturing Systems, 30(4), 234-240.
  • Lu, C., Gao, L., Li, X., Pan, Q., & Wang, Q. (2017). Energy-efficient permutation flow shop scheduling problem using a hybrid multi-objective backtracking search algorithm. Journal of Cleaner Production, 144, 228-238.
  • Jovane, F., Yoshikawa, H., Alting, L., Boër, C. R., Westkamper, E., Williams, D., Paci, A. M. (2008). The incoming global technological and industrial revolution towards competitive sustainable manufacturing. CIRP Annals - Manufacturing Technology, 57(2), 641-659.
  • Mori, M., Fujishima, M., Inamasu, Y., & Oda, Y. (2011). A study on energy efficiency improvement for machine tools. CIRP Annals - Manufacturing Technology, 60(1), 145-148.
  • Pinedo, M. L. (2012). Scheduling: Theory, Algorithms, and Systems. Springer - Verlag New York.
  • افسر، امیر. بهنامیان، جواد. (1398). زما‌ن‌بندی چندعاملی ماشین‌های موازی ناهمگن با درنظر گرفتن هزینه انرژی و کارهای به‌هنگام،‌ سال هفتم، شماره 15، صفحه 287–
  • Zhang, M., Yan, J., Yan, S., & Zhang, Y., (2019). Optimization for energy-efficient flexible flow shop scheduling under time of use electricity tariffs, Procedia CIRP, Volume 80, 251-256.
  • Masmoudi, O., Delorme, X. & Gianessi, P., (2019). Job-shop scheduling problem with energy consideration, International Journal of Production Economics, 216, 12-22.
  • Marichelvam, M.K., Geetha, M., (2021). A memetic algorithm to solve uncertain energy-efficient flow shop scheduling problems, The International Journal of Advanced Manufacturing Technology, 115, 515-530.
  • Guo, J., Lei, D. & Li, M., (2021). Two-phase imperialist competitive algorithm for energy-efficient flexible job shop scheduling, Journal of Intelligent & Fuzzy Systems, 40, 12125-12137.
  • Li Z., Yang H., Zhang S., Liu G. (2016) Unrelated parallel machine scheduling problem with energy and tardiness cost. The International Journal of Advanced Manufacturing Technology, 84(1), 213-226.
  • Che A., Zhang S., Wu X. (2017) Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs. Journal of Cleaner Production, 156: 688-697.
  • Wang Y., Wang M., Lin S. (2017). Selection of cutting conditions for power constrained parallel machine scheduling. Robotics and ComputerIntegrated Manufacturing, 43, 105-110.
  • Zeng Y., Che A., Wu X. (2018). Bi-objective scheduling on uniform parallel machines considering electricity cost. Engineering Optimization, 50(1), 19-36.
  • Wu, X. & Che, A., (2018). A memetic differential evolution algorithm for energy-efficient parallel machine scheduling, Omega Volume 82 , 155-165.
  • Safarzadeh, H., Akhavan Niaki, S.T., (2019). Bi-Objective Green Scheduling in Uniform Parallel Machine Environments, Journal of Cleaner Production, 217, 559-572.
  • Wang, S., Wang, X., Yu, J., Ma, S., & Liu, M. (2018). Bi-objective identical parallel machine scheduling to minimize total energy consumption and makespan, Journal of Cleaner Production, 193, 424-440.
  • Anghinolfi, D., Paolucci, M. & Ronco, R., (2020). A bi-objective heuristic approach for green identical parallel machine scheduling, European Journal of Operational Research, S0377-2217(20)30631-7.
  • Zhang, H., Wu, Y., Pan, R. & Xu, G., (2020). Two-stage parallel speed-scaling machine scheduling under time-of-use tariffs, Journal of Intelligent Manufacturing. s10845-020-01561-6
  • Karimi, E., Keshavarz, T. & Shakhsi-Niaei, M., (2021). Unrelated Parallel Machines Scheduling with Sequence Dependent Setup Times to Minimize Makespan and Tariff Charged Energy Consumption, Advances in Industrial Engineering, Winter, 55(1): 91-113.
  • Zhou, B. & Gu, J., (2021). Energy-awareness scheduling of unrelated parallel machine scheduling problems with multiple resource constraints, International Journal of Operational Research, Vol. 41, No. 2, pp 196-217.
  • Modos, I., Sucha, P. & Hanzalek, Z., (2021). On parallel dedicated machines scheduling under energy consumption limit, Computers and Industrial Engineering, Volume 159, Issue C.
  • Rego, M., Pinto, J., Cota, L. & Souza, M., (2022). A mathematical formulation and an NSGA-II algorithm for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling, Advances in Industrial Engineering, PeerJ Computer Science. 844.
  • Asadpour, M., Hodaei, Z., Azami, N. & Kehtari, E., (2022). A green model for identical parallel machines scheduling problem considering tardy jobs and job splitting property, Sustainable Operations and Computers. Volume 3, Pages 149-155.
  • Arbib, C., Felici, G., & Servilio, M., (2019). Common operation scheduling with general processing times: A branch-and-cut algorithm to minimize the weighted number of tardy jobs, Omega, 84, 18-30.
  • Wang J , Qiao C , Yu H . (2011). On progressive network recovery after a major disrup- In: Proc. of IEEE INFOCOM ;  p. 1925–33 . Shanghai, P.R. China , 10-15.
  • Cheng TCE , Diamond J , Lin BMT .(1993) Optimal scheduling in film production to min- imize talent hold J Optim Theory, 79,197–206.
  • Cherri, A., Arenales, M., Yanasse, H., Poldi, K., & Vianna, A., (2014). The one-dimensional cutting stock problem with usable leftovers – A survey. European Journal of Operational Research, 236, 395-402.
  • Hinxman, A., )1980(. The trim-loss and assortment problems: A survey. European Journal of Operational Research 5, 8–18.
  • Dyckhoff, H., )1990(. A typology of cutting and packing problems. European Journal of Operational Research 44, 145–159.
  • Wascher, G., Haußner, H., & Schumann, H., (2007). An improved typology of cutting and packing problems European Journal of Operational Research, 183, 1109-1130.
  • Arbib, C., Marinelli, F., (2014). On cutting stock with due dates, Omega, 46,11-20.
  • Kwon, S., Joung, S., & Lee, K., (2019). Comparative analysis of pattern-based models for the two-dimensional two-stage guillotine cutting stock problem, Computers and Operations Research, 109, 159-169.
  • Cui, Y., Zhong, C., & Yao, Y. (2015). Pattern-set generation algorithm for the one-dimensional cutting stock problem with setup cost. European Journal of Operational Research, 243(2), 540–546.
  • Wuttke, D., Heese, H.S., (2017). Two-dimensional cutting stock problem with sequence dependent setup times, European Journal of Operational Research, 1-13.
  • Ma, N., Liu, Y., & Zhou, Z., (2019). Two heuristics for the capacitated multi-period cutting stock problem with pattern setup cost, Computers and Operations Research, 109, 218-229.
  • Arbib C, Felici G, Servilio M., (2016). Sorting common operations to minimize the number of tardy jobs. Networks, 64, 306–20.
  • Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of discrete mathematics: Elsevier; p. 287-326.
  • Garey, M. R. & Johnson D. S. (1978). “Strong” NP-completeness results: motivation, examples, and implications. Journal of the ACM, 25(3):499-508.
  • LI, Z., Yuan, H., Zhang, S. & Liu, G. (2015). Unrelated parallel machine scheduling problem with energy and tardiness cost, Int J Adv Manuf Technol, 170-015-7657-2.
  • Azizoglu, M. & Kirca, O. (1977). Tardiness minimization on parallel machines, Int. J. Production Economics 55, 163-168.
  • Lenstra, J.K., Rinnooy Kan, A.H.G. & Brucker, P. (1977). Complexity of machine scheduling problems, Annals of Discrete Mathematics 1, 343–362.
  • Mavrotas, G. (2009). Effective implementation of the ε-constraint method in Multi-Objective Mathematical Programming problems, Applied Mathematics and Computation, Volume 213, Issue 2, Pages 455-465.
  • Deb K., Agarwal S., Pratap A. & Meyarivan T. (2000). A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: NSGA-II. Parallel Problem Solving from Nature, 6: 849-858.
  • خیرخواه، امیرسامان. نوبری، آرش. حاجی‌پور، وحید. (1395). ارائه الگوریتم رقابت استعماری چندهدفه جهت بهینه‌سازی مسأله برنامه‌ریزی تولید ادغامی پایا، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید،‌ سال چهارم، شماره 7، صفحه 1-15.
  • Bandyopadhyay, S., Bhattacharya, R., (2013). Solving multi-objective parallel machine scheduling problem by a modified NSGA-II. Applied Mathematical Modelling.
  • Rahmati, S.H.., Hajipour, V. & Akhavan Niak, S.T. (2013). A soft-computing Pareto-based meta-heuristic algorithm for a multi-objective multi-server facility location problem, Applied Soft Computing 13, 1728–1740.
  • Ehtesham Rasi, R. (2021). Optimization of the multi-objective flexible job shop scheduling model by applying NSGAII and NRGA algorithms, Journal of Industrial Engineering and Management Studies, 8, No. 1, 2021, pp. 45-71.
  • Al Jadaan, O., Rajamani, L. & Rao, C.R. (2008). Non-Dominated Ranked Genetic Algorithm for Solving Muti-Objective Optimization Problems: NRGA, Journal of Theoretical and Applied Information Technology.
  • نجفی، امیرعباس. ارجمند، مسعود. (1395). ارائه سه الگوریتم فراابتکاری توسعه‌یافته به‌منظور حل مسأله هزینه دسترس‌پذیری منابع بااهداف کمینه‌سازی زمان اتمام پروژه و مجموع هزینه‌های منابع به‌صورت هم‌زمان، ویژه‌نامه ‌یازدهمین ‌کنفرانس بین‌المللی مهندسی‌ صنایع،‌ دوره 50، شماره 3، صفحه 471-482.
  • حاجی‌سلطانی، فاطمه. سیف‌برقی، مهدی. (1399). ارائه مدلی چندهدفه برای مکانیابی-تخصیص سیستم‌های مراقبت سلامت پیشگیرانه با تقاضای احتمالی، نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید،‌ سال هشتم، شماره 16، صفحه 15-37.
  • Taguchi, G., (1986). Introduction to Quality Engineering 1th Ed University of California, The Organization.
  • Afzalirad, M. & Rezaeian, J. (2017). A realistic variant of bi-objective unrelated scheduling parallel machine problem: NSGA-II and MOACO approaches. Applied Soft Computing 50, 109–123.
  • Cota, L., Coelho, V., Guimaraes, F. & Souza, M., (2018). Bi-criteria formulation for green scheduling with unrelated parallel machines with sequence-dependent setup times, Intl. Trans. in Op. Res. 00, 1–22.

Balakrishnan, N., Kanet, J. & Sridharan, S., (1999). Early/tardy scheduling with sequence dependent setups on uniform parallel machines, Computers & Operations Research 26, 127-141.