تعدادی کار و تعدادی پردازنده داریم. برای هر کار، تعدادی پردازنده‌ی مجاز وجود دارد. زمان اجرای کار ‎$i$‎ام روی پردازنده‌های مجازش ‎$t_i$‎ و روی پردازنده‌های غیرمجازش بی‌نهایت است. یک زمان‌بندی عبارت است از پخش کارها روی پردازنده‌ها و انجام کارهای هر پردازنده به یک ترتیب خاص و پشت‌سرهم.

در یک زمان‌بندی، به کار‎$i$ «ناراضی»‎ می‌گوییم اگر با ثابت نگه داشتن بقیه کارها و بردن کار ‎$i$‎ به یک پردازنده‌ی دیگر (و نه لزوماً هر پردازنده‌ی دیگر) و انجام آن کار پس از اجرای بقیه‌ی کارهای آن پردازنده‌ی دیگر، زمان پایان کار ‎$i$‎ کم‌تر شود. به یک زمان‌بندی ‎«پایدار»‎ می‌گوییم اگر و فقط اگر در آن هیچ کاری ناراضی نباشد. هزینه‌ی یک زمان‌بندی عبارت است از مقدار زمانی که طول می‌کشد تا همه‌ی پردازنده‌ها دست از کار بکشند.

برای هر ‎$n>10$ (که ‎$n$‎ تعداد پردازنده‌هاست)، مثالی از سیستم بالا با یک زمان‌بندی پایدار بزنید که هزینه‌اش حداقل ‎$\lfloor \log n\rfloor$‎ برابر هزینه‌ی زمان‌بندی بهینه (و نه لزوماً پایدار) باشد.

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