تمرین های فصل 2 WS (زمانبندی کارها) 2.1,2.3

2- فرض مساله را به صورت زیر می نویسیم

OPT/3 < w_1 <= w_2 <=...<=w_m

الگوریتم LPT هم کارها را به ترتیب از زمان اجرای زیاد به کم انجام می دهد. می خواهیم ثابت کنیم این کار به جواب بهینه می رسد.

از فرض داده شده می فهمیم به هر پردازنده حداکثر 2 کار می رسد. جواب بهینه جوابی است که زوج کارهایی که به یک پردازنده داده می شوند، جمعشان مینیمم شود. اگر تعداد پردازنده ها از نصف کارها بیشتر باشد که کارهای با زمان طولانی تر به تنهایی روی یک پردازنده اجرا می شوند و کارهای با زمان کمتر هر دو تا روی یک پردازنده اجرا می شوند. پردازنده هایی که به آنها دو کار داده شده است، باید طوری باشند که جمع این دو کار مینیمم شود. برای این کار بهترین کار این است که کار با بیشترین زمان و کمترین زمان را با هم به یک پردازنده بدهیم.

3- الگوریتم زمانبندی لیست کارها را به ترتیبی دلخواه در یک لیست می گذارد و کار بالای لیست را به اولین پردازنده ای که بیکار شد می دهد. اثبات آن به اثبات جستجوی محلی ارجاع داده شده بود.

بر خلاف اثبات سوال بدون اولویت نمی توانیم از میانگین به عنوان کران پایین استفاده کنیم.