ارائه يك مدل رياضي و يك الگوريتم شاخه‌وكران براي مسأله زمان‌بندي تك‌ماشين با فرض زوال خطي و ورود غيرهم‌زمان كارها

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