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

در این مقاله مسأل هی زمان بندی تک ماشین با فرض زوال خطی-تکه ای 1 با هدف کمینهسازی تعداد کارهای دیرکرددار وزنی بررسی شده است که در آن مدت زمان پردازش هر کار بر اساس یک تابع خطی -تکه ای به زمان شروع آن کار وابسته است و تمام کارها نرخ زوال 2 مجزایی دارند. در ابتدا پیچیدگی مسأله بررسی و ثابت شده است که این مسألهNP-hard است. بنابراین برای حلمسأله فوق یک رویکرد شاخه و کران با در نظر گرفتن اصول غلبه و حدود پایین ارائه شده است. نتایج محاسباتی برای 1900 مسأله نشان می دهد که رویه شاخ هو کران قادر به حل مسائل با ابعاد 28 فعالیت می باشد و در بعضی از گروه ها مسائل با ابعاد بزرگ تر نیزحل شد هاند. به طور کلی الگوریتم شاخ هو کران96/9%از نمونهها را به صورت بهینه حل می کند، که این امر کارآیی بالای رویه ارایه شده را نشان می دهد

کلیدواژه ها:

زمان بندی ، فعالیت های روبه زوال ، تعداد کارهای دیرکرددار وزنی ، شاخه و کران