International Journal of Industrial Engineering & Production Management (2012)

-135635-23819

September 2012, Volume 23, Number 2
pp. 149-160

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

Modelling a Novel Multi-Objective Open-Shop Scheduling Problem and Solving by a Scatter Search Method

N. Amiri, R. Tavakkoli-Moghaddam*, Y. Gholipour-Kanani & S.A. Toarbi

Nafiseh Amiri, Department of Industrial Engineering, Research & Science Branch, Islamic Azad University, Tehran, Iran.
Reza Tavakkoli-Moghaddam, Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran. Yosouf Gholipour-Kanani, Faculty of Management, Qaemshahr Branch, Islamic Azad University, Qaemshahr, Iran. Seyed Ali Torabi, Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

Keywords 1ABSTRACT

Open shop scheduling problems,
Tardiness and earliness time,
Makespan, Setup cost, NSGA-II,
Multi-objective scatter search This paper proposes a novel, multi-objective integer programming model for an open-shop scheduling problem (OSSP). Three objectives are to minimize the makespan, total job tardiness and earliness, and total jobs setup cost. Due the complexity to solve such a hard problem, we develop a meta-heuristic algorithm based on multiobjective scatter search (MOSS), and a number of test problems are solved by this proposed algorithm. Finally, to prove its efficiency, the related results are compared with the results obtained by the wellknown multi-objective evolutionary algorithm, called NSGA-II. The results confirm the efficiency and the effectiveness of our proposed MOSS to provide good solutions, especially for medium and largesized problems.

© 2012 IUST Publication, IJIEPM. Vol. 23, No. 2, All Rights Reserved

*
Corresponding author. Reza Tavakkoli-Moghaddam Email: tavakoli@ut.ac.ir

م دل سازي يک مسأله زمانبن دي کارگاه باز چن د هدفه ج دي د و ح ل آن با استفاده از روش جستجوي پراکن ده

نفيسه اميري، رضا توکلي مق دم*، يوسف قليپورکنعاني و سي دعلي ترابي

کلمات کليدي چکي ده:

مسايل زمانبندي کارگاه باز، در اين مقاله، يک مدل رياضي چندهدفه جديدي براي زمانبندي توليد در محيط کارگاه باز ارايه زمان ديرکرد و زودکرد، ميشود. اهداف مدل پيشنهادي شامل حداقل نمودن حداکثر زمان تكميل کارها، مجموع زمان حداکثر زمان تكميل کارها، ديرکرد و زودکرد کارها و مجموع هزينه راهاندازي کارها است. مسأله مورد نظر با توجه به ماهيت هزينه راهاندازي، پيچيده آن در زمره مسايل NP-hard قرار مي گيرد، بنابراين يک الگوريتم فراابتکاري چندهدفه بر جستجوي پراکنده چند هدفه، مبناي روش جستجوي پراکنده براي حل آن ارايه می شود و مسايل متنوعی با ابعاد مختلف مورد NSGA-II حل قرار میگيرد. در نهايت براي اثبات کارايی روش پيشنهادي، نتايج حاصل از آن با جوابهاي توليد شده توسط ي ك روش تكاملي چندهدفه معروف به NSGA-II مقايسه می شوند. نتايج مربوطه نشان دهنده کارايي روش پيشنهادي در توليد جوابهاي با کيفيت، متنوع و داراي پراکندگي بالا است.

سوددهي واحدهاي توليدي مي گردد [۳]. يک مسأله زمانبندي در محيط کارگاه باز با مجموعه اي از فعاليت ها مواجه است که در انجام آن ها لزومي به رعايت ترتيب خاصي وجود ندارد. بنابراين فضاي حل در مسايل زمان بندي کارگاه باز بهطور قابل ملاحظهاي از فضاي جواب مسايل زمانبندي ديگر نظير زمانبندي گردش کاري و توليد کارگاهي بزرگتر است که البته محققان تاکنون توجه کمتري نسبت به اين مسايل داشته اند [۳].
در يک مسأله زمانبندي در محيط کارگاه باز

ماشين و

کار در نظر گرفته مي شوند که هر کار حداکثر ميتواند شامل

عمليات باشد. هر عمليات بايستي بر روي يک ماشين با زمان پردازش معين انجام شود. مسأله توليد کارگاه باز مشابه مسأله توليد کارگاهي بوده ولي با اين تفاوت که ممکن است کارها بر روي يک ماشين با هر توالي دلخواهي پردازش شود. بنابراين در اين مسايل توالي وابسته به عمليات وجود ندارد.
شا و سو [۴] الگوريتمي را بر مبناي الگوريتم بهينه سازي ذرات انبوه در محيط کارگاه باز ارايه نمودند. اندرسون و همکاران [۵] الگوريتمي بر مبناي شبيهسازي تبريد و الگوريت م ژنتيک براي ۱. مقدمه١
زمان بندي عمل تعيين اولويت ها و يا مرتب نمودن فعاليت ها براي برآورده نمودن الزامات مشخص، محدوديت ها و يا اهداف است [۱].
زمان بندي يک فرآيند تصمي م گيري است که در تنظيمات
حمل و نقل و توزيع و ساير انواع صنايع توليدي و خدماتي بکار ميآيد [۲]. يک برنامه زمانبندي کارا منجر به بهره برداري مؤثر از ظرفيتهاي توليد، کاهش زمان تکميل کارها و در نهايت افزايش
تاريخ وصول: ۱۹/۴/۸۹
تاريخ تصويب: ۲۹/۳/۹۰
نفيسه اميري، دانش آموخته كارشناسي ارشد گروه مهندسي صنايع، دانشکده فني و مهندسي، واحد علوم تحقيقات، دانشگاه آزاد اسلامي،
nafiseh_amiri@yahoo.com
*نويسنده مسئول مقاله: دكتر رضا توکلي مق دم، استاد گروه مهندسي

صنايع، پرديس دانشكده هاي فني، دانشگاه تهران، tavakoli@ut.ac.ir
يوسف قلي يپورکنعان، مربی گروه مديريت، واحد قائ مشهر، دانشگاه آزاد
gholipourkanani@yahoo.com ،اسلامي
سي دعلي ترابي، دانشيار گروه مهندسي صنايع، پرديس دانشكده هاي فني،
satorabi@ut.ac.ir ،دانشگاه تهران
ل دـورشهري ـ ـورشماره المللالملليصنايصنايع
کمينه سازي ميانگين زمان جريان ساخت در مسأله زمانبندي کارگاه باز ارايه نمودند. چن و همکاران [۶] به بررسي توالي هاي انبوه براي مسأله زمانبندي کارگاهي باز با فرض وجود زمان هاي ترخيص پرداختند . لو و يه [۷] الگوريت م ژنتيکي را بر مبناي روش هاي ابتکاري براي مسأله بنديزمان کارگاه باز ارايه نمودند.
آنها فرض نمودند که هايزمان آماد ه سازي و پردازش و تخليه مجزا از يکديگر مي باشند. معياري که آنها براي کمينه سازي انتخاب نمودند، ديرکرد کل کارها مي باشد. بلام [۸] بر روي ترکيب الگوريت م بهينه سازي مورچگان و جستجوي پرتو کار نموده و کاربرد آن را بر روي الگوريتم زمان بندي کارگاه باز مورد بررسي قرار داده است. لياو و همکاران [۹] بنديزمان دو ماشينه در محيط کارگاه باز را در حالت بدون توقف مورد بررسي قرار دادند. لياو [۱۰] الگوريت م را بر مبناي جستجوي ممنوع براي حل مسأله بنديزمان کارگاه باز دو ماشينه با فرض مجاز بودن انقطاع کارها ارايه کرد. تابع هدف کمينه سازي نيز ديرکرد کل مي باشد.
کنونف و سويريدنکو [۱۱] روش تقريبي را براي كمينهسازي حداکثر زمان تکميل کارها در محيط کارگاه باز با فرض موعد زمان ترخيص ارائه کردند. بريت، اشميت و استروسويچ [۱۲] مسأله زمان بندي کارگاه باز را در حالت دو ماشينه با محدوديت دسترسي مورد بررسي قرار دادند. لياو [۱۳] الگوريت م ژنتيک ترکيبي را براي مساله زمانبندي کارگاه باز ارايه کرده است و سپس الگوريت م ژنتيک را با جستجوي ممنوع ترکيب نموده و کاربرد آن را بر روي مسأله کارگاه باز مورد بررسي قرار داده است.
کراوچنکو [۱۴] به مطالعه کمينه سازي تعداد کارهاي همراه با ديرکرد در محيط کارگاه باز زمان واحد پرداخت. لياو [۱۵] يک روش تقريبي براي يافتن کمترين مقدار حداکثر زمان تکميل کارها در يک مسأله کارگاه باز با فرض غير مجاز بودن انقطاع ارايه کرد.
لياو [۱۶] مساله زمان بندي کارگاه باز را در حالت عدم وجود
انقطاع مورد بررسي قرار داد. وي الگوريت م شبيه سازي تبريدي را براي کمينه سازي حداکثر زمان تکميل کارها ارايه کرده است.
سراج و توکلي مقدم [۱۷] يک الگوريت م جستجوي ممنوع چندهدفه جديد که بر مبناي رويکرد تصميم گيري چندهدفه فازي است، را براي حل مسأله کارگاه باز دوهدفه ارايه نمودند.
در اين مقاله، مسأله زمانبندي در محيط کارگاه باز مورد بررسي قرار ميگيرد. با توجه به اينکه در دنياي واقعي تصميم گيرنده در بسياري از مواقع نيازمند است تصمي م خود را نه تنها بر اساس يک هدف بلکه بر اساس مجموعه اي از اهداف موجود اتخاذ نمايد؛ لذا وجود يک روش حل مسأله چند هدفه مي تواند موجب رسيدن به جواب هاي واقعي تر، عملي تر و کاربرديتر شود. اين مقاله، به ارايه يک مدل رياضي جديد چندهدفه براي حداقل نمودن حداکثر
۱۵۱
زمان تکميل کارها، حداقل کردن زمان ديرکرد و زودکرد کارها وحداقل کردن هزينه راه اندازي در محيط کارگاه باز که تاکنون بهآن پرداخته نشده است، مي پردازد. اين مسأله با توجه به ماهيتپيچيده آن در زمره مسايل NP-Hard قرار مي گيرد [۱۸]، لذا ميتوان از الگوريت م هاي فراابتکاري جهت حل اينگونه مسايل استفاده کرد. سپس براي حل مسأله مورد نظر در ابعاد کوچک، متوسط و بزرگ، يک الگوريت م جستجوي پراکنده چند هدفه براي يافتن تقريب خوبي از جواب بهينه پارتو براي حداقل نمودن سه تابع هدف پيشنهاد مي شود.
ويژگي متمايز الگوريتم جستجوي پراکنده چند هدفه پيشنهادي در جستجوي فضاي جواب مسأله از طريق يک روش هوشمند است که بر خلاف روش هاي فراابتکاري ديگر مانند الگوريت م ژنتيک، از روشي صرفاﹰ تصادفي و در برخي موارد، بدون پشتوانه منطقي، اجتناب ميورزد و همچنين استفاده از جواب هاي با بهترين کيفيت و بيشترين پراکندگي براي به دست آوردن جواب هاي غالب است. در انتها نيز براي اثبات کارايي روش پيشنهادي، نتايج حاصل از آن با جوابهاي توليد شده توسط روش NSGA-II مقايسه ميشود. الگوريت م NSGA-II، ي ك الگوريت م چند هدفه، نخبه گرا و بر اساس الگوريت م ژنتيک است که توسط دب [۱۹] ارايه شده است. کارايي اين الگوريتم از لحاظ پراکندگي بيشتر جوابها ونزديک تر بودن جوابها به منحني پارتو واقعي بهتر از دو الگوريت م ه م طبقه خود به نام هاي PAES و SPEAمي باشد. در نتيجه با توجه به کارايي بالاي الگوريت م NSGA-II و استفاده ساير نويسندگان و پژوهشگران از اين الگوريتم براي مقايسه نتايج محاسباتي، در اين مقاله براي مقايسه کارايي الگوريت م پيشنهادي، از الگوريت م NSGA-IIاستفاده شده است. اين مقاله، از بخش هاي زير تشکيل شده است، بخش ۲ شامل مدل رياضي جديد براي مسأله مورد نظر است. بخش ۳ به ارايه روش جستجوي پراکنده پيشنهادي براي حل مسأله مورد نظر اشاره مي پردازد. نتايج محاسباتي در بخش ۴ و سپس نتيجه گيري نيز در بخش ۵ آورده ميشود.

۲. م دل پيشنهادي
مدل پيشنهادي چند هدفه با تشريح مفروضات, پارامترها، متغيرها، تابع هدف و محدوديت ها در ادامه ارايه مي گردد.

۱ ‐ ۲. مفروضات م دل
مفروضات در نظر گرفته شده براي اين مدل عبارتند از:
کارها ميتوانند بر روي ماشينها با هر ترتيب دلخواهي پردازش شوند.
زمان پردازش کارها بر روي ماشينهاي متفاوت ممکن استبا ه م تفاوت داشته باشد.
۱۵۲
هر کار در لحظه مي تواند فقط بر روي يک ماشين پردازش شود و هر ماشين در لحظه تنها مي تواند يک عمليات را انجام دهد.
بريدگي کارها و خرابي ماشين ها مجاز نمي باشد.
هر کار داراي موعد تحويل معيني است.
از هر نوع ماشين تنها يکي در محيط کاري وجود دارد.
تمامي ماشين ها از ابتدا در دسترس مي باشند.
هزينه راه اندازي هر کار بر روي ماشين به کار قبلي روي همان ماشين بستگي دارد.
زمانهاي پردازش و موعدهاي تحويل قطعي است.

۲ ‐ ۲. ان ديس ها
انديسهاي بکار رفته در مدل رياضي اين مساله به صورت زير است:
i و j : نماد کارها است که متعلق به مجموعه {i={1,…,n است و n تعداد کارها است.
k : نماد ماشين که متعلق به مجموعه {j={1,…,m مي باشد و m تعداد ماشين ها است.

۳ ‐ ۲. پارامترهاي ورودي مسأله
مقادير پارامترهاي ورودي که بايد در ابتداي حل مدل رياضي مشخص شوند, عبارتند از: زمان پردازش، زمان تکميل کارها، موعد تحويل کارها، عمليات مربوط به کارها بر روي ماشين ها، هزينه راه اندازي ماشين ها. وروديها با نمادهاي زير نشان داده ميشوند:
Tik: زمان پردازش کار i روي ماشين k di: موعد تحويل کار i

: عمليات مربوط به کار i روي ماشين k
(:Si(j,k هزينه راه اندازي ماشين k براي کار j وقتي که کار قبلي روي ماشين k و i باشد.

۴ ‐ ۲. متغيرهاي تصميم گيري Cik: زمان تکميل کار i روي ماشين k mci: زمان تکميل کار i

۵ ‐۲. مدل رياضي
مدل رياضي سه هدفه پيشنهادي به صورت زير ارايه مي شود:

(۱)

(۲)

(۳)



قیمت: تومان


پاسخ دهید