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

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

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