بخشی از مقاله
چکیده
پژوهش حاضر به بررسی مسئله زمان بندي دستهاي در محیط جریان کارگاهی با در نظر گرفتن اندازه کار و زمان آماده بودن، با هدف حداقل کردن زمان تکمیل آخرین کار میپردازد. ما در این مقاله براي نخستین بار زمان آماده بودن غیر صفر، براي کارها در نظر گرفته و مدل برنامهریزي عدد صحیح مختلط آن را ارائه مینماییم. سپس با توجه به اینکه مسئله داراي پیچیدگی محاسباتی سخت است، الگوریتم فراابتکاري جستجوي پراکنده - - SS را براي حل مدل توسعه خواهیم داد. در ادامه پس از تنظیم پارامترهاي مدل، مسائل نمونه استاندارد که در پژوهشهاي پیشین نیز از آنها استفاده شده است، با استفاده از نرم افزار و نیز با استفاده از الگوریتم فراابتکاري پیشنهادي به اجرا گذاشته میشوند. نتایج عددي نشان میدهند که الگوریتم فراابتکاري میتواند جوابهاي کارایی براي مسئله پیدا کند.
.1 مقدمه
در مسئله زمانبندي دستهاي، کارها به جاي پردازش تکی بطور دستهاي پردازش میشوند . همچنان که پیندو[1] در کتاب خویش ذکر نموده است پرداختن به کارها به صورت دستهاي ارزانتر و آسانتر از پرداخت تکی کارها است. در تولید دستهاي با ماشینهاي پردازشگر دستهاي - BPM - سر و کار داریم. این ماشینها قابلیت پردازش چند کار را به طور همزمان دارا هستند. از ماشینهاي پردازشگر دستهاي در صنایعی از قبیل صنایع دارویی، ساخت فولاد، عملیات مربوط به تولید نیمههاديها و.... استفاده میشود. مسئله زمانبندي ماشینهاي پردازشگر دستهاي از جمله مسائل داراي پیچیدگی محاسباتی زیاد هستند و روشی قطعی براي حل آنها وجود ندارد.
در این مقاله به زمانبندي دستهاي در محیط جریان کارگاهی پرداخته میشود. n کار متفاوت که هر یک داراي زمان پردازش مشخص روي هر ماشین، زمان آماده بودن و اندازه کار میباشند، میبایست روي m ماشین متفاوت در قالب دستهها پردازش شوند. وقتی دستهاي شروع به پردازش میکند اضافه کردن یا کم کردن کار از دسته ممکن نیست. زمان پردازش هر دسته مساوي با طولانیترین زمان پردازش کارهاي موجود در دسته است . کارها ابتدا به دستهها تخصیص مییابند و سپس توالی دستهها روي ماشینها مشخص میشود و این فرآیند باید به گونه اي انجام گیرد که تابع هدف زمان تکمیل آخرین کار یا Cmax، حداقل گردد.
همه ماشینها داراي ظرفیت مشخص و یکسان بوده و کارها را بطور دستهاي تا جایی که اندازه آنها از ظرفیت ماشین تجاوز نکند پردازش میکنند. فرض میکنیم که اندازه همه کارها از ظرفیت ماشینها کوچکتر است و کارها قابل شکافتن نمیباشند. به این معنی که اگر ظرفیت باقیمانده دسته از اندازه کار کوچکتر بود آن کار تماما به دسته بعدي تخصیص مییابد و تخصیص بخشی از آن به یک دسته مجاز نیست.کارها با ترتیب یکسان روي همه ماشینها پردازش میشوند و در واقع مسئله، از نوع جریان کارگاهی جایگشتی میباشد.
.2 مرور ادبیات
در این قسمت به برخی از تحقیقات انجام شده که در زمینه تولید دستهاي و در محیط جریان کارگاهی میباشند اشاره خواهیم کرد. وانگ و چرن[2]، مسئله جریان کارگاهی دستهاي را با دو ماشین و کارهاي مربوط به چند خانواده بررسی کردند و کوشیدند توالی خانوادهها و توالی کارها در هر خانواده را به گونهاي بیابند که زمان تکمیل آخرین کار، کمینه شود. آنها الگوریتمی چند جملهاي براي حل ارائه نمودند. داموداران و سریهاري[3]، مسئله جریان کارگاهی دو ماشینه با ماشینهاي دستهاي را با هدف کمینه کردن زمان تکمیل کارها در دو حالت ذخیره میانی صفر و ذخیره میانی نامحدود بررسی نموده و براي هر یک مدل ریاضی ارائه کردند. لیائو و لیائو [4]، مسئله زمانبندي دستهاي را در محیط جریان کارگاهی با هدف کمینه کردن زمان تکمیل کارها و داشتن دو ماشین بررسی نمودند.
آنها نیز براي دو حالت ذخیره میانی صفر و ذخیره میانی نامحدود، مدل ریاضی ارائه نموده و نشان دادند که مدل آنها حالت بهبود یافته مدل ارائه شده توسط داموداران و سریهاري[3] است که با کمتر کردن حجم زیادي از محدودیتها، مسئله را به خوبی توصیف میکند. آنها همچنین براي حالت ذخیره میانی نامحدود روش ابتکاري کارایی ارائه نمودند. منجشوار و همکاران[5]، دو ماشین تولید دستهاي را در حالت جریان کارگاهی با هدف کمینه کردن Cmax بررسی کردند. آنها یک روش ابتکاري و یک رویکرد تبرید شبیه سازي شده گسترش داده و نشان دادند که دسته بندي کارها بر اساس الگوریتم جانسون جواب بهینه را براي مسئله تحت بررسی تضمین نمیکند.
لیائو و هوانگ[6]، به زمانبندي کارهاي یک دسته به حالت جریان کارگاهی با دو ماشین با داشتن اندازه کار و با هدف کمینه کردن زمان Cmax پرداختند. یک جواب اولیه با استفاده از الگوریتم جانسون یافته و سپس براي بهینه شدن زمان تکمیل از تکنیک تعویض همسایه استفاده نمودند و عملکرد روش پیشنهادي را با حد پایین گرفته شده از پژوهش مربوط به لیائو و لیائو[4]، مقایسه کردند. لی و وانگ [7]، به مسئله زمانبندي جریان کارگاهی با تعداد زیادي ماشینهاي تولید دستهاي و در نظر گرفتن اندازه کار با هدف کمینه کردن حداکثر دیر کرد پرداختند . آنها یک الگوریتم جستجوي همسایگی موثر، پیشنهاد نموده و جایگشت کار و جایگشت دسته را براي حل مسئله نشان دادند.
ابتدا حل اولیه بدست آمد و سپس دو مبادله براي بهبود جواب صورت گرفت. نتایج محاسباتی نشان داد که روش پیشنهادي عملکرد بهتري نسبت به الگوریتم تبرید شبیه سازي شده دارد. بهنامیان و همکاران[8]، یک مسئله زمان بندي دستهاي را در محیط جریان کارگاهی که یک ماشین دستهاي میان دو ماشین پردازشگر غیر دستهاي در مراحل اول و سوم قرار دارند با در نظر گرفتن ظرفیت و دفعات حمل و نقل مابین ماشینها و هدف کمینه کردن زمان Cmax مطالعه نمودند. آنها ابتدا برنامه ریزي عدد صحیح مختلط و سپس الگوریتم ابتکاري براي یافتن جواب نزدیک بهینه را پیشنهاد نموده و در پایان الگوریتم ژنتیک را با معرفی عملگرها و درجهبندي پارامترها ارائه کردند.
نوروزي و همکاران[9]، مسئله زمان بندي دسته اي را در محیط جریان کارگاهی با m ماشین و با در نظر گرفتن اندازه کار با هدف کمینه کردن همزمان دیرکرد کل، زودکرد کل و زمان تکمیل آخرین کار بررسی نمودند. در این مقاله یک رویکرد یادگیري تطابقی الهام گرفته از شبکههاي عصبی براي بهینه شدن عملکرد سه نوع مختلف از الگوریتمهاي هوشمند به نامهاي الگوریتم ژنتیک ترکیبی، تبرید شبیه سازي شده ترکیبی و بهینه سازي تجمع ذرات بهبود یافته، براي حل مسئله زمان بندي ماشینهاي دستهاي بکار گرفته شد. ملاحظه میشود که از میان پژوهشهاي مربوط به تولید دستهاي، بیشتر به حالت دو ماشینه پرداخته شدهاست.
پژوهش حاضر در ادامه کار محققین ذکر شده، مسئله زمانبندي را براي حالت بیش از دو ماشین و با در نظر گرفتن محدودیت زمانهاي آماده بودن متفاوت و غیرصفر که پیش از این به آن پرداخته نشده است و با در نظر گرفتن داشتن بیش از یک کار براي هر نوع کار و تابع هدف حداقل کردن Cmax، بررسی نموده و مدل ریاضی مربوط به آن را ارائه میکند. در نهایت براي حل مدل ارائه شده، الگوریتم فراابتکاري جستجوي پراکنده ارائه میشود.
.3 مدل ریاضی
در مسئله جریان کارگاهی جایگشتی، به دنبال یافتن توالی جایگشت بهینه n کار متفاوت که همگی داراي توالی عملیات یکسان روي m ماشین متفاوت هستند، میباشیم و این جایگشت روي همه ماشینها یکسان است. فرضهاي مسئله عبارتند از:
- هر کار داراي اندازه - v - ، زمان پردازش - p - و زمان دردسترس بودن - r - است و همه مقادیر قطعی هستند.
- ذخیره میانی بین ماشین ها نا محدود است.
- فرض میشود هیچ کاري وجود ندارد که اندازه آن به تنهایی از ظرفیت دسته بزرگتر باشد.
- زمانی که پردازش دسته شروع شود کارها نمیتوانند از دسته حذف یا به آن اضافه شوند.
- وقتی فرآیند آغاز می شود نمی توان در آن وقفه بوجود آورد.
- خرابی ماشین مجاز نیست.
- شکاف کارها مجاز نیست.
همانگونه که در قسمت مرور ادبیات نیز ذکر شد در سال 2004 داموداران و سیري هاري، یک مدل ریاضی براي مسئله n کار و دو ماشین در دو حالت محدود بودن ذخیره میانی ماشینها و نامحدود بودن آن ارائه کردند. مسئله آنها نیز همچون مسئله ما مربوط به محیط جریان کارگاهی جایگشتی بود. آنها در مدل خود از دو متغیر تصمیم و استفاده نمودند که اولی مربوط به تخصیص کار j به دسته b و دیگري مربوط به تخصیص دسته b به موقعیت k میشد. در سال 2008 لیائو و لیائو، مدل ارائه شده توسط داموداران و سریهاري را بهبود داده و نشان دادند که مدل بدون متغیر تصمیم نیز به خوبی عمل خواهد کرد. در این قسمت سعی بر آن است که یک مدل برنامه ریزي عدد صحیح مختلط براي مسئله مورد بررسی، بر اساس مدل بهبود یافته ارائه شده توسط لیائو و لیائو ارائه شود.
تابع هدف مسئله، یعنی کمینه کردن زمان تکمیل آخرین کار، در - - 1 بیان شده که برابر خواهد بود با کمینه کردن زمان تکمیل آخرین دسته B، روي آخرین ماشین .M محدودیت - 2 - تضمین میکند که هر کار تنها به یک دسته اختصاص مییابد. محدودیت - 3 - تضمین میکند که کارهاي تخصیص یافته به یک دسته، از ظرفیت دسته تجاوز نخواهند کرد. محدودیت - 4 - زمان پردازش دسته b را روي ماشین m محاسبه میکند که بزرگتر یا مساوي زمان پردازش همه کارهاي موجود در دسته b روي ماشین m است.
محدودیت - 5 - زمان آماده بودن هر دسته را محاسبه میکند. محدودیت - 6 - زمان تکمیل اولین دسته را روي اولین ماشین نشان میدهد و برابر با زمان پردازش دسته روي ماشین اول به اضافه زمان آماده بودن دسته است. محدودیتهاي - 7 - و - 8 - زمان تکمیل دستههاي دیگر را روي ماشین اول محاسبه میکنند. محدودیت - 9 - زمان تکمیل دسته اول را روي سایر ماشینها نشان میدهد . محدودیت - 10 - و - 11 - زمانهاي تکمیل سایر دستهها را روي سایر ماشینها محاسبه میکنند. محدودیت - 12 - تابع هدف مسئله را محاسبه میکند که برابر است با زمان تکمیل آخرین دسته روي آخرین ماشین. محدودیت - 13 - محدودیت صفر و یک بودن متغیر تصمیم مسئله است و محدودیت - 14 - مثبت بودن متغیرهاي وابسته مسئله را نشان میدهد.
.4 الگوریتم حل
داموداران و سیري هاري [3]،که مسئلهاي مشابه مسئله حاضر را در حالت دو ماشینه بررسی کردند در مقاله خود نشان دادند که مسئله آنها داراي پیچیدگی محاسباتی سخت است و از آنجا که مدل مسئله حاضر نیز تعمیم یافته مسئله آنها و در ابعاد بزرگتر میباشد، لذا مسئله تحت بررسی در این پژوهش نیز داراي پیچیدگی سخت است. بنابراین باید به توسعه روشهاي فراابتکاري جهت حل آن بپردازیم. در همین راستا با استفاده از الگوریتم فراابتکاري جستجوي پراکنده به حل مسئله تحت بررسی خواهیم پرداخت.
.1,4 نحوه نمایش جواب
هر حل به صورت یک بردار که از n مولفه تشکیل شده است نشان داده میشود. شیوه نمایش جواب در الگوریتم جستجوي پراکنده با استفاده از روش کلیدهاي تصادفی بوده و بدین صورت است که هر مولفه بر اساس مقادیر تصادفی در بازه 1]،[0 بدست میآید.
