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

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

کلیدواژه ها:

زمان بندی ، تک ماشین ، تغییر ابزار الگوریتم تقریبی