منابع پایان نامه با موضوع سلسله مراتب، پژوهشگران

معیاره از اواخر دهه ١۹٨۰ به طور جدی نظر محققان را به خود جلب کرد، اما اولین مقاله در زمینه حل مسائل چند معیاره توسط اسمیت در سال ١۹۵۶ منتشر شد. از آن زمان تاکنون مسائل زمان بندی چند معیاره از مدل های تک ماشینی به مسائل کارگاهی و ماشین های موازی و فرای آن ها ترقی یافت. از اواخر دهه ١۹۹۰ تاکنون نتایج به دست آمده در زمینه بهینه سازی چند معیاره، در حل مسائل زمان بندی در نظر گرفته شد ]66 [
مفاهیم پایه ای مسائل بهینه سازی چند هدفه
کلیات بهینه سازی چند هدفه
یک مساله بهینه سازی چند هدفه در حالت کلی به صورت زیر تعریف می شود:
که درآن توابع هدف ، X بردار متغیرها، و D مجموعه جواب های شدنی می باشند. (لازم به یادآوری است که در مسائل هیبریدی مانند زمان بندی، D یک مجموعه گسسته می باشد.)
همچنین یک جواب، جواب کارا نامیده می شود اگر شرایط زیر برقرار باشد:
جواب کارا می باشد هرگاه جواب دیگری در مجموعه D وجود نداشته باشد به طوری که به ازای هر K، باشد و به ازای حداقل یک K حالت تساوی برقرار نباشد]67 [. به جواب کارا، جواب بهینه پارتو نیز گفته می شود. شکل (6-1) نمونه ای از مجموعه جواب های ناچیره (یا پارتو) را نشان می دهد
نمونه ای از جواب های پارتو
برای درک بهتر مسائل چند هدفه، برای نمونه، دو معیار عملکرد و درنظر گرفته می شود. بدون از دست دادن کلیت مساله، فرض بر این است که این دو معیار باید حداقل شوند. معمولا با احتمال زیاد جوابی وجود ندارد که هر دو معیار را هم زمان حداقل سازد، از این رو باید از کیفیت جواب حداقل یک معیار به نفع دیگری مقداری چشم پوشی شود. اگر یکی از معیارها مثلا از اهمیت بیش تری برخوردار باشد، یک روش، یافتن جواب بهینه نسبت به این معیار (که با نشان داده می شود)، و یافتن بهترین جواب از نظر معیار در بین جواب های بهینه به دست آمده برای معیار می باشد. به این رویکرد بهینه سازی سلسله مراتبی87 یا لکسیکوگرافیک88 گفته می شود: در مرحله اول معیار مهم تر حداقل می شود، و در مرحله بعد معیار دوم با توجه به یک محدودیت اضافی حداقل می شود. می توان این رویکرد را با نماد نشان داد. اگر هیچ یک از دو معیار نسبت به هم برتری نداشته باشند، بهینه سازی لکسیکوگرافیک می تواند منجر به یک زمان بندی نامتوازن شود؛ در حالی که ممکن است امتیاز معیار دوم در قبال از دست دادن مقدار جزئی از امتیاز اول، بهبود چشمگیری داشته باشد. در این حالت، بهینه سازی هم زمان انتخاب مناسب تری خواهد بود ]68 [سه رویکرد متمایز در بهینه سازی هم زمان وجود دارد:
بهینه سازی با اولویتهای از پیش تعیین شده(مقدم)89، بهینه سازی تعاملی90، بهینه سازی با اولویت بندی موخر91،(منظور دخالت دادن نظرات تصمیم گیرنده در مراحل متفاوتی از بهینه سازی است). در حالت بهینه سازی مقدم، هر دو معیار در قالب یک تابع هدف هیبریدی، با یکدیگر ادغام می شوند؛ ، که در آن جواب بهینه (برنامه زمان بندی) به دست آمده برای تابع هیبریدی می باشد. تابع F می تواند خطی، غیرخطی، درجه دو و یا حتی غیر متعارف باشد. مثلا می تواند به صورت مجموع ضرایبی از دو معیار باشد که ضرایب نشان دهنده اهمیت نسبی آن ها خواهد بود. در این رویکرد دو مشکل عمده وجود دارد؛ مشکل اول در عمل ایجاد می شود: معمولا نوع تابع F ناشناخته و تعیین آن دشوار است. شخص مسئول ممکن است در قبال گزینه های مختلفی از برنامه زمان بندی، برنامه بهتر را تشخیص دهد؛ اما درک آن در قالب تابع F برای وی دشوار خواهد بود. مشکل دوم، دشوار بودن حداقل کردن تابع F به صورت مستقیم می باشد خصوصا وقتی که F غیر خطی باشد. دو راه برای غلبه به این مشکلات وجود دارد.
اولین راه حل دخالت دادن فعال تصمیم گیرنده در طول فرآیند حل مساله است. با به دست آوردن جواب در هر مرحله، تصمیم گیرنده باید موارد ترجیحی را مشخص کند و اگر جوابها راضی کننده نباشد، باید جهت جستجو را تعیین کند. به این سناریوی حل، بهینه سازی تعاملی گفته می شود. دومین راه حل برای مشکل ذکر شده، حل آن به شیوه ای پیچیده تر است. منطق پشت این روش بدین صورت است که از مجموعه جواب ها، زیر مجموعه ای انتخاب می شود که جواب های بهینه برای چندین تابع هیبریدی F (توابعی که به نظر مناسب می رسند)، در آن وجود داشته باشد، اگر تابع F مطلوب شناخته شده باشد، جواب بهینه از درون این مجموعه به دست می آید؛ اگر F را نتوان به طور صریح تعیین نمود، از تصمیم گیرنده خواسته می شود از بین جواب های موجود در مجموعه به دست آمده، جواب ترجیحی را انتخاب کند. به این رویکرد، بهینه سازی موخر گفته می شود، که مشکل ترین رویکرد از بین همه رویکردها می باشد؛ زیرا اگر مساله به این شیوه حل شود، مطمئنا به دو شیوه دیگر نیز مساله قابل حل است. باید توجه داشت، تنها محدودیتی که برای تابع F وجود دارد این است که این تابع باید نسبت به هردو آرگومان، غیر نزولی باشد ]67،68 [
مسائل بهینه سازی چند هدفه از نظر ارتباط توابع هدف با یکدیگر به سه حالت زیر تقسیم می شوند:
مسائلی که در آنها اهداف به طور کامل با یکدیگر در تضاد هستند.
مسائلی که در آنها اهداف هیچ گونه تضادی با یکدیگر ندارند.
مسائلی که در آنها اهداف به طور جزئی با یکدیگر در تضاد هستند]69[.
چیرگی پارتو92 و مجموعه حل های غیر غالب
مفهوم جوابهای غیرغالب و چیرگی پارتو از جملهی اساسیترین موضوعات بهینهسازی چند هدفه میباشند. برخلاف مسائل تک هدفه، که در آنها بهینگی یک معنای کاملا منحصر به فرد را داراست، در مسائل چند هدفه سه حالت ممکن بین راهحل های مختلف وجود دارد که بر اساس بهینگی پارتو تعریف میگردند.
تعریف 1: چیرگی پارتوی ضعیف: به طور ضعیف بر غالب است که با نشان داده می شود، اگر و فقط اگر به طوری که .
تعریف 2: چیرگی پارتوی قوی: به طور قوی بر غالب است که با نشان داده میشود، اگر و فقط اگر به طوری که و برای .
تعریف 3: چیرگی غیر قابل قیاس: غیر قابل مقایسه است با که با نشان داده میشود، اگر و فقط اگر به طوری که و برای .
مرز بهینه پارتو و مجموعه حل های بهینه پارتو
با توجه به تعاریف صورت گرفته برای مفهوم چیرگی پارتو، اکنون میتوان چگونگی انتخاب مجموعه جوابهای دلخواه را برای یک مسئلهی چند هدفه، به عنوان مجموعه جوابهای بهینه و همین طور مرز بهینهی تشکیل شده در فضای اهداف را به عنوان مرز بهینهی پارتو مشخص کرد. تعاریف زیر به این موضوع اشاره دارند:
تعریف 4: مرز بهینه ی پارتو: این مرز که با نمایش داده میشود، عبارت است از مجموعهی حلهای غیر غالب با توجه به فضای اهداف به طوری که:
تعریف 5: مجموعه حلهای بهینهی پارتو: این مجموعه که با نمایش داده میشود، عبارت است از مجموعه حلهایی که در فضای اهداف غیر غالب هستند، به طوری که:
به عبارت دیگر مجموعهی حلهایی که با یکدیگر تبادل93 مقداری دارند، به عنوان مجموعهی حلهای بهینهی پارتو شناخته میشوند. بردار اهداف مربوط به این راه حل ها “غیر غالب” نامیده میشوند. هر کدام از اهداف یک حل غیر غالب در مجموعهی حل های بهینهی پارتو تنها در صورتی بهبود مییابد که حداقل یکی دیگر از اهداف تنزل بهینگی دهد]69[.
مروری بر روش های حل مسائل بهینه سازی چند هدفه
در این باره رویکرد های مختلفی برای حل مسائل چند هدفه توسعه داده شده است. دسته بندیها و طبقه بندیهای مختلفی توسط پژوهشگران برای این گونه مسائل ارائه شده است. برخی از مهمترین این دسته بندیها در ادامه توضیح داده می شوند.
طبقه بندی بر اساس تعداد حل های بهینه به دست آمده
این نوع طبقه بندی به دو دستهی کلی تقسیم میگردد:
رویکرد تک هدفه 2- الگوریتم های تکاملی چند هدفه]70[.
طبقه بندی بر اساس روش حل
این تقسیم بندی که توسط کولت و همکاران ]71[ انجام شده است، شامل چهار گروه زیر میباشد:
روش های اسکالر
در این گونه از روش ها که به نام روش های اسکالر شناخته می شوند، اهمیت نسبی بین توابع هدف مختلف تعیین شده تا از این طریق بتوان آنها را در قالب یک تابع هدف معادل در نظر گرفت و مسأله را با رویکردهای بهینهسازی تک هدفه حل کرد. برخی از روش های اسکالر عبارتند از: روش جمع وزنی ، روش Keeney-Raiffa، روش جبرانی ، روش هیبریدی، روش دستیابی به هدف و … .
روش های تعاملی
همان طور که پیش از این نیز توضیح داده شد، این روش ها مبتنی بر اولویتدهی به توابع هدف در طی فرایند حل مسأله میباشد. این روش ها مانند روشهای اسکالر، مسأله ی مورد نظر را با تخصیص وزنهایی به توابع هدف، به یک تابع هدف معادل تبدبل میکنند. این روشها یکی از اساسیترین عیبهای روش قبلی را که تخصیص وزنهایی از پیش تعیین شده بود، بر طرف مینماید. به عبارتی دیگر، وزنهای تخصیص یافته به هر یک از اهداف، در طی فرایند حل مسأله از طریق روشی سیستماتیک بهبود مییابند.
از دیگر روش های تعاملی موارد زیر را می توان نام برد:
روش مرز بهینهی معادل
روش Fuandel
روش Jahn
روش های فازی
در این گونه روش ها با تعیین توابع عضویت مناسب برای هر یک از هدفها، دامنهی تغییرات مجاز برای آنها تعیین میگردد. سپس با استفاده از یک الگوریتم کارا، سطح مطلوبیت مشترک بین این توابع هدف به گونهای بهینه میگردد که مقدار هر یک از اهداف در دامنهی تعیین شده قرار گیرد و هر یک از توابع هدف بهینه گردند. میزان دقت این روش در به دست آوردن جواب های پارتو، بستگی دارد به دامنهی تعریف شده توسط تابع عضویت برای هر یک از اهداف دارد.
به طور کلی این گونه روشها را میتوان به دو دستهی اصلی زیر تقسیم نمود:
روش Sakawa
روش Reardon
روش های فرا ابتکاری
روش های فرا ابتکاری به عنوان روشهای بهینهسازی برای مسائلی تعریف میگردند که پیدا کردن جوابهای بهینه سراسری یا محلی مناسب برای آنها با افزایش ابعاد مسئله سختتر می گردد.
روش های فرا ابتکاری در یک دیدگاه کلی، به دو دسته ی زیر تقسیم بندی میگردند:
روشهای قطعی: این روشها با استفاده از یک رویکرد از پیش تعیین شده و غیر احتمالی، سعی میکنند تا حد امکان به جوابهای بهینهی سراسری دسترسی پیدا کنند.
روشهای غیر قطعی: این روش ها با استفاده از یک روش جستجوی تصادفی سعی میکنند تا به جواب های بهینهی سراسری دسترسی پیدا کنند. برخی از مهم ترین الگوریتمهای این دسته عبارتند از: الگوریتم ژنتیک، شبیهسازی تبرید، جستجوی ممنوع، شبکههای عصبی، الگوریتم ایمنی و … .
روش های پیشنهادی برای حل چند هدفه مسئله مورد مطالعه
در ادامه روش های استفاده شده در این تحقیق توضیح اده می شود.
برای حل مساله جریان کارگاهی دو مرحله ای انعطاف پذیر بدون وقفه به صورت چند هدفه از الگوریتم شبیه سازی تبرید استفاده شده است. دو تابع هدف در نظر گرفته شده برای این مساله مینیمم سازی ماکزیمم زمان اتمام کارها و مینیمم سازی ماکزیمم تاخیر می باشد. هر سه رویکرد استفاده شده در قالب الگوریتم شبیه سازی تبرید عمل می کند. این 3 رویکرد عبارتند از:
1- روش وزنی کلاسیک 2- روش مجموع وزنی نرمالایز شده 3- روش فازی
ساختار هر سه الگوریتم کاملا مشابه است. تفاوت آنها در تابع برازندگی آنهاست. در ادامه توابع برازندگی هر یک از انها توضیح داده خواهد شد.
روش وزنی کلاسیک
در این روش به هر یک از دو تابع هدف استفاده شده وزنی بین صفر تا یک داده شده و با یکدیگر به صورت وزنی جمع می شوند. در این تحقیق وزن ها به صورت صعودی 0.1 به یکی از آنها اضافه شده و 0.1 از دیگری کم می شود. در اینصورت 11 مجموعه عدد که مجموع آنها 1 خواهد بود داریم. به عبارت دیگر این رویکرد طبق معادله(6-2) به دست می آید.وزن های استفاده شده برای این روش در جدول (6-1) آمده است.

مطلب مشابه :  پایان نامه با کلید واژگان بازاریابی

دیدگاهتان را بنویسید