ام تاخير دار باشد مقدار آن برابر 1 و در غير اينصورت صفر است.j اگر کار

Tardy jobs

فاز اول-مسئله بدون زمان تحويل
در اين بخش مسئله مورد مطالعه را در ساده ترين حالت ممکن و با در اختيار داشتن زمان هاي پردازش مرحله اول و دوم در نظر مي گيريم. در اين بخش الگوريتم MRS1 را به منظور افزايش ميزان بهره برداري از ماشين آلات در دسترس و يا به عبارت ديگر مينيمم نمودن زمان بيکاري ماشين ها، پيشنهاد داده ايم. اين الگوريتم از الگوريتم MDA الهام گرفته شده است.
ساختار الگوريتم پيشنهادي MRS1
الگوريتم پيشنهادي با بهره گرفتن از يک رويکرد پويا، همزمان با توليد توالي کارها، کار تخصيص ماشين به کارها را نيز انجام مي دهد. هدف اين الگوريتم ماکزيمم نمودن درصد بهره برداري^[66] از ماشين ها مي باشد. اين تابع هدف بيشتر براي شرکت هايي قابل استفاده است که از ماشين آلات استيجاري استفاده مي کنند و به ازاي ميزان ساعت استفاده از ماشين آلات بهاي آنرا بايد پرداخت نمايند زيرا با بهره گرفتن از اين تابع هدف بيکاري ماشين آلات به حداقل ممکن رسيده و حداکثر بهره برداري ممکن از ماشين آلات صورت مي گيرد.
مراحل الگوريتم پيشنهادي به شرح زير مي باشد:
مرحله صفر:
فرض مي کنيم :
مرحله يک: در ابتدا فرض مي کنيم که کليه کارهاي موجود قابل زمان بندي در زمان صفر هستند، مقدار  را براي کليه کارهاي زمان بندي نشده حساب کرده و کاري که داراي کوچکترين مقدار  است به عنوان کار انتخاب شده جهت زمان بندي در نظر مي گيريم.
مرحله دو: اگر  آنگاه
و يا اگر  آنگاه
بعد از به روزرساني، کار زمانبندي شده از مجموعه  حذف شده و به مجموعه  اضافه شود.
مرحله سه: اگر  ، اجراي الگوريتم متوقف مي شود و تابع هدف بهره برداري محاسبه مي شود. در غير اينصورت به مرحله يک بازمي گرديم.
الگوريتم پيشنهادي براي توضيح بيشتر توسط يک مثال ساده با 8 کار و دو ماشين در هر مرحله حل شده است. زمان هاي پردازش مربوط به مرحله اول و مرحله دوم کارها در جدول (3-3) ارائه شده است. برنامه متناظر توليد شده توسط الگوريتم  براي مثال ارائه شده در شکل (3-1) نمايش داده شده است. در شکل، شماره داخل مستطيل نشان دهنده شماره کار زمانبندي شده است. مستطيل هاي همراه با هاشور در شکل نشان دهنده اين است که ماشين ها منتظر قرار دادن کارها روي خود هستند و بيکار مانده اند.
زمان هاي پردازش مرحله اول و دوم براي مثال ارائه شده

j

1

2

3

4