ارائه یک مدل ریاضی و یک الگوریتم شاخهوکران برای مسأله زمانبندی تکماشین با فرض زوال خطی و ورود غیرهمزمان کارها | ||
نشریه پژوهش های مهندسی صنایع در سیستم های تولید | ||
دوره 9، شماره 19، اسفند 1400، صفحه 169-187 اصل مقاله (897.6 K) | ||
نوع مقاله: مقاله پژوهشی | ||
شناسه دیجیتال (DOI): 10.22084/ier.2021.24228.2024 | ||
نویسندگان | ||
عباسعلی جعفری ندوشن* 1؛ محمدحسین دهقانی صدرآبادی2؛ علی بزرگی امیری3 | ||
1استادیار، گروه مهندسی صنایع، دانشکده فنی و مهندسی، دانشگاه میبد، میبد، ایران | ||
2دانشجوی دکتری، دانشکده مهندسی صنایع، دانشگاه علم و صنعت ایران، تهران، ایران؛ | ||
3دانشیار، دانشکده مهندسی صنایع، پردیس دانشکدههای فنی، دانشگاه تهران، تهران، ایران | ||
چکیده | ||
در این مقاله مسأله زمانبندی تکماشین با فعالیتهای روبه زوال خطی و فرض ورود غیرهمزمان کارها مورد بررسی قرار گرفته شده است که هدف حداقل کردن تعداد کارهای دارای دیرکرد میباشد. با تکیهبر ادبیات موضوع ثابت میگردد که مسأله موردنظر یک مسأله NP-hard است. درابتدا یک مدل ریاضی برای مسأله ارائه شده و جهت حل مسأله بهصورت بهینه نیز یک الگوریتم شاخهوکران با درنظر گرفتن اصول غلبه و حدود پایین پیشنهاد گردیده است. بهمنظور بررسی عملکرد الگوریتم شاخهوکران پیشنهادی و همچنین تأثیر پارامترهای مرتبط روی این الگوریتم، نتایج محاسباتی در چهار مرحله ارائه شده است. براساس آزمون تحلیل واریانس مشخص گردید که کارایی الگوریتم شاخهوکران بالاست بهطوریکه قادر به حل اکثر مسائل با ابعاد 30 فعالیت در مدت زمان قابل قبولی بوده و متوسط درصد کل گرههای قطع شده در تمامی مسائل حداقل برابر با 85.61 درصد میباشد. همچنین نشان داده شد که مسائل با لاندای بزرگتر و نرخ زوال کوچکتر سخت هستند و متوسط زمان حل الگوریتم در آنها بالا میباشد. ازطرفی اگر موعد تحویل کارها بزرگ یا کوچک باشند نیز مسأله ساده بوده و زمان حل آن نسبتبه مسائل با موعد تحویل متوسط کمتر است. | ||
کلیدواژهها | ||
فعالیتهای روبه زوال؛ زمانبندی؛ تعداد کارهای دارای دیرکرد؛ ورود غیرهمزمان؛ الگوریتم شاخه وکران | ||
مراجع | ||
]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.
| ||
آمار تعداد مشاهده مقاله: 323 تعداد دریافت فایل اصل مقاله: 257 |