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

s.t
fj ≤ ej j≠i j=1,2,…,k
xϵX
ej کران بالای jامین هدف است که در هر بار اجرای مدل تغییر داده می‌شود و در هر بار اجرا یک حل از حل‌های پارتو بدست خواهد آمد.
روش سلسله‌مراتبی:
ابتدا اهداف را رتبه‌بندی کرده وسپس با توجه به اولویت آنان به نوبت بهینه‌سازی انجام می‌شود.
برنامه‌ریزی آرمانی:
ابتدا برای هر حل یک حد مطلوب توسط تصمیم گیرنده در نظر گرفته می‌شود و محدودیت‌ها، سطوح رضایت تصمیم‌گیرنده را از اهداف بیان می‌کنند و ما به دنبال حلی هستیم که به بهترین شکل سایر اهداف از پیش ‌تعیین‌شده را ارضا کند.
ارزیابی مبتنی بر پارتو:
این روش بر خلاف بعضی از روش‌های قبلی نیاز به هیچ‌گونه اطلاعات از پیش ‌تعیین ‌شده‌ای از سوی تصمیم‌گیرنده ندارد و مجموعه‌ای از حل‌ها را ایجاد می‌کند پس از رتبه‌بندی آنان می‌توان به مجموعه‌ی حل‌های نامغلوب مؤثر پی برد از دیگر مزایای این روش رسیدن به چندین حل مؤثر در یک بار اجرا می‌توان اشاره کرد.
۱-۴٫تعریف مسأله زمان‌بندی مربوط به تحقیق
در این تحقیق ما به دنبال زمان‌بندی یک ماشین با قابلیت پردازش دسته‌ای[۴] کارها هستیم که کارها متعلق به خانواده‌های ناسازگار[۵] است و کارهای هر خانواده دارای زمان پردازش یکسان است و ماشین فقط قابلیت پردازش همزمان کارهای هم‌خانواده را دارد. اهدافی که در این مسأله دنبال می‌کنیم حداقل‌سازی زمان تکمیل آخرین دسته[۶] از کارها و حداقل‌سازی حداکثر دیرکرد از موعد تحویل کارها[۷] به‌صورت همزمان می‌باشد. این دو هدف به طور واضح میتوانندبا هم در تناقض‌ باشند زیرا هدف اول سعی در پردازش زودتر تمامی کارها دارد در حالی ‌که ارضای بهینه‌ی این هدف ممکن است موجب افزایش دیرکرد از موعد تحویل بعضی از کارها شود. [۷]
اگرچه زمان‌بندی تولید دسته‌ای با اهداف و محدودیت‌ها مسئله‌ی ما به‌طور مجزا مورد مطالعه‌ی فراوان در گذشته قرار گرفته است ولی در هیچ یک از مطالعات قبلی این مسئله به صورت چندهدفه و با محدودیت‌های:خانواده‌های ناسازگار از کارها-زمان دسترسی کارها-اندازه ی سفارش مختلف از کارهاو زمان آماده‌سازی بین خانواده‌ها و …. به‌طور همزمان و یکجا مورد مطالعه و بررسی قرار نگرفته است.
به همین دلیل ما بر آن شدیم تا با درنظرگیری تمامی محدودیت‌های فوق به‌صورت یکجاوهمزمان مسئله‌ی زمان‌بندی تک ماشین با قابلیت پردازش دسته‌ای را مورد مطالعه قرار دهیم واین مسئله را تا جای ممکن به دنیای واقع نزدیک‌تر کنیم.
به عبارت دیگر مسئله‌ای که ما در نظر می‌گیریم را می‌توان به‌صورت زیر بیان نمود:
N کار مستقل باید روی یک ماشین با ظرفیت B بصورت دسته‌ای پردازش شوند بطوریکه این کارها متعلق به m خانواده هستند که کارهای متعلق به هر خانواده دارای زمان پردازش یکسان می‌باشند واین ماشین فقط قابلیت پردازش همزمان کارهای هم‌خانواده را دارد. فرض بر این است که هر کار دارای یک زمان دسترسی دلخواه و یک موعد تحویل معین می‌باشد وهم‌چنین برای هر کار یک میزان سفارش (تعداد سفارش) تعیین شده است که برای کارهای مختلف میتواندمتفاوت ‌باشد.
خرابی در ماشین مجاز نمی‌باشد و پیوسته ماشین در دسترس است و یک کار قابلیت شکست روی تعداد سفارشات در دسته‌ های مختلف را دارد و زمان آماده‌سازی ماشین برای پردازش دسته‌ هایی از خانواده‌های مختلف تعریف می‌شود.
اهدافی که ما در این مسئله دنبال می‌کنیم بگونه‌ای هستند که ماشین نیاز به زمان بیکاری غیراجباری ندارد(یعنی در این مساله )
در صورتی ماشین بیکار است که کار هنوز وارد سیستم نشده باشد.(بیکاری اجباری)و این ماشین پردازش یک دسته را بدون وقفه یا شکست و به‌صورت پیوسته انجام می‌دهد یعنی زمان تکمیل تمامی کارهای متعلق به یک دسته با هم برابر می‌باشند.
۱-۵٫روش حل مسأله
مسئله‌ی زمان‌بندی پردازش دسته‌ای بدون تمامی محدودیت‌های ذکر‌شده در سایز واقعی جزء دسته مسائل NP-Hard قرار دارد.[۸,۹] یعنی با افزایش اندازه‌ی مسأله، زمان حل بصورت نمایی افزایش می‌یابد. بنابراین با بکارگیری یک الگوریتم دقیق شمارشی نمی‌توان در یک زمان معقول حل‌های بهینه را برای ابعاد بزرگ مسئله بدست آورد. از آنجایی که مسئله ما با تمامی مفروضات بیان شده و برای بررسی همزمان دو هدف با پیچیدگی خیلی بیشتری نسبت به مطالعات قبلی روبرو است، لذا در دسته‌ی مسائل NP-Hard جای خواهد گرفت. از این رو برای بدست آوردن جواب‌های بهینه و یا نزدیک به بهینه از روش فراابتکاری استفاده خواهیم کرد.
الگوریتم‌های فراابتکاری که برای بهینه‌سازی چندهدفه استفاده می‌شوند منجر به تولید مجموعه‌ای از حل‌های کارا در یک بار اجرا خواهند بود از جمله جدیدترین و کاراترین الگوریتم‌های تکاملی مبنی به دسته‌بندی نامغلوب الگوریتم NSGA- NSGA II- NRGA و … می‌باشند. که ما در این تحقیق از یک نوع ساختار الگوریتم ژنتیک مبتنی بر دسته‌بندی نامغلوب بنام NSGA II استفاده خواهیم کرد و معیار‌های عملکرد آنرا در ابعاد بزرگ و متوسط و کوچک با روش‌های دقیق شمارشی از جمله روش اپسیلون-محدودیت مقایسه می‌کنیم.
در الگوریتم NSGA II مد نظر ما دو نوع رتبه‌بندی خواهیم داشت، اول براساس رتبه‌بندی نامغلوب حل‌ها و دومی در هر مرز از حل‌های نامغلوب، رتبه‌بندی برحسب فاصله‌ی ازدحامی[۸] انجام می‌شود. همچنین کارایی الگوریتم‌ها همانند سایر الگوریتم‌های تکاملی به عواملی نظیر: چگونگی ایجاد جمعیت اولیه خوب از حل‌ها- نحوه بکارگیری اپراتورهای مناسب برای ایجاد نسل های بعدی- ونحوه‌ی انتخاب حل‌های خوب وابسته می‌باشد.
از آنجایی که مسئله مورد بررسی دارای دو هدف متناقض می باشد خروجی الگوریتم شامل مجموعه‌ای از حل‌هایی است که در لبه‌های نامغلوب دسته‌بندی شده‌اند که اولین لبه‌ی پارتو از حل‌ها- به عنوان پارتوی بهینه از حل‌ها در اختیار تصمیم‌گیرنده قرار خواهد گرفت تا تصمیم‌گیرنده براساس معیار و ترجیهات خود بهترین حل را از میان حل‌های پاتوی بهینه انتخاب کند.
۱-۶٫ضرورت انجام تحقیق
از آنجایی که عملکرد بسیاری از سیستم‌های تولیدی به وسیله‌ی کیفیت زمان‌بندی گلوگاه‌هایی که شامل یک ماشین است تعیین خواهد شد، مطالعه در زمینه‌ی زمان‌بندی تک‌ماشینه از گذشته تا به حال مورد توجه فراوان بوده است و از طرفی دیگر وجود یک ماشین با قابلیت پردازش دسته‌ای از کارها در ایستگاه گلوگاهی خط تولید، بسیاری از مشکلات خط تولید که از ایستگاه گلوگاه[۹] ناشی می‌شود را می‌تواند بهبود دهد. از طرفی دیگر بررسی مسائل زمان‌بندی تک‌ماشینه در هر حالتی که باشد به‌عنوان اساس و شروع مسیر برای بسط به مدل‌های پیچیده‌تر خواهد بودبعبارت دیگرمسائل زمان‌بندی تک‌ماشینه در عین حال که از ساده‌ترین مدل‌های زمان‌بندی می‌باشد به‌عنوان مبنا و اساس کار برای ایجاد قواعدوضوابط جدید در سایر مدل‌های پیچیده‌تر به حساب می‌آید یعنی اگر بخواهیم محدودیت و راهکارهای جدیدی را بر مسائل زمان‌بندی اضافه کنیم آنرا ابتدا در مورد مسائل تک‌ماشینه تحلیل می‌کنیم و سپس می‌توانیم برای مدل‌های چند ماشینه بسط دهیم.
بهمین دلیل مساله تک‌ماشینه‌ی مورد بررسی ما، برای کارهای آتی مربوط به سایر مدل‌ها پیچیده‌تر در زمینه‌ی تولید دسته‌ای از ضرورت و اهمیت زیادی برخوردار خواهد بود. درضمن به دلیل کاربرد زیاد پردازش دسته‌ای در صنعت امروزی، زمان‌بندی روی چنین ماشین‌آلاتی از اهمیت ویژه‌ای برخوردار است. از طرفی محدودیت‌هایی از قبیل در دسترس نبودن تمامی کارها از لحظه‌ی صفر – قابلیت پردازش کارهای هم‌خانواده به‌طور همزمان-اندازه سفارشات مختلف برای کارها و قابلیت تفکیک یک کار روی میزان سفارش از جمله ویژگی‌هایی است که در این تحقیق به این مدل اضافه شده است و مسأله را به دنیای واقع نزدیک‌تر کرده است و این در حالی است که بررسی چنین مسائلی بااهداف متناقضی نظیر Cmax و Tmax بطور همزمان بر زیبایی و ضرورت تحقیق می‌افزاید زیرا بررسی چند معیاره ی مسائل برای کسب منافع همزمان (در این تحقیق,رضایتمندی بیشتر مشتری- هزینه‌ی کمتر خط تولید) در بازار رقابتی امروزی برای تولید‌کنندگان از اهمیت بالایی برخوردار است.
همچنین امروزه با افزایش بکارگیری کامپیوتر و توسعه‌ی الگوریتم‌های فراابتکاری زمینه‌ی مناسبی برای حل مسائل NP-Hard در ابعاد واقعی فراهم شده است از این‌رو در زمینه‌ی زمان‌بندی تولید دسته‌ای که موضوع تحقیق ما بوده و جزء مسائل NP-Hard به حساب می‌آید توسعه‌ی چنین الگوریتم‌هایی ضروری به نظر می‌رسد.
۱-۷٫اهداف تحقیق
– بررسی خلا موجود در مساله زمان بندی پردازش دسته ای با توجه به پیشینه تحقیق.
-رفع مشکلات ناشی ازایستگاه های گلوگاهی بابکارگیری سیستمهای پردازش دسته ای.
– نزدیکتر کردن مسائل زمان‌بندی‌ سیستم‌های تولید دسته‌ای تک‌ماشینه به دنیای واقعی.
– توسعه‌ی الگوریتم فراابتکاری NSGAII برای مسأله مدنظر.
– اثبات کارایی الگوریتم پیشنهادی نسبت به روش‌های دقیق شمارشی با توجه به معیارهای عملکرد تعریف شده.
۱-۸٫جمع‌بندی
یکی از مسائل موجود در زمینه زمانبندی مدل های تک ماشینه مساله زمان بندی کارها در سیستم های پردازش دسته ای است.ار آنجاییکه ثابت شده حالت کلی این مساله با فرضیات مفروض در کلاس مسائل NP-hard قرار دارد نمی توان در ابعاد واقعی مساله به جواب بهینه در زمان محاسباتی معقول رسید.بنابراین استفاده از رویکردهای فرا ابتکاری در این زمینه ضروری است.از آنجاییکه مساله مد نظر ما به صورت دو هدفه بررسی می شود به پیچیدگی آن افزوده خواهد شد.لذا ما برای حل مساله الگوریتم فرا ابتکاری با ساختار NSGA II را توسعه خواهیم داد.
فصل دوم
مروری بر ادبیات
۲-۱٫مقدمه
در این پایان‌نامه، مسأله‌ی زمان‌بندی دو هدفه با اهداف کمینه سازی زمان تکمیل آخرین کار وکمینه سازی حداکثر دیرکرد کارهاازموعد تحویل روی یک ماشین با قابلیت پردازش بیش از یک کار در هر لحظه از زمان, در حالتی که کارها دارای زمان دسترسی متفاوت‌اند و هر کار دارای اندازه‌ی متفاوتی از سفارش است و کارهای متعلق به خانواده‌های مختلفی‌اند که فقط کارهای هم‌خانواده قابلیت پردازش همزمان توسط ماشین را دارند در ضمن از جمله محدودیت‌های دیگر مسئله وجود زمان آماده‌سازی[۱۰] بین دسته‌ هایی متعلق به خانواده‌های متفاوت و قابلیت تفکیک یک کار روی اندازه‌ی سفارش[۱۱] آن می‌باشد یعنی مقداری از سفارش یک کار می‌تواند در یک دسته انجام شود و بقیه سفارش همان کار در دسته‌ های دیگر پردازش شود.
مسائل زمان‌بندی تولید در طی دهه‌ های گذشته تکامل چشم‌گیری داشته است که شامل: ارائه‌ قواعد ساده تا الگوریتم‌های پیچیده نظیر: شاخه حد[۱۲]– برنامه‌ریزی پویا[۱۳]– روش‌های ابتکاری و فراابتکاری می‌باشند.
روش‌های حل مسائل زمان‌بندی تک ماشینه در محیط‌های پردازش دسته‌ای (BPM) را به ۲ دسته‌ی کلی می‌توان تقسیم کرد:
۱- روش‌های دقیق: که تکنیک‌های حلی هستند که برای یافتن حل بهینه بکار می‌روند و معمولاً برای مسائلی با ابعاد کوچک کاربرد‌ی‌اند.
نظیر: الگوریتم‌های شاخه و کران- برنامه‌ریزی پویا
۲- روش‌های تقریبی: این روش‌ها قادر به حل مسائل پیچیده و بزرگ در زمان معقول با کیفیت حل خوب و یا نزدیک بهینه می‌باشند.
در ادامه این فصل ابتدامروری برانواع مسائل زمان‌بندی خواهیم داشت،سپس یک طبقه‌بندی از مسائل تک ماشینه با قابلیت پردازش دسته ای را ارائه می‌دهیم و با بکارگیری علائم اختصاری برای هر طبقه به ساده‌سازی نمایش آنان می‌پردازیم و بعد از مروری از کارهای انجام شده در دهه‌ های اخیر در این زمینه و شرح رویه‌ها و الگوریتم‌های بکار رفته برای حل اینگونه مسائل به خلا موجود پی خواهیم بردوسپس یک کلی‌نگری به ساختار الگوریتم‌های ژنتیک چندهدفه خواهیم داشت که اساس کار الگوریتم تحقیق ما مبتنی بر آن خواهد بود.
۲-۲٫ انواع مسائل زمان‌بندی
مسائل زمان‌بندی را می‌توان به شیوه‌های مختلف دسته‌بندی کرد از جمله:
تکماشینه یا چندماشینه-ایستا یا پویا – قطعی یا احتمالی- تک محصول یا چندمحصولی- تک‌پردازش یا پردازش به صورت دسته‌ای و ….
۲-۲-۱٫ زمان‌بندی تک ماشینه
دراین نوع زمان‌بندی فقط یک ماشین به‌عنوان سرویس‌دهنده در اختیار است که باید مجموعه‌ای از کارها توسط آن ماشین پردازش شوند.
به‌عبارت دیگر، ماشین در هر لحظه از زمان فقط قادر است یک کار را پردازش کند. این مدل از زمان‌بندی که در مقایسه با سایر مدل‌ها ساده‌تر است مبنایی برای کار سایر مدل‌ها می‌باشد و نتایج ناشی از آن قابل بسط برای سایر مدل‌های پیچیده‌تر خواهد بود.
۲-۲-۲٫زمان‌بندی ماشین‌های ‌موازی[۱۴]
در این مدل تعدادی ماشین‌های مشابه در اختیار می‌باشند یعنی هرکار قادر به پردازش توسط هر کدام از این ماشین‌ها است. این سیستم، از نظر ویژگی ماشین‌ها نظیر:سرعت پردازش- کیفیت محصولات تولیدی- هزینه‌ی تولید به دو دسته‌ی ماشین‌های موازی یکسان و یا متفاوت تقسیم می‌شوند.
۲-۲-۳٫جریان کارگاهی[۱۵]
در این سیستم، کارها روی چند ماشین در یک توالی یکسان پردازش می‌شوند ولی زمان پردازش هر کار روی هر ماشین ممکن است متفاوت با زمان سایر کارها روی همان ماشین باشند.
۲-۲-۴٫ جریان کارگاهی مختلط[۱۶]