International Journal of Industrial Engineering & Production Management (2012)

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

-135635-23819

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

در این سایت فقط تکه هایی از این مطلب درج می شود که ممکن است هنگام انتقال از فایل ورد به داخل سایت کلمات به هم بریزد یا شکل ها درج نشود

شما می توانید تکه های دیگری از این مطلب را با جستجو در همین سایت بخوانید

ولی برای دانلود فایل اصلی با فرمت ورد حاوی تمامی قسمت ها با منابع کامل

به سایت مرجع

www.homatez.com

مراجعه نمایید

 

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

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

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

ماشین و

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

صنایع، پردیس دانشکده های فنی، دانشگاه تهران، 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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

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

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

(۱)

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

(۲)

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1

(۳)

دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1


دانلود رایگان تحقیقrtavakkoli A 10 243 9 9309c0c 1
قیمت: تومان

پاسخ دهید