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

مقدمه

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

• مسئله چیدمان پویای تسهیلات با اندازه دپارتماهای یکسان و جریان مواد قطعی
• مسئله چیدمان پویای تسهیلات با اندازه دپارتماهای یکسان و جریان مواد احتمالی
• مسئله چیدمان پویای تسهیلات با اندازه دپارتماهای متفاوت

مسئله چیدمان پویای تسهیلات با اندازه دپارتماهای یکسان و جریان مواد قطعی

قسمت عمده ای از تحقیقات انجام شده در حوزه DFLP با فرض قطعی بودن جریان مواد صورت گرفته است. در بسیاری از این موارد حل مسائل DFLP در برگیرنده مسائل SFLP نیز می شود زیرا در بسیاری از فرضیات دو مسئله مشابه هم هستند و همچنین می توان روش های حل مسائل SFLP را با در نظر گرفتن چند دوره زمانی برای مسائل DFLP به کار برد. از طرفی می دانیم که اگر تعداد دپارتمان ها زیاد باشد به دست آوردن جواب بهینه به آسانی امکان پذیر نخواهد بود. بسیاری از الگوریتم های ابتکاری که می توانند اینگونه مسائل را در زمان نسبتا مناسبی حل کنند با فرض قطعی بودن میزان جریان مواد پیشنهاد شده اند. یعنی در صورت اینکه میزان جریان مواد قطعی باشد این الگوریتم ها قابل اجرا هستند. این الگوریتم های ابتکاری را می توان به دو دسته تقسیم کرد:

1. الگوریتم های سازنده،
2. الگوریتم های بهبود دهنده.

 به عنوان مثال الگوریتم CRAFT یک الگوریتم بهبود دهنده مشهور است که از معاوضه دوبه دو استفاده می کند. در واقع استفاده از الگوریتم معاوضه دو به دو در طی چند دوره زمانی منجر به الگوریتم جدیدی تحت عنوان CRAFT می شود.

تمام فرمول های ارائه شده برای مسائل DFLP گسترده شده فرمول های QAP هستند که برای مسائل SFLP به کار می روند.  تفاوت بین فرمول های QAP ارائه شده برای مسائل SFLPو مسائل DFLP در این است که در مدل های QAP که برای مسائل DFLP مورد استفاده قرار گرفته اند تنها هزینه حمل و نقل مواد را مورد بررسی قرار نمی دهند و علاوه بر آن هزینه دیگری تحت عنوان هزینه تغییر جانمایی در طی دوره های زمانی از افق برنامه ریزی مورد توجه قرار می دهند. روش های حل زیادی برای حل مسائل DFLP مورد استفاده قرار گرفته اند. روش های حل ارائه شده را می توان در دو دسته کلی زیر تقسیم بندی کرد:

• روش های دقیق (Exact)
• الگوریتم های ابتکاری (Heuristic) و فراابتکاری (MetaHeuristic)

شکل زیر تقسیم بندی هر یک از انواع روش های فوق را نشان می دهد.

با استفاده از روش های دقیق برای حل مسائل DFLP می توان به جواب بهینه رسید اما زمان رسیدن به جواب نهایی حتی برای مسائل DFLP با اندازه کوچک نسبتاً زیاد است. برای مسائل با اندازه بزرگتر روش های ابتکاری با وجود اینکه رسیدن به جواب بهینه را تضمین نمی کنند اما در عمل روش های کارآمدتری هستند. در ادامه به بررسی هر یک از این روش ها و بررسی مقالات ارائه شده مربوط به آن ها خواهیم پرداخت.

روش های دقیق

روش های دقیق تنها می  توانند مسائلی با ابعاد کوچک را در زمان مناسب حل کنند. این روش ها از آن جهت حائز اهمیت هستند که در مسائل کوچک جواب بهینه را به ما می دهند. یک مسئله نمونهDFLP با بیش از ۲۰ دپارتمان با استفاده از روش های دقیق نمی تواند در زمان مناسب حل شود. از آن جا که مسائلDFLP مسائل عمومیت یافته مسائلQAP هستند در نتیجه حل آن ها نیز سخت تر است.  به یاد داشته باشید که حل مسائل DFLP مستلزم حل یک سری از مسائل QAP است (Shang,2002). روش های دقیقی که برای حل مسائل DFLP در مقالات مورد استفاده قرار گرفته اند عبارتند از برنامه ریزی پویا و الگوریتم شاخه  و  حد که در بخش بعد به بررسی این مقالات خواهیم پرداخت.

برنامه ریزی پویا

پس از طرح این موضوع که «تغییرات اساسی درمکان تجهیزات متناوبا تکرار می شوند و مدیریت باید این تغییرات را در برنامه های آتی خود در دستور کار قرار دهند» توسط Nicol و Holier، استفاده از رویکرد پویا در تجزیه  و تحلیل چیدمان ضروری به نظر رسید. بر این اساس Rosenblatt در سال ۱۹۸۶ برای اولین بار به طور جدی بحث مکان یابی پویای تسهیلات را مطرح کرد. تا قبل از این مقاله مسائل مکان یابی عموما به صورت استاتیک مورد بررسی قرار می گرفتند. او در این مقاله ضمن ارائه مسئله DFLP از روش حلی مبتنی بر برنامه ریزی پویا برای حل این مسئله استفاده کرد (Rosenblatt,1986). در روش برنامه ریزی پویای ارائه  شده توسط Rosenblatt هر دوره زمانی به عنوان یک مرحله (Stage) مد نظر قرار می گیرد و راه حل های استاتیکی برای هر مرحله تحت عنوان وضعیت (State) شناخته می شوند ((Kuppusamy,2001. جواب بهینه با استفاده از رابطه بازگشتی و با آغاز از آخرین دوره زمانی و پیدا کردن چیدمان بهینه برای هر دوره با در نظر گرفتن یک رویکرد استاتیکی برای آن دوره به دست می آید.  بر مبنای طبیعت کار دوره زمانی می تواند بر حسب ماه، فصل، سال و… باشد. در حل مسئله فرض بر این است فضا مسئله ما قطعی است یعنی اینکه تعداد دفعات تقاضا و میزان آن مانند تاریخ تولید برای محصولات همگی در یک افق زمانی محدود مشخص و معلوم است. روش برنامه ریزی پویا ارائه شده توسط Rosenblatt به صورت زیر مدل می شود.

با وجود اینکه جواب بهینه با استفاده از رابطه برگشتی ارائه شده توسط نویسنده به دست می آید، اما در این روش تمام چیدمان های ممکن را در محاسبات در نظر می گیرد، بنابراین زمان محاسبه جواب با افزایش ابعاد مسئله به صورت نمایی افزایش می یابد (Shang,2002). در سال ۱۹۸۶، Rosenblatt برای حل این مشکل و برای اینکه این روش برای مسائل DFLP با ابعاد بزرگتر کارآمد باشد دو راهکار را معرفی کرد. راهکار اول استفاده از روش ارائه شده توسط Ballou (که در سال ۱۹۶۸ که برای مسائل چیدمان انبار مورد استفاده قرار گرفت) است.  این روش بهترین چیدمان بر اساس رویکرد SFLP برای هر دوره زمانی را مورد توجه قرار می دهد.  راهکار دیگر تولید یک سری چیدمان تصادفی برای هر دوره زمانی است. در این روش تولید چیدمان تصادفی به وسیله الگوریتم های CRAFT ارائه شده توسط Buffa و Armour در سال ۱۹۶۳ و COFAD ارائه شده توسط Reed و Tempkins در سال ۱۹۷۶ که برای مسائل SFLP مورد استفاده قرار می گرفتند صورت می پذیرد.  هر دو این راهکارها تعداد چیدمان های مورد نیاز که باید مورد توجه قرار گیرند را کاهش می دهند .(Kuppusamy,2001) نتایج نشان داد که راهکار اول کارآمد تر است.  با وجود اینکه Rosenblatt عملا هیچ مسئله با ابعاد بزرگی را تجربه نکرد اما این مقاله از آنجا که مسئله DFLP را به روشنی تعریف کرده و در مورد روش های حل مسئله با ابعاد کوچکتر راهنمایی هایی کرده توسط بسیاری از مقالات در این حوزه ارجاع داده شده است (Balakrishnan&Cheng,1998).

استفاده از برنامه ریزی پویای ناقص در حالتی که هزینه جانمایی دوباره ثابت بوده و مستقل از جانمایی دوباره دپارتمان ها است، برای مسئله DFLP توسط Urban در سال ۱۹۹۸ نیز مورد بررسی قرارگرفت. این مقاله در ابتدا به بیان این نکته می پردازد که روش های حل بهینه موجود درباره مسائل DFLP عموما از روش های حل مسائل QAP در چارچوب روش برنامه ریزی پویا استفاده می کنند. اما نیازمندی های محاسباتی برای مسائل DFLP ایجاب می کند الگوریتمی کارا که بتوان آن را منحصرا برای این دسته از مسائل به کار برد ایجاد شود. این مقاله به ایجاد چنین الگوریتمی می پردازد.

در مقاله پیش رو هزینه تغییر چیدمان فقط از هزینه ثابت تشکیل شده و راه حل هایی برای حل مسئله با این فرض ارائه شده است. با در نظر گرفتن چنین فرضی تعداد حالت های بررسی در هر دوره به شدت کاهش می یابد. برای حل این مسئله الگوریتم برنامه ریزی پویا ناقص[۱] توسط Wesolowsky ارائه شد. در این مقاله دو روش هیوریستیکی برای حل مسئله بزرگتر ارائه می شود. این دو روش عبارتند از:

• الگوریتم [۲]GRASP
• الگوریتم [۳]IMG

در ادامه این مقاله برای سنجش عملکرد این دو الگوریتم یک مسئله آزمایشی با اندازه دپارتمان ۶ تا ۴۰ واحد و دوره زمانی ۴ تا ۸ واحد زمانی ایجاد شد. با مقایسه نتایج حاصله، نشان داده شد که هر دو الگوریتم کارآمد هستند. برای مسائل اندازه کوچکتر، الگوریتم GRASP منجر به هزینه پایین تر و زمان اجرا طولانی تر نسبت به الگوریتم IMG شد و در مسائل بزرگتر نتایج عکس به دست آمد.

Erel و همکارانش در سال ۲۰۰۳ روش جدیدی که بر مبنای برنامه ریزی پویا بود ارائه دادند. نویسندگان مقاله یک روش ابتکاری جدید سه فازی را ارئه دادند. در این روش فاز اول مربوط به شناسایی مجموعه چیدمان های مناسب است. فاز دوم حل مسئله کوتاه ترین مسیر برای این چیدمان ها از طریق برنامه ریزی پویا بوده و فاز سوم به بهبود محلی جواب های حاصل از فاز دوم می پردازد. برای آزمایش کارایی الگوریتم، نتایج محاسباتی حاصل از ۴۸ مسئله آزمایشی برگرفته از مقاله (Balakrishnan&Cheng,2000) مورد بررسی قرار گرفت. نتایج نشان می داد که روش ابتکاری پیشنهادی برای حل مسئله DFLP تا حد مناسبی سریع است و همچنین جواب هایی با کیفیت مشابه روش های دیگر تولید می کند.

الگوریتم های حل مسائل تخصیص نمایی

 Lacksonen و Enscore در سال ۱۹۹۳ از فرمول مسائل تخصیص نمایی[۴] (QAP) ارائه شده برای حل مسئله DFLPاستفاده کردند. آن ها ۵ الگوریتم حل QAP که برای مسئله SFLP مورد استفاده قرار گرفته بودند را برای حل مسئله DFLP بکار بردند. روش های ارائه شده به شرح زیر بودند (Lacksonen & Enscore , 1993):

۱- الگوریتم CRAFT

این الگوریتم در سال ۱۹۶۳ توسط Armour ارائه شد. نوع پیشرفته تر آن توسط Heider در سال ۱۹۷۳ ارائه شد. هر دفعه اجرای الگوریتم با ۸ چیدمان تصادفی آغاز می شود و سپس بعد تمام جفت های ممکن برای معاوضه دو به دو تست می شوند.

۲- الگوریتم صفحه برش[۵]

این الگوریتم برای اولین بار در سال ۱۹۸۳توسط Burkard و Bonnigerبرای حل مسئله QAP به کار برده شد.

۳- الگوریتم شاخه  و  حد[۶]

 Pardalosو Crouse در سال ۱۹۸۹ این الگوریتم را برای حل مسئله QAP بکار بردند.  این الگوریتم جواب روش شاخه و حد را به عنوان حد بالایی در نظر می گیرد. الگوریتم به صورت ابتکاری بهترین گره ها (هر دپارتمان به عنوان یک گره شناخته می شود) را ذخیره می کند و خاتمه الگوریتم بعد از بررسی تعداد مشخص گره است.

۴- برنامه ریزی پویا

تنهاRosenblatt در سال ۱۹۸۶ برنامه ریزی پویا رابرای مسئله جانمایی تسهیلات پویا مورد استفاده قرار داده است.

۵- درخت برش[۷]

این الگوریتم در سال ۱۹۸۹ توسط Montreuil و Ratliff به منظور حل مسئله QAP مورد استفاده قرار گرفت. هر دپارتمان در هر دوره به عنوان یک گره شناخته می شود. کمان ها بیانگر جریان مواد و چیدمان دوباره تجهیزات است. نتیجه حاصل از الگوریتم درخت برش با استفاده از الگوریتم معاوضه بهبود می یابد.

از بین ۵ الگوریتم فوق تنها ۲ الگوریتم برنامه ریزی پویا و شاخه  و  حد، روش های دقیق هستند. کلیه این برای حل مسائل آزمایشی با اندازه ۶ دپارتمان و ۳ دوره تا مسائل با ۳۰ دپارتمان و ۵ دوره مورد استفاده قرار گیرفتند. نتایج حاکی از این واقعیت بودند که الگوریتم های شاخه  و  حد و الگوریتم صفحه برش در مسائل بزرگتر نسبت به الگوریتم CRAFT عملکرد بهتری دارند و الگوریتم های برنامه ریزی پویا و درخت برش از عملکرد مناسبی برخوردار نیستند. به علاوه اجرای الگوریتم درخت برش برای مسائل با اندازه ۳۰ دپارتمان با مشکل مواجه شد. در این اندازه جواب الگوریتم های برنامه ریزی پویا و CRAFTبه ترتیب ۱٫۳% و ۳٫۷% نسبت به حل صفحه برش بدتر بودند. هر چند که زمان اجرای الگوریتم صفحه برش نسبت به الگوریتم های برنامه ریزی پویا وCRAFT به ترتیب ۲۷ بار و ۸۰ بار طولانی تر بود Balakrishnan,1998)&Cheng). الگوریتم های ارائه شده بر اساس درصد جواب های بالاتر از بهترین جواب موجود بوده و همچنین بر اساس زمان پردازش، امتیازدهی شدند. بر اساس امتیازات داده شده نتیجه گیری شده که الگوریتم صفحه برش نسبت به الگوریتم های دیگر جواب بهتری را ارئه می دهد. نکته مهمی که در این مقاله مورد توجه قرار گرفت تعیین مقدار هزینه تغییر چیدمان است. هزینه تغییر چیدمان بر حسب میزان مترمربع جابجایی است و هزینه های دیگری که در جانمایی دوباره تسهیلات موثر هستند مانند هزینه برنامه ریزی خارج کردن، ساخت، نصب، برقراری ارتباط تاسیسات نیز در آن منظور می شود. همچنین اگر این جانمایی دوباره در ساعات غیر شیفت کاری انجام شده باشد باید هزینه اضافه کاری نیز در این هزینه منظور گردد.

الگوریتم های ابتکاری و فراابتکاری

معاوضه دو به دو

روش معاوضه دو به دو[۸] یا دودویی برای حل مسئله DFLP برای اولین بار توسطUrban در سال ۱۹۹۳ به کار برده شد که با توسعه الگوریتم CRAFT برای چند دوره زمانی و در نظر گرفتن هزینه تغییر جانمایی تسهیلات حاصل می شود (Balakrishnan,1998&Cheng). در روش پیشنهادی Urban از اصل «پنجره های پیش بینی[۹]» برای حل مسئله DFLP استفاده می شود. در این روش اطلاعات جریان برای یک یا چند دوره با هم ادغام می شود و برای تعیین چیدمان در دوره زمانی  مربوطه مورد استفاده قرار می گیرد. علاوه بر این، یک چیدمان اولیه نیز برای دوره زمانی اول پیشنهاد می شود. برای مثال وقتی پنجره پیش بینی برابر ۱ است و در دوره زمانی اول قرار داریم، این روش از اطلاعات جریان دوره زمانی اول برای بهبود چیدمان اولیه داده شده استفاده می کند. این چیدمان بهبود یافته (چیدمان اولین دوره زمانی) به عنوان چیدمان اولیه برای دوره زمانی دوم مورد استفاده قرار می گیرد و با استفاده از اطلاعات جریان دوره زمانی دوم، چیدمان بهبود یافته برای دوره زمانی دوم نیز حاصل می شود. این فرآیند تا بهبود چیدمان آخرین دوره زمانی ادامه می یابد. به طور مشابه وقتی پنجره زمانی برابر ۲ است و ما در دوره زمانی اول هستیم اطلاعات جریان مربوط به دوره های زمانی اول و دوم با هم ادغام می شود تا چیدمان اولیه داده شده را بهبود دهند. این چیدمان بهبود یافته به عنوان چیدمان اولیه برای دوره زمانی دوم مورد استفاده قرار می گیرد و برای بهبود آن از اطلاعات جریان دوره های زمانی دوم و سوم استفاده می شود. این فرآیند ادامه می یابد تا چیدمان آخرین دوره زمانی بهبود یابد (شکل زیر). برایm دوره زمانی m راه حل (طرح چیدمان) وجود خواهد داشت و چیدمانی که کمترین هزینه را دارد انتخاب می شود.

در این مقاله Urban روش پیشنهادی خود را با روش Ballou و روش Rosenblatt مقایسه نموده است. نتایج نشان می داد که روش پیشنهادی Ballou نسبت به روش پیشنهادی توسط Urban برای مسائل کوچکتر عملکرد بهتری داشتند اما وقتی ابعاد مسئله افزایش می یابد روش Ballou نمی تواند کارائی لازم را داشته باشد. همچنین در تمامی حالت ها روش پیشنهادی Urban نسبت به روش Rosenblatt عملکرد بهتری را نشان می دهد.

 Balakrishnan و Cheng در سال ۲۰۰۰ دو الگوریتم ابتکاری را ارائه کردند که روش ابتکاری ارائه شده توسط Urban را بهبود می دادند   (Balakrishnan et al.,2000). این روش ابتکاری از جواب نهایی روش Urban استفاده می کند و در جهت برگشتی حرکت کرده تا به جواب بهتر برسد.  روش ابتکاری دوم ارائه شده در این مقاله، روش Urban را با روش برنامه ریزی پویا ادغام می کند. حرکت به عقب در روش معاوضه دو به دو از دوره زمانی T-1 آغاز می شود و تا اولین دوره زمانی ادامه پیدا می کند. در این روش ابتکاری هزینه چیدمان دوباره بین دوره زمانی T تا دوره زمانی T-1 و هزینه تغییر جانمایی بین دوره های زمانی T تا دوره زمانی T-1 مورد ملاحظه قرار می گیرد. البته اطلاعات جریان مانند روش Urban ادغام نمی شود (Kuppusamy,2001). در روش ابتکاری دوم جواب نهایی Urban به عنوان چیدمان اولیه برای الگوریتم برنامه ریزی پویا مورد استفاده قرار می گیرد. مانند روش اول Urban در الگوریتم برنامه ریزی پویا ادغام می شود و در نهایت نویسنده ادعا می کند که برنامه ریزی پویا در نهایت منجر به جواب بهتری نسبت به روش Urban می شود. روش ابتکاری مذکور بر روی چند مسئله آزمایشی با تعداد ۳۰و۱۵و۶ N = دپارتمان و دوره های زمانی به اندازه ۱۰و۵T = اجرا شده است. نتایج نشان می دهد روش مورد بحث روش ارائه شده توسط Urban را بهبود می دهد (Balakrishnan,1998&Cheng).

اندازه گیری و کران گذاری

 Balakrishnan و همکارانش برای اولین بار در سال ۱۹۹۳ از «روش اندازه گیری[۱۰]» را برای کم کردن تعداد چیدمان ها ایستا در DFLP مورد استفاده قرار دادند (Balakrishnan et al.,1992).  یکی از مزایای روش اندازه گیری این است که می توان آن را بدون داشتن هیچ گونه جواب اولیه ای به دست آورد. ضعف این روش را می توان ارتباط میزان کارآمدی آن با هزینه تغییر چیدمان دانست. برای هزینه های تغییر جانمایی بالا این روش مناسب به نظر نمی رسد. Betta در مقاله خود در سال ۱۹۸۷ نشان داد که اگر یک چیدمان مشابه را برای تمام دوره ها به کار ببریم مسئله DFLP به یک مسئله SFLP تقلیل می یابد که جریان بین دپارتمان ها با اضافه کردن اطلاعات جریان مربوط به همه دوره ها حاصل می شود.

Urban نیز در مقاله خود در سال ۱۹۹۳ کاربرد حد پایین را برای مسائل DFLP مورد بررسی قرار داد (Urban,1993). این روش در مواقعی که از روش هایی چون الگوریتم شاخه و حد استفاده می شود برای حذف جواب های ناکارآمد و همچنین برای سنجش میزان کارایی جواب مسئله، در مواقعی که جواب بهینه موجود نباشد مناسب است. Rosenblattدر مقاله خود در سال ۱۹۸۶ پیشنهاد داد که از مجموع جواب های بهینه مسئله ایستا به عنوان کران برای مسئله پویا استفاده شود (Rosenblatt,1986).  این کار موجب نادیده گرفتن هزینه تغییر چیدمان می شود و یک حد پایینی را برای مسئله می سازد. این کران به جواب بهینه مسئله ایستا نیاز داشته و برای مسائل بزرگتر به سختی به دست می آید.

Urban کران های دیگری همچون کران ارائه شده درمقاله Gilmore و کران احتمالی را نیز مورد بررسی قرار داد. محاسبات مربوط به کران نوعGilmore نسبت به کران نوع Rosenblattکمتر بود. یک کران احتمالی را می توان به صورت  نشان داد که و میانگین و انحراف استاندارد توزیع جریان حمل و نقل مواد هستند. همچنین عملکرد محاسباتی انواع مختلف کران ها با یک آزمایش مقایسه شد. به طور کلی این کران ها وقتی کارآمد هستند که اختلاف در جریان کاری بین دپارتمان ها و و اختلاف فواصل بین دپارتمان ها کم باشد. کران Rosenblatt عموما کارآمدترین کران برای مسائل کوچک است. در حالتی که میزان k و تغییر پذیری جریان پایین است کران احتمالی نسبت به کرانRosenblatt از نظر محاسباتی و عملکرد کارآمدتر است. کران Rosenblatt نسبت به کران نوعGilmore عملکرد بهتری دارد.

Urban در سال ۱۹۹۸ یک سری دیگر از کران های بالا و پایین را پیشنهاد کرد.  (Urban,1998) این کران ها حل مسائل QAP زیادتری نسبت به کران های  Balakrishnan  و Betta وRosenblatt را شامل می شد. در آزمایشی بر روی مسئله ای با اندازه دپارتمان نزدیک به ۱۵ و تعداد دوره زمانی نزدیک به ۸، کران های پیشنهادی دراین مقاله قابلیت بیشتری نسبت به کران های مسئله Rosenblatt و Betta داشتند .

در ضمن این کران نسبت به روش اندازه گیری و کران گذاری که توسط Balakrishnan ارائه شده، برای مسائل با افق زمانی کوچکتر منجر به حذف تعداد زیادتری مسئله ایستا می شود. البته در مسائل با ابعاد بزرگتر روش Balakrishnan عملکرد بهتری دارد (Balakrishnan&Cheng, 1998)

الگوریتم ژنتیک

Conway وVenkataramanan در سال ۱۹۹۴یک روش حل بر مبنای الگوریتم ژنتیک[۱۱] برای مسئله DFLP ارائه دادند.  در این روش، جواب های شدنی رشته[۱۲] نامیده می شوند که به طور تصادفی برای اولین نسل تولید می شوند. هر رشته یک طرح چیدمان کامل برای هر افق برنامه ریزی را در بر دارد. احتمال انتخاب هر کدام از این رشته ها به نسبت مقدار برازندگی شان افزایش می یابند. سپس یک نقطه اتصال تصادفی انتخاب شده و رشته به زیر رشته هایی تبدیل می شود. این زیر رشته ها در ادامه جایگاهشان را تعویض می کنند. اگر در نتیجه این تعویض جواب های نشدنی حاصل شدند تعویض های اضافی برای برقراری شرط شدنی بودن انجام می شود. قوی ترین رشته (بیشترین مقدار برازندگی) در میان نسل جدید حفظ می شود. بقیه رشته ها در طی هر بار تولید نسل جدید جابجا می شوند. الگوریتم ژنتیک پیشنهادی بر روی مجموعه داده های آزمایشی ارائه شده توسطRosenblatt آزمایش شدند. این الگوریتم دارای اندازه جمعیت ۴۰۰ و ۵۰ نسل بود. همچنین الگوریتم بر روی مجموعه داده های مقاله نیز امتحان شدند و بهترین نتایج گزارش شد.

Balakrishnan و Cheng در سال ۲۰۰۰ الگوریتم ارائه شده توسط Conway و Venkataramanan را تصحیح کردند (Balakrishnan,2000& (Cheng. آن ها از یک اپراتور تقاطع نقطه به نقطه برای تقاطع دادن دو رشته قوی استفاده کردند (بر مبنای تابع برازندگی). به جای اینکه تمام اعضای یک نسل تعویض شوند (رویکرد ارائه شده توسط Conway و Venkataramanan) روش ارائه شده در این مقاله تنها بعضی از افراد جامعه را جابجا می کند.

روش پیشنهادی الگوریتم ژنتیک با حلقه های تودرتو[۱۳] نامیده می شود این روش شامل دو حلقه می شود:حلقه درونی و حلقه بیرونی. در حلقه درونی اپراتورهای جهش و تقاطع برای تولید فرزند (چیدمان) مورد استفاده قرار می گیرند. یک امتحان برای تعیین مجار بودن فرزندان (نشدنی بودن جواب) صورت می گیرد. حداقل هزینه در میان فرزندان مجاز (جواب های شدنی) جایگزین والدین با بیشترین هزینه در جمعیت می شود. همچنین استراتژی های گوناگون مانند جهش بکار گرفته می شود تا الگوریتمی تولید شود که تمام فضای موجود را مورد جستجو قرار دهد. در نهایت حلقه بیرونی بعضی از چیدمان های تولید شده تصادفی را جایگزین بعضی از والدین ناکارآمد جمعیت می کند (والدینی که دارای کمترین مقدار برازندگی باشند).

با جایگزینی جواب ها، حلقه بیرونی از فعالیت حلقه درونی بر روی بعضی از جمعیت ها برای جلوگیری از چندین بار تولید مثل استفاده می نماید. به عبارتی دیگر حلقه بیرونی جمعیت را مجزا می کند. خاتمه الگوریتم بر مبنای مقادیر حدی است. وقتی اختلاف دو چیدمان (فرزند) برتر در دو نسل پی درپی کمتر از یک مقدار محدود باشد الگوریتم خاتمه می یابد. روش پیشنهادی در مسئله ای با تعداد دپارتمان برابر N= 6, 15, 30 و دوره زمانی برابر T= 5, 10 امتحان شد  و نتایج با نتایج حاصل از روش ارائه شده توسط Conway و Vankataramanan مقایسه شد. روش قبلی نسبت به روش جدید تنها برای مسائل با ۱۰ دوره زمانی بهتر عمل می کند  (Kuppusamy,2001).

در ادامهBalakrishnan و همکارانش در سال ۲۰۰۳ یک الگوریتم ژنتیک ترکیبی را برای مسئله DFLP پیشنهاد دادند (Balakrishnan et al.,2003). الگوریتم پیشنهادی آن ها برخی از نواقص الگوریتم های ژنتیک موجود را برطرف کرد. در این الگوریتم برای تولید نسل جدید در عملگر تقاطع از برنامه ریزی پویا استفاده شده و برای عملگر جهشی از الگوریتم CRAFT استفاده شده است. با استفاده از یک مسئله آزمایشی نتایج الگوریتم پیشنهادی با نتایج الگوریتم های ژنتیک ارائه شده توسط Balakrishnan وCheng در سال ۲۰۰۰ و الگوریتمSA ارائه شده توسط Baykasoglu و Gindy در سال ۲۰۰۱ مقایسه شده است. نتایج نشان می دهد کیفیت جواب های الگوریتم پیشنهادی نسبت به الگوریتم های ماقبل بهتر است.

الگوریتم بازپخت شبیه سازی شده

Baykosaglu و Gindy اولین افرادی بودند که الگوریتم شبیه ساز حرارتی[۱۴] را در سال ۲۰۰۱ برای مسئله DFLP به کار بردند (Gindy&Baykasoglu,2001). رویکردی که نویسندگان برای حل مسئله DFLP بکار برده اند بسیار ساده بوده و اجرای ساده الگوریتم بر روی مسئله DFLP را شامل می شد. یک چیدمان تصادفی به عنوان چیدمان اولیه در نظر گرفته می شود و الگوریتم SA چیدمان اولیه را بهبود می دهد. در الگوریتم SA پیشنهادی در این مقاله پارامتر های الگوریتم مانند دمای اولیه و دمای نهایی، شدت سرد شدن، تعداد تکرارها در دما بر اساس مجموعه ای از رویه های تکراری که بر مبنای حد بالایی و پایینی مسائل نمونه هستند تعیین می شوند. همچنین نویسندگان مقاله برای تعیین حد بالایی و پایینی تعدادی اجرا آزمایشی را برای هر مسئله نمونه ترتیب دادند. الگوریتم SA پیشنهادی بر روی تعدادی از مسائل آزمایشی با اندازه دپارتمان های N= 6, 15, 30 وتعداد دوره زمانی T= 5, 10 که توسطBalakrishnan و Cheng در سال ۲۰۰۰ ارائه شد، استفاده کردند. نتایج نشان داد که الگوریتمSA نسبت به الگوریتم های GA ارائه شده توسطConway و Venkataramanan در سال ۱۹۹۴  و الگوریتم Cheng وBalakrishanan در سال ۲۰۰۰، برای مسائل DFLP با ابعاد بزرگ عملکرد بهتری دارد (Venkataramanan& Conway, 1994) و (Balakrishnan&Cheng,2000).

 Kuppusamy و همکارانش در سال ۲۰۰۶ در مقاله ای دو الگوریتم SA را برای مسائل DFLP معرفی کردند (Kuppusamy et al., 2005). اولین الگوریتم (SA I) یک اجرای مستقیم از الگوریتم SA بود  و دومین الگوریتم (SA II) یک استراتژی گرمای مجدد را به الگوریتم اول اضافه می کند. تجربیات محاسباتی بر روی یک سری اطلاعات ارائه شده توسط Balakrishnan و Cheng در سال ۲۰۰۰ انجام شد و عملکرد الگوریتم بر مبنای دو مقیاس اندازه گیری شد: کیفیت جواب ها و زمان حل مورد ارزیابی قرار گرفت. نتایج نشان دادند که الگوریتم های پیشنهادی برای مسئله DFLP کارآمد هستند (Balakrishnan&Cheng,2000).

الگوریتم جستجوی ممنوع

Kaku و Mazzola در سال ۱۹۹۷ برای اولین بار در مقاله ای الگوریتم جستجوی ممنوعه[۱۵] را برای مسائل DFLP به کار بردند  (Kaku &Mazzola,1997) .    الگوریتم پیشنهادی آن ها شامل یک فرآیند جستجوی دو مرحله ا ی است که استراتژی های گوناگونی[۱۶] و تشدید[۱۷] را در خود دارد.  استراتژی گوناگونی در سه حالت مورد بررسی قرار گرفت:

• تولید تصادفی چیدمان اولیه
• تولید چیدمان اولیه با استفاده از یک الگوریتم سازنده
• اجرا معیارهای ممنوعه به صورت تناوبی

استراتژی تشدید در ساختار الگوریتم ادغام شده است.  این استراتژی با استفاده از لیست های ممنوعه تطبیقی[۱۸] اجرا می شود. در استراتژی تطبیقی ممنوعه، اندازه ممنوعیت وقتی هیچ بهبود قابل توجهی برای تعداد نسل های از پیش تعیین شده وجود نداشته باشد به نصف ارزش واقعی آن کاهش می یابد (Kuppusamy, 2001).

در طی مرحله اول فرآیند جستجو، تعدادی جواب اولیه با استفاده از استراتژی گوناگونی تولید می شود و یک جستجوی ممنوعه مبنا (با اندازه ثابت ممنوعیت) برای هر جواب اولیه ساخته شده به کار می رود. در انتهای مرحله اولn تا از بهترین جواب ها برای فرآیند تشدید انتخاب می شوند. در گام دوم، جستجوی ممنوعه تعریف شده (اندازه ممنوعیت تطبیقی) برای جواب های اولیه در ارتباط با هر یک از n تا جواب به کار می رود.  روش پیشنهادی بر روی داده های ارائه شده توسط Lacksonen و Enscore در سال ۱۹۹۳ امتحان شد .  نویسندگان نتایج خود را با بهترین جواب ارائه شده توسط Lacksonen و Enscore در سال ۱۹۹۳ و نتایج Urban در سال ۱۹۹۳ مقایسه کرد. نتایج نشان دادند که الگوریتم پیشنهادی با افزایش اندازه مسئله عملکرد بهتری داشته است (Lacksonen&Enscore,1993) و (Urban,1993).

الگوریتم بهینه سازی کلونی مورچگان

در سال ۲۰۰۵ McKendal و Shangیک الگوریتم ترکیبی کلونی مورچگان(HAS)[19] را ارائه نمودند. در این مقاله بر اساس الگوریتم ترکیبی کلونی مورچگان برای مسئله QAP[20] که توسط Gambardella و همکارانش در سال ۱۹۹۹ ارائه شده است، الگوریتم جدیدی برای مسئله DFLP تعریف شد. این الگوریتم با کمی تغییرات در ساختار الگوریتم به صورت ۳ الگوریتم مجزا مورد بررسی قرار گرفت (Shang&McKendall,2005):

• الگوریتم اول که HAS I نامیده شد کاملا منطبق بر الگوریتم HAS-QAP بود. در این الگوریتم از معاوضه تصادفی جفت نسل ها[۲۱] برای جستجوی همسایگی استفاده می کند.
•  الگوریتم دوم تعریف شده مشابه الگوریتم HAS I است با این تفاوت که به جای استفاده از الگوریتم معاوضه تصادفی جفت نسل ها برای جستجوی همسایگی از الگوریتم SA استفاده می کند. این الگوریتم HAS II نامیده می شود.
• الگوریتم سوم نیز مشابه الگوریتم HAS I است با این تفاوت که الگوریتم معاوضه تصادفی جفت نسل ها برای جستجوی همسایگی استفاده می شود از استراتژی Look ahead–look back استفاده می کند. این الگوریتمHAS III نامیده می شود.

در نهایت نویسندگان مقاله با بررسی عملکرد الگوریتم های ارائه شده بر روی ۸۰ مسائل آزمایشی (که ۳۲تای آن ها به وسیله Lacksonen و Enscore و ۴۸ تای دیگر توسط Balakrishnan و Cheng ارائه شده است) به این نتیجه رسیدند که الگوریتم آن ها عملکرد موثری داشته است.

در مقاله ای دیگر که در سال ۲۰۰۶ توسط Baykasoglu و همکارانش به چاپ رسید الگوریتم بهینه سازی کلونی مورچگان (ACO)[22] برای مسائل DFLP و CDFLP مورد استفاده قرار گرفته است.

نوآوری این مقاله را می توان در کاربرد الگوریتم ACO برای مسائلCDFLP ذکر کرد. نویسندگان در این مقاله برای مقایسه الگوریتم خود از اطلاعات آزمایشی ارائه شده توسط Balakrishnan و Cheng استفاده کرده و نتایج حاصله را با الگوریتم های[۲۳]NLGA ، ارائه شده توسط Balakrishnan و Cheng، الگوریتم CONGA ارائه شده توسط Conway و Venkataramanan و الگوریتم شبیه ساز حرارتی و برنامه ریزی پو یای ارائه شده توسطErel مقایسه کرده اند. نتایج نشان دادند الگوریتم ارائه شده نسبت به الگوریتم های CONGA و NLGA عملکرد بهتری دارد اما به خوبی الگوریتم Erel در مسائل بزرگتر نبود. همچنین این الگوریتم برای مسائل CDFLP نیز به خوبی کارایی خود را نشان داد.

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

مسئله چیدمان پویای تسهیلات (اندازه دپارتمان ها یکسان و جریان مواد احتمالی)

زنجیره مارکوف

در سال ۱۹۹۱، Kiran و Kouvelis چیدمان پویا با فرض عدم قطعیت در جریان مواد استفاده کردند. روشی که آن ها در مقاله خود ارائه کردند منحصر به سیستم های تولیدی اتوماتیک می شد.(Kouvelis&Kiran,1991) مدل اساسی ارائه شده در مقاله آن ها شامل بهبود مدل QAP بود که یک شبکه بسته صف[۲۴] را در بر داشت.  این شبکه به آن ها اجازه می داد تا فاکتورهای احتمالی نظیر زمان آماده سازی و زمان حمل مواد، برنامه فرآیند های جانشین و ترکیب مواد را مدل کند.  در مدل پویا برای به روز کردن احتمال ترکیب محصول در هر دوره زمانی، ما تریس انتقالی مورد استفاده قرار می گیرد. اما مدل ارائه شده آن ها فقط در دسته خاصی از مسائل DFLP و فقط با استفاده از برنامه ریزی پویا قابل حل بود (Cheng&Balakrishnan,1998)

Palekar و همکارانش در سال ۱۹۹۲، به مطالعه بر روی عدم قطعیت در مسائل چیدمان تسهیلات پرداختند و برای مسائل DFLP در حالت احتمالی روش های دقیق و ابتکاری دیگری را پیشنهاد کردند (Palekar,et al.,1992). مسائل DFLP در حالت احتمالی یکی از پیچیده ترین مسائل چیدمان بوده و تمامی مسائل دیگر را می توان به عنوان حالت خاصی از این مسائل قلمداد کرد. مسئله DFLP احتمالی به صورت یک مسئله برنامه ریزی عدد صحیح غیر خطی[۲۵] مدل سازی می شود. در یک حالت خاص وقتی فقط یک دوره زمانی برای مسائل DFLP در نظر گرفته می شوند اینگونه مسائل به مسائل QAP و یا SFLP تبدیل می شوند.

عدم قطعیت برای تقاضای محصولات به وسیله تعیین میزان تولید در سه سطح خوشبینانه، محتمل و بدبینانه برای هر محصول و سپس تعیین احتمال خروجی هر محصول از این سطوح مشخص می شود. با استفاده از این تخمین برای هر دوره زمانی می توان جریان میان دپارتمان ها را در هر دوره زمانی پیش بینی کرد. تغییرات شرطی از یک دوره زمانی به دوره زمانی دیگر را نیز می توان با استفاده از زنجیره مارکوف مدل کرد. تابع هدف مسائل DFLP مجموع هزینه های حمل و نقل میان دپارتمان ها و هزینه چیدمان دوباره را در طی دوره  های مختلف را کمینه می کند. به عنوان یک روش حقیقی نیز می توان از برنامه ریزی پویا استفاده کرد که در این حالت دستیابی به جواب بهینه برای مسائل تا اندازه ۱۲ دپارتمان و ۸ دوره زمانی امکان پذیر است  (Sadan,2002).

نیرومندی

استفاده از فرض قطعی بودن جریان مواد در بسیاری از موارد منجر به جواب درست نمی شود. علت این امر را Kouvelis و همکارانش در مقاله ای در سال ۱۹۹۲ با استفاده از مفهوم چیدمان های نیرومند[۲۶] مطرح کردند (Kouvelis et al.,1992). نیرومندی[۲۷] یک چیدمان بیانگر قابلیت انعطاف آن چیدمان در حمل و نقل و در برابر تغییرات احتمالی در تقاضا است. آن ها به جای تعریف نقطه بهینه با تعریف یک بازه به عنوان بازه بهینگی، انتخاب چیدمانی را مد نظر قرار دادند که بتواند تمام حالت های ممکن در بازه بهینگی را پوشش دهد. آن ها همچنین در این مقاله مفهوم Monuments را ارائه کردند که بر اساس این مفهوم ابتدا دپارتمان هایی که به طور غیر قابل اجتنابی پرهزینه و مهم هستند جابجا می شوند تا در مکان خود قرار گیرند. در این روش آن ها از روش شاخه و حد برای انتخاب جواب هایی که در هر دوره زمانی در بازه بهینگی قرار دارند استفاده می کنند. سپس در میان آن ها جواب هایی که به نوعی هم خانواده هستند شناسایی می شوند. یک دسته جواب  های هم خانواده جواب هایی هستند که در طی چند دوره زمانی مکان Monument  های آن ها تغییر نکنند. سپس در بین این خانواده جواب ها، جواب های متعارف انتخاب می شوند. این جواب های نهایی لیست جواب های کاندید که برای ارزیابی انحراف نسبت به جواب بهینه مورد استفاده قرار می گیرند را تشکیل می دهند. تجربه نشان می دهد که برای بیش از ۱۵ دپارتمان روش شاخه و حد قبل از رسیدن به بهینگی خاتمه می یابد. روش شاخه  و  حد تنها منحصر به مسائل با اندازه دپارتمان یکسان می شود.

مسئله چیدمان پویای تسهیلات (اندازه دپارتمان ها متفاوت)

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

در سال ۱۹۹۱، Mountreuil وVenkatadri برای اولین بار در مقاله خود این مسئله را مطرح کردند. آن ها در مقاله خود طراحی چیدمان برای تسهیلات یک کارخانه را مد نظر قرار دادند. همچنین فرض شده این تسهیلات در حال تولید محصولی هستند که در دوره زمانی رشد از چرخه عمر خود قرار دارد. در طی این دوره زمانی وضعیت سیستم عموما در حال حرکت به سمت وضعیت بلوغ است. آن ها در این مقاله برای طراحی تسهیلات تولیدی در طی دوره زمانی رشد از استراتژی پیش بینی[۲۸] استفاده کردند. بر مبنای این استراتژی ابتدا سناریوهای محتمل از نیازمندی های سیستم در وضعیت بلوغ تخمین زده می شود  و بر مبنای این سناریوها یک طراحی بهینه صورت می گیرد. سپس با برگشت رو به عقب چیدمان اولیه تسهیلات تعیین می شود. فرض مهم دیگری که در مدل سازی این مسئله وجود دارد این است که تسهیلات مورد استفاده در این مسئله از نوع تسهیلات سخت[۲۹] هستند.

تسهیلات سخت به آن دسته از تسهیلاتی اطلاق می شود که به علت هزینه جابجایی بسیار بالای آن ها جابجا کردن آن ها تقریبا غیر ممکن است مانند ماشین های CNC، جرثقیل های هوایی و… . بنابراین در این مدل فرض می شود که اندازه دپارتمان ها با نرخ های گوناگون ممکن است افزایش یا کاهش یابد اما موقعیت مکانی مرتبط با آن ها در طول زمان تغییر نمی کند. آن ها این شرایط پویایی را با استفاده از برنامه ریزی خطی مدل کردند (Venkatadri&Mountreuil,1991 ).

در مدل ارائه شده متغیرها در راستای محورهای X و Y منطبقند و به وسیله ابعاد ساختمان در طول محور X وY محدود شده اند. تابع هدف میانگین وزنی هزینه های جریان را حداقل می کند به گونه ایی که وزن اختصاص داده شده به یک فاز به طول دوره فاز و ارزش زمانی پول بستگی دارد. از آن جا که مدل ارائه شده خطی است مدل می تواند مسائل با اندازه واقعی را حل کند. یک مسئله با ۱۲ دپارتمان نیازمند ۵۰۴ متغیر و ۶۴۸ محدودیت بوده و در ۱۰ دقیقه در یک کامپیوتر IBM AT قابل حل بود. این تحقیق ناکارآمدی مدل پایه QAP در مواردی که اندازه دپارتمان ها در مسئله متفاوت باشند را نشان می دهد. همچنین این مدل ناکارآمدی هایی را در مدل Balakrishnan و همکارانش در سال ۱۹۹۲ نشان می دهد. با وجود این، این مدل معایب مخصوص به خود را دارد :

• اول اینکه این مدل تنها با محدود کردن طرح چیدمان پویا به یک ساختار از پیش تعیین شده قابل حل بود.
• ثانیا اینکه هزینه تغییر جانمایی در نظر گرفته نشده و بنابراین دپارتمان ها نمی توانند با همدیگر جابجا شوند.

در سال ۱۹۹۲ Montreuil وLaforge تحقیقات انجام شده توسط Montreuil و Venkatadri را گسترش دادند (Montreuil&Laforge,1992). آن ها در مقاله خود روش جامع تری را برای تحلیل طرح چیدمان در شرایط عدم قطعیت ارائه دادند. نویسندگان مقاله یک سری سناریوهای احتمالی در آینده را برای طراحی چیدمان در نظر گرفتند. از آن جا که مدل آن ها عدم تداخل سلول ها را تضمین نمی کند ساختار اولیه ای پیشنهاد شد. بنابراین موقعیت های مرتبط با دپارتمان ها تغییر نمی کند وفقط شکل و اندازه دپارتمان ها ممکن است تغییر  کند. از آنجا که این ساختار اولیه ممکن است به نظر رسد که مدل را محدود می کند نویسندگان مقاله یک رویکرد تعاملی را پیشنهاد کردند که در آن ساختارهای گوناگون برای سناریو های مختلف در آینده در نظر گرفته می شوند. نویسندگان در مقاله خود یک مسئله آزمایشی با اندازه ۱۲ دپارتمان و ۷ سناریو مختلف در آینده را حل کردند. چیدمان بهینه برای هر یک از سناریوهای آینده در درختی نشان داده شد (Cheng&Balakrishnan,1997).

بسیاری از الگوریتم های ارائه شده در حوزه چیدمان پویای تسهیلات عموما با در نظر گرفتن فرض برابری اندازه دپارتمان ها صورت گرفته و اگر فرض متفاوت بودن اندازه دپارتمان ها را نیز در نظر گرفتند عموماً از طریق چیدمان های ساختاری[۳۰] صورت گرفته اند. برای اولین بار Lacksonen در سال ۱۹۹۴ یک الگوریتم دو مرحله ای را پیشنهاد کرد که از مزایای هر دو نوع الگوریتم های ارائه شده در بالا استفاده می کرد. در مرحله اول شکل QAP از مسئله چیدمان پویا برای پیدا کردن ترتیب تقریبی دپارتمان ها مورد استفاده قرار می گیرد. الگوریتم در این مرحله از روش ابتکاری صفحه برش برای تولید جواب اولیه مناسب استفاده می کند. این روش هزینه تغییر ارایش چیدمان را با جلوگیری از تغییر اولیه چیدمان در طی دوره های زمانی حداقل می کند. با ثابت نگه داشتن دپارتمان هایی که در این مرحله ساکن هستند در مرحله دوم هزینه تغییر چیدمان کاملا مشخص می شود. در این مدل هزینه تغییر چیدمان با هر فوت مربع جابجایی رابطه خطی دارد. در مرحله ۲ مدل اصلاح شدهMontreuil و Venkatadri مورد استفاده قرار گرفت. این مدل از مدل برنامه ریزی خطی مختلط عدد صحیح[۳۱] برای حداقل کردن هزینه جریان استفاده می کند. مدل از متغیرهای عدد صحیح برای تعریف محدودیت های ناهمپوشانی استفاده می کند. محدودیت های دیگر مدل محدودیت های نیازمندی  فضا ودپارتمان های ساکن هستند. شکل کلی این مدل به صورت زیر است (Lacksonen,1994):

Minimize:

        هزینه های جریان

Subject to:

        نیازمندی های فضا

       دپارتمان های ساکن

       ناهمپوشانی دپارتمان ها

بسیاری از آزمایشات بر روی حالت ایستای مدل صورت گرفت. آزمایشات بر روی مسئله با ۱۲ دپارتمان قابلیت این الگوریتم دو مرحله ای را برای یافتن جواب مناسب ثابت کرد. محدودیت های زمانی مانع از یافتن جواب مناسب برای الگوریتم با بیش از ۱۲ دپارتمان می شد. از آن جا که هیچ الگوریتم مشابه ای برای حل مسائل تسهیلات پویا موجود نبود هیچ مقایسه ای نیز امکان پذیر نبود. همچنین بر اساس محدودیت های زمانی بزرگترین مسئله ای که حل شد دارای ۱۲ دپارتمان و ۳ دوره زمانی بود (Balakrishnan&Cheng,1997).

مدل ارائه شده توسطLacksonen ناکارآمدی های موجود در مدل های  Balakrishnan و همکارانش در سال ۱۹۹۲ و Laforge و Mountreuil در سال ۱۹۹۲ را نشان می دهد. دپارتمان ها با اندازه متفاوت می توانند جابجا شوند و نیازی نمی باشد که چیدمان ساختاری اولیه تعیین شود. هر چند همچنان این محدودیت وجود دارد که موقعیت های مکانی نسبت داده شده به دپارتمان ها و اندازه مسئله در دوره زمانی اول نمی توانند در دوره زمانی دوم جابجا شوند  (Balakrishnan&Cheng, 1997).

Dunker و همکارانش در سال ۲۰۰۵ مسئله DFLP را با در نظر گرفتن متفاوت بودن اندازه دپارتمان ها مدل کردند. مدل ارائه شده توسط آن ها دارای محدودیت های ساختاری نمی باشد  و نسبت به مدل های قبلی ارائه شده در این زمینه دارای کارائی بیشتری بود. آن ها برای حل مدل ارائه شده در مقاله از الگوریتم ژنتیک به همراه برنامه ریزی پویا استفاده کردند. فضای جستجو در الگوریتم آن ها نسبتا مناسب است. آن ها برای مقایسه نتایج حاصل از الگوریتم خود از مثال های ارائه شده در مقاله Yang و Peters استفاده کردند (Yang&Peters,1998). نتایج حاصله نشان می داد که چیدمان های ارائه شده در این مدل نسبت به مدل ارائه شده در مقاله Yang و Peters دارای کیفیت مناسب تری است. (Dunker et al.,2005).

نتیجه گیری

از آغاز شکل گیری مسئله DFLP تا به امروز نزدیک به دو دهه می گذرد. در طی سال های اخیر مقالات بسیاری توسط محققان در زمینه چیدمان پویای تسهیلات کارخانه ارائه شده است. در این فصل تلاش گردید با بررسی مقالات ارائه شده در این حوزه در راستای طبقه بندی آن ها گام برداشته و جهت گیری های آتی تحقیقات در این حوزه و اهمیت هر کدام از آن ها بیان شود.

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

• در زمینه بررسی مدل DFLP با اندازه دپارتمان نابرابر و غیر قطعی بودن اندازه جریان و یا ترکیب این دو حالت مقالات محدودی ارائه شده و در نظر گرفتن این پارامترها در مدل سازی مسئله و گسترش مدل و ارائه روش های حل برای این دسته از مدل ها می تواند مورد توجه قرار گیرد.
• بررسی چیدمان های جز شده با در نظر گرفتن رویکرد پویا (چیدمان ماشین آلات به همراه دپارتمان ها) گزینه مناسبی برای ادامه تحقیقیات در این حوزه قلمداد می شود.
• روش های ترکیبی یا Hybrid که از ادغام الگوریتم های ابتکاری و فراابتکاری (مانند ادغام الگوریتم جستجوی ممنوعه با الگوریتم ژنتیک و یا ادغام الگوریتم جستجوی ممنوعه با الگوریتم شبیه ساز حرارتی) حاصل می شوند می توانند به عنوان رویکرد جدیدی برای حل مسائل DFLP مورد توجه قرار گیرند.
• با توجه به اینکه الگوریتم های محدودی برای مسائل چیدمان پویای تسهیلات با محدودیت بودجه ارائه شده می توان حل این دسته از مسائل با الگوریتم های دیگر مانند الگوریتم ژنتیک و یا الگوریتم شبیه ساز حرارتی مورد توجه قرار گیرد
• با توجه به رویکرد جدید مسائل چیدمان به سمت مسائل پیشرفته  تری در حوزه چیدمان مانند سیستم های تولیدی انعطاف پذیر، سیستم های تولیدی سلولی یا تکنولوژی گروهی، استفاده از رویکرد چیدمان پویای تسهیلات برای این دسته از مسائل می تواند جذاب تر و دارای کاربرد به روز تری باشد.

پاورقی ها

• [۱] Incomplete Dynamic Programming
• [۲] Greedy Randomize Adaptive Search Procedure
• [۳] ‌Initialize Multi Greedy
• [۴] Quadratic Assignment Problem
• [۵] Cutting Planes
• [۶] Branch and Bound
• [۷] Cut Trees
• [۸] Pair Wise Exchange
• [۹] Forecast Windows
• [۱۰] Fathoming
• [۱۱] Genetic Algorithm
• [۱۲] String
• [۱۳] Nested Loop Genetic Algorithm
• [۱۴] Simulated Annealing
• [۱۵] Tabu Search (TS)
• [۱۶] Diversification
• [۱۷] Intensification
• [۱۸] Adaptive Tabu List
• [۱۹] Hybrid Ant System
• [۲۰] HAS-QAP
• [۲۱] Random Descent Pair Wise Exchange
• [۲۲] Ant Colony Optimization
• [۲۳] Nested Loop Genetic Algorithm
• [۲۴] Close Queuing Network
• [۲۵] Quadratic Integer Program
• [۲۶] Robust Layout
• [۲۷] Robustness
• [۲۸] Proactive Strategy
• [۲۹] Rigid Facilities
• [۳۰] Skeleton Layout
• [۳۱] Mixed Integer Linear Programming