۱-۸- جمعﺑندی:
دو علم زمانبندی و توالی, امروزه یکی از علوم کاربردی میﺑاشند. طبقهﺑندیﻫای مختلفی برای مسائل مربوط به آنها وجود دارد که به برخی از آنها در این مطالعه بطور مختصر اشاره گردید. از جمله این طبقهﺑندیﻫا, در ارتباط با مسائل ماشینﻫای موازی میﺑاشد. با توجه به مسائلی که اخیرا در زمینه زمانبندی ماشین آلات در محیطﻫای تولید به موقع مطرح شده است, اکثر شرکتﻫای تولیدکننده مجبور به ایجاد زمانبندیﻫایی هستند که نیاز مشتری را در موعد تحویل یا نزدیک به آن رفع سازد. بنابراین در نظر گرفتن همزمان دو معیار مجموع وزنی دیرکرد و زودکرد این مسائل را به واقعیت نزدیکﺗر کرده و آنها را پیچیدهﺗر ساخته است. در این مطالعه, سعی شده است که مساله ماشینﻫای موازی با در نظر گرفتن معیار, بررسی شده و با توجه به پیچیدگی مساله مورد نظر, یک روش فراابتکاری برای حل آن پیشنهاد گردیده است. در فصل بعد به مرور ادبیات در زمینه ماشینﻫای موازی میﭘردازیم.

مروری بر ادبیات موضوع
فصل دوم
۲-۱- مقدمه:
زمانبندی در اوایل قرن گذشته با مطالعات صورت گرفته توسط هنری گانت و سایر پیشگامان در کانون توجه قرار گرفت.با این وجود سالها به طول انجامید تا اولین تحقیقات در حوزه زمانبندی انتشار یابد.در سالهای آغازین دهه پنجاه میلادی مطالعاتی در زمینه توالی عملیات که انگیزه آنها از زمانبندی تولید ناشی می شد منجر به ارائه الگوریتمهای مهمی چون قاعده جانسون برای مسئله سیستم کارگاه جریانی ، قاعده زودتر موعد تحویل برای کمینه سازی زمان تاخیر بیشینه و قاعده کوتاه ترین زمان پردازش با هدف کمینه سازی زمان جریان میانگین شد.در طول دهه شصت با پدید آمدن مسائل پیچیده تر تعداد قابل ملاحظه ای از تحقیقات به روش های دقیق چون برنامه ریزی خطی و برنامه ریزی پویا معطوف شد.پس از انتشار مقاله مشهور ریچارد کارپ]۱[در زمینه نظریه پیچیدگی ،محققان دریافتند که الگوریتم دقیق در مدت زمان معقول قادر به یافتن جواب بهینه در مسائل پیچیده نیستند و در نتیجه در طول دهه هفتاد میلادی بخش عمده تحقیقات بر روی سلسله مراتب پیچیدگی مسائل زمانبندی متمرکز شد
اخیرا مطالعه در زمینه جریمه دیر کرد و زود کرد در مدلهای زمانبندی، بطور وسیعی مورد توجه محققان بوده است. تحقیق های گذشته بیشتر بر روی معیارهای منظم مانند حداکثر زمان تکمیل، حداکثر دیر کرد و یا میانگین دیر کرد، متمر کز بوده اند. ولی امروزه به دلیل جریمه های حاصل از زود کرد، این معیار نامنظم، نیز مورد توجه محققان علم زمانبندی قرار گرفته است. همه تولید کنندگان برای مقابله با فشارهای رقابتی بطور افزاینده ای خودشان را با عقیده JIT و حداقل هزینه موجودی، مطابقت می دهند که این مستلزم در نظر گرفتن زود کرد کارها می باشد. در واقع در JIT زود کرد کارها به اندازه دیر کرد آنها اهمیت دارد. گرچه فرض بر این است که موعد تحویل یک متغیر خارجی بوده و کنترل آن خارج از عهده مدیران است، ولی اهمیت تحویل در موعد به خوبی روشن است. کانوی[۱۰]، برای اولین بار این نظریه را مطرح کرد که موعد تحویل قسمتی از مسأله زمانبندی است. از کسانی که در این زمینه مطالعه کردند می توان از وبستر و بیکر[۱۱]، راگاتز و مابرت[۱۲]، کریستی و کانت[۱۳]، نام برد. مطالعات زیادی در زمینه مسائل زمانبندی مختلف با معیارهای دیر کرد و زود کرد (E/T) ، صورت گرفته است. وبستر، بیکر و جاگ[۱۴]، مسأله تک ماشینه (E/T) را با در نظر گرفتن موعد تحویل یکسان و نامعین به عنوان یک متغیر تصمیم، برای دو حالت زمان های آماده سازی مستقل و وابسته به توالی با روش الگوریتم ژنتیک حل کرده اند. کریستوفر بک و فیلیپ رفالو[۱۵]، یک روش ترکیبی با بهره گرفتن از برنامه ریزی خطی و برنامه ریزی مفید برای مسأله زمانبندی با معیار هزینه زود کرد و دیر کرد ارائه کردند. سوریا د.لیمان، شریکانت س.پالواکر و سانسرن دونگمی[۱۶]، مسأله زمانبندی تک ماشینه با موعد تحویل محدود شده به یک فاصله و زمان پردازش قابل کنترل را ارائه کردند. آنها جریمه کلی که شامل جریمه های زود کرد، دیر کرد، زودترین موعد تحویل، طول فاصله مربوط به موعد تحویل و مقدار واقعی کاهش زمان پردازش می باشد را با یک روش ابتکاری کمینه می کنند.
ون-کیانگ زایو و چانگ لانلی[۱۷]، به بررسی روش های تقریبی برای تخصیص موعد تحویل مشترک به کارها و زمانبندی آنها در مسأله ماشین های موازی پرداختند. هدف، تخصیص موعد تحویل کارها می باشد، بطوریکه مجموع وزنی موعد تحویل، کل زود کرد و کل دیر کرد کمینه گردند.
زایو کینگ کی و زایان زو[۱۸]، مسأله زمانبندی تک ماشینه با زمان پردازش احتمالی با توزیع نمایی و موعد تحویل احتمالی، با هدف کمینه کردن مجموع هزینه های وزنی دیر کرد و زود کرد را بررسی کرده اند. در این مسأله خرابی ماشین^[۸] جزو فرضها بوده و مسأله با روش برنامه ریزی پویا حل شده است.
محسن الحافی[۱۹] مسأله زمان انتظار^[۹] بهینه را در سیستم های تولیدی جزء به جزء^[۱۰]، با معیار هزینه های زود کرد و دیر کرد را بررسی کرد. مسأله مذکور شامل N مرحله است که زمان انتظار پشت هر مرحله احتمالی است. هدف در اینجا پیدا کردن زمان های انتظار بهینه بوده، بطوریکه هزینه های دیر کرد و زود کرد کمینه شوند. سانجی رادها کریشنان و جزی ا.ونتورا[۲۰]، مسأله زمانبندی ماشین های موازی با معیار هزینه زود کرد و دیر کرد با زمان های آماده سازی وابسته به توالی با رویکرد فراابتکاری پازپخت شبیه سازی شده حل کرده اند.
شریکانت س.پالواکر و سوریا د.لیمان[۲۱]، مسأله زمانبندی با n کار که هر کدام شامل یک عملیات بر روی هر ماشین بوده را با معیار هزینه های دیر کرد و زود کرد بررسی کرده اند. در این مسأله شکستگی کار مجاز نبوده و پارامترهای موعد تحویل و زمان پردازش معین می باشند. هدف در اینجا تعیین تعداد ماشین ها می باشد، بطوریکه هزینه های زود کرد و دیر کرد کمینه گردد.
۲-۲- مروری بر رویکرد و اصول سیستم تولیدی JIT
امروزه با پیشرفت روز افزون تکنولوژی، متنوع شدن نیازها و خواسته های مشتریان حرکت به سوی ساخت و تولید بر اساس سفارش مشتری، محیط رقابتی را در بین شرکت های تولیدی ایجاد و بالطبع مشکلاتی را گریبان گیر آنها نموده است. تولید کنندگان به دنبال سیستم های تولیدی هستند که نیازهای مشتریان نظیر کاهش قیمت، تنوع محصولات، دقت و کیفیت بالا را برآورده سازند. موفق بودن JIT بستگی زیادی به میزان ضایعات ایجاد شده طی فرایند تولید دارد؛ اگر در مرحله ای از تولید ضایعاتی رخ دهد، فرایند های بعدی با مشکل روبرو خواهند شد و کل سیستم دچار اختلال خواهد شد. لذا لازمه ی این سیستم این است که خود کارگران اصلاح کننده سیستم باشند و ضایعات را در حین تولید کشف کرده و نسبت به اصلاح سیستم چه مربوط به ماشین آلات باشد و چه مربوط به کارگران اقدام نمایند[۲۲].
سرعت تولید یک عامل بسیار مهم در سیستم تولید JIT است که هم از لحاظ رویکرد موجودی ها و هم از لحاظ رویکرد کیفیت حائز اهمیت است به عبارتی همیشه اقدام به تولید زیاد و وجود داشتن تعداد زیادی محصول طی فرایند تولید باعث می شود که قسمتی از محصول تکمیل و قسمتی به عنوان کار در جریان ساخت باقی بماند “رویکرد موجودی ها” از طرفی اقدام به تولید زیاد و به جریان انداختن محصولات زیاد باعث می شود که اگر یک نقص در ابتدای فرایند تولید وجود داشته باشد و این نقایص در مراحل بعد کشف شود مقادیر زیادی از محصولات تولید شده مشمول این نقص شود.
تقاضا برای تولید یک عامل بسیار مهم دیکر در سیستم تولید JIT است. تولید زمانی انجام خواهد شد که سفارش از مشتری گرفته شود به همین خاطر این سیستم تولید را اصطلاحا سیستم کشش تولید “تقاضا” نیز نامیده اند، زیرا تا مشتری تقاضا نکند تولیدی انجام نمی شود و لذا عکس سیستم تولیدی سنتی است که در آن مواد تا حد ممکن به فرایند تولید تزریق می شود و فرایند نیز تا حد ممکن تولید می کرد. زیرا هدف این است که مواد خام و قطعات تولیدی فقط در زمان مصرف این مواد و قطعات در فرایند تولید، از فروشندگان تحویل گرفته می شود.
میزان موجودی ها اعم از مواد اولیه، موجودی های نیمه ساخته، کالا و مواد ساخته شده باید تا حد ممکن در سطح بسیار پایین “حتی در حد صفر” نگه داشته شود. مواد فقط زمانی که به آن نیاز است از فروشندگان مواد دریافت شود. میزان اقدام به تولید به نحوی انتخاب می شود که از به وجود آمدن کار در جریان ساخت جلوگیری شود. سیستم تولید JIT بر این اساس بوده که در تولید یک محصول یکسری فعالیتهایی وجود دارد که هیچ گونه ارزشی به محصول تولید شده نمی دهند بلکه فقط هزینه های آن را بالا می برند و از طرفی بعضی از فعالیتها هستند که از ابتدا تا انتها در جهت افزایش ارزش محصول هستند، فعالیتهای غیر ارزشی مثل هزینه های انبارداری، هزینه های راه اندازی دستگاه ها و ماشین آلات، فعالیتهای مربوط به بازرسی مواد و کنترل کیفیت محصول، زمانی که کارگران و ماشین آلات بیکار هستند و فعالیتهای ارزشی همان فعالیتهایی است که مستقیما بر روی محصول و در جهت پردازش و تکمیل آن انجام می شود. این فعالیتها اگر انجام نشود محصول نیز به وجود نخواهد آمد، در صورتیکه در خصوص فعالیتهای نوع اول “غیر ارزشی” وجود یا حذف آن اثری بر به وجود آمدن یا نیامدن محصول ندارد.
رویکرد پایانی که می خواهیم به آن اشاره کنیم، رویکرد مدیریت کیفیت در سیستم JIT است. این رویکرد بر این امر اشاره دارد که سیستم تولیدی JIT صرف نظر از سایر رویکردهایش گامی اثر بخش در کنترل هزینه های محصول است بدون اینکه از کیفیت محصول کاسته شود. این امر تا حدی از طریق ارتباط دائمی با تعدادی محدود از فروشندگان منتخب میسر می شود. این ارتباط از این جهت مهم است که برای رسیدن به کیفیت بالا و بلند مدت، لازم است مواد با کیفیت و بدون نقص دریافت شود حتی اگر قیمت خرید این مواد کم ترین نباشد. بنابراین اگر کیفیت مطرح است هزینه مواد خام نباید فاکتور مهم و تعیین کننده ای در انتخاب فروشندگان مواد اولیه باشد. در حقیقت قیمتهای خرید بالاتر، در بلند مدت باعث بهبود کیفیت و صرفه جویی در هزینه ها می شود. برای نمونه اگر یک فروشنده مواد اولیه توانایی تحویل مواد با کیفیت را به طور دائمی تضمین کند از این بابت تولید کننده می تواند زمان صرف شده و به تناسب آن هزینه هایش در بازرسی و آزمایش مواد را کم کند. از طرفی بالا بردن کیفیت علاوه بر برقراری ارتباط با فروشندگان، با عامل مهمتری همچون استقرار موفق سیستم JIT نیز بستگی دارد.
به طور کلی، توابع هدفی که محققان در ادبیات تولید بهنگام به کار می برند را می توانیم به دو دسته اصلی تقسیم کنیم؛ مدل کلاسیک و مدل غیر کلاسیک. بعضی از محققان این تقسیم بندی را به این صورت توضیح داده اند که اگر در محیط JIT، حین انجام کارها، شکست در کارها مجاز نباشد(زمانبندی بدون قطعی کار) مدل مربوطه جزو مدلهای کلاسیک به حساب می آید و اگر شکست در کار مجاز باشد، این مدل از زمانبندی جزو مدلهای غیر کلاسیک به حساب می آید.
در زیر تعدادی از تابع هدف هایی که در محیط کلاسیک JIT، محققان از آن استفاده کرده اند، آورده شده است.
(۲-۱)
(۲-۲)
(۲-۳)
(۲-۴)
(۲-۵)
(۲-۶)
(۲-۷)
(۲-۸)
(۲-۹)
۲-۳- توالی ماشینﻫای موازی با معیار دیرکرد
۲-۳-۱- حداقل کل دیرکرد
مساله کلاسیک کل تاخیر ماشین های موازی^[۱۱](PMTP) میﺗواند بصورت زیر بیان شود:
“یک مجموعه کارهای مستقل باید روی تعدادی ماشین موازی مشابه در دسترس بطور پی در پی پردازش شود. هر ماشین تنها یک کار در یک زمان میﺗواند انجام دهد و هر کار میﺗواند روی یک ماشین پردازش شود. هر کار در شروع افق برنامه ریزی حاضر می باشد. هر کار زمان پردازش مجزا و موعد تحویل مجزا دارد. هدف, تعیین زمانبندی است که کل تاخیر را حداقل کند.”
بایلژ و همکاران[۲۳]مساله توالی مجموعهﺍی از کارهای مستقل با زمانﻫای آمادهﺳازی وابسته به توالی را روی مجموعهﺍی از ماشینﻫای موازی یکنواخت با هدف حداقل کردن کل دیرکرد در نظر میﮔیرند.در صورتیکه زمان تکمیل کارi با c_i نشان داده شود, میزان تاخیر کار i برابر باT_i=max{0,c_i-d_i}میﺑاشد. هدف, یافتن ترتیب پردازش کارها به گونه ای است که مجموع تاخیر کارها حداقل گردد. آنها یک رویکرد جستجوی ممنوع^[۱۲] (TS) برای مساله تعریف شده در بالا ارائه کردهﺍند. الگوریتم تعریف شده توسط آنها برای حل مساله داده شده توسط سیوریکایا و اولسوی [۲۴] به کار برده شده است (آنها برای مساله حداقل کردن کل هزینهﻫای زودکرد و دیرکرد یک الگوریتم ژنتیک^[۱۳](GA) با یک اپراتور تقاطعی جدید ارائه کردهﺍند). تفاوت در این است که در این مقاله وزن جریمه دیرکرد برابر با صفر در نظر گرفته شده است. نتایج نشان می دهد که الگوریتم ارائه شده توسط آنها به جوابﻫای بهتری نسبت به الگوریتم ژنتیک میﺭسد.
در بررسی کاو و همکاران [۲۵] به مساله انتخاب و زمانبندی همزمان ماشینﻫای موازی به منظور حداقل کردن هزینه نگهداری ماشین آلات و هزینه دیرکرد کارها اشاره شده است. مساله بصورت زیر میﺑاشد:
“N کار مستقل بایستی روی تعدادی ماشین موازی که از مجموعه ای از K ماشین موجود انتخاب می گردند، زمانبندی شوند. اگر ماشینی برای انجام کار انتخاب گردد، هزینه مربوط به نگهداری ماشین را بایستی پرداخت. یک کار می تواند بوسیله بیش از یکی از ماشینﻫای انتخابی انجام شود. زمان انجام کار روی ماشینﻫای مختلف متفاوت میﺑاشد. انقطاع کارها مجاز نمیﺑاشد. موعد تحویل کارها مشخص میﺑاشد. هدف, حداقل کردن هزینه نگهداری ماشین آلات و هزینه دیرکرد کارها میﺑاشد.”
آنها از یک مدل بهینه سازی ترکیبی استفاده کرده اند. از آنجا که مساله NP-hard می باشد, آنها یک روش ابتکاری برای حل مساله معرفی کردهﺍند. نتایج, بیانگر کارایی الگوریتم فوق میﺑاشند.
تاپان و همکاران [۲۶] مسائل کل دیرکرد و کل دیرکرد وزنی را بررسی کردهﺍند. در حالت تک ماشینه بیشترین تحقیقات انجام شده روی دو مساله کل (میانگین) دیرکرد و کل (میانگین) دیرکرد وزنی میﺑاشد. در این مقاله روشﻫای فراابتکاری و تکنیکﻫای بهینهﺳازی برای محیط تک ماشینه با تابع هدف دیرکرد بازنگری شدهﺍند. برخی تعمیمﻫای مسائل کل دیرکرد و کل دیرکرد وزنی برای محیطﻫای چند ماشینه نیز در این بررسی نشان داده شده است.
سینگ و زانگ [۲۷]مساله توالی ماشینﻫای موازی با کارهای قابل شکست^[۱۴] را در نظر گرفته اند. آنها فرض می کنند که کارها به زیر دستهﻫای پیوسته تقسیم شده و هر بخش از یک کار میﺗواند بطور همزمان روی هر یک از m ماشین موجود پردازش شود. Mماشینبمنظور پردازش n کار موجود میﺑاشند.
سینگ و زانگ [۲۷] به زیر دستهﻫا با عنوان بخشﻫای تقسیمﺷده میﻧگرند. این مساله تقسیم, در محاسبه سیستمﻫای کامپیوتری چند پردازشگر موازی نیز روی میﺩهد. در این مقاله ابتدا چند مثال ساده ارائه گردیده که بصورت چند جملهﺍی قابل حل هستند. سپس یک حل ابتکاری ML به همراه تحلیل بدترین حالت آن برای مساله P/Split/c_max با زمانﻫای آمادهﺳازی مستقل معرفی شده است.
سو [۲۸] مسئله زمان بندی ماشین های موازی یکسان را مورد بررسی قرار داده که در آن هدف کمینه کردن (E+T)/ می باشد.آنها یم مدل برنامه ریزی عدد صحیح باینری ساده و موثر برای حلوp||(E+T)/توسعه دادند.
عزیزقلو و کیرکا [۲۹] مساله زمانبندی کارها روی ماشینﻫای موازی مشابه را به منظور حداقل کردن کل دیرکرد در نظر میﮔیرند. مساله شامل زمانبندی n کار با زمان های پردازش p₁,…,p_nروی m ماشین موازی مشابه میﺑاشد. همه کارها در زمان صفر آماده پردازش میﺑاشند. بریدگی برای کارها مجاز نمیﺑاشد. ماشینﻫا بطور پیوسته در دسترس بوده و هر کار باید به یک ماشین تخصیص یابد. کار j موعد تحویلd_j را دارد. آنها مدلی شرح دادهﺍند که دو ویژگی را به منظور ایجاد یک زمانبندی پیچیده ترکیب میﮐند. یکی مفهوم پردازش موازی است که موضوع تخصیص منبع را ترقی میﺩهد. دیگری, صحت زمانبندی از طریق مقیاس کل هزینه دیرکرد است. این دو ویژگی در عمل از عناصر اساسی بسیاری از مسائل زمانبندی میﺑاشند لیکن ادبیاتی که این دو ویژگی را بطور همزمان در نظر بگیرد, بسیار کمیاب میﺑاشد. آنها خصوصیاتی را بیان میﮐنند که ساختار یک زمانبندی بهینه را توصیف میﮐند. سپس یک الگوریتم شاخه و حد معرفی کردهﺍند که این خصوصیات را با یک رویه حد پایین مناسب ترکیب میﮐند. آنها درمیﻳابند که راه حلﻫای بهینه میﺗواند در زمانی معقول برای مسائل تا ۱۵ کار بدست آید. بعلاوه آنها بسط مدل خود به ماشینﻫای موازی یکنواخت را نیز در نظر میﮔیرند.
لاموس و همکاران [۳۰] مسأله زمانبندی ماشین های موازی با زمان آماده سازی و محدودیت زمانی برای انجام کارها را مورد بررسی قرار دادند. آنها از روش تبرید شبیه سازی شده^[۱۵] به منظور کمینه سازی کل دیر کردها استفاده کردند.
یالوی و چو [۳۱] یک روش دقیق برای حل مساله ماشینﻫای موازی یکسان با تابع هدف کل دیر کرد ارائه دادهﺍند. مساله بصورت زیر میﺑاشد:
” مجموعه ای از N کار بایستی بدون انقطاع روی M ماشین موازی مشابه زمانبندی شوند. هر ماشین در یک زمان حداکثر یک کار را میﺗواند پردازش کند. کارها در زمان صفر در دسترس هستند. هر کار i یک زمان انجام p_i و یک موعد تحویل d_i دارد. کارiدر صورتی دیرکرد دارد که زمان تکمیل آن بیش از موعد تحویلش باشد. هدف, تعیین زمانبندی است که کل دیرکرد کارها را حداقل کند.”
آنها از یک الگوریتم شاخه و کران به منظور حل مساله بالا استفاده کردهﺍند. به منظور هرس کردن درخت جستجو،آنها چند خاصیت را اثبات کرده و به کمک این خواص حد بالا و پایین مناسبی برای مساله یافتهﺍند. این الگوریتم روی یک مجموعهﺍی از مسائل ایجاد شده بصورت تصادفی با اندازه متوسط آزمایش شده است. نتایج کامپیوتری نشان دادهﺍند که این الگوریتم برای مسائلی با ۳۰ کار و دو ماشین در زمان محاسباتی معقولی به جواب بهینه میﺭسد. این الگوریتم کاراتر از روشﻫای موجود برای حل این مساله عمل میﮐند.
مسئله کمینه سازی کل دیرکردها در ماشین های موازی توسط بیسکاپ و همکاران [۳۲] مورد مطالعه قرار گرفت. به دلیل Nphard بودن مسأله یک رویکرد فراابتکاری جدید برای مسأله پیشنهاد شد، که نتایج محاسبات انجام شده نشان داد الگوریتم پیشنهادی برای حل مسأله بسیار موثر است.
۲-۳-۲- حداقل کل دیرکرد وزنی:
پارک و همکاران [۳۳] مساله زیر را در نظر گرفتهﺍند:
“n کار و m ماشین موازی در زمان صفر در دسترس هستند. کار j دارای زمان انجامp_j، وزنw_j و موعد تحویل d_j میﺑاشد. اگر کار k بعد از کار j انجام شود، زمان آمادهﺳازی وابسته به توالیs_jk نیاز میﺑاشد. C_jنشانﺩهنده زمان تکمیل کار j میﺑاشد. همچنین دیرکرد کار j با_j-d_j} T_j=max{0,c نمایش داده میﺷود. هدف, حداقل کردن مقدار  میﺑاشد.”
آنها مساله زمانبندی را تحت شرایطی بررسی کردهﺍند که مجموعهﺍی از کارها در یک صف منتظر میﺑاشند. بین اتمام یک کار و شروع کار بعد زمان آمادهﺳازی وجود دارد که وابسته به توالی میﺑاشد. هدف, یافتن توالی از کارها روی ماشینﻫا است که حاصلضرب دیرکرد در وزنﻫای داده شده را حداقل کند. وزن مربوط به کارهای مختلف متفاوت میﺑاشد. از آنجا که مساله مورد بررسی حتی برای تک ماشین NP-hard میﺑاشد, تعدادی روش ابتکاری به منظور یافتن توالی کارها روی ماشینﻫا با اهداف مختلف توسعه داده شدهﺍند. یک روش ابتکاری معروف برای مساله کل دیرکرد وزنی از قواعد توزیع امکانات استفاده کرده و سپس یک مقدار اولویت به هر کار تخصیص میﺩهد. اولویت یک کار میﺗواند بصورت تابعی از پارامترهای مربوط به آن کار از قبیل زمان انجام, موعد تحویل و وزن محاسبه گردد. دو قاعده EDD^[16] و WSPT^[17] سادهﺗرین قواعد بکار گرفته شده هستند. این دو قاعده در مسالهﻫای با شرایط خاص, جوابﻫای خوبی تولید نمیﮐنند. قواعدی که به منظور حل مساله کل دیرکرد وزنی استفاده گردیدهﺍند عبارتند از: ^[۱۸]COVERT،^[۱۹]ATC و^[۲۰]ATCS[33].