بخشی از مقاله
چکیده:
در صنایع تولیدی و شرایط رقابتی امروزی زمان بندی فعالیت ها و برنامه ریزی کارها به منظور کاهش هزینه ها و عرضه سریع محصولات، کاملاً ضروری به نظر می رسد. از این رو تعیین بهینه زمان بندی و توالی تولید محصولات توسط ماشین های مختلف اهمیت ویژه ای پیدا میکند.
در این مقاله مدل مورد مطالعه در زمینه انتخاب و برنامه ریزی کارها بر روی ماشین های موازی به صورت همزمان می باشد که با هدف حداقل نمودن مجموع هزینه نگهداری و هزینه دیرکرد طراحی شده است و روش حل مدل با استفاده از الگوریتم فرا ابتکاری ژنتیک میباشد که به منظور بررسی کارایی الگوریتم نتایج آن با الگوریتم جستجوی ممنوعه مورد ارزیابی قرار می گیرد. حل مسائلی عددی توسط الگوریتم ارائه شده، موید کارایی و اثربخشی محاسباتی مطلوب الگوریتم ارایه شده است.
1 مقدمه
در بسیاری از سیستم های تولیدی، کارهای تولیدی باید از مراحل مختلف تولیدی عبور کنند، که در هر مرحله تعدادی ماشین موازی با ظرفیتهای متفاوت کارها را پردازش می کنند. از اینرو بررسی مسائل برنامهریزی ماشینهای موازی، جهت حداقل نمودن هزینه تولید مورد توجه محققین قرار گرفته است. در مسئله عمومی برنامهریزی ماشینهای موازی، مجموعهای از کارهای مستقل روی تعدادی ماشین موازی برای حداقل نمودن زمان تکمیل برنامهریزی میشوند. حداقل نمودن دیرکرد و زودکرد یکی از توابع هدفی است که اغلب برای برنامهریزی ماشینهای موازی به کار میرود.
در مسائل زمانبندی با ماشین های موازی، با دو مرحله تصمیم گیری تخصیص کارها به ماشین ها و تعیین توالی کارها بر هر ماشین رو به رو هستیم. مسائل ماشین های موازی می توانند به سه صورت یکسان1 ، یکنواخت2 و نامرتبط3 در نظر گرفته شوند. در ماشین های یکسان مدت زمان فرآیند کارها مستقل از ماشین است در حالی که در دو حالت دیگر زمان فرآیند کارها روی ماشین ها بر اساس نوع ماشین تغییر می کند.
روش های حل مختلفی برای مدل های فوق ارائه شده است که در ابعاد کوچک می توان از الگوریتم های دقیق مانند الگوریتم شاخه و کرانه برای حل مسئله استفاده نمود [4] و در ابعاد بزرگتر با با توجه به افزایش نمایی جواب های مسئله، از الگوریتم های فرا ابتکاری استفاده می شود.
یکی از الگوریتم های پرکاربرد در این زمینه الگوریتم ژنتیک می باشد که مطالعات زیادی در این زمینه انجام شده است که در این مقاله از نتاج آنها مورد استفاده قرار گرفته است. به عنوان مثال کمینه کردن کل دیرکرد و زودکرد در حل مسئله ماشینهای موازی که در سال 2014 برای حالتی که زمان فرآیند قابل کنترل باشد ارائه شده است
همچنین در سال 2012 در مقاله ای دیگر راهنمایی برای حل مسائل ماشینهای موازی و زمان بندی کارگاهی منعطف با استفاده از الگوریتم ژنتیک 4 ارائه شده است. [6] مطالعات جدیدتر نیز بر روی الگوریتم های ترکیبی یا همان هیبریدی می باشد که با ترکیب الگوریتمهای فرا ابتکاری با یکدیگر خیلی سریعتر به جواب می رسد که در این زمینه مسائل ماشین های موازی نیز مطالعاتی صورت گرفته است.
الگوریتم های فرا ابتکاری دیگر نیز در این زمینه ارائه شده است از جمله کمینه کردن دیرکرد در مسائل ماشین های موازی با استفاده از الگوریتم جستجوی ممنوع ، الگوریتم شبیه سازی تبرید برای کمینه کردن زمان تکمیل فرآیند در ماشین های موازی ، الگوریتم بهینه سازی ازدحام ذرات7 برای مسائل چند هدفه فازی در ماشین های موازی [11] و الگوریتم بهینه سازی کلونی مورچگان8 برای حل مسائل ماشینهای موازی در حالت تولید بچ با اندازه های متنوع [12] که نتایج بدست آمده از کاربرد این الگوریتمها نشانگر کارایی آنها در رسیدن به جوابهای بهینه یا نزدیک به بهینه برای مسائل برنامهریزی ماشینهای موازی با سایزهای واقعی است.
در اغلب مطالعات صورت گرفته در خصوص برنامه ریزی ماشین های موازی کمینه نمودن دیرکرد به عنوان تابع هدف قرار گرفته است این در حالی است که در این مقاله به مسئله برنامهریزی ماشینهای موازی و علاوه بر آن، به تصمیم گیری در رابطه با انتخاب تعدادی ماشین از بین مجموعه ماشینهای موجود میپردازیم، بعبارت دیگر انتخاب تعدادی ماشین و برنامهریزی کارهای مستقل روی ماشینهای موازی مسئله مورد بحث میباشد. که هدف از این انتخاب و برنامهریزی حداقل نمودن مجموع هزینه نگهداری ماشین و هزینه دیرکرد وزنی کل است. این مسئله اولین بار در سال 2005 مورد بحث قرار گرفت که با استفاده از الگوریتم جستجوی ممنوع مدل حداقل نمودن مجموع هزینه نگهداری ماشین و هزینه دیرکرد ارائه شد و جواب بهینه یا نزدیک به آن بدست آمده که از نتایج و مدل بدست آمده از این مطالعه در این مقاله مورد استفاده قرار گرفته است.
همچنین در سال 2014 در مقاله ای که توسط دکتر بهرام علی دایی و همکارش ارائه شد با استفاده از مدل مذکور یعنی مدل انتخاب و برنامهریزی ماشینهای موازی، مجموع هزینه های نگهداری و هزینه های مرتبط با زمان و دیرکرد کمینه شده اند که از نتایج و مدل ارائه شده در این مقاله استفاده شده است
در این مقاله به منظور حل مسئله انتخاب ماشین موازی و برنامهریزی کارها، الگوریتم ژنتیک توسعه مییابد و هدف از حل این مسئله حداقل نمودن هزینه ماشین و هزینه دیرکرد وزنی کل است که تاکنون مطالعه ای در این زمینه صورت نگرفته است . در نهایت نتایج بدست آمده از آنها با نتایج الگوریتم جستجوی ممنوعه که توسط کاو و همکارانش ارائه شده است،[13] مقایسه میگردد.
2 تعریف مسئله
مسئله ای را به صورت برنامهریزی n کار مستقل روی تعدادی ماشین موازی انتخاب شده از بین مجموعه mتایی ماشینهای موجود در نظر بگیرید. در صورتی هزینه یک ماشین به سیستم تحمیل میگردد که آن برای پردازش کارها انتخاب شود. هزینه ماشینی با ظرفیت پردازش بالاتر باید بیشتر از ماشینی با ظرفیت پایینتر باشد. تمامی ماشینها قادر به انجام کلیه کارها، هستند. زمان پردازش کار روی ماشینهای مختلف متفاوت است و این تفاوت به تفاوت در ظرفیت ماشینها باز میگردد. هنگامی که کاری برای پردازش روی ماشینی انتخاب میگردد، تا انتهای کار روی آن ماشین باقی میماند و انقطاع مجاز نیست. موعد تحویل کارها مشخص و جریمه دیرکرد هنگامی پرداخت می شود که زمان تکمیل کاری از موعد تحویل آن بیشتر شود. تابع هدف ترکیبی در این مسئله کمینه سازی مجموع هزینههای ماشین و جریمه دیرکرد کل میباشد.
قبل از معرفی مدل ریاضی بهینه یابی،تعاریف و علائم بکار رفته در مدل در زیر آورده میشود.
در مدل PMSSM، معادله - 1 - تابع هدف ترکیبی با دو جمله است. جمله اول هزینه نگهداری ماشین و جمله دوم هزینه دیرکرد وزنی کل است. این تابع هدف به تعادل بین هزینه سیستم و هزینه دیرکرد بازمیگردد. معادله - 2 - تضمین مینماید که هر کار فقط در یک موقعیت روی یک ماشین پردازش میشود. معادله - 3 - تضمین مینماید که کار بایستی بلافاصله بعد از کار دیگری که بر روی ماشین انجام می شود شروع شود به شرط آن که کار بر روی ماشین مذکور تخصیص یافته باشد. معادله - 4 - میگوید که اگر کار i ، L 0 ، روی ماشین حداکثر یک کاردیگر بعد از آن قرار میگیرد.معادله - 5 - تضمین مینماید که فقط یک کار بعد از کار فرضی روی ماشین انتخاب شده قرار میگیرد.در معادله - - 6، M1 ، عدد مثبت بزرگی است. این معادله تضمین مینماید که اگر کار بعد از کار روی ماشین پردازش شود، زمان تکمیل آن - - بیش از مجموع زمان تکمیل کار - - و مدت زمان پردازش کار - - میباشد. معادله - 7 - خصوصیات متغیرهای تصمیم را شرح میدهد.
3 الگوریتم حل مسئله
همانطور که توضیح داده شد، الگوریتم پیشنهادی برای حل مسئله در این مقاله، الگوریتم ژنتیک می باشد که نتایج آن با الگوریتم جستجوی ممنوع که در مقاله کاو و همکارانش ارائه شد[13] مقایسه می شود. بدین منظور ابتدا الگوریتم جستجوی ممنوع مقاله مذکور تشریح خواهد شد و سپس الگوریتم ژنتیک پیشنهادی برای حل مدل PMSSM ارائه خواهد شد.
1-3 الگوریتم جستجوی ممنوع - TS -
الگوریتم TS که توسط گلاور10 توسعه یافت، فرآیند جستجویی است که حل بهینه یا نزدیک به بهینه را در مسائلی که دارای بهینه محلی میباشند، مییابد. در روش کوتاه مدت11، سعی میشود در فرآیند جستجو از قرار گرفتن در جواب بهینه محلی با بکارگیری مکانیزمی در تولید همسایگی پرهیز گردد. با ثبت مشخصات فرایند، خصوصیات خاصی که به تازگی در محل جواب دیده شده است به صورت ممنوعه در نظر گرفته میشود و در لیست ممنوعه - TL - 12 قرار میگیرند.
حرکتهای بعدی که شامل این خصوصیات یا عناصر باشند، انجام نمیگیرند. مکانیزم جستجوی ممنوعه از حرکتهایی که منجر به بازگشت به این جوابها میشوند در تعدادی از تکرارهای بعدی که این تعداد با اندازه لیست ممنوعه تعیین میشود جلوگیری میکند. بعلاوه در صورتی که در یک حرکت تابو، تابع هدف بهبود یابد، در صورتیکه این حرکت معیار آرمانی یا رد ممنوعیت13 را ارضا نماید، این حرکت انجام می گیرد.
