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

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

نویسنده

دانشگاه کاشان

چکیده

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

کلیدواژه‌ها


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

Modeling and Solution of Job Shop Scheduling with No-Wait Orders to Minimize Makespan: A Decomposition Approach based on Order Sequencing and Timetabling

نویسنده [English]

  • Hadi Mokhtari
kashan university
چکیده [English]

Job shop scheduling problem with no-wait is a special case of general job shop scheduling problem where there is no waiting time between operations and within jobs. In other words, when the operation of each order starts, there is no stop. In literature of scheduling problems, this problem has been known as NP-hard problem. The proposed approach for solving such problems generally decompose the problem into two sub problems: sequencing and timetabling. In this paper, after analyzing the genetic algorithm based approaches presented in literature, we will present a new approach. After introducing the main problem and solution approaches, we will investigate the solution approaches and evaluate their limitations and advantages. Finally a GA based on the improvements will be presented which exhibits relatively high efficiency.

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

  • scheduling
  • No-Wait
  • Optimization
  • Decomposition Approach
  • Metaheuristics
[1] Hall, N. G., and Sriskandarajah, C. (1996), “A Survey of Machine Scheduling Problems with Blocking and no-wait in Process”, Operations Research, Vol. 44, pp. 510–525.
[2] Mascis, A., and Pacciarelli, D.,(2002), “Job-Shop Scheduling with Blocking and no-Wait Constraints”, European Journal of Operational Research, Vol. 143, pp. 498–517.
[3] Raaymakers, W. H. M., and Hoogeven, J. A.(2000), “Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing”, European Journal of Operational Research, Vol. 126, pp.131–151.
[4] Macchiaroli, R., Mole, S., Riemma, S., and Trifililetti, L., (1996), “Design and Implementation of a Tabu Search Algorithm to Solve the no-Wait Job-Shop Scheduling Problem”. In Proceeding of the CESA’96, Lille.
[5] Schuster, C., and Framinan, J.M., (2003), “Approximative Procedures for no-Wait Job Shop Scheduling”, Operations Research Letters, Vol. 31, pp. 308–18.
[6] Brizuela, C. A., Zhao, Y., and Sannomia, N., (2001),“No-Wait and Blocking Job-Shops: Challenging Problems for GA’s”,In IEEE International Conference on Systems, Man, and Cybernetics, Tucson, Arizona, USA.
[7] Zhu, J., Li, X., and Wang, Q.,(2009), “Complete Local Search with Limited Memory Algorithm for no-Wait Job Shops to Minimize Makespan”, European Journal of Operational Research, Vol. 198, pp. 378-386.
[8] Wang, L., and Zheng, D.,(2001), “An Effective Hybrid Optimization Strategy for Job-Shop Scheduling Problems”, Computers & Operations Research, Vol. 28, pp. 585–96.
[9] Pan, J. C.-H., and Huang H.-C.,(2009), “A Hybrid Genetic Algorithm for no-Wait Job Shop Scheduling Problems”, Expert Systems with Applications, Vol. 36, pp. 5800-5806.
[10] Mokhtari, H., Abadi, INK and Zegordi, SH., (2011), “Production capacity planning and scheduling in a no-wait environment with controllable processing times: An integrated modeling approach”, Expert Systems with Applications, Vol.38, pp. 12630-12642.
[ 11 [ مخ اری، هادی، نخبی امال ت ادی، می ی امین ناأری محمدر ا، ) 1392 (، "مدلسازی ا لحلیلی م له رنامه ریزی ظرفیت
زمانبندی لیلید یکپارچه: اس خراج اراظ پااین طراای ی الگیری م شامه اراظ اارا"، مجله ملمی-پژ ه ی مهندسی
أنایع مدیریت لیلید، د ره 24 ، شماره 2 ، أیحه 139 - 118
[12] Goyal, S. K., (1975), “Job-Shop Sequencing Problem with no Wait in Process”, International Journal of Production Research, Vol. 13, pp. 197–206, 197.
[13] Framinan, J.M., and Schuster, C.,(2006), “An Enhanced Timetabling Procedure for the no-Wait Job Shop Problem: A Complete Local Search Approach”, Computers & Operations Research, Vol. 331, pp. 1200–1213.
[14] Schuster, C., (2006), “No-Wait Job Shop Scheduling: Tabu Search and Complexity of Subproblems”, Mathematical Methods of Operations Research, Vol. 63, pp. 473–491.