ارائه یک مدل ریاضی و یک الگوریتم شاخه‌وکران برای مسأله زمان‌بندی تک‌ماشین با فرض زوال خطی و ورود غیرهم‌زمان کارها

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

نویسندگان

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

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

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

چکیده

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

کلیدواژه‌ها

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

A Mathematical Model and a Branch and Bound Algorithm for the Single Machine Scheduling Problem Under Linear Deterioration and Release Times

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

  • Abbasali Jafari Nodoushan 1
  • Mohammad Hossien Dehghani Sardabadi 2
  • Ali Bozorgi-Amiri 3
1 Assistant Professor, Department of Industrial Engineering, Faculty of Engineering, Meybod University, Meybod, Iran
2 Ph.D Candidate, Department of Industrial Engineering, Iran University of science & Technology, Tehran, Iran
3 Associate Professor, School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
چکیده [English]

In this paper, the single machine scheduling problem with linear deteriorating jobs under release times is considered where the objective is to minimize the number of tardy jobs. The problem is proved NP-hard according to the literature review. At first, a mathematical model is presented to the problem and a Branch and Bound algorithm with considering dominance rules and lower bounds is supposed to solve the problem optimally. Computational results are presented in four parts to evaluate the performance of the proposed algorithm and the effect of related parameters on the algorithm. According to the variance analysis test, it was found that the efficiency of the branch and bound algorithm is high so that it is able to solve the most problems with job size 30 within a reasonable time and the average percentage of entire fathomed nodes in all the problems is at least 85.61 percentage. It was also shown the problems with larger λ and smaller deterioration rates are difficult and the average solution time of the algorithm is high for them. On the other hand, if the due date of the jobs was big or small, the problem will be simple and the solution time is less than the problems with medium due dates.

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

  • Deteriorating Jobs
  • Scheduling
  • Number of Tardy Jobs
  • Release Time
  • Branch and Bound Algorithm

مراجع

]1[ جعفری ندوشن، عباسعلی. (1396). "زمان‌بندی فعالیت‌های روبه زوال خطی در محیط تک‌ماشین بافرض ورود غیرهم‌زمان کارها". چهاردهمین کنفرانس بین‌المللی مهندسی صنایع، دانشگاه علم و صنعت ایران.
]2[ فخرزاد، محمدباقر، علی‌نژاد، اسماعیل. (1392). "برنامه‌ریزی و زمان‌بندی پیشرفته با درنظر گرفتن اثر یادگیری در سیستم‌های ساخت کارگاهی انعطاف‌پذیر". نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 1(1): 24-13.
[3] Delorme, M., Lori, M., Mendez, N.F.M. (2021). "Solution methods for scheduling problems with sequence-dependent deterioration and maintenance events". European Journal of Operational Research, 295(3): 823-837.
]4[ بهنامیان، جواد، دیانت، فاطمه. (1395). "مقایسه سه روش فراابتکاری برای کمینه نمودن زمان چرخه در مسأله زمان‌بندی جریان کارگاهی مختلط دوره‌ای با درنظر گرفتن اثر یادگیری". نشریه پژوهش‌های مهندسی صنایع در سیستم‌های تولید، 4(8): 105-117.
[5] Expósito-Izquierdo, C., Angel-Bello, F., Melián-Batista, B., Alvarez, A., Báez, S. (2019). "A metaheuristic algorithm and simulation to study the effect of learning or tiredness on sequence-dependent setup times in a parallel machine scheduling problem". Expert Systems with Applications, 117: 62-74.
[6] Ouazene, Y., Yalaoui, F. (2018). "Identical parallel machine scheduling with time-dependent processing times". Theoretical Computer Science, 721: 70-77.
[7] Cheng, T.C.E., Ding, Q., Lin, B.M.T. (2004). "A concise survey of scheduling with time-dependent processing times". European Journal of Operational Research, 152(1): 1-13.
[8] Wang, J.B., Wang, J.J. (2015). "Single-machine scheduling problems with precedence constraints and simple linear deterioration". Applied Mathematical Modelling, 39(3): 1172-1182.
[9] Wu, C.C., Lee, W.C. (2006). "Two-machine flowshop scheduling to minimize mean flow time under linear deterioration". International Journal of Production Economics, 103(2): 572-584.
[10] Pinedo, M. (2002). Scheduling: Theory, Algorithms, and Systems. Prentice-Hall, New Jersy.
[11] Cheng, T.C.E., Kravchenko, S.A., Lin, B.M.T. (2020). " Scheduling step-deteriorating jobs to minimize the total completion time". Computers & Industrial Engineering, 144: 106329.  
[12] Browne, S., Yechiali, U. (1990). "Scheduling deteriorating jobs on a single processor". Computers & Operations Research, 38(3): 495-49.
[13] Lee, W.C., Wu, C.C., Chung. Y.H. (2008). "Scheduling deteriorating jobs on a single machine with release times". Computers & Industrial Engineering, 54(3): 441-452.
[14] Jafari, A., Moslehi, G., (2011). "Scheduling linear deteriorating jobs to minimize the number of tardy jobs". Journal of Global Optimization, 54(2): 389-404.
[15] Hsu, Y.S., Lin, B.M.T. (2003). "Minimization of maximum lateness under linear deterioration". Omega, 31(6): 459-469.
[16] Cheng, T.C.E., Hsu, C.J., Huang, Y.C., Lee, W.C. (2011). "Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness". Computers & Operations Research, 38(12): 1760-1765.
[17] Lee, W.C., Lin, J.B., Shiau, Y.R. (2011). "Deteriorating job scheduling to minimize the number of late jobs with setup times". Computers & Industrial Engineering, 61(3): 782-787.
[18] Lee, W.C., Lu, Z.S. (2012). "Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs". Applied Mathematics and Computation, 218(17): 8750-8757.
[19] Wu, C.C., Cheng, S.R., Wu, W.H., Yin, Y., Wu, W.H. (2013). "The single-machine total tardiness problem with unequal release times and a linear deterioration". Applied Mathematics and Computation, 219(20): 10401-10415.
[20] Lee, W.X., Zhao, C.L. (2015). "Deteriorating jobs scheduling on a single machine with release dates, rejection and a fixed non-availability interval". Journal of Applied Mathematics and Computing, 48(1-2): 585-605
[21] Jafari, A.A., Khademi-zare, H., Lotfi, M.M., Tavakkoli-Moghaddam, R. (2016). "Minimizing Makespan with Start Time-Dependent Jobs in a Two-Machine Flow Shop", International Journal of Engineering, IJE TRANSACTIONS B: Applications, 29(6): 778-787.
 [22] Lee, W.C., Wu, C.C., Wen, C.C., Chung. Y.H. (2008). "A two-machine flowshop makespan scheduling problem with deteriorating jobs". Computers & Industrial Engineering, 54(4): 737-749.
[23] Wang, J.B., Wang, M.Z. (2013). "Minimizing makespan in three machine flow shop with deteriorating jobs". Computers & operations research, 40(2): 547-557.
[24] Jafari, A.A., Khademi-zare, H., Lotfi, M.M., Tavakkoli-Moghaddam, R. (2016). "A note on “minimizing makespan in three machine flowshop with deteriorating jobs”". Computers & operations research, 72: 93-96.
[25] Wang, L., Sun, L.Y., Sun, L.H., Wang, J.B. (2010). "On three-machine flow shop scheduling with deteriorating jobs". International Journal of Production Economics, 125(1): 185-189.
[26] Jafari, A.A., Khademi-zare, H., Lotfi, M.M., Tavakkoli-Moghaddam, R. (2017). "A note on “On three-machine flow shop scheduling with deteriorating jobs”". International Journal of Production Economics, 191: 250-252.
[27] Li, Dw., Lu, Xw. (2020). "Parallel-batch scheduling with deterioration and rejection on a single machine". Applied Mathematics-A Journal of Chinese Universities, 35: 141–156.
[28] Mor, B., Mosheiov, G. (2020). "Minimizing total load on parallel machines with linear deterioration". Optimization Letters, 14: 771–779.
[29] Bai, D., Bai, X., Yang, J., Zhang, X., Ren, T., Xie, C., Liu, B. (2021). "Minimization of maximum lateness in a flowshop learning effect scheduling with release dates". Computers & Industrial Engineering, 158: 107309.
[30] Brucker, P. (2006). Scheduling algorithm, 5th Edition, Springer, Berlin, Heidelberg, New York.
[31] Chen, R., Yuan, J. (2020). " Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices". Journal of Operation Research, 18(2): 177-196.
[32] Moslehi, G., Jafari, A. (2010). "Minimizing the number of tardy jobs under piecewise-linear deterioration". Computers & Industrial Engineering, 59(4): 573–584.
 
نشریه پژوهش های مهندسی صنایع در سیستم های تولید
دوره 9، شماره 19
اسفند 1400
صفحه 169-187

فایل ها

هم رسانی

ارجاع به این مقاله

آمار