فرض کنید که $n$ کار برای اجرا به ما داده شده است و $M$ ماشین برای اجرای این کارها در اختیار داریم. هر یک از کارها را می‌توانیم روی هر یک از ماشین‌ها اجرا کنیم. البته اجرای هر یک از کارها باید بدون توقف روی یکی از ماشین‌ها انجام شود. زمان اجرای کار $i$ ام، روی هر یک از ماشین‌ها برابر با $t_i$ است. می‌خواهیم ترتیب اجرای کارها روی ماشین‌ها، و این که هر یک از کارها روی چه ماشینی اجرا شود را به گونه‌ای تعیین کنیم، که متوسط زمان پایان یافتن کارها مینیمم شود. منظور از زمان پایان یافتن کار $i$ ام، که آن را با $C_i$ نشان می‌دهیم، زمانی است که اجرای این کار تمام شده است و منظور از متوسط زمان پایان یافتن کارها، $\frac{1}{n} \sum_{i=1}^n$ است.

برای این منظور الگوریتم زیر پیشنهاد شده است: در هر لحظه که ماشینی بی‌کار شد، از بین کارها‌ی باقی‌مانده، کاری که زمان اجرای آن از همه کم‌تر است را پیدا کرده، آن را برای اجرا به آن ماشین می‌دهیم. در صورتی که چند ماشین در یک لحظه بی‌کار باشند (مثلا در لحظه‌ی اول که همه‌ی ماشین‌ها هم‌زمان بی‌کار هستند)، به یک ترتیب دل‌خواه ماشین‌های بی‌کار را در نظر می‌گیریم و بر طبق الگوریتم فوق به آن‌ها کار می‌دهیم.

ثابت کنید که الگوریتم فوق درست کار می‌کند؛ یعنی جوابی که به دست می‌آورد همواره بهینه است.

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