از توالی شلیک انتقال ها در مدل پتری نت استفاده میکند. عملگر انتخاب آن روش مسابقه ای95 و عملگر تبادل آن تبادل تک نقطه ای96 است و برای جهش دو ژن بصورت تصادفی انتخاب شده مکان آنها هم جابجا می شود.
از مزایای این الگوریتم استفاده از پتری نت برای مدل سازی، شبیه سازی و زمانبندی سیستمهای تولید انعطاف پذیر است و از معایب آن، اعمال محدودیت های زیاد برای سیستم های تولید انعطاف پذیر و در نظر نگرفتن مساله توزیع شدگی و مساله نگهداری است.
الگوریتم GA-ACO97
Rossi و Boschi یک الگوریتم ابتکاری ترکیبی برای حل مساله زمانبندی کار کارگاهی با ماشینهای موازی ارائه دادند که هدف آن کمینه کردن زمان اتمام کارها است. در این الگوریتم از ترکیب الگوریتم ژنتیک و کلونی مورچگان برای حل مسئله استفاده شده است. شکل 2-21 مراحل الگوریتم ارائه شده را نشان می دهد.
در این الگوریتم از عملگر تبادل مبتنی بر کار و عملگر جهش شیفتی استفاده شده است. شکل 2-22 عملگرتبادل مبتنی بر کار و شکل 2-23 عملگر شیفتی استفاده شده در این الگوریتم را نشان می دهد. از مزایای این الگوریتم استفاده از ترکیب الگوریتم ژنتیک با الگوریتم کلونی مورچگان است و از معایب این الگوریتم در نظر نگرفتن مساله نگهداری، مساله توزیع شدگی و عدم توجه به هزینههای تولید است.
شکل ‏222: عملگر مبتنی بر کار
شکل ‏223: عملگر جهش شیفتی
الگوریتم GA-Fuzzy
Raja و همکارانش برای بهینه سازی چند هدفه زمانبندی ماشین های موازی98 (PMS) ترکیبی از الگوریتم ژنتیک و منطق فازی99 را ارائه دادند. در این روش از الگوریتم ژنتیک برای تولید زمانبندی بهینه تصادفی و از منطق فازی برای انتخاب بهترین زمانبندی از میان زمانبندی های تصادفی تولید شده با توجه به چندین هدف استفاده شده است. در این الگوریتم نیز از توالی انجام کارها برای نمایش کروموزوم استفاده شده است. شکل 2-24 یک کروموزوم نمونه را نشان می دهد. همچنین از عملگر تبادل تک نقطه ای برای تولید فرزند استفاده شده است. عملگر جهش نیز جای دو ژن تصادفی یک کروموزوم را با هم تعویض می نماید.
3
1
4
2
5
شکل ‏224: یک کروموزوم نمونه در الگوریتم GA-Fuzzy
در کروموزوم شکل 2-24 برای مثال کار 5 قبل از کار 2 انجام می شود. از مزایای این الگوریتم در نظر گرفتن چندین معیار برای سنجش شایستگی کروموزوم ها است و از معایب آن محدود کردن مساله و در نظر نگرفتن مساله نگهداری ماشینها است.
Sakawa نیز الگوریتم مشابهی برای حل مساله زمانبندی سیستم های تولید انعطاف پذیر ارائه داده است.
الگوریتم HGA100
Kamrul hasan و همکارانش برای حل مساله زمانبندی کار کارگاهی، یک الگوریتم ژنتیک ترکیبی پیشنهاد دادند که هدف آن کمینه کردن زمان اتمام کارها است. این الگوریتم برای نمایش کروموزوم از توالی انجام کارها استفاده می کند. شکل 2-25 یک کروموزوم نمونه را نشان می دهد برای مثال ژن 3 عدد 2 است چون دومین تکرار کار 2 در کروموزوم است پس نشان می دهد عملیات دوم از کار 2 باید انجام شود. فلوچارت زمانبندی با الگوریتم HGA در شکل 2-26 آمده است.
3
1
3
2
1
1
2
2
3
شکل ‏225: یک کروموزوم نمونه در الگوریتم HGA
شکل ‏226: فلوچارت الگوریتم HGA
الگوریتم GADG101
اخیرا Chan و همکارانش یک الگوریتم ژنتیک برای حل مساله زمانبندی سیستم های تولید انعطاف پذیر توزیع شده با در نظر گرفتن مساله نگهداری ارائه دادند که هدف از آن کمینه کردن زمان اتمام کارها است. ایده اصلی این مقاله، ارائه الگوریتم ژنتیک با ژن های برتر به نام GADG است. در این الگوریتم از ژن های برتر برای مشخص و ثبت نمودن برترین ژن ها و کروموزوم های متناظر استفاده شده است. ساختار هر ژن به صورت FMJOSD است که به ترتیب عبارتند از: شماره کارخانه (F)، شماره ماشین (M)، شماره کار (J)، شماره عملیات (O)، نگهداری (S)، و ژن برتر (D). شکل 2-27 یک کروموزوم نمونه را نشان می دهد.
112211
131200
132110
121101
شکل ‏227: : یک کروموزوم نمونه در الگوریتم GADG
برای مثال در کروموزوم شکل 2-27، ژن دوم 132110 نشان می دهد عملیات اول از کار دوم در ماشین سوم از کارخانه اول اجرا می شود، همچنین پارامتر S این ژن یک است که نشان می دهد این ماشین پس از اتمام اجرای عملیات، به حالت نگهداری می رود و پارامتر D آن صفر است که نشان می هد این ژن یک ژن برتر نیست.
در این الگوریتم از عملگر تبادل بر پایه ژن های برتر استفاده شده است. به عبارت دیگر فرزند، تمام ژن های برتر موجود در والدین خود را به ارث می برد و ژن های باقیمانده را از یک والد خود می گیرد. همچنین در این الگوریتم از دو نوع جهش استفاده شده است. در جهش نوع اول دو ژن به صورت تصادفی انتخاب شده، با هم جابجا می شوند و در جهش نوع دوم تعدادی ژن انتخاب شده پارامتر F یا M آنها تغییر می کند. نکته مهم اینجاست که جهش نوع اول در این الگوریتم می تواند به تولید کروموزوم های نامعتبر ختم شود که در این حالت باید کروموزوم مربوط اصلاح شود.
همانطور که گفته شد هدف از این الگوریتم کمینه کردن زمان تولید است. این الگوریتم هزینههای تولید، زمان تحویل کار و غیره را در نظر نمی گیرد که از معایب این الگوریتم محسوب میشود. همچنین به علت استفاده از الگوریتم ژنتیک سرعت همگرایی آن به سمت بهینه سراسری کند است. این الگوریتم در دفعات اجرا، جواب های متفاوتی را تولید می کند که نشان دهنده عدم پایداری الگوریتم است.
از مزایای این الگوریتم در نظر گرفتن مساله نگهداری در زمانبندی و ثابت نبودن مسیرهای تولید است.
الگوریتم های دیگر
Matta یک الگوریتم ژنتیک را برای مساله زمانبدی چند پردازنده کارگاه باز ارائه کرده است. وی با طراحی کروموزومی نوین، با جایگشتی در ژن ها به جوابهای شدنی قابل قبول دسترسی پیدا کرده است، و با جهش و تقاطع بر روی عملگرهای ژنتیکی که در هر تکرار جستجو انجام میگیرد به جواب بهتری دست پیدا کرده است. در نتیجه او توانست زمان تکمیل کارها در مساله زمانبندی چند پردازنده کارگاه باز را به کمترین مقدار مورد نطر برساند [8].
Cheung و همکارانش یک بررسی کامل روی مقالاتی که از الگوریتم ژنتیک برای حل مساله زمانبندی کار کارگاهی کلاسیک استفاده کردند، ارائه دادند.
اخیرا jia و همکارانش یک الگوریتم ژنتیک اصلاح شده برای حل مسائل توزیع شده پیشنهاد کردند. آن ها یک روش نمایش کروموزوم، عملگر تبادل و دو عملگر جهش اختصاصی ارائه دادند. از معایب این الگوریتم ثابت بودن مسیرهای تولید است.
فصل سوم روش تحقیق
در این فصل مراحل مختلف الگوریتم پیشنهادی به همراه کدهای مربوط به پیاده سازی آن شرح داده شده است که یک روش جدید با الگوریتم ژنتیک با ویژگی چند جمعیتی برای حل مساله سیستم باز ارائه شده است. این الگوریتم مساله نگهداری ماشین ها را نیز در نظر می‌گیرد و هدف آن ایجاد مصالحه بین زمان تولید و هزینه های تولید102 ناشی از نگهداری ماشین می باشد. این اولین بار میباشد که در این مساله، نگهداری ماشین در نظر گرفته می شود.
مراحل الگوریتم پیشنهادی:
مراحل کلی الگوریتم پیشنهادی عبارتند از:
مقدار دهی اولیه: تولد کروموزوم هایی برای جمعیت اولیه در چند جمعیت
انتخاب والدین به روش تصادفی
عملگر تبادل تک، دو و چند نقطه ای
عملگر جهش روی فرزندان
تعویض جمعیت: انتخاب فرزندان برای جمعیت نسل بعد
اتمام: اگر تعداد تولید نسل ها کامل شده است، پایان؛ واگرنه برو به 3
شکل 3-1 فلوچارت الگوریتم پیشنهادی را نشان می‌دهد.
شکل ‏31: فلوچارت الگوریتم پیشنهادی
نمایش کروموزوم
در الگوریتم پیشنهادی برای نمایش کروموزوم از یک آرایه یک بعدی استفاده شده که طول آرایه برابر تعداد کل عملیات کارها یعنی n*m است. هر ژن به صورت NMB بوده که N معرف شماره کار، M شماره ماشین و B فیلد نگهداری ماشین است. اگر B=1 باشد یعنی این ماشین پس از انجام عملیات فعلی به حالت نگهداری می رود و بر اساس مقدار سن103 ماشین، طبق یک قائده مشخص مانند شکل 3-3 ،مدت زمانی برای نگهداری آن ماشین تعیین می‌شود که در این زمان تعیین شده ماشین نمی‌تواند عملیات باقیمانده‌اش را اجرا کند.
نحوه نمایش جواب مسئله و ژن ها در موفقیت الگوریتم و نحوه پیاده سازی الگوریتم ژنتیک تاثیر بسیار مهمی دارد. در بیشتر مسائل نیز روش های مختلفی برای نشان دادن جواب مساله می توان طراحی کرد.
کروموزوم باید به گونه ای طراحی شود که تا حد ممکن از اطلاعات مسئله برای کاهش تعداد حالات فضای حالت استفاده کند. در یک کروموزوم باید بتوان براحتی محدودیت های مسئله را اعمال کرد و در اثر اعمال مراحل دیگر الگوریتم ژنتیک محدودیت های مسئله نقض نگردد تا حد امکان کروموزوم نباید در اثر اجرای مرحله ادغام ( تولید نسل جدید ) به حالت نامعتبر تبدیل گردد. در برخی مسائل گریز از حالت های نامعتبر در نحوه نمایش امکان پذیر نخواهد بود و باید در روش ادغام کروموزوم ها تغییر ایجاد کنیم. در این مساله با توجه به پیچیدگی مراحل بعد و امکان پذیری و با توجه به امکان در نظر گرفتن نگهداری به شکل ساده از آرایه یک بعدی برای نمایش کروموزوم استفاده کردیم.
شکل 3-2 یک کروموزوم نمونه را نشان می دهد که در آن n=3 و m=3 می باشد.
1،2،0
3،3،1
2،1،1
1،3،0
3،1،0
3،2،1
1،1،0
2،2،0
2،3،1
شکل ‏32: یک کروموزوم نمونه
برای مثال در کروموزوم شکل 3-2 ژن چهارم 3,2,1 است که نشان می دهد عملیات دوم از کار 3 در ماشین شماره 2 انجام شود و چون فیلد نگهداری این ماشین برابر 1 است این ماشین پس از پردازش این عمل برای مدت زمان تعیین شده به مرحله نگهداری می رود و نمی تواند عملیات جدیدش را پردازش نماید. از مزایای این نوع نمایش کروموزوم می توان به انجام پردازش به شکل سریع تر و بهینه تر اشاره کرد.
کد مربوط به نمایش کروموزوم:
public Chromosome(int n, int m, ArrayList time)
{
Random rnd = new Random(c++);
int count = 0;
ArrayList temp = new ArrayList(m * n);
for (int i = 1; i = n; i++)
{
for (int j = 1; j = m; j++)
{
gens = new Gene(i, j, rnd.Next(0, 2), (int)time[count]);
temp.Add(gens);
count++;
}
}
شرح پارامتر نگهداری ماشین
هر ماشین پس از انجام تعدادی عملیات، نیاز به زمانی برای نگهداری دارد. در هنگام نگهداری یک ماشین، آن ماشین از دسترس خارج می‌شود و پس از اتمام نگهداری دوباره در دسترس قرار می‌گیرد و توانایی انجام عملیات را پیدا می‌کند. شکل 3-3 زمان لازم برای نگهداری ماشین با توجه به سن ماشین را نشان می‌دهد. سن ماشین با مجموع زمان‌های پردازش عملیات توسط ماشین برابر است. حداکثر سن ماشین A است اگر سن ماشین A شود بعد از اتمام عملیات جاری ماشین به حالت نگهداری می‌رود و پس از هر نگهداری سن ماشین مجددا صفر می‌شود. البته این یک مدل از نگهداری می باشد و می توان با توجه به شرایط، قاعده متفاوتی را در نظر گرفت که لازم است در جایی دیگر به بحث در مورد آن پرداخت [14 و 15].
شکل ‏33: نگهداری ماشین وابسته به سن ماشین
شکل 3-4 یک کروموزوم نمونه را نشان می دهد که در آن n=3 و m=3 می باشد.
3،3،0
1،1،1
2،2،0
3،1،1
2،1،0
1،2،1
3،2،0
2،3،0
1،3،0
شکل ‏34: یک کروموزوم نمونه با در نظر گرفتن نگهداری

این مطلب رو هم توصیه می کنم بخونین:   منابع پایان نامه درموردبهبود عملکرد، اشتراک منابع، عدم تقارن
دسته‌ها: No category

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