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
0
32
32

2
28
0
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

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


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