ارائة یک الگوریتم تقریب جدید با حد بدترین خطای بسته برای مسئله زمان‌بندی تک ماشین با تغییر ابزار و کارهای ویژه

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

نویسندگان

دانشگاه صنعتی اصفهان

چکیده

مسئله زمانبندی با تغییرات ابزار به طور گسترده در دو دهه اخیر مورد بررسی قرار گفته است. این مسئله در فعالیت‌های نگهداری و تعمیرات انعطاف‌پذیر که در آن ابزار ممکن است در هر زمان از طول عمر خود تعویض شود کاربرد فراوانی دارد. همچنین در نظر گرفتن شرایط تولید، از جمله کیفیت ابزار مورد استفاده، در تعیین کیفیت محصول نهایی امری اجتناب ناپذیر است. از این رو در این مطالعه با توجه به زمان استفاده از ابزار برای پردازش کارها، کارها از نظر کیفیت به دو دسته ویژه و معمولی تقسیم‌بندی می‌شوند. در این مقاله مدل کلاسیک زمان‌بندی تک ماشین همراه با تغییرات ابزار روی ماشین مورد بررسی قرار میگیرد. در این مسئله دو مجموعه کار‌های ویژه و کارهای معمولی در نظر گرفته می‌شوند و کارهای ویژه باید طی مدت زمان معین پس از تغییر ابزار انجام شوند. این مسئله در ادبیات موضوع مورد بررسی قرار گرفته و برای حل آن در ابعاد کوچک و متوسط دو مدل برنامه‌ریزی ریاضی و برای ابعاد بزرگ شش الگوریتم بر مبنای مسئله جای‌گذاری ظرف (Bin Packing) ارائه شده است که تمرکز اصلی مطالعه مذکور نیز بر روی عملکرد شش الگوریتم بوده است. در این مقاله به ارائه یک الگوریتم جدید دیگر برای حل این مسئله در ابعاد بزرگتر پرداخته می‌شود. نتایج محاسباتی نشان می‌دهد کارایی الگوریتم ارائه شده در نیمی از مسائل نمونه بهتر از چهار الگوریتم مطالعة قبل و در نیم دیگر از مسائل نمونه بهتر از تمامی شش الگوریتم توسعه داده شده در مطالعه قبلی برای این مسئله است.

کلیدواژه‌ها

موضوعات


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

Developing a new approximation algorithm with a tight worst-case for a single machine scheduling problem with tool change and special jobs

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

  • Mohammad_Hasan Ahmadi_Darani
  • Mohammad Reisi-Nafchi
چکیده [English]

Scheduling problems with tool changes considerations have been investigated extensively in the last two decades. Tool change activities applied in flexible maintenance activities where the tools may be changed at any time of their lifespan. Also, to determining the quality of the final product, considering the quality of the tools as a production condition items is inevitable. In this paper, the classical single machine scheduling problem with tool change is examined. In this problem, two sets of jobs, namely special jobs and normal jobs are considered. Special jobs must be processed during a certain time after the tool change. This problem has been studied in the literature. Mathematical programming models used to solve scheduling problems with small size and medium size. For scheduling problems with large size, six algorithms based on Bin Packing problem presented and focused on their performance. In this paper, we present a new algorithm for solving large size scheduling problems. The computational results show that the proposed algorithm performance at the half of instance problems is better than four algorithms of literature. In addition, in the other instance it is better than all developed literature algorithms.

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

  • Scheduling
  • Single machine
  • Tool change
  • Approximation algorithm

[1]     Schmidt, G., (2000). “Scheduling with limited machine availability”, European Journal of OperationalResearch, 121: 1-15

[2]     Ma, Y., Chu, C., Zuo, C., (2010). “A survey of scheduling with deterministic machine availability constraints”, Computers and Industrial Engineering, 58: 199-211.

[3]     Akturk, M.S., Ghosh, J.B., Gunes, E.D., (2003(. “Scheduling with tool changes to minimize total completion time: a study of heuristics and their performance”, Naval Research Logistics, 50: 15–30.

[4]     Akturk, M.S., Ghosh, J.B., Kayan, R.K., (2007). “Scheduling with tool changes to minimize total completion time under controllable machining conditions”, Computers and Operations Research, 37: 2130–2146.

[5]     Akturk, M.S., Ghosh, J.B. Gunes, E.D., (2004). “Scheduling with tool changes to minimize total completion time: basic results and SPT performance”, European Journal of Operational Research, 157: 784–790.

[6]     Chen, J.S., (2008). “Optimization models for the tool change scheduling problem”, Omega, 36: 888-894.

[7]     Qi, X., Chen, T., Tu, F., (1999). “Scheduling the Maintenance on a Single Machine”, the Journal of the Operational Research Society, 50: 1071-1078.

[8]     Xu, D., Yin, Y., Li, H., (2010). “Scheduling jobs under increasing linear machine maintenance time”, Journal of scheduling, 13: 443-449.

[9]     Shi, X., Xu, D., (2014). “Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations”, The Scientific World Journal, 2014: 547-573.

[10] Xu, D., Liu, M., Yin, Y., Hao, J., (2013). “Scheduling tool changes and special jobs on a single machine to minimize makespan”, Omega, 41: 299–304.

[11] ] Costa, A., Cappadonna, F.A., Fichera, S., (2016). “Minimizing the total completion time on a parallel machine system with tool changes”, Computers and Industrial Engineering, 91: 209-301.

[12] Yazdani, M., Khalili, S.M., Jolai, F., (2016). “A parallel machine scheduling problem with two-agent and tool change activities: an efficient hybrid metaheuristic algorithm”, International Journal of Computer Integrated Manufacturing, 29(10): 1075-1088.

[13] ] He, J., Li, Q., Xu, D., (2016). “Scheduling two parallel machines with machine-dependent availabilities”, Computers and Operations Research, 72: 31-42.

[14] Graham, R.L., Lawler, Lenstra, E.L., Rinnooy, J.K., Kan, A.H.G., (1979). “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of Discrete Mathematics, 5: 287–326.

[15] Coffman, E.G., Garey, M.R., Johnson, D.S., (1997). Approximation algorithms for bin packing: a survey, In Approximation algorithms for NP-hard problem, edited by Hochbaum, D.S., Boston: PWS Publishing Company.