بخشی از مقاله
چکیده
مسالهی چیدمان دو سطری تسهیلات، عبارت است از قرار دادن تعدادی تسهیل مستطیل شکل با ابعاد متفاوت در دو سمت یک خط به طوری که مجموع هزینهی حملونقل حداقل گردد. حل این مساله به صورت دقیق زمانبر است، بنابراین برای حل آن الگوریتمهای ابتکاری و فراابتکاری مناسب میباشند. در این مقاله روشی دو مرحلهای پیشنهاد میشود که با استفاده از سادهسازی مساله به دو مسالهی چیدمان تک سطری بدست میآید.
این مسایل از تجزیهی مسالهی چیدمان دو سطری، با استفاده از ترکیب الگوریتم فراابتکاری مورچگان و جستجوی همسایگی متغیر حل میشوند . در انتها مسالهی چیدمان دو سطری با قرار دادن دو مسالهی چیدمان تک سطری بهبود یافته در کنار یکدیگر بدست میآید . با پیادهسازی این الگوریتم و مقایسهی آن با نمونهی بدست آمده از مرور ادبیات مشاهده میشود که زمان حل مساله به صورت چشمگیری کاهش و میزان اختلاف تابع هدف از بهترین جواب بدست آمده اندکی کاهش مییابد.
-1 مقدمه
چیدمان تسهیلات یکی از مسائل مهمی است که امروزه در صنایع تولیدی و غیرتولیدی مورد توجه قرار گرفتهاست. بطور کلی در چیدمان تسهیلات ترتیب قرارگیری اجزای فیزیکی یک سیستم تولیدی یا خدماتی و نحوهی تعامل بین این واحدها مشخص میگردد. چیدمان مناسب موجب روان بودن جریان مواد در کارخانه میشود، کارهای نیمه تمام و زمان کل تولید را کاهش داده و کارایی کل سیستم تولیدی را افزایش میدهد. بر طبق نظریه فرانسیس1، هزینه جریان مواد 20 تا 50 درصد کل هزینه های عملیاتی و هم چنین 15 تا 70 درصد هزینه یک محصول را در بردارد؛ چیدمان مناسب میتواند 10 تا 30 درصد در این هزینه صرفهجویی نماید .[1]
مسایل چیدمان تسهیلات به دو گروه کلی چیدمان بلاکی و چیدمان ماشین آلات تقسیم میشوند. چیدمان ماشینآلات به نحوه قرار گرفتن تسهیلات تولیدی در کنار یکدیگر گفته میشود. چیدمان ماشینآلات با توجه به سیستم حمل و نقل مواد شامل سه بخش چیدمان سطری2، چیدمان حلقهای3 و چیدمان خوشهای4 میباشند. همچنین چیدمان خطی تسهیلات نیز به سه نوع چیدمان تک سطری تجهیزات، چیدمان دو سطری تجهیزات و چیدمان چند سطری تسهیلات5 تقسیم میشوند.
2] مساله چیدمان تک سطری تجهیزات میتواند به شکل چیدمان نیم دایره ای6، چیدمان -U شکل7، چیدمان مارپیچ8 و چیدمان خطی9 مورد استفاده قرار گیرد بدون اینکه نوع مساله تغییر کند. در این مقاله به بررسی مساله چیدمان دو سطری تسهیلات میپردازیم. این مساله یکی از مسایل مهمی است که توجه محققان زیادی را به خود جلب کرده و به علت کاربرد وسیعش مورد استفاده قرار میگیرد.
-2 مرور ادبیات موضوع
مساله چیدمان دو سطری تسهیلات یک مساله -NP سخت است که نخستین بار در سال 2010 توسط چانگ10 و نیز تانچوکو11 مطرح شد. مساله چیدمان دو سطری تسهیلات ، عبارت است از قرار دادن تعدادی تسهیل مستطیل شکل با ابعاد متفاوت در دو سمت یک خط - راهرو - به طوری که مجموع هزینه حمل و نقل حداقل گردد .[3] چیس موری12 در سال 2013 در مقالهی خود مساله را با استفاده از پنج الگوریتم ابتکاری سازنده حل کرد. در این الگوریتمها ابتدا دو تسهیل انتخاب میشود و در دو سطر متفاوت قرار میگیرد بنابراین در شروع الگوریتم، هیچ تسهیلی در سطرها قرار نمیگیرند. در هر یک از روشها از قوانین متفاوتی جهت ساختن چیدمان نهایی استفاده میشود. هر یک از روشها به همراه قوانین چینش آنها عبارتند از:
-1 ابتدا تسهیلی انتخاب میشود که کمترین هزینهی مکان را دارد . - MinLCF -
-2 ابتدا تسهیلی انتخاب میشود که کمترین جریان را دارد . - MinFF -
-3 ابتدا تسهیلی انتخاب میشود که بیش ترین جریان را دارد . - MaxFF -
-4 ابتدا تسهیلی انتخاب میشود که کمترین عرض را دارد . - MinWF -
-5 ابتدا تسهیلی انتخاب میشود که بیش ترین عرض را دارد . - MaxWF -
چیس موری و همکارانش سه روش حل جدید را بر اساس مدل عدد صحیح مختلط خطی برای مساله چیدمان دو سطری ارایه نمودند. این روشها عبارتند از MaxFFMod، MinFFasym و. MaxFFasym تفاوت این روشها در معیار انتخاب تسهیلات برای ساختن چیدمان نهایی می-باشد. در انتها نیز، از روشهای جستجوی محلی برای بهبود روش MinFFasym استفاده شده است . - LS-MinFFasym - روشهای جستجوی محلی استفاده شده در مقالهی چیس موری عبارتند از:
- جابجایی یک تسهیل از مکان فعلیاش به مکان های سطر مقابلش
- انتخاب دو تسهیل از بین تمامیتسهیلات و جابجایی آنها
روش دیگری که برای حل مساله چیدمان دو سطری تسهیلات ارایه شد روش LS-Rand میباشد که در آن جواب اولیهای به صورت تصادفی ایجاد میشود و سپس به کمک روشهای جستجوی محلی فوق بهبود مییابد. این روش برای مشخص کردن میزان کارایی روش LS-MinFFasym ارایه شد.
-3 معرفی مسئله چیدمان دو سطری
مساله چیدمان دو سطری تسهیلات ، عبارت است از قرار دادن تعدادی تسهیل مستطیل شکل با ابعاد متفاوت در دو سمت یک خط - راهرو - به طوری که مجموع هزینه حمل و نقل حداقل گردد .[3] در این مساله برای حمل و نقل از سیستم هوشمند حمل و نقل - AGV - 13 استفاده میشود که در امتداد خطی مستقیم جابجاییها را از ماشینی به ماشین دیگر انجام میدهد. در یک چیدمان شدنی از این مساله بین تمامیتسهیلات مجاور، فضایی به عنوان حداقل فاصله 14 در نظر گرفته میشود. این فضا معمولا برای قطعات در جریان تولید15، فضای مورد نیاز نگهداری و تعمیرات و دسترسی به ماشینآلات مورد نیاز میباشد. شکل 1 نمونهای از یک چیدمان دو سطری تسهیلات را نشان میدهد.
-4 مدلسازی مسئله چیدمان دو سطری
برای مدلسازی مساله چیدمان دو سطری به صورت برنامهریزی عدد صحیح از پارامترها و متغیرهایی به شرح جدولهای 1 و 2 استفاده میشود.
