دانلود پایان نامه

MRS6

obsy hop paralel J

Dj
t2j
Dj – t2j
1
36
21
15
2
32
22
10
3
46
33
13
4
58
38
20
6
42
31
11

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

Job Number
3

32
32

2
28

32
32

13
3
29
32

12
12
20
32

هنگامی که الگوریتم شروع به کار می کند. خواهیم داشت : در فاز اول الگوریتم اولین کار را طبق توضیحات مندرج در الگوریتم مطابق جدول (3-23) به دست می آوریم. با توجه به جدول (3-23) کار شماره 5 انتخاب می شود. با توجه به جدول (3-24) مشاهده می کنیم که به ازای قرار دادن کار 5 روی هر یک از ترکیب های موجود مقدار یکسان و برابر 7 می باشد. لذا یکی از ترکیب ها را به دلخواه انتخاب می نمائیم. (ماشین و انتخاب می شود ) بعد از به روز رسانی زمان ماشین ها برابر است با: در تکرار دوم کار 2 طبق جدول (3-25) انتخاب می شود. برای تعیین ماشین های تخصیص داده شده به کار 2 طبق جدول (3-26) عمل می نمائیم. همانطور که مشاهده می کنیم در جدول (3-26) کوچکترین مقدار در ستون مربوط به ترکیب می باشد یعنی ماشین و انتخاب می شود. بعد از به روز رسانی زمان ماشین ها برابر است با: تکرار های بعدی الگوریتم به طور مشابه انجام می شود. نتایج نهایی الگوریتم شامل توالی کارها و ماشین های تخصیص یافته به کارها در مرحله اول و دوم در جدول (3-27) ارائه شده است.
توالی به دست آمده برای کارها و ماشین ها توسط الگوریتم MRS6
ترتیب انجام کارها
5
2
6
3
1
4
ماشین مرحله اول

ماشین مرحله دوم

ساختار الگوریتم پیشنهادی MRS7
الگوریتم پیشنهادی با استفاده از یک رویکرد پویا، ابتدا توالی مورد نظر را به دست آورده و زودترین ماشین های در دسترس در دو مرحله را تعیین کرده و کارها را به ترتیب روی ماشین های به دست آمده قرار می دهد ساختار این الگوریتم با الگوریتم MRS4 مشابهت دارد.
مراحل الگوریتم پیشنهادی به شرح زیر می باشد:
مرحله صفر:
فرض می کنیم :
مرحله یک: مقدار را برای کلیه کارها به دست آورده و به صورت صعودی مرتب می کنیم. اولین کاری که پردازش می شود مقدار کمتری دارد و به ترتیب آخرین کاری که پردازش می شود مقدار بزرگتری دارد. .(در صورتی که بیش از یک کار دارای شرط انتخاب باشد کاری انتخاب می شود که دارای زمان پردازش بزرگتری در مرحله اول خود می باشد) کار انتخاب شده را روی زودترین ماشین های در دسترس از مرحله اول و دوم قرار می دهیم. بعد از انتخاب ماشین برای کار انتخاب شده، با توجه به فرمول به روز رسانی زیر زمان های جدید ماشین ها را به دست می آوریم.
مرحله دو: اگر آنگاه
و یا اگر آنگاه
بعد از به روزرسانی، کار زمانبندی شده از مجموعهحذف شده و به مجموعه اضافه شود.
مرحله سه: اگر ، اجرای الگوریتم متوقف می شود و تابع هدف محاسبه می شود. در غیر اینصورت به مرحله یک بازمی گردیم.
الگوریتم پیشنهادی برای توضیح بیشتر توسط یک مثال ساده با 6 کار و دو ماشین در هر مرحله حل شده است. زمان های پردازش مربوط به مرحله اول و مرحله دوم کارها به همراه زمان های موعد تحویل در جدول (3-28) ارائه شده است.
زمان های پردازش و موعد تحویل و زمان آماده کار برای مثال ارائه شده
j
1
2
3
4
5
6

10
12
3
5
7
11

7
4
20
30
9
9

36
32
46
58
30
42

4
6
10
3
9
11

طبق اعداد به دست آمده جدول (3-29) توالی انجام کارها مطابق جدول (3-30) می باشد. طبق توالی به دست آمده اولین کار انتخاب شده کار شماره 5 می باشد که با توجه به صفر بودن زمان ماشین ها یکی از ماشین های مرحله اول و مرحله دوم به دلخواه تخصیص داده می شود. (در اینجا فرض می کنیم کار 2 را روی ماشین و قرار داده ایم) بعد از به روز رسانی زمان ماشین ها بربابر است با: کار بعدی کار 2 می باشد. زودترین ماشین های در دسترس ماشین های و می باشد.لذا کار 5 را به این 2 ماشین تخصیص می دهیم. بعد از به روز رسانی زمان ماشین ها برابر است با: الگوریتم را ادامه می دهیم تا زمانی که مجموعه K تهی شود یا به عبارت دیگر کلیه کارها زمانبندی شوند. نتایج نهایی الگوریتم شامل توالی کارها و ماشین هایی که آن کار در مرحله اول و دوم در جدول (3-30) ارائه شده است.
نحوه محاسبه توالی به دست آمده برای کارها توسط الگوریتم MRS7
j
1
2
3
4
5
6

10
12
3
5
7
11

7
4
20
30
9
9

36
32
46
58
30
42

4
6
10
3
9
11

15
10
13
20
5
21

توالی به دست آمده برای کارها و ماشین ها توسط الگوریتم MRS7
ترتیب انجام کارها
5
2
3
1
4
6
ماشین مرحله اول

ماشین مرحله دوم

نتایج محاسباتی الگوریتم های ابتکاری
مقدمه
در این فصل در ابتدا به نحوه طراحی مسائل جهت تست الگوریتم ها در هر فاز خواهیم پرداخت. و در ادامه نتایج مربوط به آزمون ANOVA و آزمون توکی و همچنین مقادیر متوسط به دست آمده برای هر یک از توابع هدف به ازای چندین بار اجرای الگوریتم ها و همچنین درصد عملکرد موفقیت آمیز هر یک از الگوریتم ها
در هر یک از توابع هدف را مورد بررسی قرار خواهیم داد. گفتنی است برای انجام آزمون های آماری مورد نظر از شاخص عملکرد درصد انحراف نسبی استفاده شده است. این شاخص توسط والاداو روئیز ]55 [ و همینطور حاجی آقایی و همکاران ]56 [ مورد استفاده قرار گرفته است.ما با توجه به برخی محدودیت ها که در ادامه به ان خواهیم پرداخت، شاخص RD به شکل زیر استفاده می کنیم.

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

نتایج فاز اول
آزمایشات عددی
در این بخش در ابتدا پارامترهای مدل شبیه سازی را تعریف شده و مدل مربوطه توسط زبان برنامه نویسی ویژوال بیسیک توسعه داده شده است. پس از آن برای مقایسه الگوریتم پیشنهاد شده با سایر الگوریتم ها آزمایشات عددی را تحت شرایط مختلف انجام شده است. به عبارت دیگر الگوریتم MRS1 را با سایر الگوریتم های استفاده شده در منابع موجود در ادبیات موضوع در 216 مساله مختلف مقایسه شده است.
پارامترهای مدل شبیه سازی
پارامترهای مدل شبیه سازی در جدول (3-31) لیست شده است و جزئیات آن به صورت مشروح در زیر آمده است.
1- تعداد ماشین ها (NM) : در این مساله ما سه سطح برای مسائل کوچک و 3 سطح برای مسائل بزرگ در نظر گرفتیم. در یکی از سطوح تعداد ماشین ها در مرحله اول بیشتر از تعداد ماشین ها در مرحله دوم است. در سطح دیگر تعداد ماشین ها در دو مرحله با یکدیگر برابراست و در آخرین سطح تعداد ماشین ها در مرحله دوم بیشتر از تعداد ماشین ها در مرحله اول است.
2- تعداد کارها (N) : مشابه تعداد ماشین ها، 3 نوع از کارها را برای هر یک ار سطوح ماشین ها در نظر گرفتیم که مجموعا 9 ترکیب مختلف به وجود می آورد.
3- توزیع زمان های پردازش(DT) : برای این پارامتر دو نوع توزیع در نظر گرفته شده است که این توزیع ها عبارتند از: توزیع نرمال و توزیع یکنواخت.و در هر توزیع ، دو مقدار متفاوت برای توزیع ها در نظر گرفته شده است.
4- الگوریتم ها: در این تحقیق ما 4 الگوریتم را در کنار الگوریتمتست نمودیم. اولین الگوریتم ابتکاری، الگوریتم است که توسط جینکسینگ ژی و همکاران]45 [ ارائه شد و در این مقاله به اختصار آنرا می نامیم. دومین الگوریتم ابتکاری که تست شد، الگوریتم پیشنهادی است که در این مقاله به اختصار آنرا می نامیم.. سومین الگوریتم ابتکاری که تست شد، الگوریتم است که در این مقاله به اختصار آنرا می نامیم. چهارمین الگوریتم ابتکاری، الگوریتم است که در این مقاله به اختصار آنرا می نامیم. پنجمین الگوریتم ابتکاری، که در مدل شبیه سازی مورد تست واقع شد الگوریتم بود که توسط جانسون ]8 [ ارائه شد و آن را به اختصار در این مقاله با نمایش می دهیم. در میان الگوریتم های تست شده تنها الگوریتم های ، علاوه بر تولید توالی کارها، تخصیص کار به ماشین ها را نیز انجام می دهند.بنابراین رویکرد در نظر گرفته شده برای سایر الگوریتم ها به این شکل می باشد. زودترین ماشین در دسترس به کاری که در اولویت زمان بندی است برای سایر الگوریتم ها تخصیص می یابد.
فرایند شبیه سازی
در این بخش چگونگی اجرای شبیه سازی توضیح داده شده است. مدل اشاره شده در بخش قبل توسط زبان برنامه نویسی ویژوال بیسیک نوشته شد و تست ها به منظور ارزیابی الگوریتم ها توسط کامپیوتر شخصی با پردازنده 3.4 GHZ و 895 MB اجرا شد. این تست ها برای ترکیب های مختلفی از پارامترها انجام شد. در انتها نتایج به دست آمده توسط پروسه آنالیز واریانس و آزمون توکی نرم افزار 14 Minitab انجام شده است.

این مطلب رو هم توصیه می کنم بخونین:   تحقیق دربارهنقشه راه

پارامترهای مدل شبیه سازی برای فاز اول

مقیاس
طبقه
فاکتورها
تعداد سطوح
سطوح
کوچک
1
تعداد ماشین ها
3

بزرگ

3

کوچک
&
بزرگ
2
تعداد کارها

کوچک
&
بزرگ
3
تابع توزیع زمان های پردازش
4

کوچک
&
بزرگ
5
الگوریتم ها
6

نتایج شبیه سازی
طبق جدول (3-32) مقدار P-Value به دست آمده کمتر از مقدار می باشد. لذا فرض تساوی میانگین الگوریتم ها رد می شود. در جدول (3-32) فاصله اطمینان 95% برای RD هر یک از الگوریتم ها آورده شده است. فاصله اطمینان به دست آمده برای الگوریتم پیشنهادی MRS1 به طور قابل ملاحظه ای با سایر الگوریتم ها فاصله دارد.در جدول (3-32) میانگین درصد بهره برداری از ماشین آلات به ازای 216 بار اجرای الگوریتم به دست آمده است. همچنین در جدول (3-32) تعداد موفقیت هر یک از الگوریتم ها در 216 با اجرای مساله نمایش داده شده است. و در نهایت میزان متوسط زمان اجرای مساله در (جدول3-32)نمایش داده شده است. با توجه به اینکه فرض صفر آزمون ANOVA یعنی برابرای میانگین الگوریتم ها، رد می شود. بنابراین برای بررسی عملکرد الگوریتم ها از آزمون مقایسات زوجی توکی استفاده می کنیم. این نتایج به صورت خلاصه شده در جدول (3-32) آورده شده است. گفتنی است علامت * نشاندهنده پذیرفته شدن فرض برابری دو الگوریتم می باشد.
نتایج فاز اول برای تابع هد
ف ماکزیمم کردن درصد بهرهبرداری از ماشین آلات

One-way ANOVA: MDA, MRS1, LPT, SPT, Johnson

Source DF SS MS F P
Factor 4 4.08689 1.02172 554.76 0.000
Error 1075 1.97988 0.00184
Total 1079 6.06677

Johnson
SPT
LPT
MDA
MRS1

MRS1

MDA

LPT
*

SPT

Johnson

نتایج فاز دوم
آزمایشات عددی
در این بخش در ابتدا پارامترهای مدل شبیه سازی را تعریف شده و مدل مربوطه توسط زبان برنامه نویسی ویژوال بیسیک توسعه داده شده است. پس از آن برای مقایسه الگوریتم پیشنهاد شده با سایر الگوریتم ها آزمایشات عددی تحت شرایط مختلف انجام شده است. به عبارت دیگر الگوریتم های MRS4 MRS2,MRS3, با سایر الگوریتم های استفاده شده در منابع موجود در ادبیات موضوع در 324 مساله مختلف مقایسه شده است.
پارامترهای مدل شبیه سازی
پارامترهای اضافه شده و تغییر یافته نسبت به مدل شبیه سازی قبل در جدول (3-33) لیست شده است.
این پارامترها عبارتند از: 1- تعداد ماشین ها 2- تعداد کارها 3-تابع توزیع زمان های پردازش4- تابع توزیع زمان های موعد تحویل 5- الگوریتم ها
تعریف پارامترهای ذکر شده مشابه فاز اول می باشد با این تفاوت که برای تابع توزیع زمان های پردازش در هر یک از توزیع های یکنواخت و نرمال یک توزیع در نظر گرفته شده است.همچنین تابع توزیع زمان های موعد تحویل (DD)به این فاز اضافه شده است. برای این پارامتر 3 سطح در نظر گرفته شده است که عبارتند از : توزیع خوش بینانه، توزیع منطقی و توزیع بدبینانه.
پارامترهای مدل شبیه سازی برای فاز دوم

مقیاس
طبقه
فاکتورها
تعداد سطوح
سطوح
کوچک
&
بزرگ
3
تابع توزیع زمان های پردازش
2

کوچک
&
بزرگ
4
تابع توزیع زمان های موعد تحویل
3

کوچک
&
بزرگ
5
الگوریتم ها
9

فرایند شبیه سازی
مشابه فاز اول می باشد.
نتایج شبیه سازی
تابع هدف مینیمم سازی ماکزیمم زمان اتمام کارها:
طبق جدول (3-34) مقدار P-Value به دست آمده کمتر از مقدار می باشد. لذا فرض تساوی میانگین الگوریتم ها رد می شود. در (جدول3-34) فاصله اطمینان 95% برای RD هر یک از الگوریتم ها آورده شده است. فاصله اطمینان به دست آمده برای الگوریتم پیشنهادی MRS2 و MRS3به طور قابل ملاحظه ای با سایر الگوریتم ها فاصله دارد. با توجه به اینکه فرض صفر آزمون ANOVA یعنی برابری میانگین الگوریتم ها، رد می شود. بنابراین برای بررسی عملکرد الگوریتم ها از آزمون مقایسات زوجی توکی استفاده می کنیم. این نتایج به صورت خلاصه شده در جدول (3-34) آورده شده است.
نتایج فاز دوم برای تابع هدف مینیمم سازی ماکزیمم زمان کارها

One-way ANOVA: MRS2, MRS3, MRS4, EDD, MDA, MRS1, LPT, SPT, Johnson

Source DF SS MS F P
Factor 8 4129.39 516.17 114.77 0.000
Error 2907 13073.76 4.50
Total 2915 17203.15

Johnson
SPT
LPT
MRS1
MDA
EDD
MRS4
MRS3
MRS2

*

MRS2

MRS3
*
*
*

*
*

MRS4

*

*

EDD
*
*
*

MDA

MRS1
*
*

LPT
*

SPT

Johnson

تابع هدف مینیمم سازی


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