مسائل بهینه سازی چند هدفه و بهینه سازی چند معیاره

دانلود پایان نامه

در بسیاری از تحقیقات صورت گرفته در حیطه مسائل زمانبندی، محیط هایی مورد مطالعه قرار می گیرند که در آن ها فرض بر این است تمام کارها می توانند بدون هیچ محدودیتی روی تمام ماشین های موجود پردازش شوند. اما در بعضی از مواقع این فرض با شرایط واقعی حاکم بر سیستم های تولیدی و خدماتی در تضاد است و شرایطی وجود دارد که کارها دارای ویژگی هایی هستند که تنها بخشی از ماشین ها قادر به پردازش آنها می باشند. بدین صورت که کار نوع j تنها روی تعدادی از ماشین ها و نه تمام آن ها قبل پردازش است. مجموعه ماشین هایی که قادرند کار نوع j راپردازش کنند، در قالب یک مجموعه بصورت نمایش داده می شوند که زیر مجموعه ای از تمام ماشین های موجود می باشد. کاربرد مسائل زمانبندی با فرض دسترسی محدود به ماشین ها در بسیاری از محیط های تولیدی و خدماتی دیده می شود. به عنوان مثال، در محیط های بیمارستان هزینه های هنگفتی به منظور تجهیز اتاق های عمل صرف می شود و با توجه به محدودیتی که در میزان تجهیزات موجود در هر اتاق وجود دارد، هر اتاق تنها برای تعدادی از بیماران قابل دسترس است.
سنتنو و آرماکست [41] مسئله زمانبندی ماشین های موازی یکسان را با فرض دسترسی محدود به ماشین ها و زمان های آماده به کار متفاوت با هدف کمینه سازی بیشینه زمان تاخیر در نظر گرفتند. آن ها یک الگوریتم ابتکاری که ترکیبی از قانون اولویتی کار با کمترین انعطاف پذیری(LFJ) و قانون اولویتی ماشین با کمترین انعطاف پذیری (LFM) است برای حل این مسئله ارائه دادند. بعد ها سنتنو و آرماکست [42] یک الگوریتم ابتکاری که ترکیبی از (LFJ) ، (LFM) و قانون طولانی ترین زمان پردازش (LPT) برای مسئله مشابه با تابع هدف کمینه سازی بیشینه زمان تکمیل کارها پیشنهاد کردند. چپین و واخانیا [43] یک الگوریتم چند جمله ای با نسبت عملکردی برای مسئله زمانبندی ماشینهای موازی نامرتبط با فرض دسترسی محدود به ماشین ها به منظور کمینه سازی بیشینه زمان تکمیل کارها پیشنهاد دادند. شین و همکاران [44] یک الگوریتم دقیق شاخه و کران برای مسئله زمانبندی ماشین های موازی با فرض دسترسی محدود به ماشین ها و محدودیت در دسترس نبودن ماشین ها در طول زمانبندی با هدف کمینه سازی بیشینه تاخیر پیشنهاد کردند. لیانگ و لی [45] تحقیقی جامع بر روی ماشین های موازی یکسان، یکنواخت و نامرتبط با فرض وجود محدودیت دسترسی به ماشین ها در دو حالت زمانبندی با فرض مجاز بودن شکست کارها و غیر مجاز بودن شکست کارها بررسی نمودند. طبق بررسی آن ها مساله زمانبندی ماشین های موازی با محدودیت مورد نظر با اسمی مختلفی توسط محقیق علوم کامپیوتر و علوم تحقیق در عملیات نامگداری شده است. این محدودیت عموماً با عناوین محدودیت مجموعه پردازشی، زمانبندی سیستم ها بر اساس نوع عملکرد، زمانبندی ماشین چند منظوره، محدودیت دسترسی و محدودیت دسترسی محدود به ماشین ها شناخته می شوند. لی و همکاران [46] الگوریتمی را برای مسئله زمانبندی ماشین های موازی یکسان که دارای محدودیت دسترسی محدود به ماشین ها و زمان های آماده به کار متفاوت با هدف کمینه سازی بیشینه زمان تکمیل کارها پیشنهاد دادند که توانایی بدست آوردن جواب بهینه را دارد. آنها برای ساده سازی این مسئله فرض کردند که تمامی فعالیت ها دارای زمان پردازش یکسانی باشند.
جاوو [47] مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود محدودیت های دسترسی محدود به ماشین ها با در نظر گرفتن همزمان دو هدف کمینه سازی بیشینه زمان تکمیل کارها و کمینه سازی مجموع زودکرد و دیرکرد کارها مورد بررسی قرار داد. برای حل این مسئله نسخه چند هدفه الگوریتم سیستم ایمنی مصنوعی پیشنهاد شده است. گوخال و ماسی راجان [7] یک مدل برنامه ریزی عدد صحیح مختلط و چند الگوریتم ابتکاری برای مسئله زمانبندی ماشین های موازی یکسان با فرض وجود محدودیت های دسترسی محدود به ماشین ها، زمان آماده سازی وابسته به توالی کارها و زمان های آماده به کار متفاوت به منظور کمینه سازی مجموع وزنی در جریان کارها پیشنهاد دادند. ونگ و همکاران [4] مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود محدودیت های دسترسی محدود به ماشین ها، زمان آماده سازی وابسته به توالی کارها و زمان های آماده به کار متفاوت به منظور کمینه سازی تعداد کارهای دارای دیرکرد در نظر گرفتند. آن ها برای این مسئله یک مدل برنامه ریزی عدد صحیح مختلط و یک الگوریتم ابتکاری برای ایجاد پاسخ اولیه و بهبود آن با یک رویه جستجوی محلی پیشنهاد دادند.

2-5- زمان آماده سازی وابسته به توالی کارها


به عنوان یک تعریف کلی، زمان نصب برای هر ماشین به مفهوم زمان مورد نیاز برای آماده سازی ماشین به منظور پردازش کارهای تخصیص یافته به آن می باشد. به طور معمول، در مسائل زمانبندی زمان های آماده سازی به دو گروه کلی تقسیم می شوند. در گروه اول زمان نصب تنها به نوع کاری که روی ماشین پردازش می شود بستگی دارد و اصطلاحاً به آن زمان نصب مستقل از توالی گفته می شود. در گروه دوم زمان نصب علاوه بر نوع کاری که بر روی ماشین پردازش می شود، به کار قبلی که بر روی ماشین پردازش شده است نیز بستگی دارد و از آن به عنوان زمان آماده سازی وابسته به توالی یاد می شود. مسائل زمانبندی مربوط به گروه دوم خود به دو دسته تقسیم می شود. دسته اول شامل مسائلی هستند که در آن ها زمان آماده سازی، وابسته به توالی کارها و مستقل از نوع ماشین آلات است و در دسته دوم زمان نصب هم وابسته به توالی کارها و هم وابسته به نوع ماشین آلات می باشد. در رابطه با اهمیت این موضوع می توان به تحقیقات صورت گرفته توسط برخی از محققین اشاره کرد. بر اساس گزارش پانوالکار [48] که در دهه هفتاد میلادی به چاپ رسید، نزدیک به 70% افراد شاغل در زمینه زمانبندی اذعان کردند که در حداقل یک چهارم کارهایی که توسط آنها زمانبندی می شوند، نمی توان نقش زمان های آماده سازی برای ماشین ها را نادیده گرفت. همچنین، فلین [49] تاثیر فرآیند های نصب وابسته به توالی را در افزایش ظرفیت تولید در محیط تولید سلولی و ورتمن [50] اهمیت آنها را در مدیریت ظرفیت تولید بررسی نمودند.
حال که با حالت های مختلف و اهمیت زمان آماده سازی آشنا شدیم به بررسی تحقیق های انجام شده در زمینه ماشین های موازی که این محدودیت را در نظر گرفته اند می پردازیم. همان طور که ملاحظه می کنید در بخش محدودیت پیش نیازی کارها و دسترسی محدود به ماشین ها به بررسی تعدادی از پژوهش های انجام شده که محدودیت زمان آماده سازی وابسته به توالی را در نظر گرفته بودند، پرداختیم. از این رو در این قسمت بیشتر به بررسی تحقیقاتی می پردازیم که تمرکز آن ها بیشتر روی محدودیت زمان آماده سازی می باشد. گوینت و داسوچی [51] مسئله زمانبندی ماشین های موازی یکسان را با در نظر گرفتن زمان های نصب وابسته به توالی با هدف کمینه سازی بیشینه زمان تکمیل کارها با استفاده از یک روش ابتکاری بر مبنای روش مجارستانی بررسی کردند. کیم و شین [52] مسئله مشابهی را با هدف کمینه سازی بیشترین زمان تاخیر کارها بررسی نموده و برای حل آن از الگوریتم جستجوی ممنوع بهره بردند. همچنین فاولر و همکارانش [53] برای حل مسئله مورد نظر با اهداف مختلف شامل بیشینه زمان تکمیل کارها، مجموع وزنی زمان تکمیل کارها و مجموع وزنی زمان دیرکرد کارها، یک الگوریتم ژنتیک ترکیبی را ارائه نمودند. نتایج محاسباتی بدست آمده برای هر سه معیار ذکر شده، عملکرد بهتر آن را نسبت به الگوریتم های موجود قبلی نشان می دهد. بهنامیان و همکارانش [54] یک الگوریتم فرا ابتکاری ترکیبی برای کمینه سازی بیشینه زمان تکمیل کارها برای مسئله زمانبندی ماشین های موازی یکسان با محدودیت زمان آماده سازی وابسته به توالی پیشنهاد کردند. الگوریتم پیشنهادی آن ها ترکیبی از الگوریتم بهینه سازی موچگان، الگوریتم شبیه سازی تبرید و الگوریتم جستجوی همسایگی می باشد. آن ها برای ارزیابی الگوریتم پیشنهادیشان آن را با دو الگوریتم دیگر که یکی ترکیبی از الگوریتم شبیه سازی تبرید و الگوریتم جستجوی همسایگی و دیگری ترکیبی از الگوریتم بهینه سازی موچگان و الگوریتم جستجوی همسایگی است، مقایسه کردند. نتایج محاسباتی بدست آمده کارایی بالای الگوریتم پیشنهادی آن ها را برای حل مسائلی با ابعاد بزرگ نشان می دهد. ینگ و چنگ [55] از روش ابتکاری جستجوی مکرر حریصانه به منظور حل مسئله زمان بندی ماشین های موازی یکسان با فر ض وجود زمان های آماده به کار متفاوت و زمان آماده سازی وابسته به توالی استفاده کردند.
کیم و همکاران [56] مسئله زمان بندی ماشین های موازی نامرتبط با فرض وجود زمان های نصب وابسته به توالی و مستقل از نوع ماشین را با هدف کمینه سازی مجموع زمان دیرکرد کارها بررسی نمودند و برای حل این مسئله، تعدادی روش ابتکاری بر پایه الگوریتم شبیه سازی تبرید ارائه نمودند. ژو و هیدی [57] یک مدل برنامه ریزی عدد صحیح برای مسئله مشابه با تابع هدف کمینه سازی زمان های زودکرد و دیرکرد کارها ارائه نمودند. آن ها گزارش کردند که مدل پیشنهادی برای یک مسئله با اندازه نه کار و سه ماشین در زمان قابل قبول به جواب می رسد. ونگ و همکاران [58] مسئله زمانبندی ماشین های موازی نامرتبط را با فرض وجود زمان های نصب وابسته به توالی و با هدف کمینه سازی مجموع وزنی زمان تکمیل کارها مطالعه نمودند. آن ها هفت روش ابتکاری ساده را از نظر نتایج محاسباتی با یکدیگر مقایسه نمودند و در نهایت یکی از آن ها را به عنوان بهترین روش انتخاب می نمایند. این روش هر یک کارها را بر اساس کوچکترین نرخ زمان پردازش بعلاوه زمان نصب نسبت به وزن کار در تابع هدف به ماشین ها اختصاص می دهد. روچا و همکاران [59] مسئله زمانبندی ماشین های موازی نامرتبط را با فرض وجود زمان های نصب وابسته به توالی و با هدف کمینه سازی بیشینه زمان تکمیل کارها و مجموع وزنی زمان های دیرکرد مورد بررسی قرار دادند. آن ها برای این مسئله یک روش شاخه و کران پیشنهاد نمودند و از روش فرا ابتکاری GRASP به منظور تولید یک جواب به عنوان حد بالای مسئله استفاده نمودند. آن ها همچنین برای این مسئله، دو مدل برنامه ریزی عدد صحیح آمیخته ارائه کردند و نشان دادند که روش شاخه و کران پیشنهادی، عملکرد بهتری نسبت به دو مدل ارائه شده دارد. والادا و رویز [60] برای مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود زمان های آماده سازی وابسته به توالی با در نظر گرفتن هدف بیشینه تکمیل کارها یک الگوریتم ژنتیک به همراه یک الگوریتم جستجوی محلی ارائه کردند و آن را برای مسائلی با اندازه های متوسط و بزرگ آزمایش کردند. آن ها ادعا کردند که این الگوریتم در مقایسه با سایر روش های موجود در ادبیات تحقیق دارای بهترین عملکرد است. کسکین ترک و همکاران [61] برای مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود زمان های آماده سازی وابسته به توالی به منظور کمینه سازی میانگین نسبی درصد عدم بالانس دو الگوریتم فرا ابتکاری شامل الگوریتم بهینه سازی مورچگان و الگوریتم ژنتیک و دو الگوریتم ابتکاری ارائه کردند. آن ها گزارش دادند که الگوریتم مورچگان پیشنهادی آنها عملکرد بهتری نسبت به الگوریتم ژنتیک و دو الگوریتم ابتکاری یاد شده دارد. چن [62] مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود زمان های آماده سازی وابسته به توالی و زمان آماده به کار متفاوت با هدف کمینه سازی تعداد کارها دارای دیرکرد وزنی را در نظر گرفته است. برای حل این مسئله یک الگوریتم فرا ابتکاری ترکیبی که شامل الگوریتم جستجوی ممنوع و الگوریتم جستجوی همسایگی متغیر است، پیشنهاد کردند و برای ایجاد یک جواب اولیه با کیفیت از یک رویه ابتکاری استفاده نمودند.
2-6- بهینه سازی چند هدفه
بسیاری از مسائل بهینه سازی که در عمل با آن روبرو هستیم همواره با بیش از یک معیار بهینه سازی سر و کار دارند. در یک مسئله بهینه سازی چند هدفه که بهینه سازی چند معیاره یا بهینه سازی برداری هم نامیده می شوند، هر حل بر مبنای بیش از یک هدف ارزیابی می شود. در این گونه مسائل همواره می بایستی چندین هدف که معمولاً در تضاد با یکدیگر هستند بطور همزمان بهینه شوند. از این رو همواره یک پاسخ نمی تواند به تنهایی شامل بهترین مقادیر برای توابع هدف مختلف باشد. در این مسائل همواره مجموعه ای از پاسخ ها وجود داردند که نسبت به سایر پاسخ های موجود در فضای جواب برتر هستند. این مجموعه پاسخ های نامغلوب تحت عنوان مجموعه ی بهینه پارتو نامیده می شوند. این مجموعه جواب همواره انتخاب های مختلفی را برای تصمیم گیرنده به همراه خواهد داشت که در نهایت یکی از این نقاط بعنوان نقطه نهایی توسط تصمیم گیرنده انتخاب می شود.
رویکرد روش های کلاسیک برای حل این مسائل، همواره به صورت وزن دهی به اهداف مختلف و تبدیل یک مسئله ی چند هدفه به یک مسئله تک هدفه می باشد. البته این نکته ای که در روش های کلاسیک حائز اهمیت است، اینکه توابع هدف مختلف مسئله با هم متناسب نباشند، بطور مثال یک هدف دارای مقیاس زمان و دیگری بر مقیاس سرعت باشد که این امر ترکیب معیارهای مختلف و تبدیل آن ها به یک معیار را مشکل می سازد. روش های کلاسیک نقاط ضعف مختلفی دارند، اینکه در این روش ها نیاز به اطلاعات اولیه از مسئله داریم تا بتوان وزن های مناسبی را به اهداف مختلف اختصاص داد که این امر همواره امکان پذیر نمی باشد. روش های کلاسیک توانایی پوشش کامل فضای را نداشته و بسیار وقت گیر می باشند و در هر با اجرا فقط یک حل به ما می دهند. اگر چه امروزه مسائل بهینه سازی چند هدفه می توانند بطور موفقیت آمیزی با بکارگیری نسخه ی چند هدفه الگوریتم های فرا ابتکاری از قبیل الگوریتم بهینه سازی مورچگان، الگوریتم بیهنه سازی ازدحام ذرات و الگوریتم ژنتیک و غیره حل شوند. این الگوریتم ها این توانایی را دارند که در هر بار اجرا تقریبی از مجموعه جواب های نامغلوب را بدست آورند.
بدون از دست دادن عمومیت مسئله، یک مسئله چند هدفه با اهداف مینیمم سازی را می توان بصورت زیر نمایش داد:

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

جاییکه فضای شدنی مسئله، یک بردار هدف می باشد که تابع هدف می بایستی مینیمم شوند و یک بردار تصمیم می باشد، یک حل شدنی است اگر باشد. تصویر فضای شدنی، که توسط مشخص می شود که به عنوان منطقه شدنی تابع هدف معروف است. عناصر مقادیر توابع هدف هستند که توسط یا مشخص می گردند، جاییکه به ازای مقادیر توابع هدف هستند. به فضای ، فضای متغییر های تصمیم و فضایی که مقادیر توابع هدف را در نظر می گیرد، فضای توابع هدف نامیده می شود.
اگر توابع هدف با یکدیگر در تضاد نباشند، آنگاه حلی می تواند پیدا شود که برای هر هدف مقدار بهینه اش را بدست آورده باشد. اگر چه در مسائل بهینه سازی چند هدفه همواره توابع هدف با یکدیگر در تضاد هستند ( برای مثال، بهبود در یکی از اهداف منجر به تنزل هدف دیگر می شود ) و ممکن است که هم مقیاس هم نباشند. در چنین مسائلی همواره بیش از یک نقطه بهینه وجود دارد، که این مجموعه نقاط بهینه همواره جواب های دیگر موجود در فضای جواب را شکست می دهند. این پاسخ های نامغلوب را مجموعه بهینه پارتو می نامند. همان طور که قبلاً گفته شد همواره در مسائل بهینه سازی چند هدفه تنها یک حل از پاسخ های موجود در مجموعه پارتو انتخاب می شود. در این مسیر تصمیم گیرنده (DM) نقش مهمی برای انتخاب حلی که اولویت های او را بهتر ارضا می کند، دارد. دیدگاه های مختلفی در ادبیات موضوع زمانیکه اولویت های تصمیم گیرنده به منظور هدایت جستجو مورد استفاده قرار می گیردند، در نظر گرفته شده اند[63].
بدون بیان اولویت : اولویت های تصمیم گیرنده در این مدل در نظر گرفته نمی شوند و مدل می تواند با یک روش ساده حل و پاسخ بدست آمده به تصمیم گیرنده ارائه می شود که آن را قبول یا رد خواهد کرد.
بیان اولویت پیشین : در این مدل نظرات و انتظارات تصمیم گیرنده قبل از انجام فرآیند جستجو در نظر گرفته می شود. این روش نیازمند این است که تصمیم گیرنده پیشاپیش اولویت هر از اهداف را بداند. از پیامد های ناشی از این روش می توان به این مورد اشاره کرد که تصمیم گیرنده در دادن اطلاعات کافی در مورد مدل با مشکل مواجه شود، به این دلیل که هیچ دانش و ایده ای در مورد آنچه که قابل حصول است، ندارد. علاوه بر این از میزان سازش میان توابع هدف مختلف آگاهی ندارد. سازش به این معنی است که با بهبود یک تابع هدف، توابع هدف دیگر به چه میزان تضعیف می شوند.
بیان اولویت پسین : در این مدل اولویتی از طرف تصمیم گیرنده در نظر گرفته نمی شود و بعد از حل مسئله و یافتن مجموعه پارتو، تصمیم گیرنده یک حل را از بین گزینه های موجود می پذیرد. عیب این روش هنگامی است که تصمیم گیرنده ممکن است در مجسم کردن جواب های مختلف و انتخاب از میان آن ها با مشکل مواجه شود، به ویژه اگر تعداد زیادی جواب برای مسئله ارائه شده باشد. با این وجود مسئله ی تصمیم گیری به طور قطع آسان تر شده است با توجه به این که تصمیم گیرنده آگاه است که چه جواب هایی امکان پذیر بوده اند. بنابراین روش اولویت پسین برخی از کارها را که در بهینه سازی پیشین به عهده تصمیم گیرنده می باشد به الگوریتم جستجو واگذار می کنند.
بیان اولویت تعاملی : در این مدل اولویت های تصمیم گیرنده بطور مداوم در طول فرآیند جستجو استفاده می شود و به عنوان تنظیم کننده ادامه مسیر جستجو می باشد.
زمانیکه مسئله بهینه سازی چند هدفه به یک مسئله ساده تک هدفه تبدیل می شود، تصمیم گیرنده قبل از مراحل بهینه سازی فراخوانی می شود. در این نمونه تصمیم گیرنده می بایستی اطلاعات کاملی در باره اولویت هر از اهداف داشته باشد. در حالت دیگر مسئله می تواند بعنوان یک مسئله بهینه سازی چند هدفه واقعی رفتار کند. در این مورد تصمیم گیرنده یا بعد از مراحل بهینه سازی و یا در طول فرآیند بهینه سازی فراخوانی می شود.
2-6-1- بهینگی پارتو
تعریف بهینگی برای مسائل چند هدفه بر مبنای مفهوم بهینگی پارتو می باشد. غلبه پارتو می تواند به منظور ارزیابی ارتباط بین دو حل کاندید در مسائل بهینه سازی چند هدفه مورد استفاده قرار بگیرد.