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

در مدل پایه تیوری زمان بندی فرض می شود که مدت زمان پردازش فعالیت ها مقداری ثابت است ولی این فرض در برخی از مسایل مانند فعالیت های رو به زوال نمی تواند صحیح باشد. در این مقاله مساله زمان بندی فعالیت های رو به زوال خطی با فرض ورود غیرهمزمان کارها در حالت تک ماشین مورد بررسی قرار گرفته شده که هدف حداقل کردن تعداد کارهای دیرکرددار وزنی می باشد. در ابتدا ثابت می گردد که این مساله یک مساله NP-hard است. جهت حل مساله به صورت بهینه یک رویکرد شاخه کران ارایه 1680 نمونه مساله تصادفی تولید حل شده است. نتایج نشان می دهد که این الگوریتم کارآیی بالایی دارد حداقل 82/43% از کل گره های درخت جستجو را قطع می نماید به طوری که مسایل با ابعاد 28 فعالیت را در مدت زمان قابل قبولی حل می نماید.

Keywords:

زمانبندی , ورود غیرهمزمان , تعداد کارهای دیرکرددار وزنی , شاخه کران , زوال خطی