ارزیابی دو الگوریتم ابتکاری برای مسئله زمانبندی بر روی دو ماشین

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

کلیدواژه ها:

زمان بندی ، تقریب دیفرانسیلی ، بهینه سازی ترکیباتی ، ماشین های موازی