تعریف و کاربرد
SPT میانگین زمان تکمیل را در مسئله تک‌ماشینه با زمان آماده‌بودن یکسان و بدون قطع کار کمینه می‌کند؛ EDD برای کمینه‌کردن حداکثر دیرکرد علامت‌دار (lateness) کاربرد دارد، نه لزوماً مجموع تأخیر.
پیش‌نیاز
زمان پردازش و موعد تحویل هر سفارش
SCHEDULING / SPT AND EDD
زمان‌بندی تک‌ماشینه: SPT و EDD
مقایسه دو قاعده ساده توالی مشاغل با معیارهای متفاوت.
روش حل، چهار مرحله
- 1. داده کارها را گردآوری کن
زمان پردازش و موعد تحویل را برای هر کار ثبت کن.
- 2. توالی SPT را بساز
مرتب‌سازی صعودی زمان پردازش.
- 3. توالی EDD را بساز
مرتب‌سازی صعودی موعد تحویل.
- 4. معیار مناسب را مقایسه کن
زمان تکمیل متوسط، تأخیر و حداکثر lateness یکسان نیستند.
مثال حل‌شده با داده فرضی
سه کار داریم: A با زمان ۴ و موعد ۶؛ B با زمان ۲ و موعد ۳؛ C با زمان ۳ و موعد ۷. SPT: B→C→A، زمان‌های تکمیل ۲، ۵، ۹ و میانگین ۵٫۳۳ است؛ تأخیر مثبت A برابر ۳. EDD: B→A→C، زمان‌های تکمیل ۲، ۶، ۹ و میانگین ۵٫۶۷؛ تأخیر مثبت C برابر ۲.
SPT متوسط تکمیل را بهتر می‌کند؛ EDD در این مثال بیشترین تأخیر مثبت را کمتر می‌کند
فرض‌ها، محدودیت‌ها و تفسیر
نتیجه‌های بهینگی فوق فقط برای مدل تک‌ماشینه، آماده‌بودن هم‌زمان همه کارها و بدون زمان راه‌اندازی وابسته به توالی کاربرد دارند.