بخشی از مقاله
چکیده
زمانبندی در تولید از اهمیت بالا و قابل توجهی برخوردار است. زمانبندی مناسب و با در نظر گرفتن معیارهای مختلف منجر به بهرهوری بیشتر و سودآوری خواهد شد. یکی از کاربردهای زمانبندی در تولید، مساله زمانبندی دستهای از کارها که هر یک شامل زیر مجموعهای از فعالیتهای کوچکتر هستند بین مجموعهای از ماشینهای ناهمگن است که به زمانبندی کار کارگاهی 1 - JSSP - معروف است. نوع خاصی از زمانبندی کار کارگاهی، زمانبندی انعطافپذیر است. در این تحقیق هدف ارائه رویکردی برای زمانبندی بهینه کارها با در نظر گرفتن معیارهایی از جمله زمان تکمیل کارها، مجموع بار کاری و ... میباشد. برای این منظور الگوریتم بهینه سازی رقابت استعماری که یک الگوریتم فرا ابتکاری است پیشنهاد شده است و ساختار مناسب برای حل مساله مذکور با این الگوریتم پیشنهاد گردیده است.
همچنین به منظور بهبود سرعت و همگرایی بهتر الگوریتم از اتوماتای سلولی استفاده شده است. برای ارزیابی روش پیشنهادی از مجموعه داده استاندارد2 و شناخته شده استفاده شده است و این الگوریتم از دیدگاههای مختلف از جمله رسیدن بهینه سراسری، کاهش متوسط زمان انتظار و متوسط زمان گردش کار و همچنین زمان اجرا با برخی از الگوریتمهای جدید و معتبر در این زمینه مورد مقایسه قرار گرفته است. نتایج ارزیابیها نشان میدهد که روش پیشنهادی به جز در چند مورد در اکثر مواقع پاسخهای بهینهتری به نسبت سایر روشها پیدا کرده است و مهمتر از آن اینکه سرعت اجرا الگوریتم به شکل چشمگیری بالاتر از سایر روشهای بهینهسازی در این مساله است.
واژگان کلیدی: زمانبندی کار کارگاهی انعطافپذیر، الگوریتم رقابت استعماری، اتوماتای سلولی
-1مقدمه
در دنیای صنعتی امروز یکی از مطرحترین مباحثی که توجه محققان و پژوهشگران صنعت را بخصوص در دهههای اخیر به خود اختصاص داده، مقوله زمانبندی است. یک سیستم تولیدی برای موفقیت به مؤثر بودن، مفید بودن و زمانبندی صحیح نیاز دارد. بنابراین زمانبندی، فعالیتی پیچیده در یک محیط تولیدی با قابلیتهای آسان است. در سالهای اخیر، مقالات متعددی درباره مسئله زمانبندی ارائه شد. از جمله روش پیشنهادی ژانگ و همکارانش - Zhang et al, 2009 - که نشان دادند در JSSP، مسیر کارها ثابت و مشخص بوده و نیازی به وجود مسیر یکسانی برای همه کارها نمیباشد. اما در این مساله فرض بر این است که تنها یک مسیر پردازش برای هر کار وجود دارد که این به عدم انعطاف-پذیری در سیستمهای تولیدی اشاره دارد.
همچنین Kacem و همکارانش در - Kacem et al, 2002 - ، نشان دادند که - ، انعطافپذیری در کار گارگاهی به انعطافپذیری ماشین اشاره دارد که ممکن است جزئی - مساله زمانبندی کار کارگاهی منعطف جزئی - - - TF-JSSP یا کلی - مساله زمانبندی کار کارگاهی منعطف کلی - - - PF-JSSP باشد. مساله PF-JSS یک حالت خاص از F-JSSP میباشد که در آن تعداد مشخصی از ماشینهای چند-منظوره در سراسر ایستگاهی توزیع شدهاند که تطبیقپذیری و انعطافپذیری یکسانی ندارند. در بحث اتوماتای سلولی نیز مقالات بسیاری به ثبت رسیده که مثلا در مقاله ای که بیگی و میبدی در سال 2007 ارائه داده اند - - beigy and Meybodi, 2007، دو نوع اتوماتای سلولی اتوماتای سلولی تصادفی و اتوماتای سلولی ناهمگام را ارائه دادند که این دو جزء استثنائاتی بودند که مشابهتی در قوانین به روز رسانی سلول ها در آنها وجود ندارد و ممکن است در طول زمان دچار تغییر شده و به کل شبکه به صورت همزمان اعمال نگردد.
به هر حال، در کلیه این مقالات تک کاربردی، همانطور که گفته شد قدرت زمان بندی و انعطاف پذیری مسئله، نمی تواند پاسخگوی مناسبی برای مسائلی باشد که در این زمینه کاربرد دارند. بنابراین در این تحقیق با استفاده توأمان از الگوریتم های رقابت استعماری و اتوماتای سلولی توانسته ایم عملکرد بهینه ای را از نظر سرعت با در نظر گرفتن معیارهایی از جمله زمان تکمیل کارها، مجموع بار کاری و ... ارائه دهیم. در ادامه، به مسئله زمان بندی در بخش 2، الگوریتم رقابت استعماری، نحوه شکل گیری و شرح الگوریتم در بخش 3، همچنین شرح اتوماتای سلولی و روش پیشنهادی به ترتیب در بخش های 4 و 5، آزمایشات در بخش 6 و در نهایت نتیجه گیری در بخش 7 پرداخته ایم.
روش تحقیق
-2 مساله زمانبندی
-1-2 مساله زمانبندی کار کارگاهی3
به منظور تعریف مساله در این پژوهش تعاریف خاصی مورد نیاز است. بنابراین، پیکربندی تولید اصلی-4کار گارگاهی- ابتدا نشان داده شده است و سپس چگونگی کلیت ایجاد و حل مساله روشن شده است. از اینرو این پژوهش با تعریفی از مساله کار گارگاهی - JSSP - و محیط عملیاتی آن شروع میشود. در JSSP، n کار - J1,. . . , Jn - بااندازههای متفاوت وجود دارد و هر کار نیاز به زمانبندی روی m ماشین - m1'….'Pm - دارد که به دنبال یافتن یک مسیر عملیاتی از پیش تعیین شده است تا زمانی که همه درخواستهای عملیاتی از همه کارها برآورده شود. در JSSP کلاسیک، برنامهریزی فرآیند5 - پردازش عملیات متوالی - یک قطعه شامل توالی از ماشینهایی است که باید ملاقات شوند. یک اولویت اختصاص یافته از عملیاتها به ماشینها وجود دارد. از اینرو، برنامهریزی فرآیند ثابت است و هیچ برنامهریزی فرآیند انعطافپذیری همراه نیست.
معمولا اهدافی که در مساله زمانبندی کار کارگاهی مورد نظر قرار میگیرند به تعداد زیاد، پیچیده و اغلب دارای اثرات متقابل میباشند. در ادامه به برخی از متداولترین معیارهای زمانبندی اشاره گردیده است: کاهش کل زمان تاخیر؛ کاهش تعداد کارهای تاخیردار؛ حداکثرکردن بهرهگیری از سیستم یا منابع؛ کاهش موجودی در جریان؛ بالانس مصرف منابع؛ و حداکثرکردن سرعت تولید. در JSSP، مسیر کارها ثابت و مشخص بوده و نیازی به وجود مسیر یکسانی برای همه کارها نمیباشد - . - Zhang et al, 2009 در این مساله فرض بر این است که تنها یک مسیر پردازش برای هر کار وجود دارد که این به عدم انعطافپذیری در سیستمهای تولیدی اشاره دارد.
-2-2 مساله زمانبندی انعطافپذیر کارگاهی6
بر طبق - Kacem et al, 2002 - ، انعطافپذیری در کار گارگاهی به انعطافپذیری ماشین اشاره دارد که ممکن است جزئی - مساله زمانبندی کار کارگاهی منعطف جزئی - - TF-JSSP - 7 یا کلی - مساله زمانبندی کار کارگاهی منعطف کلی - - PF-JSSP - 8 باشد. مساله PF-JSS یک حالت خاص از F-JSSP میباشد که در آن تعداد مشخصی از ماشینهای چند-منظوره در سراسر ایستگاهی توزیع شدهاند که تطبیقپذیری9 و انعطافپذیری یکسانی ندارند.
این ویژگی قادر میسازد یک قطعه خاص توسط حداقل یک ماشین از ماشینهای قابل دسترس پردازش شود. انعطافپذیری مسیریابی، به قطعهها اجازه میدهد تا در صورت مواجه شدن با هر رویداد در ایستگاه کارگاهی به صورت پویا به دیگر ماشینهای قابل دسترس دوباره تخصیص یابند مانند رویدادهای از کار افتادن ماشین - خرابیها - 10، قطع سفارش یا ورود درخواست. در PF-JSSP، m ماشین برای پردازش n کار وجود دارد که هر کار j نیازمند njعملیاتِ محدودیت-حق تقدم11، جهت انجام یافتن است. هر عملیات Oj,l میتواند روی تعدادی از ماشینهای یکسان - مشابه - 12 یا غیر یکسان پردازش شود و زمان پردازش میتواند بر اساس مشخصات ماشین متفاوت باشد. این نشان میدهد که برای برخی ازکارها چندین مسیر وجود دارد. اگر یک ماشین به طور موقت بیش از حد باری را تحمل13 کند، در حالی که ماشینهای دیگر قابل دسترس باشد، میتواند مسیریابی علیالبدل مورد استفاده قرار گیرد. از اینرو درF-JSSP دو تصمیم گیری متفاوت ارائه شده است:
