A={(1),(3,4),(2,5)} و B={(1,5),(3,4),(2)}

B A
۱۵ ۱۳ هدف۱
۳ ۵ هدف۲

شکل۲-۱:جدول لکزیکوگرافیک
برای توالی هایA,B اهداف را محاسبه می‌کنیم و می‌بینیم که با بهینه شدن یک هدف دیگری غیر ازمقدار بهینه خواهد بود که این می‌تواند دلیلی بر تناقض این دو هدف در مسئله مدنظر ما باشد.
بعد از نشان دادن تناقض بین دو هدف مذکور باید به دنبال بهینه‌سازی در لبه‌های پارتو باشیم یعنی باید به دنبال حداقل کردن زمان تکمیل آخرین کار به ازاء هر مقدار از حداکثر دیرکرد از کارها باشیم تا لبه‌ی پارتو بهینه را بدست آوریم.
جواب‌های بهینه‌ی پارتو جواب‌هایی‌اند که نمی‌توانند موجب بهبود یک هدف شوند مگر با بدتر کردن یکی از سایر اهداف واز آنجایی که هیچ جوابی نمی‌تواند هر ۲ هدف را بطور همزمان بهینه کند شخص باید به دنبال یک موازنه قابل‌قبول بین جواب‌ها باشد.
در ضمن ما از روشی به نام محدودیت‌اپسیلون [۲۳]برای یافتن حل‌های بهینه برای مثال‌هایی با اندازه‌های کوچک استفاده می‌کنیم در این روش مسئله را به زیرمسأله‌هایی تک‌هدفه با محدودیت سایراهداف تبدیل کرده و در چندبار اجرا به مجموعه‌ای از حل‌های نامغلوب بهینه دست پیدا خواهیم کرد.
و در این پایان‌نامه یک الگوریتم فراابتکاری دوهدفه با ساختار NSGA II را توسعه خواهیم داد که در این الگوریتم ویژگی‌های متمایز و اپراتورهایی کارا متناسب با مسأله تعریف خواهیم کرد تا جواب‌های نزدیک بهینه برای مسائلی با ابعاد بزرگ در زمان معقول بدست آوریم که در فصل های بعدی بطور مفصل درباره‌ی این الگوریتم ها بحث خواهیم کرد.
۲-۱۲٫مروری بر الگوریتم‌های ژنتیک چندهدفه[۲۴]
یکی از نقاط ضعف اصلی الگوریتم‌های ابتکاری گیر افتادن در نقاط بهینه‌ی محلی[۲۵] می‌باشد که به همین دلیل در سال‌های اخیر محققان بیشتر به سمت الگوریتم‌های فراابتکاری روی آوردند.
اصطلاح فراابتکاری برای اولین بار توسط فوسکا[۳۷] مطرح شد، که این الگوریتم‌ها معمولاً با یک حل اولیه یا جمعیتی از حل‌های اولیه شروع شده و با جستجو‌ی محلی در پی حرکت به سمت حل‌های بهتر می‌باشند. الگوریتم‌های فراابتکاری برخلاف رویکرد‌های جستجوی محلی اگر بهبود در حلها حاصل نشود الگوریتم متوقف نشده بلکه اجازه‌ی رفتن به سمت حل‌های بدتر را دارد تا از همگرایی زودرس به سمت جواب بهینه محلی جلوگیری کند.
الگوریتم‌های فراابتکاری با الهام از مفاهیم هوش مصنوعی و الگوریتم‌های تکاملی که ریشه در مفاهیم تکامل طبیعی دارند، حل مسائل رابه سمت حل بهینه کلی همگرا می‌کنند. برای جزئیات بیشتر از الگوریتم‌های فراابتکاری به[۳۵,۳۶,۳۹]مراجعه نمایید.
از آنجایی که الگوریتم فراابتکاری ما بر پایه‌ی الگوریتم ژنتیک استوار است ما مروری بر الگوریتم ژنتیک در بهینه‌سازی چندهدفه خواهیم داشت:
الگوریتم ژنتیک یک روش جستجو بر اساس نظریه وراثت ژنتیکی و فلسفه انتخاب اصلح در طبیعت داروینی بنا شده است. این الگوریتم با یک جمعیت تصادفی شروع به کار کرده و با عملگرهای تقاطع و جهش و یک اپراتور انتخاب مبنی بر تابع برازش از نسلی به نسل دیگر بهبود می‌یابد. الگوریتم‌های ژنتیک چندهدفه را می‌توان بر چند مبنا تقسیم‌بندی کرد.
۲-۱۲-۱٫ الگوریتم‌های ژنتیک چندهدفه مبتنی بر تابع ادغامی
در این دسته از الگوریتم‌های ژنتیک چندهدفه باید اهداف را در یک هدف ادغام کنیم از جمله روش ترکیب وزنی اهداف.
۲-۱۲-۲٫ الگوریتم‌های ژنتیک چندهدفه مبتنی بر جمعیت
از جمله الگوریتم هایی که در این دسته از الگوریتم‌های ژنتیک چندهدفه قرار می‌گیرند، الگوریتم VEGA می‌باشدکه توسط اسپرز ارائه شده است. در این نوع از الگوریتم ژنتیک، کل جمعیت M را به زیرجمعیت‌های تبدیل کرده که متناسب با تعداد اهدف‌(k)میباشد و در هر زیرجمعیت به اندازه‌ی M/K عضو ایجاد می‌کنیم و در نهایت روی ترکیب این زیرجمعیت‌ها عملگرهای تقاطع و جهش را اجرا می‌کنیم.
۲-۱۲-۳٫ الگوریتم‌های ژنتیک چندهدفه مبتنی بر پارتو
در این دسته از روش‌ها به چند طریق به بررسی رابطه‌ی مغلوب یا نامغلوب بودن حل‌ها جهت دسته‌بندی حل‌ها در لبه‌های پارتو پرداخته می‌شود لذا حل‌هایی که در لبه‌های پایین‌تر واقع می‌شوند از شایستگی بیشتر برای انتخاب برخوردارند از جمله‌ی این روش‌ها می‌توان به NSGA -NSGA II – NRGA و … اشاره کرد.[۲۴,۴۱,۵۰]
۲-۱۳٫دلایل انتخاب موضوع و روش‌های حل
با مروری بر مقالات گذشته در زمینه‌ی BPMSP ، ملاحظه کردیم که هیچ مدل ریاضی از طرف محققان برای این مسأله به‌همراه محدودیت‌های مدنظر ما در نظر گرفته نشده است.
بنابراین فقدان یک مدل جامع و کامل که بتواند بسیاری از مسائل دنیای واقع را در زمینه ی BPMSP تحت پوشش قرار بدهد احساس شده است به همین دلیل سعی ما بر این بوده تا بتوانیم تا حدودی این خلاء را پوشش دهیم البته باید این نکته را هم یادآوری کنیم که می‌توان پارامترهای دیگری هم به این مدل اضافه نمود تا مسأله بتواند محدودیت‌های بیشتری از دنیای پیرامون را پوشش دهد.
همچنین در بررسی رویکرد‌های حل مسأله BPMSP ملاحظه کردیم که اکثر محققان از روش‌های ابتکاری استفاده کرده‌اند و چند مورد هم الگوریتم‌ها فراابتکاری ارائه شده که در آن محدودیتها و فرضیات مسأله خیلی کمتربوده و بررسی به صورت تک‌هدفه انجام شده است.
۲-۱۴٫جمع‌بندی
در ابتدای این فصل مروری بر مباحث زمان‌بندی و مدل‌های آن به‌ویژه مدل‌های زمان‌بندی چندهدفه در محیط تک‌ماشینه اشاره کردیم و سپس سیستم‌های تولیدی با قابلیت پردازش دسته‌ای و مباحثی که در این سیستم‌های تولید مورد توجه‌اند را مورد بررسی قرار دادیم ودر ادامه مروری داشته‌ایم بر تحقیقات گذشته که در زمینه‌ی BPMSP انجام شده است و همچنین روش‌ها و الگوریتم‌هایی که محققان برای اینگونه مسائل پیشنهاد کرده‌اند را بررسی کردیم و از آنجایی که مسأله مدنظر ما جزء دسته مسائل Np-Hard به حساب می‌آید بیشتر تمرکز ادبیات موضوع ما روی ارائه رویکرد‌های تقریبی (ابتکاری و فراابتکاری) معطوف شده است.
ما نیز در این تحقیق جهت حل مسأله در ابعاد کوچک از روش محدودیت اپسیلون و در ابعاد واقعی از روش فراابتکاری با ساختار NSGA II استفاده می‌کنیم.
فصل سوم
مدل ریاضی پیشنهادی و
روش تحقیق
۳-۱٫مقدمه
باتوجه به اینکه بسیاری از مسائل بهینه سازی از جمله زمان بندی تک ماشینه درمحیط پردازش دسته ایNP-Hard میباشند لذاحل اینگونه مسائل در ابعاد بزرگ در زمان محاسباتی معقول غیرممکن است در نتیجه استفاده از الگوریتم های فراابتکاری برای حل تقریبی اینگونه مسائل ضروری است.
یکی ازپرکاربردترین الگوریتمهای فراابتکاری الگوریتم ژنتیک است که هم در بهینه سازی تک هدفه وهم چندهدفه بکار می رود.بطورکلی برای استفاده از هر الگوریتم فراابتکاری در بهینه سازی چندهدفه باید تغییراتی رادرتابع برازندگی الگوریتم اعمال کرد تا تمامی اهداف در بهینه سازی در نظرگرفته شوند.
در ابتدا به تعریف مدل ریاضیاتی مساله می پردازیم وسپس به معرفی ساختارواپراتورهای الگوریتم NSGAII پیشنهادی خواهیم پرداخت و در انتهای این فصل با بهره گرفتن از طراحی آزمایشات متنوع(به روش تجربی)به تنظیم پارامترهای موجود در الگوریتم NSGA II برای ابعادکوچک-متوسط-بزرگ مساله می پردازیم.
همانطوریکه در فصلهای گذشته اشاره شددر این تحقیق دو هدف بطور همزمان برای دستیابی به جوابهای بهینه مورد توجه قرار دارند:حداقل سازی زمان تکمیل آخرین دسته-حداقل سازی حداکثر دیرکردازموعدتحویل کارها.که هدف اول بدنبال کاهش نگرانی هایی از قبیل هزینه های فعالیت خط تولیدوموجودی درجریان ساخت و…میباشدوهدف دوم بدنبال کاهش نگرانی هایی از قبیل:از دست دادن حسن شهرت-جریمه های دیرکرد-نارضایتی مشتری و… است.
بنابراین تعریف کلی از مساله چندهدفه بصورت زیرخواهد بود:
Minimize
x
درواقعx یک حل شدنی ازفضای جواب است که نشان دهنده ی یک دسته بندی از کارهاوتوالی برای پردازش دسته هاروی تک ماشین مدنظراست.
ماباارائه ی روش هایی بدنبال بدست آوردن جوابهای بهینه ی نامغلوب(پارتو)هستیم تا بادر اختیار قرار دادن این مجموعه از حل ها نزد تصمیم گیرنده او را قادر به تصمیم گیری باتوجه به معیارهایش سازیم.
۳-۲٫مدل ریاضی پیشنهادی
در این بخش ابتدا مسئله ی مدنظر رابا مفروضاتش تعریف میکنیم وسپس یک مدل ریاضیاتی جدید با محدودیت های غیرخطی و متغییرهای عدد صحیح را نشان میدهیم.
۳-۲-۱٫نمادها-پارامترها-متغییرهای تصمیم گیری
نمادها:
شاخص کارها j=1,2,3,…,n
شاخص خانواده کارها i=1,2,3,…,m

جهت