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

سال انتشار: 1397
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 495

فایل این مقاله در 11 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

IIEC15_331

تاریخ نمایه سازی: 10 اردیبهشت 1398

چکیده مقاله:

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

کلیدواژه ها:

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

نویسندگان

عباسعلی جعفری ندوشن

استادیار مهندسی صنایع، دانشکده فنی مهندسی، دانشگاه میبد- میبد ایران