International Journal of Industrial Engineering & Production Management (2013)

-144144-24523

February 2013, Volume 23, Number 4
pp. 459-470

http://IJIEPM.iust.ac.ir/

Multiple Route Job Shop Scheduling with Maintenance
Activity Constraints

H.R. Golmakani* & A. Namazi

Hamid Reza Golmakani, Industrial Engineering Department, Tafresh University
Ali Namazi, Industrial Engineering Department, Tafresh University, ali.namzi@yahoo.com
Keywords 1ABSTRACT

1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Job Shop Scheduling,
Multiple Routes,
Preventive Maintenance Activities,
Artificial Immune System In scheduling problems, it is often assumed that all machines are available during scheduling horizon. Clearly, a machine may not be available due to breakdown or performing maintenance activities. This paper considers a multiple-route job shop configuration, where each part has multiple routes to be produced. In this context, the problem of scheduling jobs together with a set of pre-defined maintenance activities is of interest. Due to the complexity of the problem, no exact mathematical approach can yield solution in reasonable amount of time and, thus, applying heuristic approach is suggested. In this paper, the problem is first formulated as a 0-1 non-linear integer program. Then an approach based on artificial immune system is proposed to tackle the complexity of the problem. In order to evaluate the performance of the proposed approach 30 cases are designed and solved using the proposed approach and Lingo software. The results show that the proposed approach can obtain good solutions in reasonable time.
© 2013 IUST Publication, IJIEPM. Vol. 23, No. 4, All Rights Reserved

*
Corresponding author. Hamid Reza Golmakani Email: golmakni@mie.utoronto.ca

زمانبندی‌کار‌کارگاهی‌چندمسیره‌با‌در‌نظر‌گرفتن‌محدودیت‌نگهداری‌و‌
تعمیرات‌)نت(

حمید‌رضا‌گل‌مکانی* و‌علی‌نمازی

کلمات کلیدی چکیده:
243846168

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

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

9. مقدمه9
توالیِ عملیاتِ کارها بر روی ماشین ها تاثیر بسزائی در حجم کار در جریان ساخت، میزان برآورده کردن به موقعِ تقاضای مشتریان ،و بطور کلی قیمت تمام شده محصول تولیدی دارد. از این رو، ، در یک واحد تولیدی، سعی بر آن است تا عملیات به گونه ای
برنامه ریزی گردد تا حداکثر استفاده از منابعِ موجود، اعم از نیروی
تاریخ وصول: 91/9/19 تاریخ تصویب: 91/5/19
*نویسنده مسئول مقاله: دکتر حمیدرضا گل مکانی، دانشیار دانشکده مهندسی صنایع، دانشگاه تفرش، ابتدای جاده تهران، تفرش، ایران
golmakni@mie.utoronto.ca
علی نمازی، دانشجوی کارشناسی ارشد، دانشکده مهندسی صنایع، دانشگاه تفرش، ابتدای جاده تهران، تفرش، ایران ali.namzi@yahoo.com
12 Scheduling operation Multiple route job shop
34 Damage Preventive maintenance
کار و یا ماشین آلات، محقق گردد ]1[. معذلک وقوع خرابیِخرابی ماشین آلات امری اجتناب ناپذیر است و میتواند علاوه بر تاخیر در تکمیل سفارش مشتریان، موجب افزایش هزینه های عملیاتی گردد .
1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

اغلب، اجرای استراتژی تعمیر پس از مشاهده خرابی0 در مقایسه با استراتژی انجام فعالیتهای پیشگیرانه4 منجر به افزایش هزینههای عملیاتی است و لذا نگهداری و تعمیر پیشگیرانه به عنوان یک استراتژی موثر در کاهش هزینه ها و تبعا افزایش سودآوری، مورد استفاده واحدهای تولید قرار گرفته است]2[. انجام بازرسی و یا سرویس های دوره ای، تعمیرات اساسی و یا تعویض های پیشگیرانه موجب خواهد شد تا علاوه بر افزایش قابلیت اطمینان ماشینآلات، هزینه های عملیاتی نیز کاهش یابند .
عمدتا تعیین تناوب انجام فعالیتهای فوقالذکر با لحاظ هزینه های بازرسی، تعویض پیشگیرانه، تعمیر اساسی، هزینههای وقوع خرابی و توزیع احتمالی وقوع خرابی ها و با استفاده از مدلهای ریاضی صورت میگیرد]0[. با حل مدل های مذکور، به ازاء هریک از ماشین آلات، مجموعه فعالیتهای نگهداری و تعمیرات و همچنین محدوده زمانی بهینه برای انجام این فعالیتها مشخص میگردد .تبعا عدم انجام فعالیتهای مذکور و یا عدم انجام آنها در محدوده زمانی تعیین شده موجب افزایش نرخ خرابیها و در نتیجه افزایش هزینه های عملیاتی خواهد شد]4[. بدین ترنیب دیده میشود که برنامه ریزی عملیات تولیدی و برنامه ریزی فعالیتهای نگهداری و تعمیرات بطور کامل وابسته به یکدیگر بوده و نقش تعیین کننده ای را در سودآوری واحدهای تولیدی ایفا میکنند]6-5[.
با توجه به اهمیتاهمیتِ لحاظِلحاظ وابستگی برنامه ریزی عملیات تولیدی و برنامه ریزی فعالیتهای نگهداری، حلحلِ همزمانهمزمانِ مسئله زمانبندی کارها و فعالیتهای نگهداری و تعمیرات در سال های اخیر مورد توجه محققان قرار گرفته است. از آنجاکه عمدتا زمان انجام فعالیتهای نگهداری و تعمیرات در مقایسه با زمان مورد نیاز جهت تکمیل کارها کمتر است، اغلب محققان، انجامِانجام فعالیت نگهداری و تعمیرات را به عنوان محدودیت دسترسیدسترسیِ ماشین ها در مسئله زمانبندی عملیات تولیدی، در نظر گرفته اند ]بعنوان نمونه رجوع کنید به 12-7[.
محدودیت دسترسی ممکن است ثابت و یا شناور باشد. در محدودیت دسترسی ثابت، دسترسی به ماشین در یک محدوده زمانی از قبل تعیین شده ای میسر نیست و لذا فعالیت نگهداری و تعمیر صرفا میبایستی در محدوده زمانی مذکور انجام شود. در محدودیت دسترسی شناور، فعالیت نگهداری و تعمیر میتواند در یک بازه زمانی )که اغلب طولانی تر از زمان مورد نیاز برای انجام فعالیت نگهداری و تعمیر است( صورت گیرد ]4[.
در ادبیات مسائلمسائلِ زمانبندی با در نظر گرفتن محدودیت دسترسی به ماشین ها، شرایط متفاوتی برای انقطاع کارها وجود دارد. از آن جمله میتوان به سه مورد: مجاز بودن انقطاع عملیِات بدون جریمه، مجاز بودن انقطاع عملیات با جریمه از سرگیری عملیات و مجاز نبودن انقطاع عملیات اشاره نمود. مجاز بودن انقطاع عملیات بدون جریمه، بدین معناست که امکان قطع کردن عملیات یک کار روی یک ماشین به منظور انجام فعالیت نگهداری و تعمیرات وجود دارد و پس از اتمام فعالیت نگهداری و تعمیرات، بقیه عملیاتِ مذکور می تواند بدون هیچ جریمه ای ادامه یابد. در انقطاع عملیات با جریمه از سرگیریِ عملیات، انقطاع مجاز است معذلک عملیات انجام شده روی ماشین، قبل از انقطاع، میبایستی مجددا تکرار گردد. در حالت مجاز نبودن انقطاع عملیات، انجام فعالیت نگهداری و تعمیرات صرفا در زمان بیکار بودن ماشین میسر است ]8-5[. مسائل زمانبندی تک ماشینه و ماشینهای موازی با محدودیت عدم دسترسی بطور وسیع مورد مطالعه قرار گرفته است ]9[ . اخیراً مسئله زمانبندی با محدودیت دسترسی در
429
محیط های پیچیده تر از قبیل جریان کارگاهی، کار کارگاهی و محیط های ترکیبی بیشتر مورد توجه قرارگرفته است. در ]13[ مسئله جریان کارگاهی با در نظر گرفتن فعالیتهای نگهداری و تعمیرات با هدف مینیمم کردن معیارهای زمان شناوری و تاریخ تحویل مورد مطالعه قرار گرفته است. در ]8[ با استفاده از یک الگوریتم یکپارچه بر مبنای الگوریتم ژنتیک و جستجوی ممنوع حل مسئله زمانبندی جریان کارگاهی با محدودیت نگهداری و تعمیرات ارائه شده که در آن هدف کمینه سازی زمان تکمیل کل کارها است. در ]11[ مسئله جریان کارگاهی دو ماشینه به منظور مینیمم کردن حداکثر زمان تکمیل کارها با فرض اینکه مدت زمان نگهداری و تعمیرات ماشین ها به دوره شروع نگهداری و تعمیرات آنها بستگی دارد مورد بررسی قرار گرفته است.
در ]2[ مسئله جریان کارگاهی با سه سیاست متفاوت در نگهداری و تعمیرات ماشین ها در نظر گرفته و شش روش ابتکاری و فرا ابتکاری برای حل آن مورد بررسی قرار گرفته است .در ]10[ نیز مساله زمانبندی جریان کارگاهی دو ماشینه وقتی ماشین اول برای یک فاصله زمانی داده شده در دسترس نیست با هدف کمینه سازی حداکثر زمان تکمیل کارها بررسی شده است. در ]12[ مسئله زمانبندی کار کارگاهی با محدودیت های دسترسی به ماشین ها ارائه شده است. در ]15[ جریان کارگاهی دو ماشینه با این فرض که فعالیت نگهداری و تعمیرات باید در یک زمان ثابت بعد از تکمیل حداقل یک تعداد ثابت از کارها انجام شود، با هدف کمینه سازی حداکثر زمان تولید مورد بررسی قرار گرفته است. در ]16[ مسئله زمانبندی کار کارگاهی با زمان آماده سازی وابسته به توالی و محدودیت عدم دسترسی روی ماشین ها به منظور مینیمم کردن حداکثر زمان تولید با استفاده از دو الگوریتم شبیه سازی تبرید و الگوریتم ژنتیک مورد مطالعه قرار گرفته است .در ]17[ نیز مسئله جریان کارگاهی انعطاف پذیر با زمان آماده سازی وابسته به توالی و با لحاظ سه سیاست نگهداری و تعمیرات با استفاده از دو الگوریتم شبیه سازی تبرید و الگوریتم ژنتیک مورد مطالعه قرار گرفته است. مسئله زمانبندی کار کارگاهیِ انعطاف پذیر، تعمیم یافته مسئله کارکارگاهی است ]5[ .
1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

این ساختار شامل تعدادی ایستگاه کاری است که در آن، حداقل یک ایستگاه دارای بیش از یک ماشین موازی یکسان است. هر کار در یک ایستگاه کاری که در آن بیش از یک ماشین موازی وجود دارد، میتواند توسط هریک از ماشینها پردازش شود. در حقیقت این ساختار ترکیبی از مسئله کار کارگاهی ساده و مسئله ماشین های موازی است. در ]18[ مسئله کار کارگاهی انعطاف پذیر با محدودیت دسترسی ماشینها با دوره عدم دسترس پذیر شناور و با استفاده از الگوریتم ژنتیک در نظر گرفته شده است. در ]19[ نیز مسئله زمانبندی جریان کارگاهی انعطاف پذیر با لحاط
1268732040127

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

Downloaded from ijiepm.iust.ac.ir at 14:44 IRST on Saturday November 4th 2017

426
نگهداری و تعمیرات دوره ای و با هدف حداقل کردن حداکثر زمان تولید مورد بررسی قرار گرفته است. در این تحقیق از دو روش فرابتکاری الگوریتم سیستم ایمنی مصنوعی و الگوریتم ژنتیک استفادِه شده اسِت.
تعمیم وسیع تر مسئله کارکارگاهی، مسئله کار کارگاهیِکارگاهی چند مسیره است که در آن ، هر کار میتواند از مسیرهای متفاوتی عبور کرده و به اتمام رسد. لزومالزوماً تعداد ماشینها در مسیرهای مختلف برای یک کار برابر نیست. این ساختار در اغلب واحدهای تولیدی منعطف، که در آنها ماشین های کنترل عددی قادر به انجام عملیات متفاوتی از یک کار هستند، مشاهده میشود. مساله زمانبندی کار کارگاهی، که در آن انجام هر کار صرفا از یک مسیر صورت میگیرد، یک مسئله NP-Hard است ]23[. مسئله زمانبندی کار کارگاهی چند مسیره نیز NP-Hard است چراکه وجود مسیرهای مختلف برای انجام یک کار موجب پیچیدگی بیشتر مسئله خواهد بود. در حقیقت این مسئله شامل دو زیرمسئله 1( تخصیص هر کار به یک مسیر از میان مسیرهای موجود برای آن کار و 2( تعیین توالی عملیات تخصیص یافته به ماشین ها، میباشد.
در تحقیق حاضر مسئله کار کارگاهی چند مسیره، با محدودیت دسترسی شناور، و با هدف تعیین توالی انجام کارها و همچنین فعالیت نگهداری و تعمیرات بگونه ای که زمان اتمام کارها حداقل گردد، مورد بررسی قرار گرفته است. در ادامه و در بخش 2 تعریف مسئله، فرضیات و چگونگی مدل سازی ریاضی آن ارائه خواهد شد. در بخش 0 روش پیشنهادی برای حل مسئله، که با بهره گیری از الگوریتم سیستم ایمنی مصنوعی طراحی شده است ،توضیح داده خواهد شد. در بخش 4 ، جهت ارزیابی عملکرد الگوریتم پیشنهادی ،03 مسئله در ابعاد کوچک، متوسط و بزرگ طراحی و توسط الگوریتم مذکور حل و نتایج آن ارائه شده است و در پایان نتیجه گیری و پیشنهادات برای تحقیقات آتی آورده شده است .

6. تعریف مسئله و مدل ریاضی آن
9-6.تعریف مسئله
در این تحقیق، مسئله زمانبندی کار کارگاهیِ چند مسیره با محدودیت دسترسی شناور ماشین ها، به جهت اجرای فعالیتهای نگهداری و تعمیرات )نت( و با هدف تعیین توالی انجام کارها و همچنین فعالیتهای )نت( بگونه ای که زمان اتمام کارها حداقل گردد، مورد بررسی قرار میگیرد. هر کار میتواند از مسیرهای متفاوتی عبور کرده و به اتمام رسد. تعداد ماشینهائی که یک کار در مسیرهای مختلف با آنها مواجه میشود لزوماً برابر نیست. به عبارت دیگر، ممکن است در یک مسیر، کار، با عبور از دو ماشین )هر ماشین یک عملیات( به اتمام رسد و در مسیری دیگری همان کار با عبور از چهار ماشین )هر ماشین یک عملیات و جمعاً چهار عملیات( انجام شود. لزوم اجرای فعالیتهای نگهداری و تعمیرات موجب میشود تا بخشی از زمان عملیاتی ماشین ها به آن اختصاص یابد. زمان انجام فعالیتهای نت بصورت شناور از قبل مشخص و این فعالیتها میبایستی در محدوده زمانی تعیین شده انجام شوند. واضح است که هر ماشین تنها یک عملیات و یا یک فعالیت نت را در هر لحظه می تواند انجام دهد. فرض بر این است که در صورت شروع یک فعالیت نت، قطع آن مجاز نیست .همچنین قطع عملیاتعملیاتِ یک کار بدلیل انجام فعالیت نت و یا انجام بخشی از کار در زمانی دیگر مجاز نیست. همچنانکه دیده میشود، مسئله زمانبندی کار کارگاهیِکارگاهی چند مسیره با محدودیت دسترسی شناور ماشین ها جهت اجرای فعالیتهای نت، شامل سه زیر مسئله است: 1( تخصیص مسیر به کارها ،2( تعییین توالی کارهای تخصیص داده شده و 0( زمانبندی فعالیتهای نت. هدف ،کمینه سازی زمان انجام اتمام کارها فعالیتهای نت است. در ادامه ضمن تعریف نمادهای مورد نیاز نحوه مدل سازی ریاضی آن ارائه خواهد شد .

6-6. مدل ریاضی مسئله
مدل ریاضی مسئله زمانبندی کار کارگاهیِکارگاهی چند مسیره با محدودیت دسترسی شناور ماشین ها ،یک مدل از نوع برنامه ریزی غیر خطی عدد صحیح میباشد. فرض کنید معرف تعداد کارها و

معرف تعداد ماشینها باشد. برای انجام هر کار چندین مسیر وجود دارد. تعداد کل مسیرهای کار را با و تعداد کل عملیات کار در مسیر را با نشان میدهیم . معرف
-418-821850

ماشین مورد نیاز برای انجام عملیات ام از کار ام در مسیر ام و زمان مورد نیاز برای انجام عملیات ام از کار ام در مسیر ام روی ماشین ام است. متغیرهای تصمیم گیریِ زمان شروع و ختم عملیات ام از کار ام در مسیر ام را به ترتیب
با و نشان میدهیم. فرض کنید معرف تعداد فعالیت نت که میبایستی روی ماشین ام انجام شود باشد .
82131622394

فعالیت نتِ ام روی ماشین ام را با و مدت زمان مورد نیاز برای انجام آن را با نشان میدهیم. انجام هر فعالیت نت در یک بازه زمانی از قبل تعیین شده میسر است. این بازه زمانی را با ، که در آن و به ترتیب زودترین زمان تکمیل و دیرترین زمان تکمیل فعالیت نتِ ام روی ماشین ام است، نشان میدهیم. متغیرهای تصمیم گیریِ زمان شروع و ختم فعالیت نتِ

ام روی ماشین

ام نیز با و نمادگذاری میشوند .جهت مدل سازی مسئله، چهار نوع متغیر صفر و یک به شرح زیر تعریف میشود:

31896829878



قیمت: تومان


دیدگاهتان را بنویسید