کد آماده متلب الگوریتم های فرا ابتکاری  NRGA  و  NSGAII برای حل  مدل زمانبندی چندهدفه در کلاس ماشینهای موازی نامرتبط در محیط تولید بهنگام

فایل دانلودی شامل تمامی کدهای نوشته شده در نرم افزار متلب برای حل  مدل زمانبندی چندهدفه در کلاس ماشینهای موازی نامرتبط در محیط تولید بهنگام به دو  روش الگوریتم فرا ابتکاری  NRGA  و  NSGAII میباشد و آماده اجرا در نرم افزار متلب میباشد. همچنین فایل word مدل مورد نظر برای مدل زمانبندی چندهدفه در کلاس ماشینهای موازی نامرتبط در محیط تولید بهنگام نیز به صورت کامل همراه با مفروضات و اندیس ها و پارامتر های مدل و همچنین توضیحات کامل الگوریتم های پیشنهادی و نحوه عملکرد آنها نیز توضیح داده شده است

به قسمت کوتاهی از شرح مدل بکار رفته توجه فرمایید

توضیحات مدل حل شده در این فایل

در این تحقیق، مسأله‌ی زمانبندی ماشین‌های موازی نامرتبط مورد بررسی قرار می‌گیرد. یک مجموعه از  کار متمایز برروی مجموعه ­ای از m ماشین، ، که بصورت موازی کنار هم قرار گرفتند پردازش می­شوند بطوریکه هر کار تنها بر روی یک ماشین پردازش می­شود و هر ماشین در هر لحظه قادر به پردازش تنها یک کار می­باشد. زمان پردازش هر کار ممکن است روی ماشین‌های مختلف، متفاوت باشد. در واقع زمان پردازش کارها بر روی ماشین­ها نه تنها به نوع کار بلکه به نوع ماشین هم بستگی دارد و بین زمان­های پردازش کارها بر روی ماشین­های مختلف رابطه مشخصی وجود ندارد. زمان تنظیم وابسته به توالی کارها، بین کارها وجود دارد. هر کار متمایز از سایر کارها، زمان دسترسی و ضرایب هزینه‌ی مربوط به خود را دارد. هدف، زمانبندی این کارها روی m ماشین است به‌طوری‌که هزینه‌های مربوط به زودکرد و دیرکرد از یک طرف و مجموع زمان تکمیل کارها از طرف دیگر حداقل گردند(دو هدفه)

توضیحات مدل و الگوریتم های به کار رفته 

الگوریتم‌های ژنتیک II به دلیل پتانسیل بالای آن‌ها به عنوان یک رویکرد جدید به مسایل بهینه‌سازی چندهدفه که تحت عنوان روش‌های تکاملی یا بهینه‌سازی چندهدفه ژنتیک شناخته می‌شود، توجه خاصی شده است. ویژگی‌های ذاتی الگوریتم‌های ژنتیک بیانگر دلایل مناسب بودن جستجوی ژنتیک در مسایل بهینه‌سازی چندهدفه هستند. ویژگی‌های اصلی الگوریتم ژنتیک چند جهته بودن و جستجوی سراسری  با حفظ جمعیتی از حل‌های خوب از نسلی به نسل دیگر است. رویکرد نسل به نسل در زمان بررسی حل‌های پارتو مفید است.

الگوریتم ژنتیک رتبه‌بندی غیرمغلوب (NRGA)      

در سال ۲۰۰۸ یک الگوریتم تکاملی چند هدفه با نام الگوریتم ژنتیک مبتنی بر رتبه ­بندی نامغلوب­ها  (NRGA)  به طور موفقیت آمیزی توسط عمرالجدان و همکارانش برای بهینه­ سازی توابع غیر­محدب، غیر خطی و گسسته توسعه داده شد. آنها الگوریتم ­های چند هدفه­ای را که براساس مرتب کردن غیر مغلوب­ها کار می­کردند مورد بررسی قرار دادند. براساس مسائل موجود در رویکردهای قبلی، آنها رویکرد جدیدی را با ترکیب الگوریتم انتخاب چرخه رولت مبتنی بر رتبه ­بندی و الگوریتم رتبه­ بندی جمعیت براساس پارتو توسعه دادند. که الگوریتم ژنتیک رتبه ­بندی نا­مغلوب (NRGA) نامگذاری شد. در این ترکیب یک رتبه­بندی دو لایه­ای براساس انتخاب عملگر انتخاب چرخه رولت ارائه می­شود. که نسل جدید والد براساس انتخاب بهترین جواب­ها (باتوجه به برازش و گستردگی) به طور تصادفی انتخاب می­کند. این الگوریتم در اکثر موارد قادر به دستیابی به گستردگی بهتری از جواب­ها در مرز پارتو و همچنین همگرایی زودتر به مرز بهینه پارتو، در مقایسه با سایر الگوریتم­های تکاملی چند هدفه ­می­باشد

مفروضات مسأله

در مسئله ارائه شده در این تحقیق فرض­های زیر در نظر گرفته می­شوند:

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

کار مجازی نوع صفر مفروض است. این کار همواره در اولین موقعیت روی تمامی ماشین­ها پردازش می­شود. زمان پردازش این کار صفر منظور می­شود و شروع پردازش آن نیازی به انجام عملیات نصب ماشین ندارد.

• تابع هدف در سطر (3-1) مجموع هزینه­های زودکرد و دیرکرد را حداقل می­کند. در این فرمول مقادیر متغیرهای تصمیم­گیری و  برای کار نوع  به ترتیب از روابط زیر بدست می­آیند:
• تابع هدف در سطر (3-2) مجموع زمان‌های تکمیل را حداقل می‌نماید.
• محدودیت (3-3) موجب می­شود تا هر کار فقط روی یک ماشین انجام گیرد.
• محدودیت (3-4) اطمینان می­دهد هر کار بعد از یک کار دیگر انجام گیرد، اولین کار بعد از کار فرضی صفر است.
• محدودیت (3-5) نشان می­دهد که بعد از هر کار حداکثر یک کار وجود دارد.
• محدودیت(3-6) نشان می‌دهد که یک ماشین در صورتی می‌تواند کاری را انجام دهد که توانایی انجام آن کار را داشته باشد. همانطور که در بخش پارامترهای ورودی مدل بیان شد، اگر امکان پردازش کار نوع بر روی ماشین نوع  وجود داشته باشد، پارامتر  مقدار یک و در غیر این صورت مقدار صفر را می­گیرد. امکان پردازش کار نوع  بر روی ماشین نوع  با توجه به مجموعه پردازشی کار نوع یعنی  مشخص می­شود.  زیر­مجموعه­ای از مجموعه ماشین­هامی­باشد که  شامل ماشین­هایی می­باشد که می­توانند کار نوع  را پردازش کنند. به این ترتیب این محدودیت مدل را مقید می­سازد که برای تخصیص ماشین نوع  به کار نوع  و به تبع آن تخصیص مقدار یک به متغیر تصمیم­گیری ، مقدار  را که جزء پارامتر­های ورودی مدل می­باشد را نیز بررسی نماید و در صورتی این تخصیص صورت می پذیرد که که مقدار  نیز همانند یک باشد.
• محدودیت (3-7) نشان می‌دهد که دو کار در صورتی می‌توانند پشت هم انجام گیرند که روی یک ماشین انجام شوند.
• محدودیت‌های (3-8) تا (3-9) زمان شروع کارها را مشخص می­کنند.
• محدودیت (3-10) زمان تکمیل کارها را مشخص می‌نماید.
• محدودیت (3-11) زمان زودکرد و دیرکرد کارها را محاسبه می­نماید. در واقع این محدودیت بیانگر رابطه بین زمان­های تکمیل، زمان­های زودکرد، زمان­های دیرکرد و موعد تحویل کارها می­باشد و ارتباط تنگاتنگی با مقدار تابع هدف دارد. یکی از فرض های موجود در بخش مفروضات مدل مجاز بودن بیکاری ماشین­هاست. طبق این فرض و با در نظر گرفتن محدودیت ارائه شده در این قسمت، زمانی که پردازش یک کار بر روی یک ماشین به اتمام می­رسد می­توان ماشین را بیکار نگه داشت و از پردازش کارهای بعدی بر روی آن جلوگیری نمود مشروط بر اینکه بهبودی در مقدار تابع هدف حاصل شود. بیکار نگه داشتن یک ماشین موجب می­شود که زمان تکمیل کاری که پردازش آن قبل از آغاز زمان بیکاری به اتمام رسیده به اندازه زمان بیکاری افزایش یابد. در نتیجه زمان زودکرد یا دیرکرد آن کار و کارهای بعدی و به تبع آن مقدار تابع دستخوش تغییر می­شود. بدین ترتیب بیکاری اختیاری ماشین­ها می­تواند موجب بهبود تابع هدف مدل شود.
• محدودیت (3-12) بیان کننده‌ی باینری بودن متغیرهای تصمیم است.