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

امروزه مسایل زمان بندی در بسیاری از سیستم های تولیدی و خدماتی کاربرد وسیعی یافته اند. در مسایل زمان بندی کلاسیک مدت زمان پردازش کارها، مقداری ثابت فرض می شود. اگرچه این فرض در بعضی از حالتها درست می باشد ولی با در نظر گرفتن اثرات یادگیری، فراموشی و زوال این فرض نمی تواند همیشه صحیح باشد. در این مقاله مساله زمان بندی تک ماشین با فرض زوال خطی و ورود غیرهمزمان کارها و با هدف کمینه کردن تعداد کارهای دیرکرددار مورد بررسی قرار گرفته شده است. ثابت می شود که این مساله NP - hard است. بنابراین جهت حل آن به صورت بهینه یک الگوریتم شاخه و کران با در نظر گرفتن اصول غلبه و حدود پایین ارایه شده است. نتایج نشان داد که الگوریتم قادر به حل مسایل با ابعاد 24 فعالیت در مدت زمان قابل قبولی میباشد. همچنین ثابت گردید که عملکرد الگوریتم پیشنهادی بسیار بالاست به طوری که درصد گره های قطع شده در تمام مسایل حداقل برابر با 81 / 02 ٪ می باشد.

Keywords:

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