در کارخانه‌ای یک دستگاه وجود دارد که باید $n$ کار را انجام دهد. می‌دانیم که انجام کار $i$ام به اندازه‌ی $t_i$ از این دستگاه وقت می‌گیرد و باید حداکثر تا زمان $d_i$ تحویل داده شود. فرض کنید که دستگاه در زمان صفر شروع به کار می‌کند. علاوه‌بر‌این، می‌دانیم که این دستگاه نمی‌تواند در هر لحظه بیش از یک کار را انجام دهد.

اگر دستگاه در زمان $s_i$ شروع به انجام کار $i$ام کند، انجام آن در زمان $s_i+t_i$ به پایان خواهد رسید. اگر $s_i+t_i>d_i$، یعنی کار $i$ام در زمانی که باید تحویل داده شود هنوز به طور کامل انجام نشده باشد، مقدار $L_i=s_i+t_i-d_i$ را دیر کرد کار $i$ام می‌نامیم. در غیر این صورت دیر کرد کار $i$ام برابر با صفر تعریف می‌شود. دیرکرد کل دستگاه برابر با بیش‌ترین دیرکرد کارها، یعنی $L=max⁡\{L_1 ,L_2,…,L_n \}$ تعریف می‌شود.

می‌خواهیم ترتیب انجام کارها را به گونه‌ای پیدا کنیم که مقدار دیرکرد کل دستگاه حداقل شود. برای این منظور الگوریتمی به این صورت پیشنهاد داده شده است:

ابتدا کارها را برحسب مقدار $d_i$ آن‌ها به ترتیب صعودی مرتب می‌کنیم و دستگاه کارها را به‌این‌ ترتیب انجام می‌دهد.

ثابت کنید که این الگوریتم درست عمل می‌کند، یعنی اگر کارها را به این ترتیب انجام دهیم، مقدار دیرکرد کل دستگاه حداقل می‌شود.

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