بخشی از مقاله
چکیده
طراحی مسیرهاي حملونقل در سیستمهاي تاندم، بر پایه افراز مجموعه ایستگاهها در قالب مسیرهاي حلقوي بسته تک وسیله غیرمتداخل بنا شده است. هر حلقه حداقل داراي یک ایستگاه اضافی تخلیه و بارگیري به عنوان نقطه انتقال، براي تبادل جریان بین حلقههاي مجاور است. در این مقاله، به توسعه روش حلی بر پایه روش جستجوي ممنوع، براي طراحی سیستمهاي تاندم پرداخته شده است.
الگوریتم جستجوي ممنوع با داشتن جواب اولیه تعدیل شده حاصل از خوشه بندي k_means، سعی میکند ایستگاهها را در حلقهها طوري افراز کند که حداکثر بارکاري حلقهها، ضمن جلوگیري از ایجاد تقاطع مسیر در حلقهها، حداقل شود. الگوریتم مزبور و الگوریتم مبناي Bozer - 1992 - و Srinivasan، با حل مسائل آزمایشی تصادفی تولید شده مورد مقایسه قرار گرفتهاند. نتایج نشان میدهد در مسائل بزرگ، الگوریتم مبنا علیرغم زمان حل کمتر، در بیشتر موارد، جوابهاي ناموجه با حلقههاي متقاطع را نتیجه میدهد.
مقدمه
طراحی سیستمهاي انتقال مواد از بحثهاي مهم مطرح در زمینه طراحی تسهیلات است. هزینه انتقال مواد در سیستمهاي تولیدي، رقمی در حدود 20 تا 50 درصد کل هزینههاي عملیاتی را شامل میشود .[1] وسایل نقلیه خودکار1 وسایلی هستند که بدون نیاز به راننده قادر به حملونقل مواد هستند. آنها توسط سیستم کنترل از راه دور و بطور خودکار بر روي مسیرهاي از پیش تعیین شده بصورت نوارهاي الکترومغناطیسی یا مسیرهاي رنگ شده حرکت میکنند .[2]
در یک تقسیم بندي کلی، 5 نوع سیستم حملونقل برايAGVها قابل طرح است Bidirectional Shortest Path Systems :[2]، Conventional Systems، Single Loop Design، Segmented Flow Topology و .Tandem Configuration سیستم تاندم براي اولین بار توسط Bozer و Srinivasan در سال 1989 به دنیا معرفی شد. طراحی مسیرAGVها در این سیستم بر پایه فلسفه "Divide & Conquer" بنا شده است. مجموعه مسیرهاي انتقال مواد در آن، از چندین مسیر حلقوي بسته مستقل از هم تشکیل میشود. در هر مسیر تنها یک AGV جابجایی بارها را به عهده داشته و ارتباط مسیرهاي حلقوي توسط ایستگاههایی به نام نقاط انتقال برقرار میشود.
از مزایاي این سیستمها، میتوان به منتفی شدن مسئله ترافیک در حلقهها، سادگی در سیستم کنترلی و انعطاف پذیري بیشتر به دلیل ماهیت غیر متمرکز آن اشاره نمود. برخی از معایب آن عبارتند از: نیاز به جابجایی بار توسط بیش از یک AGV براي رسیدن به مقصد، که این خود زمان حمل بار را افزایش میدهد، فضا و هزینه اضافی براي ایجاد نقاط انتقال و کانوایرهاي ارتباط دهنده آنها و ایجاد اختلال در حملونقل، در صورت خرابی هر یک از AGVها در درون حلقهها. مطالعات انجام شده در زمینه سیستمهاي تاندم در دو گروه قابل بررسی هستند.
گروه اول مربوط به مطالعاتی است که در زمینه طراحی مسیرها در سیستمهاي تاندم انجام شده است. Bozer و Srinivasan به عنوان معرفی کنندگان این سیستم به دنیا، در اولین مقالات خود [3,4] پس از معرفی سیستمهاي تاندم، به ارائه یک مدل تحلیلی2 براي محاسبه بارکاري یک تک حلقه پرداختهاند. آنها در [5]، به توسعه روشی ابتکاري براي افراز ایستگاهها در مسیرهاي حلقوي براي این نوع سیستم پرداختهاند.
Hsieh و Sha در [6] مسئله طراحی چیدمان و طراحی مسیرهاي تاندم را بطور همزمان، مورد بررسی قرار دادهاند. Aarab و همکارانش در [7] روشی براي طراحی مسیرها در چیدمان بلوکی به کمک خوشه بندي سلسله مراتبی و جستجوي ممنوع ارائه کردهاند. Yu و Egbelu در [8] مسئله طراحی سیستمهاي تاندم را براساس مفهوم جدید مسیرهاي متغیر3 مطرح نمودهاند.
گروه دوم، مطالعاتی هستند که به طرح مسائل و فرضیات جدید در زمینه سیستمهاي تاندم پرداختهاند. Bozer و Lee در [9] به مسئله حذف نقاط انتقال و کانوایرهاي ارتباط دهنده آنها و استفاده از ایستگاههاي کاري به عنوان نقاط انتقال پرداختهاند. Ventura و Lee در [10] مسئله سیستمهاي تاندم با بیش از یک AGV در هر حلقه را مورد بررسی قرار دادهاند. Huang در [11] به مسئله استفاده از مرکز حملونقل براي ارتباط نقاط انتقال جهت جابجایی بارهاي بین حلقهاي پرداخته است.
در این مقاله به مسئله طراحی مسیرها در سیستمهاي تاندم به کمک روش جستجوي ممنوع4، براساس فرضیات مطرح شده در [5] توسط Bozer و Srinivasan پرداخته شده است. الگوریتم جستجوي ممنوع با داشتن طرح چیدمان نقطهاي، برگ مسیر و تعداد حلقهها به عنوان ورودي، ایستگاهها را طوري به حلقهها تخصیص میدهد که بدون ایجاد تداخل، حداکثر بارکاري5 حلقهها حداقل شود.
الگوریتم جستجوي ممنوع و الگوریتم Bozer و Srinivasan توسط مسائل آزمایشی طراحی شده مورد مقایسه قرار گرفتهاند. مطالب موجود در مقاله به این صورت طبقه بندي شدهاند. در بخش 2 به تعریف مسئله و فرضیات مورد استفاده در مسئله پرداخته شده است. بخش 3 به شرح الگوریتم توسعه داده شده بر پایه جستجوي ممنوع میپردازد..
2 تعریف مسئله
سیستمهاي حمل نقل تاندم یا سیستمهاي چند حلقهاي، اولین بار توسط Y. Bozer و M. Srinivasan در [2] معرفی شدند. این سیستمها، هم در مورد حملونقل درون کارخانه و هم در مورد حملونقل درون انبار قابل پیادهسازي هستند. ولی اساسا از ابتدا براي کاربرد در سطح کارخانه تعریف شدهاند. مفهوم سیستمهاي تاندم، طراحی مسیر AGVها بر پایه فلسفه "Divide & Conquer" بنا شده است.
در این سیستمها، مجموعه مسیرهاي انتقال مواد از چندین مسیر حلقوي بسته - حلقه - مستقل از هم تشکیل میشوند، که هیچگونه تداخل مسیر یا همپوشانی با یکدیگر ندارند. در هر حلقه، تنها یک AGV مسئول جابجایی بارها است. ارتباط حلقهها با یکدیگر توسط نقاط انتقال برقرار میشود که این نقاط برقرار کننده ارتباط بین حلقهها، جهت انتقال بارها از حلقهاي به حلقه دیگر میباشند. نقاط انتقال میتوانند توسط نقالهها به همدیگر مرتبط شوند. نمونهاي از این سیستم در شکل 1 نشان داده شده است.
فرضیات مورد استفاده توسط Bozer و Srinivasan براي طراحی الگوریتم ابتکاري افراز، مبناي طراحی الگوریتم TS در این مقاله قرار گرفتهاند که در اینجا به آنها اشاره میشود. چیدمان بصورت نقطهاي بوده و هر ایستگاه میتواند نمایانگر یک یا چند ماشین - مثلا به عنوان سلولهاي تولیدي و یا دپارتمان - باشد. بطور کلی دو نوع ایستگاه در این سیستم موجود است. ایستگاههاي پردازش کننده1 که بر روي بارها عملیات تولیدي انجام میدهند و ایستگاههاي ورودي/ خروجی2، که بار از طریق آنها از سیستم خارج یا به آن وارد میشود.
با این اوصاف ایستگاههایی که نقش نقاط انتقال را دارند نیز در مجموعه ایستگاههاي ورودي خروجی قرار میگیرند. نقاط تخلیه و بارگیري بر ایستگاهها منطبق هستند. هر ایستگاه داراي یک صف ورودي3 و یک صف خروجی4 است. بارهایی که باید وارد ایستگاه شوند در صف ورودي و بارهایی که از آن خارج میشوند، در صف خروجی قرار میگیرند.
