$n$ کار با زمان‌های پردازشی $t_1,t_2,…,t_n$($t_i$ ها عددی طبیعی هستند) وجود دارند. رابطه‌ی پیشنیازی بین این کارها به صورت گراف جهت‌دار بدون دور $G$ داده شده است و در گراف $G$، هر کار توسط یک راس نشان داده شده است و یال $e=(i,j)$ دراین گراف نشان‌دهنده‌ی این است که کار $i$ پیشنیاز کار $j$است؛ به این معنا که شروع انجام کار $j$ باید بعد از اتمام انجام کار $i$ باشد.

$p$ پردازنده وجود دارند که می‌توانند به صورت هم‌زمان این کارها را انجام دهند؛ وقتی پردازنده‌ای انجام کاری را شروع می‌کند باید آن را تا اتمام کار بدون وقفه انجام دهد.

الگوریتم حریصانه‌ی زیر را برای انتساب کارها به پردازنده‌ها در نظر بگیرید:

هر پردازنده هنگامی که بیکار است، به دنبال کار انجام نشده‌ای می‌گردد که همه‌ی کارهای پیشنیازی آن انجام شده باشند؛ اگر چنین کاری پیدا کرد، آن را تا اتمام انجام می‌دهد و دوباره همین الگوریتم را تکرار می‌کند و اگر چنین کاری نبود بیکار می‌ماند و مرتبا در هر لحظه به دنبال چنین کاری می‌گردد تا آن را اجرا کند.

وزن هر مسیر در گراف $G$ را مجموع $t_i$ های مربوط به کارهای متناظر رئوس متعلق به مسیر تعریف می‌کنیم و $L$ را وزن سنگین‌ترین مسیر در گراف $G$ می‌گیریم.

$W$ را مجموع زمان‌های کارها به صورت $W=\sum_{i=1}^{n} t_i$ تعریف می‌کنیم.

$T$ را زود‌ترین زمانی در نظر می‌گیریم که با اجرای الگوریتم حریصانه‌ی فوق پردازش همه‌ی کارها تمام شده باشد.

ثابت کنید:

• سوال بعد
• سوال قبل