فهرست نشریات علمی دسترسی آزاد ایران

در این مقاله مسأله زمان‌بندی تک‌ماشین با فعالیت‌های روبه زوال خطی و فرض ورود غیرهم‌زمان کارها مورد بررسی قرار گرفته شده است که هدف حداقل کردن تعداد کارهای دارای دیرکرد می‌باشد. با تکیه‌بر ادبیات موضوع ثابت می‌گردد که مسأله موردنظر یک مسأله NP-hard است. درابتدا یک مدل ریاضی برای مسأله ارائه شده و جهت حل مسأله به‌صورت بهینه نیز یک الگوریتم شاخه‌وکران با درنظر گرفتن اصول غلبه و حدود پایین پیشنهاد گردیده است. به‌منظور بررسی عملکرد الگوریتم شاخه‌وکران پیشنهادی و همچنین تأثیر پارامترهای مرتبط روی این الگوریتم، نتایج محاسباتی در چهار مرحله ارائه شده است. براساس آزمون تحلیل واریانس مشخص گردید که کارایی الگوریتم شاخه‌وکران بالاست به‌طوری‌که قادر به حل اکثر مسائل با ابعاد 30 فعالیت در مدت زمان قابل قبولی بوده و متوسط درصد کل گره‌های قطع شده در تمامی مسائل حداقل برابر با 85.61 درصد می‌باشد. همچنین نشان داده شد که مسائل با لاندای بزرگ‌تر و نرخ زوال کوچک‌تر سخت‌ هستند و متوسط زمان حل الگوریتم در آن‌ها بالا می‌باشد. ازطرفی اگر موعد تحویل کارها بزرگ یا کوچک باشند نیز مسأله ساده بوده و زمان حل آن نسبت‌به مسائل با موعد تحویل متوسط کمتر است.