زمان بندی برای تولید کارگاهی (job shop) از دو زمینه مدیریت محصول و بهره وری گروهی خیلی مهم است.
هر چند که این امر کاملا متفاوت است با بدست آوردن یک جواب بهینه با متدهای بهینه یابی مرسوم، زیرا مسئله مورد نظر دارای محاسبات خیلی پیچیده می باشد.(مسئله فوق از نوع NP-Hardاست.)
اثبات شده است که الگوریتم ژنتیک (GA) برای تنوع وضعیت هایی که شامل زمان بندی و توالی می باشند(S.S) موثر می باشد.
در این مقاله یک نوع الگوریتم ژنتیکی ابتکاری هایبرید برای مسئله n/m/G/Cmax پیشنهاد شده است ، هایبرید به این خاطر که قوانین زمان بندی از قبیل SPT و MWKR با الگوریتم ژنتیک ادغام شده اند، همچنین از تکنیک جستجوی محلی (NST ) به عنوان رویه ای کمکی جهت بهبود حل عملکردی کمک گرفته ایم.
کارایی و اثر بخشی این الگوریتم جدید به وسیله مقایسه با برخی متدهای معروف دیگر از قبیل الگوریتم های NST (تکنیک جستجوی محلی)، SA (تبرید شبیه سازی شده) و ژنتیک ، به اثبات رسیده است.
1. مقدمه
زمان بندی برای تولید کارگاهی یک موضوع مهم در مدیریت تولید است، که توجه آن برروی معین کردن سفارش ترخیص و زمان های مجموعه پدیده ها بر روی ماشین های مربوطه،با در نظر گرفتن محدودیت های مربوطه معطوف شده است، که مجموعه n پدیده بایستی توسط m ماشین پروسه شوند، که عملیات iام بایستی برروی ماشین jام با زمان فرآیند معینی tij انجام شود. همچنین هر ماشین تنها یک پدیده را در یک زمان می تواند پروسه نماید و یک فعالیت نمی تواند مانع انجام کار شود.
هدف مسئله این است که Cmax (دوره ساخت) مینیمم شود.
این مسئله از نوع NP-Hard است(Garey.Johnson & Sethi 1976) که از متدهای موجود الگوریتم ژنتیک بالاترین کارایی را از خود نشان داده اند.
2.الگوریتم ژنتیک
1-2- مقدمه
در میان روش های بهینه سازی الهام گرفته از طبیعت جاندار، الگوریتم ژنتیک (GA) که بر اساس اصول تکامل طبیعی پایه ریزی شده،از تکامل یافته ترین ها به شمار می آید.
الگوریتم ژنتیک یک روش بهینه سازی غیر کلاسیک و جستجوی مستقیم است که فقط با خود تابع و نه مشتقات آن سرو کار داردو بر اساس مکانیزم بقای اصلح و علم ژنتیک طبیعی ،الهام گرفته از نظریه تکامل داروین بنا شده است. در این روش جستجو از چندین نقطه در فضای حل و بطور همزمان اغاز می شود و با جستجوی نقطه به نقطه فضای متغیرهای تابع هدف بررسی شده و نهایتا نقطه ای که بیشترین و یا کمترین مطلق است، به عنوان نقطه بهینه مطرح می شود.این الگوریتم ابتدا توسط جان هلند، همکاران و دانشجویانش در دانشگاه میشیگان ایالات متحده در سال 1962 بیان شد و بنام الگوریتم ژنتیک شهرت یافت.وی بیان کرد که الگوریتم ژنتیک در طول دورهای محاسباتی مختلف با شناسایی واحدهای ساختاری خوب و الحاق آنها به یکدیگر ، به نواحی با متوسط برازندگی بیشتر، همگرا می شود.
آنها از تحقیقاتشان دو هدف اصلی زیر را دنبال می کردند:
1- ارائه شرح دقیق و خلاصه ای از عملکرد قابل قبول از سیستم های طبیعی.
2- طراحی نرم افزارهای سیستم های ساختگی که ساز و کارهای اصلی سیستم را در بر داشته باشد.
مهمترین کاربرد الگوریتم های ژنتیک برای بهینه سازی می باشد. در روش های معمولی و متعارف بهینه سازی (برنامه ریزی خطی و غیر خطی،معادله لاگرانژ و...) توابع هدف باید حتما پیوسته و مشتق پذیر باشند،در حالی که در روش الگوریتم ژنتیک نیازی به تابع پیوسته و مشتق پذیرنیست.بر اساس روش کار الگوریتم ژنتیک یک نمونه از تمامی متغیرهای تصمیم گیری که موثر بر تابع عملکرد می باشند بعنوان یک عضو تلقی می گردند که تعدادی از این نمونه ها ، مجموعه ای از اعضا را تشکیل می دهند.در این روش مجموعه ای از جمعیت متغیرها در روند جستجو به کار می روند بدین ترتیب همزمان با ایجاد بیشتر برای متغیر های شایسته تر ، احتمال یافتن نقطه بهینه مطلق یا سراسری افزایش می یابد، این ویژگی بخصوص برای توابعی با تغییرات ناگهانی و دارای چندین نقطه بهینه موضعی ،مناسب می باشد.
2-2- مفاهیم اولیه در الگوریتم ژنتیک
قبل از ارائه الگوریتم لازم است مفاهیم اولیه این روش و اجزاء تشکیل دهنده آن بررسی شوند که بترتیب به شرح آنها پرداخته شده است:
- کد کردن : GA به جای اینکه برروی پارامترها یا متغیرهای مسئله کارکند، با شکل کد شده آنها به طور مناسب سروکار دارد. درGA جوابها در قالب رشته ای از ژنها که کروموزوم نامیده می شوند ،نمود پیدا می کند. به این دلیل انتخاب نوع کدگذاری و طول رشته کروموزوم اهمیت ویژه ای می یابد.ژنها می توانند به صورت اعداد در مبنای باینری (0, 1)، اعداد در مبنای دهدهی (9,...,2,1( ، حروف انگلیسی یا هر نماد دیگر بیان شوند.
- رشته : یک رشته دنباله ای از بیت ها ست که به عنوان شکل کد شده یک جواب ممکن (مناسب یا نامناسب) از مسئله مورد نظر می باشد.در حقیقت بیت های یک رشته نقش ژنها در طبیعت را بازی می کنند.هر بیت متغیر گسسته ای است که از یک مجموعه Q عضوی انتخاب می شود.چنانچه از کدگذاری باینری استفاده شود ، هر بیت یکی از دو مقدار 0و1 را می پذیرد بنابراین در این حالت Q=2 می باشد.
- جمعیت : مجموعه ای از رشته ها را جمعیت می گویند.یکی از ویژگی های جمعیت این است که به جای تمرکز روی یک نقطه از فضای جستجو یا یک رشته ،بر روی جمعیتی از رشته ها کار می کند.بنابراین در هر مرحله الگوریتم دارای جمعیتی از رشته ها بوده که خواص مورد نظر را از جمعیت مرحله قبل دارا می باشد.
به هنگام استفاده از GA به عنوان یک روش بهینه سازی، باید در خصوص تعیین اندازه جمعیت تصمیم گرفته شود.از جمله مهمترین عواملی که در این کار موثر هستند می توان به شیوه نمایش فضای جواب ، نوع مسئله ای که باید حل گردد و عملگرهای به کار رفته اشاره نمود.اما آنچه بهترین جواب را می دهد تجربه و آزمایش است.اندازه جمعیت تاثیر فراوانی در عملکرد و راندمان الگوریتم های ژنتیک دارد.اگر تعداد جمعیت خیلی کم باشد این الگوریتم ها با راندمان بسیار پائین عمل خواهند کرد ، زیرا نمونه های مورد نیاز به قدر کافی برای نمایش اکثریت فضاهای جستجو وجود ندارد.
کار کردن با جمعیت های زیاد اگرچه ارائه دهنده فضاهای جستجوی زیادتری می باشد و GA می تواند جستجوی آگاهانه تری را ارائه دهد ، ولی این تعداد زیاد جمعیت باعث می گردد که یک همگرایی زود هنگام به سمت نقاط بهینه محلی بدست می آید. بعلاوه تعداد زیاد جمعیت باعث می گردد که تعداد ارزیابی ها بالا باشد، لذا سرعت همگرایی کند و آهسته خواهد بود.
1-2-2- مقدار برازندگی
یکی از مراحل GA ارزیابی جوابهای بدست آمده در هر مرحله است. در واقع ارزش جوابهای بدست آمده در هر مرحله تعیین می شود.مناسب بودن یا نبودن جواب با معیاری که از تابع هدف بدست می آید ، سنجیده می شود.هر چه که یک جواب مناسب تر باشد ، مقدار برازندگی بیشتری دارد که با استفاده از محدوده دانش مسئله به کار برده شده محاسبه می شود.برای آنکه شانس بقای چنین جوابی بیشتر شود احتمال بقای آن متناسب با مقدار برازندگی آن در نظر گرفته می شود.بنابراین رشته ای که برازنده تر است با احتمال بیشتری در تولید فرزندان شرکت می کند و دنباله های بیشتری را بوجود می آورد. با ارزشترین جوابها درهرمرحله ، مانند قویترین موجودات در یک جمعیت می باشند.در تکثیر، رشته های با میزان تطبیق کم ، از جمعیت حذف می شوند و رشته های با میزان تطبیق زیاد، تاثیر بیشتری در تولید جمعیت بعدی خواهند داشت.