International Journal of Industrial Engineering & Production Management (2013)

-144144-24523

November 2013, Volume 24, Number 3
pp. 327-338

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

A Multi-Objective Fuzzy Job Shop Scheduling by Extremal
Optimization

M.Nosratabadi, M.Vafaei Jahan* & M.R. Akbarzadeh Totonchi

Masoud Nosratabadi, M.S. Computer, Azad University, Mashhad, Iran
Majid Vafaei Jahan, Computer Engineering Department, Azad University, Mashhad, Iran
Mohamad Reza Akbarzadeh Totonchi, Computer and Electronic Engineering Department, Ferdusi Mashhad University, Mashhad, Iran
Keywords 1ABSTRACT

1268732040127

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

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

Fuzzy Job Shop Scheduling,
Extremal Optimization,
Multi-Objective Problems
20919442084408

Job shop scheduling deals with distributions between jobs in order to find a schedule with minimum possible time. To formulate job shop scheduling problems, various factors such as the activity processing time and due date for delivering jobs are often ambiguously known to the analyst. In these situations, the use of fuzzy parameters and multi-objective goals based on fuzzy knowledge seems necessary. Since this problem is non polynomial, we propose a method based on extremal optimization in order to select and modify less valuable but more probable activities. This method leads to decrease the number of less valuable activities and to increase the number of activities with the same value. In such cases, any partial change in scheduling may produce big changes. For instance, it leads to escape from local optima and move toward global one. Lots of simulations on and experimental data, demonstrate proper convergence rate and good results in comparison with other methods. The correctness of given results and proposed algorithm have been proven by means of axiom of convergence, statistical t-test t and possibility error (F).

© 2013 IUST Publication, IJIEPM. Vol. 24, No. 3, All Rights Reserved

*
Corresponding author. Majid Vafaei Jahan Email: VafaeiJahan@mshdiau.ac.ir

زمانبندی کار فازی چند هدفه با استفاده از الگوریتم بهینهسازی اکسترمال

مسعود نصرت آبادی، مجید وفایی جهان* و محمد رضا اکبرزاده توتونچی

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

-137152875

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

میباشد، بههمین دلیل روشی مبتنی بر الگوریتم اکتشافی بهینهسازی اکسترمال پیشنهاد میشود. بهطوری که فعالیت-های کم ارزش را با احتمال بیشتر انتخاب و تغییر میدهد، این باعث میشود تعداد فعالیتهای کم ارزش، کمتر و تعداد فعالیتهای با ارزش یکسان، بیشتر شود در این حالت هر تغییر جزئی در زمانبندی ،تغیرات زیادی در آن ایجاد میکند بنابراین باعث فرار از بهینه محلی شده و به سمت بهینه سراسری حرکت میکند. با توجه به نتایج حاصل از شبیهسازی بر روی دادههای آزمایشی و

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

1. مقدمه1
دردهه گذشته، کاربرد مختلف مسائل زمانبندی درحوزههای مختلفی ازقبیل صنعت، اقتصاد و علوم پایه سبب شده تا تحقیقات گستردهای در این زمینه صورت گیرد. به طورخاص، تلاشهای قابل توجهی در زمینه توسعه و تکامل الگوریتمهای اکتشافی برای این منظور صورت گرفته است. مساله زمانبندی کارکارگاهی یکی از سختترین مسائل بهینهسازی ترکیبی میباشد که به
تاریخ وصول: 3/6/39 تاریخ تصویب: 3/1/31
مسعود نصرت آبادی، کارشناس ارشد مهندسی کامپیوتر- نرم افزار، دانشگاه آزاد اسلامی- واحد مشهد،Msd.Nosratabadi@gmail.com
*نویسنده مسئول مقاله: دکتر مجید وفایی جهان، استادیار گروه کامپیوتر-
نرم افزار، دانشگاه آزاد اسلامی-واحد مشهد.VafaeiJahan@mshdiau.ac.ir دکتر محمد رضا اکبرزاده توتونچی استاد گروه برق و کامپیوتر، دانشگاه فردوسی مشهد ،Akbarzadeh@ieee.org
1268732040127

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

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

عنوان یک مساله معروف است]1[، بطوریکه تاکنون الگوریتمهای اکتشافی زیادی برای حل آن پیشنهاد شده-است. یکی از اولین تلاشهای صورت گرفته جهت زمانبندی کارکارگاهی، ارائه نوعی الگوریتم ژنتیک بود که میتوان آن را در کار تحقیقاتی دیویس3 در سال 1985 ملاحظه نمود ]2[. پس از آن تعداد قابل توجهی از کاربردهای الگوریتم ژنتیک و دیگر الگوریتمهای اکتشافی در مسائل زمانبندی کار کارگاهی به چشم میخورد]3-4-5[. در این مقاله به دلیل ویژگیهای خاص نوعی الگوریتم اکتشافی، به نام الگوریتم بهینهسازی اکسترمال]6[، به حل نوعی مساله زمانبندی کار کارگاهی، با استفاده از این الگوریتم پرداخته میشود. در مسائل زمانبندی کارکارگاهی ، فاکتورهای مختلفی از جمله زمان پردازش هر فعالیت و زمان موعد مقرر تحویل کار، به صورت مقادیری دقیق و قطعی تعریف میگردد. البته به هنگام فرمولبندی مسائل زمان بندی کارکارگاهی، بسیاری از فاکتورها بطور ناقص یا مبهم برای
3 Davis

1268732040127

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

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

913
تحلیلگر تعریف میشوند]17،9[. این مشکل بطور خاص در بسیاری از موقعیتهای دنیای واقعی، مخصوصا هنگامی که عوامل انسانی در اینگونه مسائل دخیل میگردند، صادق میباشد. در چنین شرایطی، در نظر گرفتن زمان پردازش فازی با توجه به عوامل انسانی مناسبتر میباشد و زمان موعد مقرر فازی نیز باعث تحمل تاخیر احتمالی در زمان انجام کار میشود. به طور واضحتر ،با ملاحظه برخی از عوامل انسانی موجود در عملیات و برنامهریزی زمانبندی کار کارگاهی، بطور غیر قابل انکاری به فازی بودن زمانهای پردازش، پی برده میشود و با توجه به زمانهای موعد مقرر تحویل کارها میتوان موقعیتهای مختلفی را در نظر گرفت ،که در آنها رضایتمندی زمان موعد مقرر مطلوب میباشد و البته با مقدار معینی تاخیر، درجه رضایتمندی کاهش مییابد. گری1 وهمکارانش ]1،1[ ثابت کردند که مساله زمانبندی کار کارگاهی یک مساله

است، بنابراین از آنجایی که مساله زمانبندی کار کارگاهی فازی بسط مساله زمانبندی کار کارگاهی با زمان پردازش فازی برای هرفعالیت و زمان موعد مقررفازی برای تحویل هر کار می باشد، این مسئله قویا

خواهد
بود .
به همین دلیل در این مقاله برای ایجاد حل مساله زمانبندی کار کارگاهی از الگوریتم اکتشافی بهینهسازی اکسترمال استفاده می-شود. به طور معمول برای مسائل زمانبندی کار کارگاهی از جمله مسئله زمانبندی کار کارگاهی فازی تنها یک تابع هدف در نظر گرفته میشود، اما برای انعکاس مناسبتر موقعیتهای دنیای واقعی، در زمانبندی کار کارگاهی فازی، استفاده از توابع چندهدفه مطلوب و لازم به نظر میرسد، بدین منظور در این مقاله یک زمانبندی چند هدفه تعریف میشود .
از این رو بر اساس زمان تکمیل فازی هر کار، زمان موعد مقرر فازی برای تحویل هر کار و شاخصی برای بیان میزان رضایتمندی زمان انجام هر کار، در برابر زمان موعد مقرر تحویل آن کار)شاخص توافق2(، زمانبندی چند هدفه کار کارگاهی فازی، با سه هدف: بیشینه کردن مینیمم شاخص توافق، بیشینه کردن میانگین شاخص توافق و کمینه کردن ماکزیمم زمان تکمیل فازی کارها تعریف میشود]7[. علاوه بر این، با در نظر گرفتن ماهیت غیر قطعی تصمیمگیریهای انسانی، فرض میشود که فرد تصمیم گیرنده برای هر یک از توابع هدف، دارای یک هدف فازی میباشد و بعد از مشخص کردن توابع عضویت خطی این اهداف، برای ادغام آنها، از روش فازی بلمن3 و زاده4 ]11[ یا عملگر مینیمم استفاده میشود. برای بیان کارآمدی الگوریتم بهینهسازی
1 Garey
اکسترمال جهت زمانبندی کار کارگاهی فازی و مشاهده نتایج آن ،از مجموعه دادههای عددی و

که در ]3[ ارئه شده است، استفاده میشود. در ادامه در بخش مساله کار کارگاهی فازی تعریف میشود و در بخش 3 عملگرهای فازی استفاده شده توضیح داده میشود و سپس در بخش 4 اهداف مساله مطرح میشود، در بخش 5 روش پیشنهادی بیان میشود و در نهایت شبیهسازی و مقایسه نتایج آزمایشگاهی همراه با آزمون آماری جهت اثبات درستی روش پیشنهادی و همچنین مثالی جهت بررسی و مقایسه نهایی جواب مساله بیان میشود.

1. تعریف مساله کار کارگاهی فازی
11526514952

537540844262

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

بر روی ماشین یک فعالیت نامیده میشود و بهصورت زوج مرتب و یا بهصورت نشان داده میشود و همچنین هر کار شامل عملیات می باشد . بین هر دو
فعالیت، یک کار، یک رابطه پیش نیازی وجود دارد، ولی بین هر دو فعالیت از کارهای مختلف هیچ گونه رابطه پیش نیازی وجود ندارد. هر یک از کارها برای پردازش بر روی ماشینها دارای یک مسیر پردازش مختص خود است که بوسیله توالی ماشینها مشخص میشود و در واقع روابط پیشنیازی ما بین فعالیتهای آن را نشان میدهد. علاوه بر محدودیتهای فوق، مفروضات و محدودیتهای دیگری نیز وجود دارد که عبارتند از]12-11[:
کارها از توالی منظم عملیات تشکیل شده است.
یک کار، دو بار روی یک ماشین اجرا نمی شود.
از هر ماشین فقط یک نوع در کارگاه موجود است.
پس از شروع عملیات با یک ماشین قطع آن مجاز نیست .
هر ماشین در یک زمان فقط میتواند یک عملیات را انجام دهد.
هر ماشین پیوسته برای تولید در دسترس است.
9. یک کار به طور همزمان نمی تواند روی چند ماشین اجرا شود.
یکی از فاکتورهای مهمی که در مساله زمانبندی کار گارگاهی وجود دارد زمان موعد مقرر برای تحویل هر کار میباشد، منظور از زمان موعد مقرر، حداکثر زمانی است که برای تکمیل یک کار در نظر گرفته میشود که در واقع زمان تکمیل هر کار باید کمتر از زمان موعد مقرر آن کار باشد. بر خلاف مساله زمانبندی کلاسیک

، در این مساله زمان پردازش هر عمل و زمان موعد مقرر هر کار به صورت مقادیری فازی میباشند. در مساله
زمانبندی کار کارگاهی فازی، زمان پردازش عملیات

از طریق متغیر مثلثی فازی

که بصورت سهتایی نشان داده میشود، بیان میشود )شکل

مربوط

مقرر

.)
موعد

زمان

همچنین

کار

به

فازی

متغیر

با

دوتایی

که
بصورت

مشخص

است
،
بیان

می
شود

شکل
(

)
[
7
.]

مربوط

مقرر



قیمت: تومان


پاسخ دهید