مسئله طراحی و چیدمان تسهیلات: مدل سازی مسئله (بخش سوم)

مقدمه

تفاوت در خصوصیات در نظر گرفته شده در مسئله، استاتیک و یا داینامیک بودن مسئله و دیگر ملاحظات، انواع مختلفی از فرموله کردن مسئله چیدمان تسهیلات را نتیجه می دهد. مدل های مختلفی از مسائل چیدمان تسهیلات با در نظر گرفتن فرض های متفاوتی در ادبیات به چشم می خورد. اما با وجود گوناگونی های بسیار زیاد موجود در ادبیات شاید بتوان انواع مدل های ارائه شده در مسائل را به چند دسته کلی تقسیم کرد.

رویکردهای کلان در مدل سازی مسئله چیدمان تسهیلات

مهمترین و پرکاربردترین نوع مدل سازی مسائل چیدمان تسهیلات QAP می باشد. QAP به طور گسترده ای برای حل مسائل چیدمان به کار رفته و روش های حل متفاوتی برای آن ارائه شده است. (Amine et al.,2007) دسته دیگری از روش ها را می توان روش هایی دانست که با استفاده از مباحث مطرح شده در تئوری گراف اقدام به مدل سازی و حل مسئله چیدمان تسهیلات می کند. دسته دیگر مسائلی هستند که با استفاده از MIP اقدام به مدل سازی مسئله کرده اند. در بخش آتی این مقاله انواع مدل سازی های مطرح شده در ادبیات تحت عنوان روش های دیگر طبقه بندی شده است. این دسته شامل مباحثی مانند فرموله کردن فازی، استفاده از برنامه ریزی چندهدفه و فرموله کردن پیوسته می باشد.

مدل سازی مسئله چیدمان تسهیلات با استفاده از روش QAP

فرموله کردن به صورت Quadratic Assignment Problem (QAP) در طراحی چیدمان برای مستقر کردن تسهیلات با اندازه برابر استفاده می شود. تا به حال این نوع از مدل سازی در تعداد زیادی از مسائل طراحی چیدمان در ادبیات به کار رفته است. این روش با تخصیص یک تسهیل به هر مکان و هر مکان فقط به یک تسهیل عمل می کند و سعی دارد هزینه اختصاص تسهیلات را به مکان ها که به صورت یک تابع هدف درجه۲ بیان می شود کمینه کند. Koopmans و Beckman در سال ۱۹۵۷ اولین نفراتی بودند که مسئله چیدمان را با در نظر گرفتن جریان مواد بین تسهیلات مدل کردند (Kusiak&Heragu,1987). آن ها مسئله خود را به صورت QAP مدل کردند. علت این نام گذاری این بود که تابع هدف براساس متغیرها از درجه ۲ می باشد و محدودیت ها به صورت خطی تعریف شده اند. آن هاخود را به صورت زیر تعریف کردند (Koopmans&Beckmann,1957):

مفروضات ایشان به صورت زیر بوده است:

با معرفی پارامترها و متغیرهای فوق و سه فرض بالا آن ها مسئله QAP را به صورت زیر بیان کردند:

اگر پارامتر a_ij را به جای عایدی هنگامی که تسهیل i در مکان j مستقر شود به صورت هزینه در نظر بگیریم می توانیم تابع هدف را به صورت معادله ۱۱ بازنویسی کنیم.

Lawler درسال ۱۹۶۳متغیر b_ijkl را به صورت زیر معرفی کرد و تابع هدف مسئله را به صورت معادله ۱۲ بازنویسی کرد(Lawler,1963).

یک فرض پایه و کلیدی در QAP

در QAP فرض بر این است که همه تسهیلات (دپارتمان ها) دارای اندازه های برابر می باشند. اما در عمل ممکن است که تسهیلات یک اندازه نباشند. اما این مسائل را هم می توان به صورت یک مسئله QAP مدل سازی کرد، بدین صورت که تسهیل را به مربع های یک اندازه تقسیم می کنیم. هر تسهیل ممکن است از تعدادی از این مربع ها تشکیل شده باشد. می توان اندازه مربع ها را کوچکتر کنیم تا چیدمان بهتری به دست آوریم اما باید به این نکته توجه داشت که این کار اندازه مسئله را بزرگتر می کند و سبب افزایش زمان اجرا می شود (Kusiak&Heragu,1987).

پیچیدگی مسئله QAP

Sahni و همکارانش در سال ۱۹۷۶ نشان داد که مسئله QAP یک مسئله NP-complete است (Sahni&Gonzalez,1976). بنابراین مسائل بزرگ فقط قابلیت حل بهینه تا ۱۵ تسهیل را دارد (Kusiak&Heragu,1987). حل مسائلی با بیش از ۲۰ تسهیل به صورت بهینه، تقریبا غیرقابل حل می باشد. Burkard در سال ۱۹۸۴ گزارشی از نتایج محاسباتی مسئله QAP ارائه داد (Burkard,1983). به عنوان مثال برای یافتن حل بهینه مسئله ای با ۱۵ تسهیل با استفاده از یک پردازنده CDC Cyber 76 به بیش از یک ساعت زمان نیاز است (Nugent et al,1968). همچنین اگر برای حل مسئله QAP از الگوریتم انشعاب و تحدید و برای کدنویسی از زبان برنامه نویسی فورترن استفاده شود نیاز به n³+5.5n²+17.5n حافظه می باشد (Burkard,1983).

مدل سازی مسئله با استفاده از تئوری گراف

استفاده از تئوری گراف هنگامی کاربرد دارد که عملیات محاسباتی برروی رئوس و بردارهای گرافی انجام شود که نشان دهنده یک چیدمان است (Foulds,1991). در این نوع از فرموله کردن هر تسهیل به وسیله یک راس از گراف نشان داده می شود و هر کمان نشان دهنده درجه نزدیکی بین دو تسهیل می باشد در ضمن در این نوع از مدل سازی از اندازه تسهیلات چشم پوشی می شود و فرض بر این است که درجه نزدیکی بین هر دو تسهیل شناخته شده است (Meller&Gau,1996). تابع هدف در این نوع از فرموله کردن به  صورت بهینه کردن روابط مابین تسهیلات تعریف می شود(Foulds,1991) . Foulds و Robinson در سال ۱۹۷۶ برای مدل سازی مسئله چیدمان تسهیلات با استفاده از تئوری گراف پارامترهای زیر را معرفی کردند (Foulds&Robinson,1976).

آنها با توجه به پارامترهای فوق آن ها مسئله چیدمان تسهیلات را با استفاده از تئوری گراف به صورت زیر فرموله کردند (Foulds&Robinson,1976):

توجه کنید که یک گراف مسطح (Planner Graph) گرافی است که بتوان آن را در روی یک سطح نمایش داد بدون اینکه کمان های آن تقاطعی داشته باشند. برای آشنایی با مفاهیم پایه ای و کلاسیک تئوری گراف می توان به (Foulds,1991)، (Harary,1969) و (Bondy&Murty,1976) مراجعه کرد. در سال ۱۹۷۹ آقای Rosenblatt با استفاده از ایده مدل فوق مدلی ارائه کرد که به طور همزمان سعی در کمینه کردن هزینه حمل و نقل مواد و بیشینه کردن درجه نزدیکی داشت (Rosenblatt,1979). در همان سال توسط خود او و در سال ۱۹۸۲ توسط Dutta و Sahu روشی هیورستیک برای حل این مدل ارائه شد (Dutta&Sahu,1982).

مدل سازی مسئله با استفاده از مدل برنامه ریزی مختلط عدد صحیح

در سال ۱۹۷۸ Kaufman و Broeckx یک مدل برنامه ریزی مختلط عدد صحیح یا Mix Integer Programing (MIP) برای مسئله QAP ارائه دادند که در میان مدل هایی که تا آن زمان ارائه شده بود دارای کمترین تعداد متغیر و محدودیت بود. آن ها مقادیر w_ij و e_ij را به صورت معادلات (۱۷) و (۱۸) تعریف کردند (Kaufman&Broechx,1978).

سپس آن ها مسئله را به صورت زیر مدل سازی کردند:

توجه کنید که مدل سازی ارائه شده دارای n² متغیر صفر و یک، n² متغیر پیوسته و n²+2n محدودیت است (Kaufman&Broechx,1978). در ادبیات مدل های معادل خطی نیز برای مسئله QAP ارائه شده  است (Bazara&Sherali,1980)، Burkard&Bonninger,1983) و (Friezi&Yadegar,1983). در اینجا مدل خطی ارائه شده توسط Bazaraa و Sherali در سال ۱۹۸۰ را ارائه می دهیم. آن ها دو مقدار g_ijkl و y’_ijkl را به صورت زیر تعریف کردند(Bazaraa&Sherali,1980).

با استفاده از تعریف فوق مدل خطی مسئله QAP به صورت زیر ارائه شد.

توجه شود که مدل فوق شاملn² متغیر عدد صحیح، n²(n-1)²/2 متغیر پیوسته و ۲n² محدودیت می باشد (Bazaraa&Sherali,1980).

سایر روش های مدل سازی مسئله

همانگونه که قبلا گفته شد روش های مدل سازی ذکر شده پرکاربردترین شیوه های مدل سازی مسائل می باشند. در مقاله بعدی انواع دیگر مدل سازی مسئله که از لحاظ کاربرد در ادبیات از درجه کمتر اهمیت برخوردار بوده و شامل موارد ذیل می شود، مورد بررسی قرار خواهند گرفت:

• مدل سازی فازی
• مدل سازی چند هدفه
• مدل سازی پیوسته