بخشی از مقاله
چکیده
این پژوهش به حل مساله زمانبندي مونتاژ دوماشینی با در نظر گرفتن محدودیت هاي موجودي مواد اولیه، همچنین نگهداري و تعمیرات پیشگیرانه می پردازد. اهداف مساله شامل کمینه سازي زمان تکمیل کل کارها - Cmax - و بیشینه سازي میزان در دسترس بودن ماشین آلات می باشند. فعالیت هاي نگهداري و تعمیرات پیشگیرانه در مساله با دو رویکرد مبتنی بر مفهوم خط مشی انجام این فعالیت ها در فواصل زمانی بهینه، در نظر گرفته شده اند؛ رویکرد نخست بیشترین تعداد فعالیت نگهداري و تعمیرات پیشگیرانه با فرض فواصل زمانی بهینه را در مساله در نظر می گیرد و رویکرد دوم این امکان را فراهم می آورد که الگوریتم تعداد فعالیت نگهداري و تعمیرات پیشگیرانه را کمتر یا مساوي این تعداد انتخاب کند. براي حل مساله از الگوریتم شبیه سازي تبرید چند هدفه استفاده شده است.
.1 بیان مساله
در این پژوهش به یک مساله زمانبندي مونتاژ دو ماشینی پرداخته شده است. این مساله شامل یک فرآیند دومرحله اي است که در مرحله نخست، دو ماشین به صورت موازي پردازش بخش هاي مختلفی از هر محصول را انجام می دهند. در مرحله دوم، محصولات نهایی مطابق سفارشات مونتاژ می شوند. اقلام اولیه جهت انجام فعالیت هاي تولیدي در زمان هاي مشخص و به میزان معینی وارد خط تولید می شوند. این اقلام را می توان در دو دسته کلی جاي داد: اقلامی که مختص پردازش هاي یکی از دو ماشین هستند و اقلامی که به طور مشترك توسط هر دو ماشین پردازش می شوند. سفارشات پس از تکمیل آخرین عملیات مونتاژ، تحویل می شوند.
در لحظه شروع پردازش، تمامی ماشین آلات در دسترس می باشند. اما در طی انجام فرآیند تولید این امکان وجود دارد که ماشین آلات تولیدي در مرحله نخست به دلیل خرابی و نقص فنی از دسترس خارج شوند. فرض بر این است که تکمیل فرآیند تولید در مرحله مونتاژ در هر زمان بدون احتمال خرابی و نقص فنی، امکان پذیر است. براي افزایش قابلیت اطمینان سیستم تولیدي، عملیات نگهداري و تعمیرات پیشگیرانه براي ماشین آلات مرحله نخست در نظر گرفته شده است. اهداف مساله شامل کاهش زمان تکمیل کل کارها و افزایش میزان در دسترس بودن ماشین آلات می باشند. سایر فرضیاتی که این پژوهش بر پایه آنها شکل گرفته است از این قرارند:
• ماشین ها در مرحله نخست یکسان نیستند.
• تمام کارها در لحظه شروع زمان بندي، در دسترس هستند.
• تامین مواد اولیه یا اجزاء و قطعات مورد نیاز براي تولید تمامی محصولات یک دوره، در مقاطع مشخص زمانی انجام می شود. یعنی نقاط زمانی مشخصی براي تجدید موجودي در نظر گرفته می شود.
• پردازش هر زیر مونتاژ زمانی قابل انجام است که تمامی مواد اولیه مورد نیاز براي تولید آن موجود باشند.
• زمان هاي آماده سازي کارها براي پردازش مستقل از ترتیب انجام آنهاست و به عنوان بخشی از زمان پردازش کارها در نظر گرفته شده اند. ICIE - 2016 -
• هنگامی که پردازش کاري روي یکی از ماشین آلات شروع شود تا زمان تکمیل آن، عملیات بدون وقفه ادامه می یابد.
• ماشین آلات پس از هر بار عملیات نگهداري و تعمیرات به خوبی روز اول می شوند.
این پژوهش در پی یافتن الگوریتمی کارآمد براي حل مساله زمان بندي خط مونتاژ دوماشینی با دو هدف کمینه سازي زمان تکمیل پردازش کل کارها و بیشینه سازي میزان در دسترس بودن ماشین آلات در مرحله اول با در نظر داشتن محدودیت موجودي اقلام اولیه است. همچنین به بررسی این نکته پرداخته می شود که به کار گیري اشکال مختلفی از یک خط مشی نگهداري و تعمیرات تا چه میزان بر نتایج به دست آمده از حل الگوریتم بهینه یابی چندهدفه تاثیرگذار خواهد بود.
.2 مرور ادبیات
از میان پژوهش هاي اندکی که در زمینه زمانبندي مونتاژ دومرحله اي چند هدفه انجام گرفته است، هیچ یک محدودیت موجودي اقلام اولیه را در نظر نگرفته اند. بیشتر مطالعات انجام شده در مورد مساله زمان بندي مونتاژ دو مرحله اي، مساله را به صورت تک هدفه در نظر داشته اند. گروهی نیز مساله را به شکل چندمعیاره بررسی کرده اند. در ادامه به بررسی مطالعات انجام شده در حوزه هاي مختلف این پژوهش پرداخته می شود.
.1,2 جریان مونتاژ دومرحله اي
مطالعات انجام شده در زمینه جریان مونتاژ بیشتر به مساله مدل کردن عملیات مونتاژ براي سر هم کردن محصولاتی که در مرحله نخست به شکل موازي تولید شده اند، پرداخته اند. نخستین پژوهش در این زمینه توسط لی و همکاران [1] انجام شده است . آنها در پژوهش خود یک مساله مونتاژ با دو ماشین در مرحله نخست را با هدف کمینه کردن زمان تکمیل آخرین کار در نظر گرفته اند. پاتس و همکاران [2] این مساله را به حالتی تعمیم داده اند که m ماشین در مرحله نخست وجود دارند. آنها نشان داده اند که براي یافتن جوابی که زمان تکمیل آخرین کار را در این مساله کمینه می کند کافی است زمان بندي هاي ترتیبی مساله بررسی شوند.
همچنین اثباتی براي میزان درجه دشواري این مساله - strongly NP-hard - آورده اند. مثال کاربردي که آنها براي این مساله ارائه کرده اند فرآیند مونتاژ کامپیوترهاي شخصی می باشد که در آن اجزایی همچون واحد پردازش مرکزي، هارد دیسک، صفحه نمایش و صفحه کلید در مرحله نخست تولید شده و سپس تمام اجزاي مورد نیاز بر اساس معیارهاي مورد نظر مشتري در مرحله دوم مونتاژ شده و به صورت محصول نهایی آمادة تحویل می شود.
اله وردي و الانزي [3] یک مساله دو معیارة زمان بندي جریان مونتاژ دو مرحله اي را با اهداف کمینه سازي جمع موزون زمان هاي تکمیل و میانگین زمان تکمیل کار ارائه کرده اند. آنها براي حل این مساله سه روش ابتکاري را به کار برده اند: شبیه سازي تبرید، بهینه سازي اجتماع مورچگان و روش تکامل تفاضلی خود- تنظیم . نتایج پژوهش آنها نشان داده است که شبیه سازي تبرید مناسب ترین روش از میان این سه روش براي حل این مساله بوده است.
.2,2 مساله هاي زمان بندي با وجود محدودیت هاي در دسترس نبودن ماشین آلات
پژوهش هایی نیز انجام گرفته اند که برنامه ریزي تعمیرات و نگهداري پیشگیرانه و زمان بندي تولید را به شکل همزمان در نظر گرفته باشند. چی و همکاران [4] مساله زمان بندي تک ماشینی را با امکان چندین فعالیت نگهداري و تعمیرات در نظر گرفته اند. گریوز و لی [5] یک مساله زمان بندي تک ماشینی را با هدف کمینه سازي جمع موزون زمان هاي تکمیل در نظر گرفته اند و تنها یک فعالیت نگهداري و تعمیرات براي تمام طول افق زمانی برنامه ریزي در نظر گرفته اند. لی و چن [6] مطالعات آنها را براي مساله ماشین هاي موازي توسعه دادند؛ اما همچنان تنها یک فعالیت نگهداري و تعمیرات در نظر گرفته اند.
زندیه و غلامی [7] براي حل مساله زمان بندي جریان کارگاهی مختلط با زمان آماده سازي و شکست ماشین آلات یک الگوریتم ایمنی مصنوعی را ارائه کرده اند. غلامی و همکاران [8] همین مساله را با استفاده از الگوریتم ژنتیک حل کرده اند. مرادي و زندیه [9] یک مساله زمان بندي ماشین هاي موازي را با دو هدف کمینه سازي زمان تکمیل کار و کمینه سازي میزان در دسترس نبودن سیستم حل کرده اند. آنها براي حل مساله الگوریتم ژنتیکی به نام الگوریتم ژنتیک با زیر جمعیت مبتنی بر شباهت - SBSPGA - را معرفی کرده اند.
مرادي و همکاران [10] چهار روش بهینه سازي براي حل مساله زمان بندي تولید در محیط کار کارگاهی مختلط همراه با عملیات نگهداري و تعمیرات پیشگیرانه با زمان هاي ثابت ارائه کرده و این روش ها را مقایسه کرده اند. راج کومار و همکاران [11] براي حل مساله زمان بندي کارگاهی منعطف با محدودیت در دسترس نبودن ماشین آلات - به طور غیر ثابت - یک رویه جستجوي حریصانه تطبیقی تصادفی را پیشنهاد داده اند.
آنها مساله را به صورت چندهدفه و با این اهداف در نظر گرفته اند: زمان تکمیل کار ، مجموع بار کاري ماشین و بار کاري ماشینی که بیشترین بار کاري را داشته است. دالفرد و محمدي [12] یک مساله زمان بندي کارگاهی منعطف را در نظر گرفته اند. ساختار مساله شامل ماشین هاي موازي، محدودیت منابع، هزینه هاي نگهداري و تعمیرات، موعد تحویل کار و زمان هاي در دسترس بودن کارها می باشد. آنها براي حل مساله با اهداف کمینه سازي میانگین تاخیر، زمان تکمیل و متوسط زمان جریان کار از دو روش فراابتکاري الگوریتم ژنتیک ترکیبی و الگوریتم شبیه سازي تبرید استفاده کرده اند. ضیائی [13] یک مساله زمان بندي کارگاهی منعطف را با عملیات نگهداري و پیشگیرانه در یک پنجرة زمانی مشخص نظر گرفته است.
اهداف مساله شامل کمینه سازي زمان کلی تکمیل کار، کل بار کاري روي ماشین آلات و بار کاري ماشینی که بیشترین بار را دارد، بوده اند. وي براي حل مساله یک الگوریتم سریع مبتنی بر یک رویه ایجادي را پیشنهاد کرده است. صیدگر و همکاران [14] یک مساله مونتاژ دو مرحله اي را با فعالیت هاي نگهداري و تعمیرات پیشگیرانه و شکست ماشین آلات در نظر گرفته اند. آنها براي حل این مساله با هدف کمینه سازي زمان تکمیل کار از الگوریتم ژنتیک و الگوریتم استعمار رقابتی به همراه شبیه سازي استفاده کرده اند.
.3,2 محدودیت موجودي اقلام اولیه
در زمینه زمان بندي مونتاژ با وجود محدودیت اقلام تولیدي می توان به مقاله کولیش و هس [15] و مقاله کولیش [16] اشاره کرد. هر دوي این پژوهش ها به بررسی یک محیط تولید سفارشی پرداخته اند که در آن باید تولیدات نهایی را بر اساس موعد تحویل مورد نظر مشتري مونتاژ کرد. هدف تخصیص قطعات به عملیات، زمان بندي عملیات بر اساس دسترسی به منابع، گنجایش محوطه مونتاژ و محدودیت هاي تکنولوژیکی در اولویت انجام فعالیت ها به گونه اي است جمع موزون دیرکردها کمینه شود.
کولیش [15] مساله را به شکل یک مساله RCPS در نظر گرفته است و با استفاده از یک روش ابتکاري لیست زمانبندي یک مدل MIP براي مساله ارائه کرده است. کولیش و هس [16] براي حل مساله یک رویه نمونه گیري تصادفی اریب و شیوة بهینه سازي گام بلند مبتی بر جستجوي ممنوعه را توسعه داده اند. ترخوف و همکاران [17] مدل MIP آنها را براي مساله یک مونتاژ دو ماشینی با محدودیت موجودي اقلام اولیه و با هدف کمینه سازي جمع موزون دیرکردها تطبیق داده اند . آنها دو مدل MIP دیگر، یکی با استفاده از متغیرهاي زمانی - بر اساس زمان شروع فعالیت ها - و یکی با استفاده از متغیرهاي مکانی - بر اساس ترتیب فعالیت ها - ارائه کرده اند.
.3 حل مساله
پاتس و همکاران [2] نشان داده اند که مساله A2//Cmax از گروه مساله هاي پیچیده با دشواري بسیار بالا می باشد. با افزوده شدن محدودیت هاي دیگر مانند محدودیت موجودي اقلام اولیه و در نظر گرفتن فعالیت هاي نگهداري و تعمیرات پیشگیرانه بر میزان این دشواري افزوده می شود. به دلیل وجود افق زمانی مشترك براي زمان بندي تولید و فعالیت هاي نگهداري و تعمیرات به یک برنامه زمان بندي مشترك براي این فعالیت ها نیاز است.
با توجه به این که انجام فعالیت هاي نگهداري و تعمیرات منجر به ایجاد وقفه در عملیات تولید می شود، هدف افزایش در دسترس بودن ماشین آلات به وضوح با اهداف تولید گرا در تعارض می باشد. از این رو براي حل این مساله نیازمند استفاده از الگوریتم هاي فراابتکاري چند هدفه می باشیم. این الگوریتم ها گر چه رسیدن به جواب هاي بهینه را تضمین نمی کنند، اما مجموعهاي از بهترین جواب هاي بدست آمده در زمانی قابل قبول را در اختیار تصمیم گیرنده قرار می دهند تا قادر به انتخاب بهترین تصمیم با توجه به شرایط موجود باشد.
در این پژوهش از الگوریتم شبیه سازي تبرید چندهدفه براي حل مساله استفاده شده است. استراتژي در نظر گرفته شده براي انجام فعالیت هاي نگهداري و تعمیرات مشابه خط مشی 2 رویز [18] می باشد، با این تفاوت که انجام این فعالیت ها در فاصله هاي زمانی بهینه - TPMop - الزام آور نمی باشد. مدلسازي مساله و عملکرد الگوریتم به نحوي می باشند که مناسب ترین زمان هاي نزدیک به TPMop را در جریان زمان بندي تولید براي انجام این فعالیت ها جستجو می کنند. در ادامه ابتدا به ارائه و تشریح مدل برنامه ریزي خطی مساله پرداخته می شود. سپس الگوریتم حل مساله ارائه خواهد شد.
.1,3 نمایش جواب
براي نمایش جواب در این مساله از یک ماتریس 2 × - n + maxi - NPMi - - براي نشان دادن توالی کارها در مرحله اول و آرایه اي به طول n براي نشان دادن توالی کارها در مرحله مونتاژ استفاده شده است. شکل 1 نمونه اي از شیوه نمایش جواب مساله را نشان می دهد.
