بخشی از مقاله
چکیده
این نوشتار یک روش کارامد برای بهینه سازی مساله چیدمان تسهیلات نابرابر ارائه می شود. در این روش، الگوریتم ژنتیک بهبود یافته و به الگوریتم ژنتیک تطبیقی توسعه داده می شود. در این الگوریتم عملگر جهش فقط زمانی اعمال می شود که میزان شباهت کروموزوم ها در هر جمعیت به حد خاصی برسد. این هوشمند سازی، از اعمال جهش در شرایطی که نیاز به آن نیست جلوگیری کرده و موجب کاهش زمان محاسباتی می شود. به منظور سنجش کارایی الگوریتم پیشنهادی عملکرد آن با عملکرد الگوریتم های ژنتیک معمولی و شبیه ساز تبرید مقایسه می شود. نتایج محاسباتی نشان می دهد که الگوریتم ژنتیک تطبیقی قادر است تا به جواب های با کیفیت تری دست پیدا کند.
-1 مقدمه
تعیین مکان استقرار هریک از تسهیلات، اغلب به عنوان مساله چیدمان تسهیلات شناخته شده است. تسهیل می تواند یک واحد تولیدی، ساختمان اداری و یا ماشین های درون کارخانه باشد. انتخاب محل مناسب برای تسهیلات تاثیر قابل توجهی بر هزینه های تولید، کار در جریان، زمان تولید و بهره وری سیستم های تولیدی دارد. 20 تا 50 درصد کل هزینه های تولید درون یک کارخانه تولیدی مربوط به هزینه های حمل و نقل می باشد. مکیندال و شانگ - 2006 - 1 این امر سبب می شود که در صورت عدم بهینه بودن چیدمان تسهیلات مختلف مبالغ هنگفتی صرف حمل و نقل مواد و در نتیجه افزایش هزینه های سیستم گردد. بنابران توسعه مدل های ریاضی و الگوریتم های بهینه یابی برای مسئله چیدمان تسهیلات همواره مورد توجه پژوهشگران بوده است.
مسئله چیدمان تسهیلات اغلب به شکل مسئله تخصیص نمایی مدل می شود که در آن هدف قرار دادن تسهیلات با اندازه های برابر در موقعیت های از پیش تعریف شده است. برابر در نظر گرفتن اندازه تسهیلات می تواند مسئله را از مسائل دنیای واقعی دور کند. بنابراین در این تحقیق فرض برابر بودن اندازه تسهیلات آزاد شده و به تسهیلات اجازه داده می شود تا اندازه های نابرابر داشته باشند. با توجه به اینکه اندازه تسهیلات نابرابر بوده مساله از حالت تخصیص نمایی خارج شده و به شکل یک مدل ریاضی خطی فرموله می شود.
تاکنون تحقیقات زیادی بر روی مساله چیدمان تسهیلات انجام شده است. سمرقندی و عشقی - 2010 - 2 یک مسئله با چیدمان تک ردیفی با تسهیلات دارای اندازه نابرابر را با استفاده از یک الگوریتم جستجوی ممنوع دارای حافظه انطباقی برای روشهای تنوع و تشدید، برای یافتن راه حل های موجود در همسایگیِ راه حل خوب و راه حل هایی که هنوز یافته نشده اند، حل کردند. نی و جیانگ - 2013 - 3 یک روش مدلسازی را توسعه دادند که به واسطه آن چیدمان تسهیلات در کارخانجات و در زمان واقعی، به راحتی میسر می گشت.
این مدل که بر اساس الگوریتم ژنتیک و با بهره گیری از روش تحلیل سلسله مراتبی عمل می کند. او و سونگ - 2015 - 4 مسئله چیدمان تسهیلات را در حالت پویا و با درنظرگرفتن اندازه تسهیلات نابرابر بررسی کردند. آنها هزینه جابجایی بین ماشین ها را به شکل پارامترهای فازی لحاظ کردند و تسهیلات را به شکل اشکال دو بعدی تصور کردند. سپس مسئله پیشنهادی را با استفاده از الگوریتم بهینه سازی اجتماع ذرات بهینه کردند.
در نهایت کارایی الگوریتم پیشنهادی با استفاده از یک مطالعه موردی بررسی و اثبات شد. وانگ و همکاران - 2015 - 5 یک روش حل مسائل چیدمان تسهیلات دو ردیفه با ترکیب الگوریتم شبیه ساز تبرید و برنامه ریزی ریاضی از سوی پیشنهاد شد که در نهایت مشخص شد این روش قابلیت تعیین راه حل بهینه برای مسائل با اندازه کوچک و نیز تعیین یک روش واقعی برای مسائل با سایزهای واقعی را دارد. آلوتاس و ایزلر - 2015 - 6 تحقیقی در یک کارخانه تولید کفش جهت حل مسئله چیدمان تسهیلات پویا توسط و با هدف کمینه کردن مجموع مواد حمل شونده و نیز هزینه های بازچیدمان با در نظرگیریِ چند دوره کاری، انجام دادند.
بدین ترتیب یک الگوریتم مبتنی بر کلونی مورچگان برای حل مسئله چیدمان تسهیلات پویا پیشنهاد شد که نهایتا در مقایسه با آزمایش ها و نتایج عددی که حاصل می شد روش پیشنهادی از عملکرد مناسب تری برخوردار بود. نقابی و تاری - 2016 - 1 بر اساس روابط نزدیکی تسهیلات یک رویکرد جدید برای مسئله چیدمان پیشنهاد دادند. در این رویکرد بر اساس میزان نزدیکی تسهیلات یک امتیاز خاص به طرح داده می شود. همچنین به منظور اعمال شاخص های ایمنی دور بودن بعضی تسهیلات نیز امتیاز محسوب می شود.
آنها یک مدل ریاضی برای مسئله پیشنهاد دادند و کارایی آن را با استفاده از آزمایش های محاسباتی سنجیدند. نتایج محاسباتی کارامدی مدل پیشنهادی را در لحاظ کردن همزمان معیارهای اقتصادی و ایمنی و ایجاد طرح های چیدمان متنوع اثبات کرد. گوان و لین - 2016 - 2 یک الگوریتم ترکیبی برای بهینه سازی مسئله چیدمان تسهیلات پیشنهاد دادند. الگوریتم پیشنهادی بر اساس ترکیب دو الگوریتم جستجوی همسایگی متغیر و کلونی مورچگان بود. آنها سه ساختار همسایگی کارامد پیشنهاد دادند و همچنین یک تکنیک جدید به منظور کاهش زمان محاسباتی در محاسبه تابع هدف ارائه کردند. از طرف دیگر یک روش جدید برای به روزرسانی فرمول ها در الگوریتم کلونی مورچگان به کار گرفته شد.
آن ها از مسائل استاندارد موجود در ادبیات به منظور ارزیابی الگوریتم استفاده کردند و برتری آن را نسبت به روش های قبلی اثبات نمودند. پاس3 و همکاران - 2017 - دو الگوریتم فراابتکاری ژنتیک ترکیبی برای حل مسئله چیدمان تسهیلات با اندازه های نابرابر ارائه دادند. الگوریتم های پیشنهادی با روش های موجود در ادبیات مقایسه شد و نتایج محاسباتی نشان داد که الگوریتم ژنتیک ترکیبی به جواب های باکیفیت تر در زمان کمتر دست پیدا می کند. باقیمانده این نوشتار به صورت زیر سازماندهی شده است: در بخش دوم ارتباطات ریاضی و مدل سازی مسئله را تشریح میکند. بخش سوم به طرح الگوریتم پیشنهادی می پردازد. در بخش چهارم پس از تنظیم پارامترهای الگوریتم پیشنهادی، نتایج حاصل از بکارگیری الگوریتم پیشنهادی ارائه میگردد. در نهایت در بخش پایانی نتیجهگیری و پیشنهاداتی برای کارهای آتی بیان میگردد.
-2 معرفی مساله
هدف اساسی این مدل تعیین مکان تسهیلات است به گونه ای که هزینه های جابجایی بین تسهیلات حداقل شود. با توجه به اینکه اندازه این تسهیلات نابرابر بوده می بایست مساله چیدمان با فرض نابرابر بودن تسهیلات بررسی شود. در چنین شرایطی مساله به شکل یک مدل ریاضی خطی فرموله می شود. هدف اساسی این مدل تعیین مکان تسهیلات است به گونه ای که هزینه های جابجایی بین تسهیلات حداقل شود.
بدین منظور می بایست موقعیت مرکز هر تسهیل و افقی یا عمودی بودن آن مشخص شود. از طرفی با توجه به محدودی فضا، تمامی تسهیلات باید به گونه ای چیده شوند که هیچ گونه همپوشانی - روی هم افتادگی - بین تسهیلات ایجاد نشود. هریک از تسهیلات مجازند تا در هر قسمت فضای در دسترس قرار بگیرند. در قسمت بعد مدلی برای پاسخ به این پرسش ارائه می شود. همچنین فرضیات در نظر گرفته شده در مدل ریاضی به قرار زیر است:
• تسهیلات مربعی-مستطیلی شکل با اندازه های نا برابراند.
• طول، عرض و مساحت مورد نیاز هر تسهیل از قبل مشخص است.
• فضای کل در دسترس محدود است.
• میزان جابجایی بین تسهیلات قطعی و از قبل مشخص است.
• فاصله بین تسهیلات اقلیدسی مرکز به مرکز در نظر گرفته می شود.
