بخشی از مقاله
چکیده
طراحی چیدمان کارا نقش بسزایی در کاهش هزینههای تولیدی دارد. مساله طراحی چیدمان مبتنی بر ساختار نواری منعطف1 یک مساله -NP سخت است، که هدف آن قرار دادن n تسهیل در یک چیدمان مستطیل شکل و به صورت ردیفی میباشد بهطوریکه مجموع وزنی جریان بین تسهیلات حداقل گردد. برای حل مساله ساختار نواری منعطف روشهای دقیق متعددی پیشنهاد شده است اما استفاده از روشهای دقیق در اندازه های عملی کارایی لازم را ندارند. از اینرو در اکثر مقالات به منظور حل این مسائل برای دستیابی به جوابهای مناسب از روشهای ابتکاری و فراابتکاری استفاده شده است.
در این مقاله با استفاده از روشی دو مرحلهای به حل مساله ساختار نواری منعطف می-پردازیم. در مرحلهی اول، مساله را به چند مساله چیدمان تک سطری2 تبدیل میکنیم و هر یک از سطرها را با روش ترکیبی الگوریتم خفاش3 و جستجوی همسایگی متغیر4 حل میکنیم. در گام دوم نیز با استفاده از جواب مرحله قبل به حل مساله ساختار نواری منعطف میپردازیم. در انتها نیز با روش-های همسایگی متعددی جواب بدست آمده را بهبود میدهیم و جواب بدست آمده را با حالتی که از الگوریتم پیشنهادی استفاده نشود مقایسه میکنیم.
واژگان کلیدی: ساختار نواری منعطف، چیدمان تکسطری تسهیلات، الگوریتم فراابتکاری خفاش، جستجوی همسایگی متغیر
مقدمه
فرآیند چیدمان تسهیلات شامل جانمایی و استقرار تسهیلات در کارخانه و طراحی سیستم جریان مواد میباشد. این فرآیند تاثیر بسزایی در هزینههای ساخت، موجودی در جریان ساخت و زمانهای تحویل و بهرهوری دارد. یک چیدمان کارا میتواند 20 تا 50 درصد از کل هزینه های عملیاتی را کاهش دهد . - Richard & White, 1974 - چیدمان مناسب موجب روان بودن جریان مواد در کارخانه میشود، کارهای نیمه تمام و زمان کل تولید را کاهش داده و کارایی کل سیستم تولیدی را افزایش میدهد.مساله طراحی چیدمان تسهیلات برای اولین بار در سال 1963 توسط آرمور و بوفا - Armour & Buffa, 1963 - ، فرمولبندی شد. هدف از طراحی بهینه یک چیدمان، تعیین محل هر تسهیل یا دپارتمان میباشد؛ به نحوی که هزینه انتقال مواد بین دپارتمانها حداقل شود. محدودیت های رایج در طراحی چیدمان عبارتند از:
1.همه دپارتمانها باید در داخل یک تسهیل با ابعاد مشخص قرار بگیرند، بطوری که هیچ کدام از دپارتمانها همپوشانی نداشته باشند.
2.در چیدمان طراحی شده، محدودیت بیشینه نسبت ابعاد یا کمینه طول کنارهها برای هر دپارتمان برآورده شود.
مساله ساختار نواری منعطف یکی از مسائل مهمی است که توجه محققان زیادی را به خود جلب کرده و به علت کاربرد وسیعش مورد استفاده قرار میگیرد. در این مقاله به بررسی مساله ساختار نواری منعطف پرداخته میشود و روش جدیدی برای حل آن پیشنهاد میشود.
-1 مرور ادبیات
مسأله چیدمان تسهیلات با مساحتهای نابرابر یکی از مهمترین مسائل چیدمان تسهیلات بلاکی میباشد. در این مسائل دو ساختار خاص برای چیدمان تسهیلات وجود دارد، که عبارتند از ساختار نواری منعطف و ساختار گیوتینی. ساختار نواری منعطف برای اولین بار در سال 1991 توسط تانگ - Tong, 1991 - 5، ارائه شد. در ساختار نواری منعطف، دپارتمانها در نوارهای افقی یا عمودی قرار میگیرند و هر دپارتمان تنها میتواند در یک نوار قرار بگیرد. دپارتمانهایی که در یک نوار قرار میگیرند عرض مساوی دارند. بدلیل -NP سخت بودن مساله طراحی چیدمان ، استفاده از روشهای دقیق در اندازههای عملی کارایی لازم را ندارند. از اینرو در اکثر مقالات به منظور حل این مسائل برای دستیابی به جوابهای مناسب از روش های ابتکاری و فراابتکاری استفاده شده است.
در طی سالیان اخیر محققین زیادی در زمینه مساله چیدمان تسهیلات کار کردهاند. کوناک و همکاران یک مدل برنامهریزی صحیح آمیخته6 برای مساله چیدمان تسهیلات با استفاده از ساختار نواری منعطف ارائه کردند - Konak, . - Kulturel-Konak, Norman, & Smith, 2006 کواردیان و وانگ برای حل مسئله چیدمان تسهیلات با ساختار نواری منعطف با مساحت های نابرابر، الگوریتم مورچگان را بکار برده و برای بهبود کارایی جستجو از چند نوع الگوریتم جستجوی محلی استفاده کردند. تابع هدف این مسئله کمینه کردن هزینه انتقال مواد بین دپارتمانها است و فاصله بین دپارتمانها به صورت مرکز به مرکز در نظر گرفته شده است.
آنها چندین مسئله با اندازه های مختلف را با الگوریتم پیشنهادی حل کردند. نتایج بدست آمده نشان دهنده این است که الگوریتم میتواند بهترین مسائل حل شده قبلی، به خصوص برای مسائل با اندازه بزرگ، بهبود بدهد . - Wong, 2010 - کولترل یک مدل برنامه ریزی خطی برای حل مسئله چیدمان تسهیلات با مساحت های نابرابر و با ساختار نواری منعطف ارائه کردند . - Kulturel-Konak, 2012 - بوذر و وانگ برای حل مسئله چیدمان تسهیلات با مساحتهای نابرابر، با بکارگیری روش تبرید شبیه سازی شده روشی برای ایجاد چیدمانهای مختلف ارائه نمودند.
آنها ابتدا نظیر هر چیدمان یک زوج گراف معرفی نمودند که در هر گراف تعداد گرهها برابر با تعداد دپارتمانها میباشد. در یکی از دو گراف موقعیت چپ و راست بودن هر زوج دپارتمان نسبت به یکدیگر، و در گراف دیگر موقعیت بالا یا پایین بودن هر دو دپارتمان نسبت به یکدیگر نشان داده شده است. آنها نشان دادند که نظیر هر دو دپارتمان تنها کافی است یک یال در یکی از دو گراف رسم شود. علاوه بر آن آنها نشان دادند که هر زوج گراف بصورت یکتا یک چیدمان را نشان میدهد. از این رو برای طراحی چیدمانهای مختلف کافی است که گراف آنها طراحی شود.
برای طراحی گراف یک مدل عدد صحیح ارائه نمودند و با حذف متغیرهای دودویی7 با توجه به خواص زوج گراف، توانستند مدلی ساده را برای طراحی گراف ارائه نمایند. بدین ترتیب قادر به حل مسائلی با اندازه های بزرگ در زمان قابل قبول شدند. نتایج حاصل شده نشان دهنده این است که با استفاده از روش ارائه شده میتوان مسائل با اندازه بزرگ را در زمان کمتر و با کیفیت حل بهتر انجام داد . - Bozer & Wang, 2012 - در سال 2013 مصطفی مازیانی مساله چیدمان تسهیلات پویا را با استفاده از مساله چیدمان نواری منعطف و با بکارگیری الگوریتم ژنتیک حل کرد . - Mazinani, Abedzadeh, & Mohebali, 2013 -
-2 تعریف مساله
در ساختار نواری منعطف، دپارتمانها در نوارهای افقی یا عمودی قرار میگیرند و هر دپارتمان تنها میتواند در یک نوار قرار بگیرد. دپارتمانهایی که در یک نوار قرار میگیرند عرض مساوی دارند. یکی از مزیتهای ساختار نواری منعطف این است که نوارها را میتوان بعنوان راهروها در نظر گرفت، از اینرو میتوان چیدمان بدست آمده را یک چیدمان واقعی در نظر گرفت.
