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

2-2-2.زمان‌بندی ماشین‌های ‌موازی14
در این مدل تعدادی ماشین‌های مشابه در اختیار می‌باشند یعنی هرکار قادر به پردازش توسط هر کدام از این ماشین‌ها است. این سیستم، از نظر ویژگی ماشین‌ها نظیر:سرعت پردازش- کیفیت محصولات تولیدی- هزینه‌ی تولید به دو دسته‌ی ماشین‌های موازی یکسان و یا متفاوت تقسیم می‌شوند.
2-2-3.جریان کارگاهی15
در این سیستم، کارها روی چند ماشین در یک توالی یکسان پردازش می‌شوند ولی زمان پردازش هر کار روی هر ماشین ممکن است متفاوت با زمان سایر کارها روی همان ماشین باشند.
2-2-4. جریان کارگاهی مختلط16
این سیستم حالت تعمیم‌یافته‌ی جریان کارگاهی است یعنی در این سیستیم دارای تعدادی کارگاه‌های متوالی هستیم که در بعضی ازاین ایستگاه‌ها تعدادی ماشین موازی یکسان وجود دارند که در هر کارگاه یک کار باید توسط حداکثر یک ماشین پردازش شود.
2-2-5.کار کارگاهی17
در این سیستیم‌ها تعدادی ماشین متفاوت در یک سالن وجود دارند که هرکار ممکن است به یک ماشین یا به تمام ماشین‌ها در یک توالی مربوط به خود نیاز داشته باشد.
2-2-6.سیستیم کارگاهی باز18
این سیستیم شبیه به سیستیم کار کارگاهی می‌باشد ولی با این تفاوت که توالی مراحل هر محصول از پیش تعیین شده نمی باشد. یعنی هیچ تقدم و تأخری برای عملیات پردازش یک محصول تعریف نشده و معمولاً هدف در این سیستیم تولیدی حداقل‌سازی زمان اتمام کلیه‌ی کارهاست.
2-2-7.پردازش دسته‌ای19
در این سیستیم یک ماشین قادر به پردازش مجموعه‌ای از کارها به‌صورت همزمان می‌باشد یعنی در یک لحظه از زمان ماشین قادر است بیش از یک کار را پردازش کند که معمولاً در این سیستیم ماشین دارای یک ظرفیت محدود برای پردازش همزمان کارها می‌باشد و زمان پردازش هر دسته از کارها برابر است با بزرگ‌ترین زمان پردازش کارهای درون آن است. که این مدل از زمان‌بندی، موضوع بحث ما در این پایان نامه خواهد بود که مهمترین اهدافی که در این سیستم‌های تولیدی دنبال می‌شوند عبارتند از:
حداقل‌سازی زمان تکمیل آخرین کار و بهره‌وری بیشتر ظرفیت از خط تولید.
2-2-8.سیستم کارگاهی وابسته
که خود به دو دسته تقسیم می‌شوند:
2-2-8-1.وابستگی به منابع
وابستگی در این سیستم‌ها در ارتباط با منابع موجود است از قبیل: خرابی ماشین‌آلات- تعمیرات و نگهداری- بیماری اپراتور- تأخیر در ورود یا کمبود مواد اولیه و …
2-2-8-2.وابستگی به کارها
وابستگی در این سیستم مرتبط با کارهای ورودی به سیستم از جمله: تغییر در موعد تحویل- تغییر در زمان پردازش- تغییر در اولویت کار- تغییر در زمان ورودی و …
2-3.انواع مسائل زمان‌بندی از لحاظ زمان آماده‌سازی
یکی دیگر از مفاهیم مهم وتأثیر گذار در زمینه‌ی زمان‌بندی، زمان آماده‌سازی ماشین است. زمان آماده‌سازی عبارت است از مدت زمان لازم برای تنظیم و آماده کردن یک ماشین جهت پردازش از یک کار به کار دیگر. در این زمان ماشین عملاً متوقف است و قادر به انجام هیچ کاری نمی‌باشد.
زمان آماده‌سازی انواع مختلفی دارد از جمله زمان آماده‌سازی وابسته به توالی کارها و یا زمان آماده سازی وابسته به ماشین و گاهی اوقات زمان آماده‌سازی قادر به چشم پوشی است یعنی در خود زمان پردازش گنجانده می شود.
زمان آماده‌سازی درنظر گرفته شده در این تحقیق با توجه به شباهت میان کارها و دسته‌بندی کردن کارها در خانواده‌های مختلف تعریف می‌شود یعنی بین پردازش کارهای متعلق به خانواده‌های یکسان زمان آماده‌سازی ناچیز است و قابل چشم‌پوشی است ولی در مقابل بین پردازش کارهای متعلق به دو خانواده‌ی مختلف زمان آماده‌سازی قابل ملاحظه‌ای وجود خواهد داشت.
در چنین مدل‌هایی سعی در این است که کارهای هم خانواده تا جای ممکن به‌صورت متوالی انجام شوند تا حداقل زمان آماده‌سازی را داشته باشیم و بتوانیم از ماشین حداکثر استفاده را بکنیم ولی از طرفی دیگر این رویه ممکن است موجب بروز تأخیر در موعد تحویل کارهای دیگر خانواده‌ها شوند.
2-4.مروری بر اصول سیستم‌های تولیدی با قابلیت پردازش دسته‌ای از کارها
بعد از یک کلی نگری از انواع مسائل زمان بندی اکنون در ادامه این پایان نامه قصد زمانبندی سیستمهای تک ماشینه با قابلیت پردازش دسته ای را خواهیم داشت.
از جمله مهمترین صنایع تولیدی در دنیای امروزی، صنایع با قابلیت پردازش دسته‌ای از کارها است که می‌توان برای مثال اشاره کرد به:
انواع کارخانجات صنایع غذایی (تولید بستنی، پر کردن بطری‌های نوشیدنی و…)
یا کوره‌های پخت (نان و شیرینی و …)
یا صنایع ذوب و یا صنایع الکتریکی (هدف آزمایش سالم بودن قطعات الکتریکی بطور همزمان و …)
مهمترین هدفی که در تمامی صنایع پردازش دسته‌ای فوق دنبال می‌شوند عبارتند از:
سرعت تولید بالاتر- خروجی بیشتر از خط تولید- کاهش هزینه‌های جریان ساخت محصول- جلوگیری از تکرار زمان‌های آماده‌سازی و هزینه‌های آماده‌سازی.
2-5.مروری بر زمان‌بندی تک‌ماشینه با قابلیت پردازش دسته‌ای از کارها از نظر اندازه‌ی سفارشات کارها
درسیستم‌های تولیدی تک‌ماشینه با قابلیت پردازش دسته‌ای, یک‌ ماشین وجود دارد که دارای ظریفیت محدود می‌باشد یعنی این ماشین قادر است که در یک لحظه از زمان، حداکثر B واحد از کارهای مختلف را پردازش کند که می‌توان تحقیقات گذشته را از نظر اندازه‌ی سفارشات دریافت شده از سوی مشتری‌ها به چند دسته تقسیم کرد:
1-در این دسته از مسائل سفارشات رسیده از سوی مشتری همگی دارای اندازه‌ی ۱ واحد می‌باشند یعنی هر کار به اندازه‌ی ۱ واحد از ظرفیت ماشین را اشغال می‌کند.[17]
2-دسته‌ای دیگر از این مسائل شامل کارهایی است که هر کدام اندازه‌ی سفارش بیشتر از یک واحد از ظرفیت ماشین را دارند ولی اندازه‌ی سفارش تمامی این کارها با هم برابر است.[4,5,11,14,15,16,18]
3-در این دسته از مسائل اندازه‌ی سفارشات کارهای مختلف می‌تواند متفاوت از هم باشند که تحقیق ما در این دسته از مسائل از نظر اندازه‌ی سفارش‌ کارها جای خواهد گرفت [2,3,6,7,8]و همچنین قابلیت تفکیک شدن یک کار روی اندازه‌ی سفارش آن کار در دسته‌های مختلف وجود خواهد داشت که به این مفهوم در گذشته در سیستم‌های پردازش دسته‌ای کمتر توجه شده است.
2-6.مروری بر زمان‌بندی تک‌ماشینه با قابلیت پردازش دسته‌ای از کارها از لحاظ دسته‌بندی خانواده‌ی کارها
در سیستم‌های پردازش دسته‌ای از نظر پردازش همزمان کارها می‌توان بدون هیچ محدودیتی با هم پردازش شوند[12,14,23] یا اینکه ماشین قادر به پردازش کارهایی به صورت همزمان خواهد بود که دارای ویژگی‌های مشترکی باشند از جمله زمان پردازش یکسان که این کارها را در خانواده‌های مشخصی جای میدهد که هر خانواده دارای کارهایی با زمان پردازش برابر می‌باشد. [19,21,22]
تحقیق ما از نوع دوم این دسته از مسائل می‌باشد که علاوه بر این محدودیت بین پردازش دسته‌هایی از خانواده‌های مختلف زمان آماده‌سازی هم تعریف می‌شود زیرا در کارهای گذشته به این مفهوم و تأثیر آن روی بهینه‌سازی اهداف مدنظر در مسئله پردازش دسته‌ای کمتر توجه شده است.
2-7.مروری بر مسائل پردازش دسته‌ای با محدودیت زمان دسترسی20 کارها
یکی دیگر ازعوامل تأثیرگذار در بهینه‌سازی اکثر اهداف در مسائل پردازش دسته‌ای زمان‌دسترسی کارها خواهد بود که یا تمامی کارها در زمان صفر در دسترس‌اند[1,2,3,4] و یا هر کار در زمان دلخواهی وارد سیستم میشود[21,22,23] که از این نظر تحقیق ما جزء دسته‌هایی قرار دارد که کارها با زمان‌دسترسی متفاوت در اختیار می‌باشند که این عامل خود بر پیچیدگی‌های محاسباتی مسئله می‌افزاید.
2-8.مروری بر روش‌های حل مسائل زمان‌بندی در محیط پردازش دسته‌ای
2-8-1.روش‌های دقیق
سونگ و همکارانش [21] یک روش برنامه‌ریزی پویا- جولای و همکارانش [6] یک روش شاخه و ارزش- داپنت و همکارانش[10,22] یک روش دقیق شاخه و کران- جولای و همکارانش [18] یک برنامه‌ریزی پویا را برای مسائل مختلفی در زمینه‌ی BPMP ارائه دادند که در ادامه‌ در مورد هر یک صحبت خواهیم کرد.
2-8-2.الگوریتم‌های فراابتکاری21
حین و همکارانش [1] از الگوریتم‌های فراابتکاری اجتماع مورچگان و ونگ و همکارانش یک الگوریتم تقریبی و کوه و همکارانش [3] یک الگوریتم ژنتیک ترکیبی و یک مدل ریاضیاتی دقیق، جولای و کریمی و همکارانش[7] الگوریتم فراابتکاری NSGA II مبنی بر روش جستجوی محلی ابتکاری آقای ملوک وهمکارانش [8] یک الگوریتم فراابتکاری شبیه‌سازی ذوب و داموداران و همکارانش[8,9] یک الگوریتم ژنتیک و شبیه‌سازی ذوب در زمینه‌ی BPMP ارائه دادند که در ادامه در قسمت‌های بعدی در مورد کار هر یک توضیح می‌دهیم.
درادامه جدولی را طراحی کرده‌ایم که خلاصه‌ای از کارهای انجام شده در دهه‌های اخیر را در زمینه‌ی زمان‌بندی تک‌ماشینه در حوزه‌ی پردازش دسته‌ای نشان می‌دهد.(جدول2-1)
در این جدول با علائم اختصاری بطور واضح نشان داده شده است که کارهای قبلی در چه وضعیتی از نظر محدودیت‌های : زمان دسترسی- اندازه‌ی سفارشات- خانواده‌ی کارها- زمان آماده‌سازی بین خانواده‌ها قرارگرفنه اند.
جدول2-1:گزارشی از تحقیقات انجام شده
Row Definition problemyear authorSolution approach11|batch_processing, S j| C max2010Husseinzadeh Kashan Branch & price21| batch-processing , incompatible job families|∑wj*Cj2001AzizoghluB&B31| batch-processing, rj, sj=s, job families| C max2002J.M.Hong Y.H.KimDynamic programming41| batch-processing, s j| C max 2006Purushothaman DamodaranGenetic algorithm51| batch-processing, , Sj | C max 2007Purushothaman DamodaranSimulated Annealing61| batch-processing, incompatible job families | ∑Uj 2005Fariborz JolaiDynamic programming71| batch-processing, incompatible job families | ∑WjTj 2005John W. FowlerbSeveral heuretic procedure81| batch-processing, rj| ∑uj Tmax 1997Chung.lun. liDynamic programming91|batch_processing, rj, sj=s|L max2002Reha UzsoyDynamic programming101|batch_processing, pj=p |various objectives2009T.C.E. Chengoptimal polynomial time algorithms111|batch_processing, sj| f(Cmax,Tmax)2010Fariborz JolaiMOGAs algorithms121| batch-processing, incompatible job families|∑WjTj2007Vishnu Erramilli · Scott J. MasonMIP modeling, heuristic procedure131| batch_ processing, rj |∑wj Cj2005Zhaohui Liua,Approximation schemes141| batch-processing, rj, sj |C max 2012Huaping ChenAnt colony optimization151| batch-processing, rj, sj |C max 2005Qiming Liudheurestic algorithms
161|BPM, incompatible job family, r j| ∑C j2012Shiqing Yao,Branch & bound
2-9.مروری اجمالی بر کارهای قبلی وبررسی خلا موجود
دراین پایان‌نامه، مسأله‌ی زمان‌بندی تک‌ماشینه با قابلیت پردازش دسته‌ای روی مجموعه‌ای از کارها که متعلق به خانواده‌های متفاوت‌اند و با اندازه‌ی سفارش و زمان دسترسی دلخواه وارد سیستم می‌شوند مورد مطالعه واقع می‌شود که اهداف مدنظر برای بررسی مسئله حداقل‌سازی Cmax و Tmax بطور همزمان می‌باشد:
از آنجایی که عملکرد بسیاری از سیستم‌های تولیدی به وسیله‌ی کیفیت زمان‌بندی گلوگاه‌هایی که شامل یک ماشین است تعیین خواهد شد، مطالعه در زمینه‌ی زمان‌بندی تک‌ماشینه از گذشته تا به حال مورد توجه فراوان بوده است و از طرفی دیگر وجود یک ماشین با قابلیت پردازش دسته‌ای از کارها در ایستگاه گلوگاهی خط تولید، بسیاری از مشکلات خط تولید که از ایستگاه گلوگاه ناشی می‌شود را می‌تواند بهبود دهد. از طرفی دیگر بررسی مسائل زمان‌بندی تک‌ماشینه در هر حالتی که باشد به‌عنوان اساس و شروع مسیر برای بسط به مدل‌های پیچیده‌تر خواهد بود.
با توجه به توضیحات بالا و بیان اهمیت موضوع مورد بحث، در ادامه مروری بر کارهای قبلی که در این زمینه انجام شده است را خواهیم داشت:
در حیطه‌ی مدل‌های زمان‌بندی تک‌ماشینه با قابلیت پردازش دسته‌ای از کارها در دهه‌های اخیر مقالات زیادی منتشر شده است که گوپتا و همکارانش در سال۱۹۹۷ [15] اولین کسانی بودند این مسئله را با هدف حداقل سازی‌سازی مجموع وزنی دیرکرد و زودکرد (JIT) مورد بررسی قرار دارند که در این مطالعه کارها متعلق به خانواده‌های متفاوت می‌باشند و زمان آماده‌سازی بین پردازش دسته‌های متعلق به خانواده‌های مختلف لحاظ شده است و روش‌حل پیشنهادی دراین مطالعه برنامه‌ریزی پویا میباشد.
در سال ۱۹۹۸ لی و همکارانش در این زمینه با هدف حداقل‌سازی حداکثر دیرکرد از موعد تحویل مطالعه کرده‌اند، آنان در مطالعاتشان کارها را با زمان دسترسی و موعد تحویل سازگار در نظر گرفتند والگوریتم پیشنهادی آنان الگوریتم برنامه‌ریزی پویا بوده است.
در سال ۲۰۰۱ عزیزاقلو و همکارانش[47] به زمان‌بندی کارهایی متعلق به خانواده‌های مختلف با هدف حداقل‌سازی مجموع وزنی زمان تکمیل کارها پرداختند که زمان دسترسی کارها متفاوت از هم بودند و روش حل پیشنهادی آنان شاخه و کران بوده است.
در سال ۲۰۰۲ سونگ وهمکارانش [21] یک روش حل دقیق مبنی بر برنامه‌ریزی پویا رابر‌ای حداقل‌سازی زمان تکمیل آخرین کار در زمان‌بندی کارهایی متعلق به خانواده‌های متفاوت و با زمان دسترسی متفاوت ارائه کردند.
داپنت و همکارانش در سال ۲۰۰۲ [10] به حداقل‌سازی زمان تکمیل آخرین کار با یک روش دقیق برای کارهایی که دارای اندازه‌ی سفارش دلخواه هستند پرداخته اند.
یوزی و همکارانش در سال ۲۰۰۲ [14] یک الگوریتم ترکیبی ژنتیک با برنامه‌ریزی پویا برای حداقل‌سازی حداکثر تأخیر برای کارهایی که دارای زمان دسترسی متفاوت‌اند، ارائه کرده‌اند.
شریف ملوک و همکارانش در سال ۲۰۰۴ [8] به حداقل‌سازی زمان تکمیل آخرین کار با روش فراابتکاری شبیه‌سازی ذوب روی کارهایی با اندازه‌ی سفارش متفاوت پرداختند.
پیرز و همکارانش در سال ۲۰۰۵ [19] با تعدادی از روش‌های ابتکاری به حداقل‌سازی مجموع وزنی دیرکرد کارهایی متعلق به خانواده‌های متفاوتند پرداخته‌اند.
داموداران و همکارانش [9] به حداقل‌سازی زمان تکمیل آخرین‌کار پرداختند. آنان با یک الگوریتم ژنتیک به بررسی کارهایی که دارای اندازه‌ی سفارش متفاوت بوده‌اند توجه کرده‌اند.
و در سال ۲۰۰۷ [11] آنان به بررسی همین مسئله با روش حل شبیه‌سازی ذوب 22پرداختند.
یانگ در سال ۲۰۰۷ [13] اثبات کرد که مسئله‌ زمان‌بندی کارهایی که متعلق به خانواده‌های مختلف‌اند و دارای زمان آماده‌سازی یکسان بین خانواده‌ها می‌باشند با هدف حداقل‌سازی حداکثر دیرکرد از موعد تحویل قویاً جزء مسائل Np-Hard بوده‌اند که از این تحقیق می‌توان برای اثبات Np-Hard بودن مسئله ما، که دارای پیچیدگی‌های بیشتری نسبت به آن است، استفاده کرد.
ایردال و همکارانش در سال ۲۰۰۷[16] یک روش برنامه‌ریزی پویا برای حداقل‌سازی مجموع وزنی تعداد کارهای دچار دیرکرد ارائه دادند.
در سال ۲۰۰۹ چِن و همکارانش [17] به بررسی زمان‌بندی پردازش دسته‌ای کارها با زمان پردازش یکسان برای تمامی کارها و بدون در نظرگیری سایر محدودیت‌ها نظیر : زمان دسترسی- زمان آماده‌سازی- خانواده‌‌ی کارها و … پرداختند که آنان در این مطالعه روش های ابتکاری متنوعی را برای بهینه سازی اهداف و معیارهای مختلف ارائه دادند.
از جمله کسانی که در زمینه‌ی زمان‌بندی پردازش دسته‌ای کارها تحقیقات زیادی انجام دادند و جزء پیشگامان پردازش دسته‌ای هستند جولای و کریمی و همکارانش می‌باشند که از تحقیقات آنان می‌توان اشاره‌ کرد به:
حداقل‌سازی تعداد کارهای دچار دیرکرد برای کارهای متعلق به خانواده‌های متفاوت با یک روش برنامه‌ریزی پویا در سال ۲۰۰۵ [18].
روش‌ بهینه‌سازی برنامه‌ریزی پویا برای پردازش دسته‌ای با کارهایی که متعلق به مشتری‌های متفاوتند با حداقل‌سازی همزمان اهداف حداکثر تأخیر و زمان تکمیل آخرین‌کار را در سال ۲۰۱۰ [20] ارائه دادند و همچنین آنان در سال ۲۰۱۰ [7] به بهینه‌سازی همزمان اهداف حداکثر دیرکرد کارها و زمان تکمیل آخرین کار با روش‌های مبتنی بر ژنتیک چندهدفه برای کارهایی که دارای اندازه‌ی سفارش متفاوتی بودند پرداختند.
با توجه به پیشینه‌ی مطالعات گذشته و بررسی خلاء موجود در میان این کارها به این نتیجه رسیدیم که برای نزدیک‌تر کردن موضوع پردازش دسته‌ای به دنیای واقعی, این تحقیق را با اهداف و محدودیت‌های معرفی شده در زیر انجام می‌دهیم:
بطور کلی مسئله‌ی مدنظر ما را می‌توان به این‌صورت تعریف کرد که می‌خواهیم مجموعه‌ای از nکار مستقل از هم که متعلق به m خانواده از قطعات می‌باشند را بگونه‌ای دسته‌بندی و پردازش کنیم که دو هدف حداکثر دیرکرد از موعد تحویل کارها و زمان تکمیل آخرین کار را بطور همزمان حداقل کنیم. در حالی‌که همه‌ی کار در زمان صفر در دسترس نمی‌باشند و هر کار دارای اندازه‌ی سفارش مختص به خود است و قابلیت تفکیک شدن یک کار روی اندازه‌ی سفارش در دسته‌های مختلف را نیز خواهد داشت و هر کار دارای یک موعد تحویل از پیش‌تعیین‌شده و زمان پردازش مختص به خود است و کارهایی که در آن زمان پردازش یکسان‌اند در یک خانواده جای می‌گیرند و ماشین قابلیت پردازش همزمان کارهای هم‌خانواده را فقط دارد( به‌عنوان مثال کوره‌های پخت شیرینی که قادر به پخت انواع مختلف شیرینی با زمان پخت یکسان‌اند) و ظرفیت محدود برای ماشین تعریف می‌شود که اندازه‌ی سفارش هیچ‌کاری پیش از ظرفیت ماشین نباید باشد.
در ضمن بین پردازش دسته‌هایی از خانواده‌های مختلف, زمان آماده‌سازی وجود خواهد داشت. که در هیچ کدام از تحقیقات گذشته تمامی این محدودیت‌ها و فرضیات با هم در پردازش دسته‌ای در نظر گرفته نشده‌اند. و ما سعی کرده‌ایم تا با اعمال تمامی محدودیت‌هایی که ممکن است امروزه در صنایع تولید دسته‌ای به آن برخورد بکنیم این مدل را تا جای ممکن به واقعیت‌ها نزدیکتر بکنیم.
با توجه به اینکه در تحقیقات قبلی کارهایی با پیچیدگی کمتر از تحقیق ما Np-Hard بودن شان ثابت شده است، می‌توان به Np-Hard بودن این مدل پی ببریم و از طرفی دیگر قصد در بهینه‌سازی چندهدفه‌ی مدل مذکور داریم که این امر خود باعث پیچیدگی بالای کارمان می‌شود.
2-10.مروری بر زمان‌بندی چندهدفه در محیط تک ماشینه
همان‌طور که در فصل قبلی اشاره کردیم زمان‌بندی در محیط‌های تک‌ماشینه برای ارائه مدل‌های پیچیده زمان‌بندی و ارائه مفهوم جدید، به‌عنوان پایه و اساس برای محققان محسوب می‌شود یعنی در عین ساده بودن این مدل از مهم‌ترین مدل‌ها می‌باشد.
براساس نوع نگرش نسبت به زمان‌بندی در سیستم‌های تولید تک‌ماشینه می‌توان معیارهای مختلفی را به عنوان هدف در نظر گرفت که در سال‌های اخیر تحقیقات محققان بیشتر روی بررسی‌های چندهدفه در محیط‌های تک‌ماشینه صورت گرفته است که این امر موجب نزدیک‌تر شدن اینگونه مسائل به دنیای واقعی شده است.
اکنون می‌خواهیم چند مورد از مطالعات چندهدفه که در زمان‌بندی تک‌ماشینه انجام شده‌اند را اشاره کنیم:
– حداقل‌سازی، بیشترین زمان دیرکرد از موعد تحویل (Tmax) و زمان تکمیل آخرین کار (Cmax) (که اهداف مورد نظر در این تحقیق هم می‌باشند)[7]
– حداقل‌سازی، بیشترین زمان زودکرد از موعد تحویل و حداکثر زمان در جریان ساخت کارها.
– حداقل‌سازی، بیشترین زمان زودکرد از موعد تحویل و تعداد کارهایی که با دیرکرد مواجه شده‌اند[46,47]
– حداقل‌سازی، مجموع وزنی زمان تکمیل کارها و بیشترین زمان تأخیر[48]
– حداقل سازی، مجموع وزنی زودکرد و دیرکرد کارها[35,40]

2-11.اهداف مورد بررسی در مدل
2-11-1.دلایل انتخاب اهداف مسأله
اهداف مورد بررسی ما در مسأله عبارتند از: حداقل‌سازی، حداکثر دیرکرد از موعد تحویل کارها (Tmax) و دیگری حداقل‌سازی زمان تکمیل آخرین کار یا دسته (Cmax).
همان طور که در مفاهیم اولیه زمان‌بندی تعریف کردیم دیرکرد از موعد تحویل کارها برای کارخانه‌ها هزینه‌هایی از قبیل: نارضایتی مشتری- جریمه‌های دیرکرد- از دست دادن مشتری‌های آتی- از دست دادن حسن شهرت و … را به دنبال خواهد داشت، بنابراین یکی از اهداف مهمی که در مباحث زمان‌بندی مطرح است تحویل به موقع و بهنگام کارها به مشتری است (JIT).
مهمترین اهداف زمان‌بندی JIT عبارتند از حداقل‌سازی:
– مجموع هزینه‌های زودکرد و دیرکرد
– حداکثر زمان تأخیر Lmax
– حداکثر زمان دیرکرد Tmax
– حداکثر زمان زود کرد Emax
– مجموع تعداد کارهای دچار دیرکرد شده
از طرفی یکی دیگر از اهداف این تحقیق حداقل‌سازی زمان تکمیل آخرین کار است (Cmax) که کارایی این هدف رادر چند مورد زیر توضیح خواهیم داد:
گاهی اوقات برای تحویل کارهای پردازش‌شده به مشتری باید تمامی کارهایی که یک مشتری سفارش داده را آماده کنیم و آنان را با هم تحویل مشتری دهیم بنابراین تا جای ممکن باید سعی در پردازش سریعتر تمامی سفارشات مشتری کنیم یعنی تا وقتی که آخرین کار مشتری پردازش نشود مابقی کارها در کارخانه دچار هزینه‌ی نگهداری خواهند شد و به مشتری تحویل داده نمی‌شوند.
دلیل دیگر حداقل‌سازی زمان تکمیل آخرین کار می‌تواند تخلیه‌ی هرچه‌زودتر خط تولید باشد. و این مورد معمولاً در صنایعی دیده می‌شود که دارای خط تولیدی با هزینه‌ی استهلاکی و نگهداری بالایی‌اند.
2-11-2.اثبات وجود تناقض بین اهداف مسئله (پارتو)
شاید در ظاهر این دو هدف در یک راستا عمل می‌کنند و هیچ تناقضی بین آنان دیده نشود یعنی این طور به نظر برسد که هر دو هدف به دنبال پردازش سریعتر کارها می‌باشند ولی برعکس این قضیه می‌توان با مثال نشان داد که توالی که منجر به مقدار بهینه‌ی ارزش Cmax خواهد شد الزاماً دارای Tmax بهینه نخواهد بود و یا برعکس قضیه هم برقرار است:
مثال:ماشینی به ظرفیتB=4وزمان آماده سازی بین خانواده ها یک واحد زمانی و کارهایی با داده های زیر را برای پردازش در نظر بگیرید:
جدول2-2:مثال عددی
JPjRjSjDj133272382133252114252853528

در این سایت فقط تکه هایی از این مطلب با شماره بندی انتهای صفحه درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

اینجا کلیک کنید

A={(1),(3,4),(2,5)} و B={(1,5),(3,4),(2)}
BA1513هدف۱35هدف۲
شکل2-1:جدول لکزیکوگرافیک
برای توالی هایA,B اهداف را محاسبه می‌کنیم و می‌بینیم که با بهینه شدن یک هدف دیگری غیر ازمقدار بهینه خواهد بود که این می‌تواند دلیلی بر تناقض این دو هدف در مسئله مدنظر ما باشد.
بعد از نشان دادن تناقض بین دو هدف مذکور باید به دنبال بهینه‌سازی در لبه‌های پارتو باشیم یعنی باید به دنبال حداقل کردن زمان تکمیل آخرین کار به ازاء هر مقدار از حداکثر دیرکرد از کارها باشیم تا لبه‌ی پارتو بهینه را بدست آوریم.
جواب‌های بهینه‌ی پارتو جواب‌هایی‌اند که نمی‌توانند موجب بهبود یک هدف شوند مگر با بدتر کردن یکی از سایر اهداف واز آنجایی که هیچ جوابی نمی‌تواند هر ۲ هدف را بطور همزمان بهینه کند شخص باید به دنبال یک موازنه قابل‌قبول بین جواب‌ها باشد.
در ضمن ما از روشی به نام محدودیت‌اپسیلون 23برای یافتن حل‌های بهینه برای مثال‌هایی با اندازه‌های کوچک استفاده می‌کنیم در این روش مسئله را به زیرمسأله‌هایی تک‌هدفه با محدودیت سایراهداف تبدیل کرده و در چندبار اجرا به مجموعه‌ای از حل‌های نامغلوب بهینه دست پیدا خواهیم کرد.
و در این پایان‌نامه یک الگوریتم فراابتکاری دوهدفه با ساختار NSGA II را توسعه خواهیم داد که در این الگوریتم ویژگی‌های متمایز و اپراتورهایی کارا متناسب با مسأله تعریف خواهیم کرد تا جواب‌های نزدیک بهینه برای مسائلی با ابعاد بزرگ در زمان معقول بدست آوریم که در فصل های بعدی بطور مفصل درباره‌ی این الگوریتم ها بحث خواهیم کرد.
2-12.مروری بر الگوریتم‌های ژنتیک چندهدفه24
یکی از نقاط ضعف اصلی الگوریتم‌های ابتکاری گیر افتادن در نقاط بهینه‌ی محلی25 می‌باشد که به همین دلیل در سال‌های اخیر محققان بیشتر به سمت الگوریتم‌های فراابتکاری روی آوردند.
اصطلاح فراابتکاری برای اولین بار توسط فوسکا[37] مطرح شد، که این الگوریتم‌ها معمولاً با یک حل اولیه یا جمعیتی از حل‌های اولیه شروع شده و با جستجو‌ی محلی در پی حرکت به سمت حل‌های بهتر می‌باشند. الگوریتم‌های فراابتکاری برخلاف رویکرد‌های جستجوی محلی اگر بهبود در حلها حاصل نشود الگوریتم متوقف نشده بلکه اجازه‌ی رفتن به سمت حل‌های بدتر را دارد تا از همگرایی زودرس به سمت جواب بهینه محلی جلوگیری کند.
الگوریتم‌های فراابتکاری با الهام از مفاهیم هوش مصنوعی و الگوریتم‌های تکاملی که ریشه در مفاهیم تکامل طبیعی دارند، حل مسائل رابه سمت حل بهینه کلی همگرا می‌کنند. برای جزئیات بیشتر از الگوریتم‌های فراابتکاری به[35,36,39]مراجعه نمایید.
از آنجایی که الگوریتم فراابتکاری ما بر پایه‌ی الگوریتم ژنتیک استوار است ما مروری بر الگوریتم ژنتیک در بهینه‌سازی چندهدفه خواهیم داشت:
الگوریتم ژنتیک یک روش جستجو بر اساس نظریه وراثت ژنتیکی و فلسفه انتخاب اصلح در طبیعت داروینی بنا شده است. این الگوریتم با یک جمعیت تصادفی شروع به کار کرده و با عملگرهای تقاطع و جهش و یک اپراتور انتخاب مبنی بر تابع برازش از نسلی به نسل دیگر بهبود می‌یابد. الگوریتم‌های ژنتیک چندهدفه را می‌توان بر چند مبنا تقسیم‌بندی کرد.
2-12-1. الگوریتم‌های ژنتیک چندهدفه مبتنی بر تابع ادغامی
در این دسته از الگوریتم‌های ژنتیک چندهدفه باید اهداف را در یک هدف ادغام کنیم از جمله روش ترکیب وزنی اهداف.
2-12-2. الگوریتم‌های ژنتیک چندهدفه مبتنی بر جمعیت
از جمله الگوریتم هایی که در این دسته از الگوریتم‌های ژنتیک چندهدفه قرار می‌گیرند، الگوریتم VEGA می‌باشدکه توسط اسپرز ارائه شده است. در این نوع از الگوریتم ژنتیک، کل جمعیت M را به زیرجمعیت‌های تبدیل کرده که متناسب با تعداد اهدف‌(k)میباشد و در هر زیرجمعیت به اندازه‌ی M/K عضو ایجاد می‌کنیم و در نهایت روی ترکیب این زیرجمعیت‌ها عملگرهای تقاطع و جهش را اجرا می‌کنیم.
2-12-3. الگوریتم‌های ژنتیک چندهدفه مبتنی بر پارتو
در این دسته از روش‌ها به چند طریق به بررسی رابطه‌ی مغلوب یا نامغلوب بودن حل‌ها جهت دسته‌بندی حل‌ها در لبه‌های پارتو پرداخته می‌شود لذا حل‌هایی که در لبه‌های پایین‌تر واقع می‌شوند از شایستگی بیشتر برای انتخاب برخوردارند از جمله‌ی این روش‌ها می‌توان به NSGA -NSGA II – NRGA و … اشاره کرد.[24,41,50]
2-13.دلایل انتخاب موضوع و روش‌های حل
با مروری بر مقالات گذشته در زمینه‌ی BPMSP ، ملاحظه کردیم که هیچ مدل ریاضی از طرف محققان برای این مسأله به‌همراه محدودیت‌های مدنظر ما در نظر گرفته نشده است.
بنابراین فقدان یک مدل جامع و کامل که بتواند بسیاری از مسائل دنیای واقع را در زمینه ی BPMSP تحت پوشش قرار بدهد احساس شده است به همین دلیل سعی ما بر این بوده تا بتوانیم تا حدودی این خلاء را پوشش دهیم البته باید این نکته را هم یادآوری کنیم که می‌توان پارامترهای دیگری هم به این مدل اضافه نمود تا مسأله بتواند محدودیت‌های بیشتری از دنیای پیرامون را پوشش دهد.
همچنین در بررسی رویکرد‌های حل مسأله BPMSP ملاحظه کردیم که اکثر محققان از روش‌های ابتکاری استفاده کرده‌اند و چند مورد هم الگوریتم‌ها فراابتکاری ارائه شده که در آن محدودیتها و فرضیات مسأله خیلی کمتربوده و بررسی به صورت تک‌هدفه انجام شده است.

دسته بندی : پایان نامه ارشد

پاسخ دهید