نشریه پژوهش های مهندسی صنایع در سیستم های تولید

نشریه پژوهش های مهندسی صنایع در سیستم های تولید

ارائه مدل زمان‌بندی چندعاملی در محیط جریان کارگاهی با فرض زوال‌پذیری کارها، زمان‌های آماده‌سازی وابسته به توالی و زمان آزادسازی کارها با استفاده از الگوریتم ازدحام ذرات چندهدفه

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

نویسندگان
سمیه قندی بیدگلی 1
مرضیه امینی 2
1 استادیار گروه مهندسی صنایع، دانشکدۀ مهندسی، دانشگاه کاشان، کاشان، ایران
2 دانشجوی کارشناسی‌ارشد، دانشکدۀ مهندسی صنایع، دانشگاه علم و صنعت، تهران، ایران
10.22084/ier.2021.23501.2009
چکیده
زمان‌بندی چندعاملی در شرایط زوال‌پذیری کارها در سال‌های اخیر مورد توجه روزافزون جوامع دانشگاهی و صنعتی قرار گرفته‌است. مسأله زمان‌بندی چندعاملی، زیرمجموعه‌ای از مسائل زمان‌بندی چندهدفه است که در آن هر عامل، دارای مجموعه‌ای از کارها است و هدف آن، بهینه کردن تابع هدف مربوط به خود است. در این پژوهش یک مسأله زمان‌بندی ‌سه‌عاملی در محیط جریان کارگاهی در شرایط زوال‌پذیری کارها مورد بررسی قرار گرفته ‌است. در مسأله درنظرگرفته شده زمان پردازش واقعی کارها تابع خطی از زمان پردازش نرمال و زمان شروع پردازش کار مربوطه می‌باشد. جهت واقعی‌تر کردن مسأله، دو فرض کاربردی» زمان‌های آماده‌سازی وابسته به توالی «و» زمان آزادسازی کاره «نیز درنظر گرفته شده‌اند. هم‌چنین یک مدل برنامه‌ریزی عدد صحیح مختلط برای مسأله توسعه داده شده که برای حل آن از روش حل دقیق محدودیت جزئی تعمیم‌یافته استفاده شده‌است. با توجه به پیچیدگی مدل و عدم توانایی روش محدودیت جزئی تعمیم‌یافته در حل مسائل با ابعاد بزرگ، الگوریتم فراابتکاری ازدحام ذرات چندهدفه پیشنهاد شده‌است. به‌منظور ارزیابی عملکرد الگوریتم پیشنهادی، به حل مسائل نمونه عددی در اندازه‌های مختلف با استفاده از این الگوریتم و الگوریتم ژنتیک مبتنی بر مرتب‌سازی نامغلوب و روش حل دقیق محدودیت اپسیلون تعمیم‌یافته پرداخته شده‌ است. سپس جهت انتخاب الگوریتم برتر از روش تصمیم‌گیری چندمعیاره ویکور استفاده شد. نتایج محاسباتی، مؤید همگرایی قابل قبول و پراکندگی خیلی خوب راه‌حل‌های الگوریتم MOPSO و هم‌چنین عملکرد بهتر این الگوریتم نسبت به روش محدودیت اپسیلون تقویت‌شده و الگوریتم NSGA-II می‌باشد.
کلیدواژه‌ها
زمان‌بندی جریان کارگاهی
زوال‌پذیری کارها
زمان‌بندی چندعاملی
الگوریتم فراابتکاری ازدحام ذرات چندهدفه
زمان آماده‌سازی وابسته به توالی
زمان آزادسازی کارها
  • Pinedo, C. Zacharias, and N. Zhu, “Scheduling in the service industries: An overview,” J. Syst. Sci. Syst. Eng., vol. 24, no. 1, pp. 1–48, 2015.
  • Fu, H. Wang, G. Tian, Z. Li, and H. Hu, “Two-agent stochastic flow shop deteriorating scheduling via a hybrid multi-objective evolutionary algorithm,” J. Intell. Manuf., vol. 30, no. 5, pp. 2257–2272, 2019.
  • Agnetis, J.-C. Billaut, S. Gawiejnowicz, D. Pacciarelli, and A. Soukhal, “Multiagent scheduling,” Berlin Heidelb. Springer Berlin Heidelberg. doi, vol. 10, no. 1007, pp. 973–978, 2014.
  • Cheng, P. R. Tadikamalla, J. Shang, and B. Zhang, “Two-machine flow shop scheduling with deteriorating jobs: minimizing the weighted sum of makespan and total completion time,” J. Oper. Res. Soc., vol. 66, no. 5, pp. 709–719, 2015.
  • Allahverdi, “The third comprehensive survey on scheduling problems with setup times/costs,” Eur. J. Oper. Res., vol. 246, no. 2, pp. 345–378, 2015.
  • N. D. Gupta and S. K. Gupta, “Single facility scheduling with nonlinear processing times,” Comput. Ind. Eng., vol. 14, no. 4, pp. 387–393, 1988.
  • Wang, Y. Fu, M. Huang, and J. Wang, “Multiobjective optimisation design for enterprise system operation in the case of scheduling problem with deteriorating jobs,” Enterp. Inf. Syst., vol. 10, no. 3, pp. 268–285, 2016.
  • S. Kunnathur and S. K. Gupta, “Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem,” Eur. J. Oper. Res., vol. 47, no. 1, pp. 56–64, 1990.
  • Cheng, W.-C. Lee, and C.-C. Wu, “Single-machine scheduling with deteriorating functions for job processing times,” Appl. Math. Model., vol. 34, no. 12, pp. 4171–4178, 2010.
  • Cheng, S. Sun, and L. He, “Flow shop scheduling problems with deteriorating jobs on no-idle dominant machines,” Eur. J. Oper. Res., vol. 183, no. 1, pp. 115–124, 2007.
  • -C. Lee, W.-C. Yeh, and Y.-H. Chung, “Total tardiness minimization in permutation flowshop with deterioration consideration,” Appl. Math. Model., vol. 38, no. 13, pp. 3081–3092, 2014.
  • -B. Wang and M.-Z. Wang, “Solution algorithms for the total weighted completion time minimization flow shop scheduling with decreasing linear deterioration,” Int. J. Adv. Manuf. Technol., vol. 67, no. 1–4, pp. 243–253, 2013.
  • Cheng, P. R. Tadikamalla, J. Shang, and S. Zhang, “Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs,” Eur. J. Oper. Res., vol. 234, no. 3, pp. 650–657, 2014.
  • Azadeh, A. H. Goodarzi, M. H. Kolaee, and S. Jebreili, “An efficient simulation–neural network–genetic algorithm for flexible flow shops with sequence-dependent setup times, job deterioration and learning effects,” Neural Comput. Appl., vol. 31, no. 9, pp. 5327–5341, 2019.
  • He, Y. Qiao, N. Wu, and T. Qu, “Total completion time minimization for scheduling of two-machine flow shop with deterioration jobs and setup time,” Adv. Mech. Eng., vol. 9, no. 4, p. 1687814017698887, 2017.
  • Lu, X. Liu, J. Pei, and P. M. Pardalos, “Permutation flowshop manufacturing cell scheduling problems with deteriorating jobs and sequence dependent setup times under dominant machines,” Optim. Lett., vol. 15, no. 2, pp. 537–551, 2021.
  • Xuan, H. Zhang, and B. Li, “An improved discrete artificial bee colony algorithm for flexible flowshop scheduling with step deteriorating jobs and sequence-dependent setup times,” Math. Probl. Eng., vol. 2019, 2019.
  • Chand, R. Traub, and R. Uzsoy, “An iterative heuristic for the single machine dynamic total completion time scheduling problem,” Comput. Oper. Res., vol. 23, no. 7, pp. 641–651, 1996.
  • Sevaux and K. Sörensen, A genetic algorithm for robust schedules in a just-in-time environment. UA, Faculty of Applied Economics UFSIA-RUCA, 2003.
  • Chang, C.-W. Chang, and C.-H. Wu, “Fuzzy DEMATEL method for developing supplier selection criteria,” Expert Syst. Appl., vol. 38, no. 3, pp. 1850–1858, 2011.
  • D. Tksarı, “A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs,” Comput. Oper. Res., vol. 38, no. 9, pp. 1361–1365, 2011.
  • -C. Wu, P.-H. Hsu, and K. Lai, “Simulated-annealing heuristics for the single-machine scheduling problem with learning and unequal job release times,” J. Manuf. Syst., vol. 30, no. 1, pp. 54–62, 2011.
  • Xu, H. Chen, and X. Li, “Makespan minimization on single batch-processing machine via ant colony optimization,” Comput. Oper. Res., vol. 39, no. 3, pp. 582–593, 2012.
  • A. Rakrouki, T. Ladhari, and V. T’kindt, “Coupling Genetic Local Search and Recovering Beam Search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates,” Comput. Oper. Res., vol. 39, no. 6, pp. 1257–1264, 2012.
  • -C. Lee, Y.-H. Chung, and M.-C. Hu, “Genetic algorithms for a two-agent single-machine problem with release time,” Appl. Soft Comput., vol. 12, no. 11, pp. 3580–3589, 2012.
  • Mahnam, G. Moslehi, and S. M. T. F. Ghomi, “Single machine scheduling with unequal release times and idle insert for minimizing the sum of maximum earliness and tardiness,” Math. Comput. Model., vol. 57, no. 9–10, pp. 2549–2563, 2013.
  • C. Vélez-Gallego, J. Maya, and J. R. Montoya-Torres, “A beam search heuristic for scheduling a single machine with release dates and sequence dependent setup times to minimize the makespan,” Comput. Oper. Res., vol. 73, pp. 132–140, 2016.
  • Abdelhadi, L. H. Mouss, and O. Kadri, “Hybrid multi-agent and immune algorithm approach to hybrid flow shops scheduling with sdst.,” Acad. J. Manuf. Eng., vol. 18, no. 3, 2020.
  • Belabid, S. Aqil, and K. Allali, “Solving permutation flow shop scheduling problem with sequence-independent setup time,” J. Appl. Math., 2020.
  • Ladhari and M. A. Rakrouki, “Heuristics and lower bounds for minimizing the total completion time in a two-machine flowshop,” Int. J. Prod. Econ., vol. 122, no. 2, pp. 678–691, 2009.
  • Amirian and R. Sahraeian, “Augmented ε-constraint method in multi-objective flowshop problem with past sequence set-up times and a modified learning effect,” Int. J. Prod. Res., vol. 53, no. 19, pp. 5962–5976, 2015.
  • -C. Lee, S.-K. Chen, C.-W. Chen, and C.-C. Wu, “A two-machine flowshop problem with two agents,” Comput. Oper. Res., vol. 38, no. 1, pp. 98–104, 2011.
  • Luo, L. Chen, and G. Zhang, “Approximation schemes for two-machine flow shop scheduling with two agents,” J. Comb. Optim., vol. 24, no. 3, pp. 229–239, 2012.
  • Mor and G. Mosheiov, “Polynomial time solutions for scheduling problems on a proportionate flowshop with two competing agents,” J. Oper. Res. Soc., vol. 65, no. 1, pp. 151–157, 2014.
  • Q. Fan and T. C. E. Cheng, “Two-agent scheduling in a flowshop,” Eur. J. Oper. Res., vol. 252, no. 2, pp. 376–384, 2016.
  • Lei, “Variable neighborhood search for two-agent flow shop scheduling problem,” Comput. Ind. Eng., vol. 80, pp. 125–131, 2015.
  • -R. Shiau, W.-C. Lee, Y.-S. Kung, and J.-Y. Wang, “A lower bound for minimizing the total completion time of a three-agent scheduling problem,” Inf. Sci. (Ny)., vol. 340, pp. 305–320, 2016.
  • Nasrollahi, G. Moslehi, and M. Reisi-Nafchi, “Minimizing the weighted sum of maximum earliness and maximum tardiness in a single-agent and two-agent form of a two-machine flow shop scheduling problem,” Oper. Res., pp. 1–40, 2020.
  • Bai et al., “Competitive bi-agent flowshop scheduling to minimise the weighted combination of makespans,” Int. J. Prod. Res., pp. 1–22, 2021.
  • -H. Wu, Y. Yin, W.-H. Wu, C.-C. Wu, and P.-H. Hsu, “A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents,” J. Ind. Manag. Optim., vol. 10, no. 2, p. 591, 2014.
  • Yin, T. C. E. Cheng, L. Wan, C.-C. Wu, and J. Liu, “Two-agent single-machine scheduling with deteriorating jobs,” Comput. Ind. Eng., vol. 81, pp. 177–185, 2015.
  • حرائیان،ر و حسین زاده، م، حل مسئله زمان‌بندی چندعاملی در محیط جریان کارگاهی با درنظر گرفتن اثر زمانی و ردکردن کارها بااستفاده از یک الگوریتم فراابتکاری، نشریه پژوهش‌های مهندسی مهندسی صنایع در سیستم های تولید، شماره 10، ص17-29، 1396.
  • V Adediran, A. Al-Bazi, and L. E. dos Santos, “Agent-based modelling and heuristic approach for solving complex OEM flow-shop productions under customer disruptions,” Comput. Ind. Eng., vol. 133, pp. 29–41, 2019.
  • -S. Chen, R. G. Batson, and Y. Dang, Applied integer programming: modeling and solution. John Wiley & Sons, 2011.
  • J. Sadjadi, M. Heidari, and A. A. Esboei, “Augmented ε-constraint method in multiobjective staff scheduling problem: a case study,” Int. J. Adv. Manuf. Technol., vol. 70, no. 5–8, pp. 1505–1514, 2014.
  • Eberhart and J. Kennedy, “Particle swarm optimization,” in Proceedings of the IEEE international conference on neural networks, 1995, vol. 4, pp. 1942–1948.
  • A. C. Coello and M. S. Lechuga, “MOPSO: A proposal for multiple objective particle swarm optimization,” in Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No. 02TH8600), vol. 2, pp. 1051–1056, 2002.
  • Saeedi, R. Khorsand, S. G. Bidgoli, and M. Ramezanpour, “Improved many-objective particle swarm optimization algorithm for scientific workflow scheduling in cloud computing,” Comput. Ind. Eng., vol. 147, p. 106649, 2020.
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 9، شماره 18
شهریور 1400
صفحه 59-79