الگوریتم بهینه سازی ازدحام ذرات و الگوریتم های ترکیبی

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

معیار کیفیت : به منظور محاسبه این معیار، تمام حل های نامغلوبی که توسط الگوریتم های مختلف بدست آمده است را با هم ترکیب می شوند، در بین آنها رقابتی ایجاد می شود و در نهایت حل هایی که نامغلوب هستند را استخراج و سپس درصد حل هایی که متعلق به هر الگوریتم است را محاسبه می کنیم. برای این معیار عملکردی، الگوریتم با بیشترین مقدار عملکرد بهتری دارد.
2-7- مسائل زمانبندی ماشین های موازی چند هدفه
در ادبیات موضوع، تمرکز بیشتر محقیق روی زمانبندی ماشین های موازی با در نظر گرفتن یک هدف بوده است. اگر چه تعدادی پژوهش وجود دارد که به بررسی زمانبندی ماشین های موازی چند هدفه پرداخته اند که ما در ادامه ی این بخش به بررسی آن ها می پردازیم. کوچران و همکاران [66] الگوریتم ژنتیک چند جمعیتی دو مرحله ای را برای زمان بندی دو هدفه ماشین های موازی یکسان با هدف کمینه سازی همزمان بیشینه زمان تکمیل کارها و مجموع وزنی دیرکرد کارها پیشنهاد دادند. در مرحله اول الگوریتم، توابع هدف به روش وزن دار کردن به یک هدف تبدیل می شوند. پاسخ های بدست آمده از مرحله اول در گروه های مختلف جمعیتی قرار می گیرند. این گرو ه های جمعیتی بعنوان جمعیت اولیه برای مرحله دوم الگوریتم می باشند. در این مرحله در هر گروه جمعیتی با استفاده از استراتژی نخبه گرایانه حل های که دارای بهترین مقدار از هر تابع هدف و بهترین مقدار ترکیب آن ها را دارند حفظ می شوند. آن ها همچنین از این الگوریتم برای حل مسئله مذکور با در نظر گرفتن سه تابع هدف بطور همزمان که شامل دو تابع هدف قبلی و مجموع وزنی زمان تکمیل کارها می باشد استفاده نمودند. چی یو و چانگ [67] مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود زمان آماده سازی وابسته به توالی به منظور کمینه سازی همزمان مجموع وزنی زمان در جریان و مجموع وزنی دیرکرد کارها را در نظر گرفتند. آن ها برای این مسئله چهار الگوریتم پیشنهاد کردند که دوتای آن ها بر مبنای الگوریتم شبیه سازی تبرید چند هدفه که تفاوت آن ها فقط در استراتژی پذیرش بوده و دوتای دیگر بر مبنای الگوریتم ژنتیک همگرایی پارتو که تفاوت آن ها فقط در نحوه نمایش کروموزومی بوده است. در یکی از الگوریتم ها از نمایش کروموزومی حالت پیوسته و دیگری از حالت گسسته استفاده شده است. آن ها با ارزیابی الگوریتم ها از طریق ایجاد مثال های تصادفی به این نتیجه رسیدند که الگوریتم ژنتیک همگرایی پارتو که دارای نمایش کروموزومی پیوسته می باشد از عملکرد بهتری برخوردار است. همان طور که در بخش محدودیت دسترسی به ماشین ها صحبت شد، جاوو [47] مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود محدودیت های دسترسی محدود به ماشین ها با هدف کمینه سازی همزمان بیشینه زمان تکمیل کارها و مجموع زودکرد و دیرکرد کارها مورد بررسی قرار داد. برای حل این مسئله نسخه چند هدف الگوریتم سیستم ایمنی مصنوعی پیشنهاد شده است. قره گوزلی و همکاران [68] مسئله زمان بندی ماشین های موازی یکسان با فرض محدودیت های زمان آماده به کار متفاوت و زمان های آماده سازی وابسته به توالی و فرض فازی بودن زمان پردازش کارها به منظور کمینه سازی همزمان مجموع وزنی زمان در جریان و مجموع وزنی دیرکرد کارها را در نظر گرفتند. آن ها برای غلبه بر این مسئله یک مدل برنامه ریزی آرمانی عدد صحیح مخلتط فازی ارائه دادند. بچری و همکاران [69] مسئله زمانبندی تولید و نگهداری ماشین های موازی یکسان به منظور کمینه سازی همزمان بیشینه زمان تکمیل کارها و زمان دردسترس نبودن ماشین ها را در نظر گرفتند. آن ها برای این مسئله الگوریتم های مورچگان چند هدفه(MOACO)، ژنتیک با مرتب سازی نامغلوب (NSGA-) و نسخه دوم الگوریتم تکاملی مبتنی بر قوت پارتو (PESA-) ارائه کردند. نتایج محاسباتی بدست آمده حاکی از عملکرد بهتر الگوریتم (MOACO) برای حل مسئله مورد نظر است. بهنامیان و همکاران [70] مسئله زمانبندی ماشین های موازی یکسان با محدودیت زمان آماده سازی وابسته به توالی را با هدف کمینه سازی همزمان بیشینه زمان تکمیل کارها و مجموع دیرکرد و زودکرد کارها را در نظر گرفتند. آن ها با استفاده از روش وزن دهی مسئله مورد نظر را به یک مسئله تک هدفه تبدیل کردند و با استفاده از الگوریتم های ترکیبی آن را حل نمودند. باندی و هاتاچاریا [71] مسئله زمانبندی ماشین های موازی نامرتبط با فرض وجود زمان آماده سازی وابسته به توالی کارها و هزینه ناشی از زوال پذیری کارها و ماشین ها با هدف کمینه سازی همزمان سه تابع هدف که شامل هزینه ناشی از دیرکرد کارها، بیشینه زمان تکمیل کارها و هزینه ناشی از زوال پذیری می باشد، را در نظر گرفتند. آن ها برای این مسئله یک الگوریتم اصلاح شده ژنتیک با مرتب سازی نامغلوب (NSGA-) را پیشنهاد دادند. آن ها برای ارزیابی عملکرد الگوریتم پیشنهادی آن را با نسخه اصلی الگوریتم (NSGA-) و الگوریتم (PESA-) مقایسه کردند. نتایج محاسباتی نشان دهنده کارایی بهتر الگوریتم پیشنهادی آن ها دارد. ترابی و همکاران [72] یک الگوریتم بهینه سازی ازدحام ذرات چند هدفه (MOPSO) برای مسئله زمانبندی ماشین های موازی نامرتبط با فرض محدودیت های زمان آماده به کار متفاوت، زمان های آماده سازی وابسته به توالی کارها و وجود منبع دوم ( یعنی کارها علاوه بر ماشین ها به منابع دیگری هم نیاز دارند که مقدار آن ها محدود است ) و با فرض فازی بودن زمان پردازش کارها و زمان تحویل به منظور کمینه سازی همزمان مجموع وزنی زمان در جریان، مجموع وزنی دیرکرد کارها و اختلاف بار کاری بین ماشین ها پیشنهاد دادند.

این مطلب مشابه را هم بخوانید :   اندازه گیری رضایت مندی مشتری و مدیریت بازاریابی خدمات

فصل سوم
مدل ریاضی پیشنهادی
3-1- مقدمه
تعیین توالی و زمانبندی در سیستمهای پیشرفته تولیدی و خدماتی از اهمیت ویژهای برخوردار است. اقتصادی بودن این سیستمها مشروط به داشتن یک مدل برنامهریزی تعیین توالی و زمانبندی مناسب میباشد. در هر مسئله زمانبندی هدف و یا اهدفی مورد توجه می باشند که میزان موفقیت برای رسیدن به این هدف (اهداف) تا حد زیادی به مدل پیشنهاد شده برای مسئله بستگی دارد. بنابراین در وهلهی اول ایجاد یک مدل ریاضی دقیق میتواند تا حد زیادی رسیدن به اهداف مورد نظر را میسر سازد.
در بسیاری از مسائل زمانبندی در محیطهای تولیدی و خدماتی، مدلهای ریاضی میتوانند ابزار مفید و در عین حال لازم برای تعیین توالی بهینه باشند. رویکرد برنامهریزی عدد صحیح به عنوان یک روش دقیق، ظرفیت عملکردی محدودی در بهینه سازی مسائل زمانبندی در زمان محاسباتی معقول دارد..
در این فصل، ابتدا به تعریف مسئله و مفروضات مرتبط با آن میپردازیم و در ادامه، برای مسئله یاد شده یک مدل برنامهریزی عدد صحیح مختلط ارائه میشود. در ادامه به بررسی درستی عملکرد مدل پیشنهادی و تحلیل حساسیت مدل نسبت به تغییر در مقادیر پارامترهای ورودی میپردازیم. قابل توجه اینکه به علت پیچیدگی بالای مسئله مورد نظر و از آنجاییکه که بهینه سازی همزمان دو تابع هدف مدنظر است، کاربرد الگوریتمهای فراابتکاری را اجتناب ناپذیر میسازد. برای حل این مسئله دو الگوریتم فراابتکاری پیشنهاد شده است که در فصل بعدی به توضیح کامل آن میپردازیم.
3-2- تعریف مسئله
مجموعهای از کار متمایز، ، بر روی مجموعهای از ماشین که بصورت موازی قرار گرفته اند پردازش میشوند. ماشینها نامرتبط بوده و زمان پردازش یک کار روی ماشینهای مختلف یکسان نمیباشد. پردازش هرکار تنها بر روی یک ماشین انجام میشود و هر ماشین در هر لحظه قادر به انجام تنها یک پردازش از هر کار میباشد. پردازش هر کار بر روی زیر مجموعهای از ماشینها میتواند پردازش شود که به این مجموعهها در اصطلاح مجموعههای پردازشی گفته میشود. کارها از هم مستقل نمیباشند و یک رابطه پیش نیازی بین کارها وجود دارد. این محدودیت بیان کننده این است که بعضی از کارها نمی توانند شروع شوند مگر اینکه کارهای پیش نیاز آنها انجام شده باشند. قبل از آغاز پردازش هر کار روی هر ماشین، به منظور آماده سازی آن ماشین برای پردازش آن کار عملیاتی انجام میگیرد که از آن به عنوان عملیات نصب روی ماشین یاد میشود و به مدت زمان مورد نیاز که برای عملیات آمادهسازی ماشین صرف میشود، زمان نصب ماشین اطلاق میشود. این زمان به نوع کار فعلی و کار قبلی و به نوع ماشینی که پردازش روی آن صورت میگیرد بستگی دارد. از طرفی تمام کارها در ابتدای افق زمانبندی دردسترس نیستند و زمان دسترسی به کارها متفاوت میباشد. معیارهای کمینه سازی میانگین وزنی زمان در جریان و میانگین وزنی دیرکرد کارها بطور همزمان در نظر گرفته شده اند.
مسئلهی درنظر گرفته شده در این تحقیق از یک مسئله واقعی در صنعت کشتی سازی الهام گرفته شده است. در این صنعت ابتدا تمامی قسمتهای مختلف یک کشتی اعم از بخشهای مختلف بدنه، عرشه، موتور و غیره … در کارگاه های مخصوص به خود ساخته میشوند و پس از اینکه تمامی مراحل ساخت آنها به پایان رسید تمامی این بلوکهای مونتاژی توسط جرثقیلهای غول پیکری از محل ذخیره سازی بلوکها به سکوی مونتاژ و محل نصب آنها حمل میشوند. مسئلهای که در این قسمت پیش میآید این است که کدامیک از بلوکهای مونتاژی توسط کدامیک از جرثقیلها میبایستی حمل شود و توالی حمل بلوکهای مونتاژی روی هر جرثقیل به چه صورت میباشد. مشخص است که این مسئله قابل تبدیل به یک مسئله زمانبندی ماشینهای موازی میباشد که جرثقیلها همان ماشینها و بلوکهای مونتاژی همان کارهای ما میباشند. بلوکهای مونتاژی دارای روابط پیشن نیازی پیچیده میباشند و از طرفی دیگر هر یک از جرثقیلها توانایی تحمل یک بار کاری بخوصی را دارند و برخی از قطعات که ابعاد بزرگ دارند توسط جرثقیل بخصوصی حمل میشوند، در نتیجه محدودیت دسترسی به ماشینها هم در این مسئله وجود دارد. وقتی عملیات نصب یک بلوک مونتاژی به پایان رسید مدت زمانی که نیاز است تا جرثقیل حرکت کند و بلوک مونتاژی بعدی را بردارد و به محل مونتاژ آن ببرد میتواند بعنوان زمان آماده سازی وابسته به توالی کارها و نوع ماشینها تعریف شود.
3-2-1- مفروضات مسئله
1. تمامی ماشین ها در لحظه زمانی صفر آماده به کار می باشند.
2. تمامی ماشین ها بطور مستمر در دسترس می باشند و امکان خرابی ماشین ها وجود ندارد.
3. هر ماشین در هر لحظه قادر به پردازش تنها یک کار می باشد.
4. بیکاری ماشین ها مجاز است.
5. زمان پردازش کارها روی ماشین های مختلف یکسان نمی باشد.
6. کارها دارای زمان های آماده سازی وابسته به توالی پردازش کارها و نوع ماشین ها می باشند، بعلاوه کارها دارای زمان آماده سازی اولیه می باشند که بستگی به نوع ماشین ها دارد.
7. هر کار در طول زمان پردازش خود تنها بر روی یک ماشین پردازش می شود و امکان شکست کارها وجو ندارد.
8. تمامی کارها در لحظه زمانی صفر آماده پردازش نمی باشند و زمان های آزاد سازی متفاوتی دارند.