شکل ‏۲‑۲۴: یک کروموزوم نمونه در الگوریتم GA-Fuzzy
در کروموزوم شکل ۲-۲۴ برای مثال کار ۵ قبل از کار ۲ انجام می شود. از مزایای این الگوریتم در نظر گرفتن چندین معیار برای سنجش شایستگی کروموزوم ها است و از معایب آن محدود کردن مساله و در نظر نگرفتن مساله نگهداری ماشین­ها است.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

Sakawa نیز الگوریتم مشابهی برای حل مساله زمانبندی سیستم های تولید انعطاف پذیر ارائه داده است.
الگوریتم HGA^[100]
Kamrul hasan و همکارانش برای حل مساله زمانبندی کار کارگاهی، یک الگوریتم ژنتیک ترکیبی پیشنهاد دادند که هدف آن کمینه کردن زمان اتمام کارها است. این الگوریتم برای نمایش کروموزوم از توالی انجام کارها استفاده می کند. شکل ۲-۲۵ یک کروموزوم نمونه را نشان می دهد برای مثال ژن ۳ عدد ۲ است چون دومین تکرار کار ۲ در کروموزوم است پس نشان می دهد عملیات دوم از کار ۲ باید انجام شود. فلوچارت زمانبندی با الگوریتم HGA در شکل ۲-۲۶ آمده است.

شکل ‑: یک کروموزوم نمونه در الگوریتم HGA

شکل ‏۲‑۲۶: فلوچارت الگوریتم HGA
الگوریتم GADG^[101]
اخیرا Chan و همکارانش یک الگوریتم ژنتیک برای حل مساله زمانبندی سیستم های تولید انعطاف پذیر توزیع شده با در نظر گرفتن مساله نگهداری ارائه دادند که هدف از آن کمینه کردن زمان اتمام کارها است. ایده اصلی این مقاله، ارائه الگوریتم ژنتیک با ژن های برتر به نام GADG است. در این الگوریتم از ژن های برتر برای مشخص و ثبت نمودن برترین ژن ها و کروموزوم های متناظر استفاده شده است. ساختار هر ژن به صورت FMJOSD است که به ترتیب عبارتند از: شماره کارخانه (F)، شماره ماشین (M)، شماره کار (J)، شماره عملیات (O)، نگهداری (S)، و ژن برتر (D). شکل ۲-۲۷ یک کروموزوم نمونه را نشان می دهد.

شکل ‏۲‑۲۷: : یک کروموزوم نمونه در الگوریتم GADG
برای مثال در کروموزوم شکل ۲-۲۷، ژن دوم ۱۳۲۱۱۰ نشان می دهد عملیات اول از کار دوم در ماشین سوم از کارخانه اول اجرا می شود، همچنین پارامتر S این ژن یک است که نشان می دهد این ماشین پس از اتمام اجرای عملیات، به حالت نگهداری می رود و پارامتر D آن صفر است که نشان می هد این ژن یک ژن برتر نیست.
در این الگوریتم از عملگر تبادل بر پایه ژن های برتر استفاده شده است. به عبارت دیگر فرزند، تمام ژن های برتر موجود در والدین خود را به ارث می برد و ژن های باقیمانده را از یک والد خود می گیرد. همچنین در این الگوریتم از دو نوع جهش استفاده شده است. در جهش نوع اول دو ژن به صورت تصادفی انتخاب شده، با هم جابجا می شوند و در جهش نوع دوم تعدادی ژن انتخاب شده پارامتر F یا M آنها تغییر می کند. نکته مهم اینجاست که جهش نوع اول در این الگوریتم می تواند به تولید کروموزوم های نامعتبر ختم شود که در این حالت باید کروموزوم مربوط اصلاح شود.
همانطور که گفته شد هدف از این الگوریتم کمینه کردن زمان تولید است. این الگوریتم هزینه­ های تولید، زمان تحویل کار و غیره را در نظر نمی گیرد که از معایب این الگوریتم محسوب می­ شود. همچنین به علت استفاده از الگوریتم ژنتیک سرعت همگرایی آن به سمت بهینه سراسری کند است. این الگوریتم در دفعات اجرا، جواب های متفاوتی را تولید می کند که نشان دهنده عدم پایداری الگوریتم است.
از مزایای این الگوریتم در نظر گرفتن مساله نگهداری در زمانبندی و ثابت نبودن مسیرهای تولید است.
الگوریتم های دیگر
Matta یک الگوریتم ژنتیک را برای مساله زمانبدی چند پردازنده کارگاه باز ارائه کرده است. وی با طراحی کروموزومی نوین، با جایگشتی در ژن ها به جواب­های شدنی قابل قبول دسترسی پیدا کرده است، و با جهش و تقاطع بر روی عملگرهای ژنتیکی که در هر تکرار جستجو انجام می­گیرد به جواب بهتری دست پیدا کرده است. در نتیجه او توانست زمان تکمیل کارها در مساله زمانبندی چند پردازنده کارگاه باز را به کمترین مقدار مورد نطر برساند [۸].
Cheung و همکارانش یک بررسی کامل روی مقالاتی که از الگوریتم ژنتیک برای حل مساله زمانبندی کار کارگاهی کلاسیک استفاده کردند، ارائه دادند.
اخیرا jia و همکارانش یک الگوریتم ژنتیک اصلاح شده برای حل مسائل توزیع شده پیشنهاد کردند. آن ها یک روش نمایش کروموزوم، عملگر تبادل و دو عملگر جهش اختصاصی ارائه دادند. از معایب این الگوریتم ثابت بودن مسیرهای تولید است.
فصل سوم روش تحقیق