زمانبندی دو معیاره برای حداقل سازی زمان دیرکرد کل و واریانس زمان انتظار بر روی یک ماشین با استفاده از الگوریتم ژنتیک

مسایل عملی زمان بندی معمولا تصمیم گیرنده را وادار به در نظر گرفتن تعداد زیادی از معیارها قبل از اتخاذ تصمیم مینمایند. این تحقیق یک مسیله زمانبندی تک ماشین را مورد بررسی قرار میدهد که هدف در آن حداقل کردن ترکیبی از دو معیار دیرکرد کل و واریانس زمان انتظار میباشد به طوری که زمان بیکاری در ماشین مجاز نیست. حداقل کردن دیرکرد کل همیشه به عنوان یک معیار عملکرد مهم در سیستمهای عملی، که میتوان با استفاده از آن از تحمیل هزینه های جریمه دیرکرد اجتناب نمود، مطرح میباشد و واریانس زمان انتظار نیز یک معیار مهم در پیادهسازی کیفیت خدمات (QoS) در بسیاری از سیستمها میباشد. هر کدام از این دو معیار از نوع NP-hard میباشند و بنابراین ترکیب خطی آنها نیز NP-hard خواهد بود. برای این مسیله الگوریتمی ژنتیک طراحی شده که از ساختار معمول آن استفاده می کند. دو نوع جمعیت هیوریستیک و تصادفی برای جمعیت اولیه و دو نوع تابع برازش در الگوریتم به کار رفته است. کارایی الگوریتم ژنتیک ارایه شده به وسیله تست روی تعداد زیادی از مسایل نشان داده میشود.

Keywords:

زمان بندی دو معیاره , تک ماشین , الگوریتم فرا ابتکاری , دیرکردکل , واریانس زمان انتظار