کارها……………………………………………………….35

2-4-2- مسائل با تمرکز بر موعد تحویل یکسان برای کارها…………………………………………………39

2-4-2-1- موعد تحویل معلوم………………………………………………………………………………………39

2-4-2-2- موعد تحویل نامعلوم…………………………………………………………………………………….44

2-5 دسترسی محدود به ماشینها …………………………………………………………………………………………..45

2-6 جمع بندی ………………………………………………………………………………………………………………….45

فصل 3- ارائهمدل ریاضی…………………………………………………………………………….58-46

3-1- مقدمه………………………………………………………………………………………………………….47

3-2-تعریف مسئله………………………………………………………………………………………………….47

3-3- فرضیات مسئله……………………………………………………………………………………………….48

3-4- مدل ریاضی پیشنهادی………………………………………………………………………………………49

3-4-1- پارامترهای ورودی…………………………………………………………………………………….49

3-4-2- نمادها، تعاریف، پارامترها و متغیر های تصمیم…………………………………………………….50

3-4-3- مدل ریاضی…………………………………………………………………………………………….51

3-5 –اعتبار سنجیمدل……………………………………………………………………………………………53

3-6 –تئوری پیچیدگی و پیچیدگی مساله مورد نظر……………………………………………………………56

3-6- جمعﺑندی……………………………………………………………………………………………………..58

فصل 4- الگوریتم پیشنهادی نتایج محاسباتی…………………………………………………..110-59

4-1 مقدمه……………………………………………………………………………………………………………………………60

4-2 الگوریتم ژنتیک ……………………………………………………………………………………………………………..62

4-2-1 شمای کلی الگوریتم ژنتیک………………………………………………………………………………………….64

4-3) اجزای الگوریتم ژنتیک…………………………………………………………………………………………………66

4-3-1) کروموزوم………………………………………………………………………………………………………….66

4-3-2) جمعیت………………………………………………………………………………………………………………66

4-3-3) مقدار برازندگی……………………………………………………………………………………………………67

6-3-4) کدگذاری……………………………………………………………………………………………………………67

4-3-5) انتخاب……………………………………………………………………………………………………………….68

4-3-6) عملگر تقاطعی……………………………………………………………………………………………………..76

4-3-7) جهش………………………………………………………………………………………………………………….82

4-3-8) جابه جایی…………………………………………………………………………………………………………….83

4-3-8) قاعده توقف………………………………………………………………………………………………………..83

4-3 الگوریتم حرکت جمعی پرندگان ……………………………………………………………………………………..84

4-4 حرکت دسته جمعی ذرات ………………………………………………………………………………………………86

4-5 مفاهیم پایه الگوریتم…………………………………………………………………………………………………………88

4-6 رابطه بروز رسانی سرعت…………………………………………………………………………………………………..88

4-7 رابطه بروز رسانی موقعیت………………………………………………………………………………………………….92

4-8 گامهای الگوریتم……………………………………………………………………………………………………………..93

4-9 شبه کد الگوریتم……………………………………………………………………………………………………………….93

4-10)طراحی الگوریتم پیشنهادی………………………………………………………………………………………………94

4-10) تنطیمات پارامترها و شرایط اجرای الگوریتم ها……………………………………………………………………99

4‐11) ساختار مسائل…………………………………………………………………………………………………………………99

4‐12)مسائل با ابعاد کوچک و متوسط…………………………………………………………………………………………100

4-13) نتایج آزمایشات……………………………………………………………………………………………………………..100

4-14 مسائل با ابعاد بزرگ…………………………………………………………………………………………………………107

4-15 جمع بندی………………………………………………………………………………………………………………………109

فصل5- نتیجه گیری و پیشنهادات آتی……………………………………………………………..113-110

5-1) نتیجه گیری……………………………………………………………………………………………………………………..111

5-2) پیشنهادات آتی ………………………………………………………………………………………………………………..113

منابع……………………………………………………………………………………………………………………………………….115

 

 

فهرست جداول

جدول 1-1- تعدادی از معیارهای کارایی زمان بندی………………………………………………………………..4

جدول 3-1.موعد تحویل و وزنهای زود کرد و دیرکرد……………………………………………………………54

جدول 3-2 زمان پردازش کارها ………… ………………………………………………………………………………54

جدول3-3 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..54

جدول3-4 زمان آماده سازی کارها روی ماشین 2…………………………………………………………………..55

جدول3-4 زمان آماده سازی کارها روی ماشین 3…………………………………………………………………..55

جدول 3-5- محاسبه تعداد متغیرها و محدودیت ها ………………………………………………………………53

جدول4-1: انتخاب کروموزوم ها با استفاده از مدل چرخ رولت………………………………………………..72

جدول4-2: مشکلات ممکن در مدل چرخ رولت…………………………………………………………………..74

جدول4-3 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 5j2m………………100

جدول4-4 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..101

جدول4-5 زمان آماده سازی کارها روی ماشین 2……………………………………………………………………101

جدول4-6 نتایج مربوط به مسئله 5 کار و 2 ماشین به تفکیک روشها………………………………………101

جدول4-7 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 5j3m……………….102

جدول 4-8 زمان آماده سازی کارها روی ماشین 1………………………………………………………………….102

جدول 4-9 زمان آماده سازی کارها روی ماشین 2………………………………………………………………….102

جدول 4-10 زمان آماده سازی کارها روی ماشین 3………………………………………………………………..103

جدول 4-11 نتایج مربوط به مسئله 5 کار و 3 ماشین………………………………………………………………103

جدول4-12 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 8j2m……………….103

جدول4-13 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..104

جدول4-15 زمان آماده سازی کارها روی ماشین 2…………………………………………………………………..105

جدول 4-16 نتایج مسئله 8 کار و 2 ماشین به تفکیک روشها……………………………………………………..105

جدول4-17 وزن زود کرد و وزن دیر کرد و موعد تحویل و زمان پردازش برای 8 کارو3 ماشین …..105

جدول4-18 زمان آماده سازی کارها روی ماشین 1…………………………………………………………………..105

جدول4-19 زمان آماده سازی کارها روی ماشین 2 ………………………………………………………………….105

جدول4-20 زمان آماده سازی کارها روی ماشین 3 ………………………………………………………………….105

جدول 4-21 نتایج مسئله 8 کار و 3 ماشین به تفکیک روشها……………………………………………………..106

جدول 4-22 نتایج مسئله 10 کار و 3 ماشین………………………………………………………………………107

جدول 4-23 نتایج مسئله 50 کار و 10 ماشین……………………………………………………………………..108

جدول 4-24 نتایج مسئله 50 کار و 20 ماشین……………………………………………………………………..108

جدول 4-25 نتایج مسئله 60 کار و 10 ماشین…………………………………………………………………….108

جدول 4-26 نتایج مسئله 50 کار و 20 ماشین……………………………………………………………………..109

فهرست اشکال:

شکل4-1: چرخ رولت………………………………………………………………………………………………………..70

شکل4-2: نمونه ای از انتخاب در چرخ رولت…………………………………………………………………………71

شکل4-3: نمونه ای از عملگر تقاطع تک نقطه ای……………………………………………………………………..77

شکل4-4: نمونه ای از عملگر تقاطع دو نقطه ای برای آرایه 0-1………………………………………………..79

شکل4-5: نمونه ای از عملگر تقاطع دو نقطه ای برای آرایه ترتیبی………………………………………………79

شکل4-6: نمونه ای از عملگر تقاطع یکنواخت………………………………………………………………………..81

شکل4-7 : ساختار کروموزوم……………………………………………………………………………………………….95

شکل 4-8 : نحوه عملکرد عملگر تقاطع…………………………………………………………………………………97

شکل 4-9: نحوه عملکرد عملگر جهش………………………………………………………………………………….98

-1-مقدمه:

در جهان رقابتی حاضر، توالی و زمانبندی موثر ضرورتی برای بقا در فضای بازار است. زمانبندی ابزاری است که استفاده از منابع در دسترس را بهینه می کند.زمان همواره یک محدودیت اساسی بوده، بنابراین زمانبندی فعالیتها به منظور حداقل کردن این منبع محدود یک الزام است. زمانبندی و توالی عملیات یکی از مهم ترین مسائل برنامه ریزی تولید بوده و کاربردهای زیادی در واحدهای تولیدی و غیرتولیدی دارد.

عمل زمانبندی در یک سازمان از مدل ها و روش های ریاضی و یا روش های ابتکاری برای تخصیص منابع محدود به کارهای در حال جریان استفاده می کند. اهمیت توالی ماشین های موازی، با هدف متمرکز بر دیرکرد از آن جهت مورد توجه است که در محیط کسب و کار حاضر، رقابت شرکت های تولیدی از طریق قابلیت آنها برای پاسخگویی سریع به تغییرات سریع در زمینه تجارتی و تولید محصولات با کیفیت بالاتر و هزینه های کمتر تعیین می شود. شرکت های تولیدی در تلاش هستند تا این قابلیت ها را از طریق اتوماسیون و مفاهیم خلاق مانند تولید به موقع[1](JIT)، پاسخگوی سریع[2](QR)، تکنولوژی گروهی[3](GT)و مدیریت کیفیت جامع[4](TQM)بدست آورند[3].

این مفاهیم ( برای مثال JIT و GT ) به بسیاری از شرکت ها در بدست آوردن سود اقتصادی کمک کرده است. در سیسستم های JIT کار نباید نه زودتر و نه دیرتر تکمیل شود، که به مسائل زمانبندی با هزینه های زودکرد و دیرکرد و تخصیص موعدهای تحویل منجر می شود. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آنها یک مقیاس عملکرد بسیار مهم برای محیط های تولید متنوع است.

مسائل با تعیین موعد تحویل در 25 سال گذشته بعلت روشهای جدید مدیریت مانند مفاهیمJITمورد توجه بسیار قرار گرفته است.چنگ که کمک زیادی به مسائل زمانبندی و تخصیص موعد تحویل کرد بیان می کند که تکمیل یک کار زودتر از موعد تحویل به معنی تحمیل هزینه های نگهداری موجودی غیر ضروری است ، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به جریمه های قراردادی و از دست دادن اعتبار مشتری می شود[4].

بطور جالب توجه هدف مسئله حداقل دیرکرد و زودکرد[5](ET) کاملا با سیاست کنترل تولید JITمطابقت دارد.مسئله ماشین های موازی از دو دیدگاه تئوری و عملی دارای اهمیت می باشند. از دیدگاه تئوری به اینخاطر که تعمیمی از حالت تک ماشینه می باشد و از دیدگاه عملی به این جهت که در دنیای واقعی بسیارمعمول است مورد توجه قرار گرفته شده است.

مسئله به کارگیری ماشین های موازی[6] از آنجا مورد توجه است که اگر زمانبندی روی یک ماشین منجر به هزینه زیادی شود ممکن است در نظر گرفتن ماشینهای بیشتر سبب کاهش هزینه شود. ضمن این که مقدار دیرکرد یا زودکرد نیز می تواند با افزایش تعداد ماشین ها کاهش یابد. در این شرایط هزینه به کارگیری ماشین یا نگهداری ماشین اضافه می شود که با حل مسئله بهینه سازی می توان تعیین کرد چه ماشین هایی به کار گرفته شوند و کدام کارها با چه توالی روی این ماشین ها انجام شود.

در عمل، زمانبندی ها با استفاده از الگوریتم های زمانبندی یا قوانین بر پایه دانش ایجاد می شوند. الگوریتم های زمانبندی ، زمانبندی را توسعه می دهد که یک معیار اندازه گیری مانند حداقل کردن انحراف موعد تحویل، حداقل جریمه دیرکرد یا حداقل حداکثر دیرکرد را بهینه می کند.

در این فصل، ابتدا مروری بر انواع مسائل زمانبندی و تعریف بعضی مفاهیم اولیه زمانبندی پرداخته می شود، در ادامه به خصوصیات و مشخصات مسأله مورد بحث این تحقیق، پرداخته می شود. در پایان اهداف، ضرورت و متدولوژی تحقیق بیان شده است.

 

1-6- تعریف مسأله زمانبندی مربوط به تحقیق :

بیان مسأله:

زمانبندی ماشینهای موازی نامرتبط حالت عمومی مسائل کلاسیک زمانبندی ماشینهای موازیبه شمار می آید.در یک مسئله کلاسیک زمانبندی ماشینهای موازی،مجموعه ای از کارهای مستقل وجود دارد که هر کدام از آنها بر روی یکی از ماشینهای موازی یکسان موجود پردازش می شوند.در حالت کلی ماشینهای موازی به صورت نامرتبط در نظر گرفته می شوند به طوریکه زمان پردازش کار ها بر روی ماشین ها نه تنها به نوع کار بلکه به نوع ماشین نیز وابسته است.در این حالت پیکربندی ماشینها یکسان نیشت و رابطه مشخصی بین زمانهای پردازش کارها بر روی ماشینهای موازی مختلف وجود ندارد.

در این تحقیق مسئله زمانبندی ماشینهای موازی نامرتبط با در نظر گرفتن محدودیت های زمان نصب وابسته به توالی پردازش کاره و زمان دسترسی کارها با هدف کمینه سازی زمانهای زودکرد و دیرکرد وزنی کل بررسی می شود.یک مدل برنامه ریزی عدد صحیح برای مسئله پیشنهاد می شود.همچنین یک روش فراابتکاری برای حل آن ارائه می گردد.

نظام تولید بهنگام[7] تفکر و نگرشی نوین در اداره سازمانهای صنعتی است که با اصل تکنیکها و روشهای برخاسته از آن، حذف کامل و جامع اتلاف و افزایش بهره وری در تمامی فعالیتها اعم از داخل و خارج سازمان تعقیب می گردد.

تعاریف بسیاری توسط کارشناسان برای تولید بهنگام ارائه شده است، در زیر به تعدادی از این تعاریف اشاره شده است.

JIT یعنی :

• پافشاری بر کیفیت برتر انجام امور خرید و تولید و … دقیقا در زمان مقرر

• بهنگام بودن نظام، مستلزم بهنگام بودن همه اجزای آن است

• در کل JIT یعنی فقط به هنگام ” نه دیرتر نه زودتر”

در JIT هدف تولید بهنگام است، یعنی اگر مشتری و تولید کننده زمان تحویل کالا را در یک زمان معین توافق کنند، تولید کننده باید تولیدات خود را طوری برنامه ریزی کند که کالا را در حد امکان در زمان مناسب تولید و در زمان مقرر تعیین شده به دست مشتری برساند. اگر این دیرتر از زمان تحویل آماده شود، تولید کننده متحمل جریمه ای به عنوان تأخیر تولید خواهد شد که این جریمه امکان دارد به صورتهای مختلف نمود پیدا کند. همچنین اگر تولید کننده، کالا را زودتر از زمان تحویل، تولید کند، این کالا را باید تا زمان تحویل در انبار نگهداری کند لذا در این صورت نیز متحمل هزینه خواهد شد.

 

1-7- مفروضات مسئله :

1-زمان نصب وابسته به توالی هنگام تعویض کارها بر روی ماشینها وجود دارد

2-هر کدام از کارها تنها بر روی زیر مجموعه ای از مجموعه ماشینها می تواند پردازش شوند

3-تمامی کارها در ابتدای افق زمانبندی در دسترس نمی باشد به عبارتی پردازش کار نمی تواند قبل از زمان دسترسی آغاز شود

4-تمامی ماشینها به طور مستمر دسترس هستند و امکان خرابی ماشینها وجود ندارد

5-هر ماشین در هر لحظه قادر به پردازش تنها یک کار می باشد

6-هر کار در طول زمان پردازش خود تنها بر روی یک ماشین پردازش می شود

7-زمانهای پردازش،نصب،موعد تحویل و ضرایب هزینه زود کرد و دیر کرد زمانی معین می باشد

8-بیکاری ماشینها مجاز است

1-8- ضرورت انجام تحقیق :

با توجه به اهمیت روزافزون مسائل ماشین های موازی در نظر گرفتن معیارهای مختلف مورد توجه محققان این علم می باشد.

امروزه در اغلب کارخانجات تولیدی و شرکت های خدماتی تأمین به موقع سفارش مشتری یا خدمت رسانی به موقع حائز اهمیت است. هزینه های زودکرد و دیرکرد در این امور نه تنها مشتری را متضرر می گرداند بلکه به شرکت نیز هزینه وارد شده و علاوه بر آن اعتبار خود را نیز از نظر مشتری از دست می دهد. مسائل تخصیص موعد تحویل زمانی جنبه عملی دارد که یک شرکت یک موعد تحویل به مشتریان در طول مذاکرات فروش پیشنهاد می کند و یک قیمت تقلیل یافته (جریمه) برای زمانیکه موعد تحویل دور از موعد انتظار باشد پیشنهاد می کند.

هر چه موعدهای تحویل ثابت شده تر باشد احتمال اینکه محصول به موقع تحویل داده شود بیشتر است. به منظور نگهداشتن یک وجهه خوب در میان مشتریان بسیاری از شرکت ها برای حفظ موعدهای تحویل ایجاد شده، هزینه های نگهداری معقولی را متحمل می شوند .

تقریبا همه مقالاتی که هدف های زودکرد و دیرکرد را در نظر می گیرند فرض می کنند که زمان آماده سازی ناچیز و یا مستقل از توالی است و همه کارها در زمان صفر در دسترس هستند لیکن زمان در دسترس بودن کار و زمان آماده سازی وابسته به توالی برای برخی صنایع از قبیل سازندگان اتومبیل و صنعت شیمی بسیار مهم است.

با توجه به اهمیت زمان دسترسی و زمان آماده سازی وابسته به توالی در این پایان نامه زمان در دسترس بودن کار و زمان آماده سازی وابسته به توالی در نظر گرفته شده است.

یک مدل ترکیبی بهینه سازی برای این منظور ایجاد شده که از نوع مسائل NP Hard است. که برای مسائل با اندازه کوچک از روشهایی که حل بهینه را می دهند استفاده شده و برای مسائل با اندازه متوسط و بزرگ از یک روش فراابتکاری که جواب بهینه یا نزدیک به بهینه را در یک زمان کوتاهتر می دهد استفاده شده است .

1-8- جمعﺑندی:

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

2-1- مقدمه:

زمانبندی در اوایل قرن گذشته با مطالعات صورت گرفته توسط هنری گانت و سایر پیشگامان در کانون توجه قرار گرفت.با این وجود سالها به طول انجامید تا اولین تحقیقات در حوزه زمانبندی انتشار یابد.در سالهای آغازین دهه پنجاه میلادی مطالعاتی در زمینه توالی عملیات که انگیزه آنها از زمانبندی تولید ناشی می شد منجر به ارائه الگوریتمهای مهمی چون قاعده جانسون برای مسئله سیستم کارگاه جریانی ، قاعده زودتر موعد تحویل برای کمینه سازی زمان تاخیر بیشینه و قاعده کوتاه ترین زمان پردازش با هدف کمینه سازی زمان جریان میانگین شد.در طول دهه شصت با پدید آمدن مسائل پیچیده تر تعداد قابل ملاحظه ای از تحقیقات به روشهای دقیق چون برنامه ریزی خطی و برنامه ریزی پویا معطوف شد.پس از انتشار مقاله مشهور ریچارد کارپ]1[در زمینه نظریه پیچیدگی ،محققان دریافتند که الگوریتم دقیق در مدت زمان معقول قادر به یافتن جواب بهینه در مسائل پیچیده نیستند و در نتیجه در طول دهه هفتاد میلادی بخش عمده تحقیقات بر روی سلسله مراتب پیچیدگی مسائل زمانبندی متمرکز شد

اخیرا مطالعه در زمینه جریمه دیر کرد و زود کرد در مدلهای زمانبندی، بطور وسیعی مورد توجه محققان بوده است. تحقیق های گذشته بیشتر بر روی معیارهای منظم مانند حداکثر زمان تکمیل، حداکثر دیر کرد و یا میانگین دیر کرد، متمر کز بوده اند. ولی امروزه به دلیل جریمه های حاصل از زود کرد، این معیار نامنظم، نیز مورد توجه محققان علم زمانبندی قرار گرفته است. همه تولید کنندگان برای مقابله با فشارهای رقابتی بطور افزاینده ای خودشان را با عقیده JIT و حداقل هزینه موجودی، مطابقت می دهند که این مستلزم در نظر گرفتن زود کرد کارها می باشد. در واقع در JIT زود کرد کارها به اندازه دیر کرد آنها اهمیت دارد. گرچه فرض بر این است که موعد تحویل یک متغیر خارجی بوده و کنترل آن خارج از عهده مدیران است، ولی اهمیت تحویل در موعد به خوبی روشن است. کانوی[10]، برای اولین بار این نظریه را مطرح کرد که موعد تحویل قسمتی از مسأله زمانبندی است. از کسانی که در این زمینه مطالعه کردند می توان از وبستر و بیکر[11]، راگاتز و مابرت[12]، کریستی و کانت[13]، نام برد. مطالعات زیادی در زمینه مسائل زمانبندی مختلف با معیارهای دیر کرد و زود کرد (E/T) ، صورت گرفته است. وبستر، بیکر و جاگ[14]، مسأله تک ماشینه (E/T) را با در نظر گرفتن موعد تحویل یکسان و نامعین به عنوان یک متغیر تصمیم، برای دو حالت زمان های آماده سازی مستقل و وابسته به توالی با روش الگوریتم ژنتیک حل کرده اند. کریستوفر بک و فیلیپ رفالو[15]، یک روش ترکیبی با استفاده از برنامه ریزی خطی و برنامه ریزی مفید برای مسأله زمانبندی با معیار هزینه زود کرد و دیر کرد ارائه کردند. سوریا د.لیمان، شریکانت س.پالواکر و سانسرن دونگمی[16]، مسأله زمانبندی تک ماشینه با موعد تحویل محدود شده به یک فاصله و زمان پردازش قابل کنترل را ارائه کردند. آنها جریمه کلی که شامل جریمه های زود کرد، دیر کرد، زودترین موعد تحویل، طول فاصله مربوط به موعد تحویل و مقدار واقعی کاهش زمان پردازش می باشد را با یک روش ابتکاری کمینه می کنند.

ون-کیانگ زایو و چانگ لانلی[17]، به بررسی روشهای تقریبی برای تخصیص موعد تحویل مشترک به کارها و زمانبندی آنها در مسأله ماشین های موازی پرداختند. هدف، تخصیص موعد تحویل کارها می باشد، بطوریکه مجموع وزنی موعد تحویل، کل زود کرد و کل دیر کرد کمینه گردند.

زایو کینگ کی و زایان زو[18]، مسأله زمانبندی تک ماشینه با زمان پردازش احتمالی با توزیع نمایی و موعد تحویل احتمالی، با هدف کمینه کردن مجموع هزینه های وزنی دیر کرد و زود کرد را بررسی کرده اند. در این مسأله خرابی ماشین[1] جزو فرضها بوده و مسأله با روش برنامه ریزی پویا حل شده است.

محسن الحافی[19] مسأله زمان انتظار[2] بهینه را در سیستم های تولیدی جزء به جزء[3]، با معیار هزینه های زود کرد و دیر کرد را بررسی کرد. مسأله مذکور شامل N مرحله است که زمان انتظار پشت هر مرحله احتمالی است. هدف در اینجا پیدا کردن زمان های انتظار بهینه بوده، بطوریکه هزینه های دیر کرد و زود کرد کمینه شوند. سانجی رادها کریشنان و جزی ا.ونتورا[20]، مسأله زمانبندی ماشین های موازی با معیار هزینه زود کرد و دیر کرد با زمان های آماده سازی وابسته به توالی با رویکرد فراابتکاری پازپخت شبیه سازی شده حل کرده اند.

شریکانت س.پالواکر و سوریا د.لیمان[21]، مسأله زمانبندی با n کار که هر کدام شامل یک عملیات بر روی هر ماشین بوده را با معیار هزینه های دیر کرد و زود کرد بررسی کرده اند. در این مسأله شکستگی کار مجاز نبوده و پارامترهای موعد تحویل و زمان پردازش معین می باشند. هدف در اینجا تعیین تعداد ماشین ها می باشد، بطوریکه هزینه های زود کرد و دیر کرد کمینه گردد.

2-2- مروری بر رویکرد و اصول سیستم تولیدیJIT