پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شماره‌ها | 1,710 |
| تعداد مقالات | 14,017 |
| تعداد مشاهده مقاله | 33,925,872 |
| تعداد دریافت فایل اصل مقاله | 13,572,186 |
ارائة الگوریتم های کارآمد برای حل مسأله زمانبندی جریان کارگاهی انعطاف پذیر با ماشینهای موازی غیرمرتبط و زمان های راه اندازی وابسته به توالی با هدف کمینه سازی مجموع زودکرد و دیرکرد | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| پژوهش در مدیریت تولید و عملیات | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مقاله 5، دوره 7، شماره 1 - شماره پیاپی 12، فروردین 1395، صفحه 65-82 اصل مقاله (671.48 K) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| نوع مقاله: مقاله پژوهشی- فارسی | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| شناسه دیجیتال (DOI): 10.22108/jpom.2016.20912 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| نویسندگان | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| سعیده غلامی* 1؛ فرزانه رجایی ابیانه2 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 1استادیار دانشکده مهندسی صنایع، دانشگاه صنعتی خواجه نصیر الدین طوسی، تهران ،ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 2کارشناسی ارشد دانشکده مهندسی صنایع، دانشگاه صنعتی خواجه نصیر الدین طوسی ،تهران، ایران | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| چکیده | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| در این مقاله، یک مدل ریاضی مبتنی بر برنامهریزی عدد صحیح آمیخته برای مسأله زمانبندی جریان کارگاهی انعطافپذیر با ماشین های موازی نا‍مرتبط و زمانهای راه‍اندازی وابسته به توالی با هدف کمینهسازی مجموع زودکرد و دیرکرد، ارائه شده است. به علت پیچیدگی این مسأله، برای حل مسائل با ابعاد بزرگ، از الگوریتمهای فراابتکاری استفاده شده است؛ در این پژوهش یک الگوریتم مبتنی بر شبیهسازی تبرید و الگوریتم دیگری مبتنی بر بهینهسازی ذرات ارائه شده است، و برای تنظیم پارامترهای الگوریتمهای پیشنهادی از روش طراحی آزمایشهای تاگوچی استفاده شده است. برای تحلیل عملکرد الگوریتمهای حل، چهلویک مسألة نمونه با ابعاد مختلف طراحی، و هرکدام ده مرتبه اجرا شده است. با توجه به تحلیل نتایج آزمایشهای محاسباتی زمان حل الگوریتم مبتنی بر بهینهسازی ذرات کمتر بوده است، ولی کیفیت جواب حاصل از الگوریتم مبتنی بر شبیهسازی تبرید بهتر از الگوریتم مبتنی بر بهینهسازی ذرات بوده است؛ به طور متوسط میزان درصد انحراف نسبی، نتایج آزمایشهای محاسباتی الگوریتم مبتنی بر بهینهسازی ذرات 4.4 درصد، و الگوریتم مبتنی بر شبیهسازی 2.3 درصد بوده است. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| کلیدواژه‌ها | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| الگوریتم بهینه سازی انبوه ذرات؛ الگوریتم شبیه سازی تبرید؛ دیرکرد؛ زمان بندی جریان کارگاهی انعطاف پذیر؛ زمانهای راه اندازی وابسته به توالی؛ زودکرد | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| اصل مقاله | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
مقدمه در مسأله جریان کارگاهی انعطافپذیر کارها باید در چند مرحله پردازش شود و حداقل یکی از مراحل بیش از دو ماشین موازی دارد. ماشینهای موازی می‍توانند یکسان[1]، یکنواخت[2] و یا غیرمرتبط[3] باشند. در ماشینهای موازی یکسان سرعت پردازش کارها روی همة ماشینهای یکسان است؛ اگر کار jام، روی هر یک از ماشین ها انجام شود، زمان پردازش آن برابر است با Pj. در ماشینهای موازی یکنواخت، ماشینهایی مشابه با سرعت پردازش متفاوت، به کار گرفته می شود؛ سرعت پردازش ماشین iام برابر vi است، اگر کار jام، به طور کامل روی ماشین iام انجا م شود، زمان پردازش آن برابر است با Pij = Pj /vi ، در ماشینهای موازی غیر مرتبط ماشینهایی متفاوت به کار گرفته میشود و ماشین i کار j را با سرعت vij پردازش میکند؛ اگر کار jام، به طور کامل روی ماشین iام انجا م شود، زمان پردازش آن برابر است با Pij = Pj /vij. در بیشتر پژوهشهای پیشین ماشینها به صورت یکسان در نظر گرفته شدهاند. در مسائل دنیای واقعی، معمولاً ماشینهای جدید را به صورت موازی با ماشینهای قدیمی قرار می‍دهند تا ظرفیت تولید افزایش یابد. در این نوشتار زمانهای آمادهسازی وابسته به توالی عملیات است، که در بسیاری از مسائل توالی عملیات در صنایع نساجی ، تولید نیمه‍رساناها، تولید کاشی و سرامیک و صنایع رنگ کاربرد دارد. تابع هدف مجموع زودکرد و دیرکرد که هزینه‍های نگهداری و هزینه‍های عدم تحویل به موقع محصول به مشتری را کاهش می‍دهد. مسأله جریان کارگاهی انعطافپذیر با دو مرحله با تعدادی ماشین موازی یکسان در مرحله اول و یک ماشین در مرحله دوم و با تابع هدف کمینهسازی بیشترین زمان تکمیل را گاپتا و همکاران(1997) بررسی کردند. بوتاگنولاز(2000) مسأله جریان کارگاهی انعطافپذیر با محدودیت پیشنیازی بین کارها و محدودیت زمانهای اتلاف بین مراحل و با تابع هدف کمینهسازی بیشترین زمان تاخیر بررسی و شش روش ابتکاری جدید ارائه کردند. تران و مینگ ننگ (2011) مسأله جریان کارگاهی انعطاف پذیر را با محدودیت ظرفیت انبارهای میانی و بدون در نظر گرفتن آن با هدفهای کمینهسازی بیشترین زمان تکمیل، مجموع موزون زمان در جریان ساخت و مجموع موزون زمانهای تاخیر بررسی و الگوریتم جریان آب [4] را ارائه کردند. لیو و چانگ (2000) یک روش دقیق ویک روش ابتکاری برای حل مسأله جریان کارگاهی انعطافپذیر با زمانهای آمادهسازی وابسته به توالی ارائه کردند و اسکین (2003) این مسأله را با هدف کمینهسازی بیشترین زمان تکمیل بررسی کرد، ویک مدل عدد صحیح، چند روش ابتکاری و یک روش الگوریتم ژنتیک با کلیدهای تصادفی ارائه کرد. نادری و همکاران (2009) برای مسأله جریان کارگاهی انعطافپذیر چند هدفه با زمانهای آمادهسازی وابسته به توالی و زمان حمل و نقل، الگوریتمی ترکیبی مبتنی بر شبیهسازی تبرید و یک روش جستجوی ساده ارائه کردند. مسأله با فرض ماشینهای موازی غیرمرتبط[5]، در مسألة جریان کارگاهی انعطافپذیر، از مسائلی است که کمتر مطالعه شده است؛ البته میتوان به تحقیقات جانگواتانیک و همکاران (2005، 2008، 2009) اشاره کرد. همچنین، یواریما و همکاران (2009) مسأله جریان کارگاهی انعطافپذیر با ماشینهای موازی غیرمرتبط، زمانهای راه‍اندازی وابسته به توالی، محدودیت زمانهای در دسترس بودن ماشینها و محدودیت انبارهای میانی را با تابع هدف کمینهسازی مجموع زمانهای تکمیل بررسی و برای حل از الگوریتم ژنتیک استفاده کردند. جانیاک و همکاران (2007) مسألة جریان کارگاهی انعطافپذیر با تابع هدف مجموع زودکرد و دیرکرد با و زمان انتظار را در نظر گرفتند و سه الگوریتم فراابتکاری و سه الگوریتم سازنده را برای آن ارائه کردند. بهنامیان و زندیه (2011) مسأله جریان کارگاهی انعطافپذیر با محدودیت زمان انتظار و تابع هدف مجموع زودکرد و مربع دیرکرد را بررسی و الگوریتم رقابت استعماری گسسته را برای حل ارائه کردند. تابع هدف مجموع زودکرد و دیرکرد تنها در مسائل جریان کارگاهی انعطافپذیر با ماشینهای یکسان درنظر گرفته شده است. در این پژوهش این تایع هدف در مسأله جریان کارگاهی با ماشینهای موازی غیرمرتبط بررسی میشود. در این نوشتار یک مسأله خاص از مسائل جریان کارگاهی انعطافپذیر با زمانهای راه‍اندازی وابسته به توالی، ماشینهای غیرمرتبط و تابع هدف مجموع زودکرد و دیرکرد بررسی میشود، و ساختار آن به شرح ذیل است: در بخش دوم مسأله زمانبندی جریان کارگاهی انعطافپذیر با زمانهای آمادهسازی وابسته به توالی تشریح میشود سپس در بخش سوم روش تحقیق و مدلسازی مسأله ارائه شده است که برای حل مسألة مورد نظر الگوریتمهای مبتنی بر شبیهسازی تبرید و بهینهسازی انبوه ذرات ارئه میشود و در بخش چهارم نتایج محاسباتی الگوریتمهای ارئه شده، گزارش میشود. در نهایت نتایج این پژوهش در بخش پنج جمعبندی میشود.
1- تشریح مسأله زمانبندی جریان کارگاهی انعطافپذیر با زمانهای آمادهسازی وابسته به توالی 2- در این پژوهش مسألة زمانبندی در یک سیستم جریان تولید کارگاهی انعطافپذیر بررسی میشود که در آن هر مرحله حداقل یک ماشین قرار دارد و به صورت موازی هستند و کارها در دو مرحله پردازش میشوند؛ زمانهای آمادهسازی، وابسته به توالی است، و بعد از اتمام پردازش هر کار در هرمرحله و شروع کار بعدی در نظر گرفته میشود که وابسته است به ترتیب این دو کار و ماشینی که پردازش روی آن انجام میشود. ماشینهای هر مرحله، غیرمرتبط هستند. پارامترها و متغیرهای مسأله قطعی است و تمام دادهها از پیش تعیین شده و ثابت هستند. تابع هدف کمینهسازی مجموع زودکرد و دیرکرد است که باعث میشود هزینه‍های نگهداری و هزینه‍های عدم تحویل به موقع محصول به مشتری، کاهش یابد. مفروضات مسأله به شرح ذیل است:
روش تحقیق و مدلسازی مسأله. در این پژوهش برای تحلیل مناسب مسأله یک مدل برنامهریزی عدد صحیح آمیخته ارائه میشود که با توجه به پیچیدگی محاسباتی آن، برای حل مسائل نمونه با ابعاد بزرگ، باید از روشهای ابتکاری/ فراابتکاری استفاده کرد؛ به همین علت در این پژوهش برای حل مسألة زمانبندی از الگوریتمهای فراابتکاری مبتنی بر بهینهسازی انبوه ذرات و شبیهسازی تبرید استفاده شده است. الگوریتمهای پیشنهادی از دو بخش تشکیل شده است، در بخش اول هدف کمینهسازی بیشترین زمان تکمیل و دیرکرد است و در بخش دوم، هدف کمینهسازی مجموع زودکرد و دیرکرد، با تغییر زمان شروع و خاتمه کارها در مرحله آخر، است. برای تعیین هزینه و زمانبندی کامل از الگوریتم پیشنهادی جانیاک (2007) استفاده میشود.
2- 1 پارامترها و متغیرهای مدل برای بیان مسأله و مدلسازی آن از پارامترها و متغیرهای زیر استفاده میشود: J: مجموعه کارها S: مجموعة مراحل Ms: تعداد ماشین در مرحله s dj: موعد تحویل Psjm: زمان پردازش کار j روی ماشینm در مرحلهs SUPskjm: زمان آمادهسازی کار k بعد از کار j روی ماشین m در مرحلهs M: یک عدد بزرگ Csjm: زمان تکمیل کار j روی ماشین m در مرحلهs Ksj: زمان ترک کار j از مرحلهs Ej: زودکرد کار j Tj: دیرکرد کار j
2-1-1 مدل ریاضی تابع هدف در این مسأله کمینهسازی مجموع دیرکرد و زودکرد است که در عبارت (1) بیان میشود، و برای تعیین مقدارهای زودکرد و دیرکرد به صورت عدد صحیح در مدل ریاضی، عبارتهای (3)، (4)، (15) و (16) در نظر گرفته میشود. عبارت (2) رابطه دیرکرد و زودکرد را با موعد تحویل مشخص میکند. عبارت (5) تضمین میکند که زمان پردازش هر کار بزرگتر یا مساوی زمان پردازش و زمان آمادهسازی کار j در مرحله اول است. با در نظر گرفتن عبارت (6) به دنبال آن هستیم که پردازش هیچ کدام از کارها روی یک ماشین همزمان نشود. عبارت (7) تضمین میکند که زمان تکمیل هر کار بزرگتر یا مساوی زمان تکمیل آن کار در مرحله قبل به علاوه زمان پردازش و زمان آمادهسازی آن کار باشد.. عبارتهای (8) و (9) مقدار ksj را برابر زمانی قرار می‍دهد که کار j مرحله را ترک میکند. عبارت (10) نشان می‍دهد که در هر مرحله هر کار فقط روی یک ماشین پردازش میشود. عبارت (11) نشان‍دهنده این است که هر کار باید به دنبال کار دیگری مثل کار i فقط روی یک ماشین پردازش شود. عبارت (12) نشان‍دهنده این است که ممکن است کاری قبل از کار دیگر روی یک ماشین برنامهریزی شده یا نشده باشد ولی آن کار حداکثر با یک کار دیگر باید دنبال شود. در عبارتهای (13) و (14) برای محاسبه زمان آمادهسازی، کار صفر به عنوان اولین کاری است که روی تمام ماشینها پردازش میشود
2- 2 الگوریتمهای پیشنهادی برای حل مسأله در اینجا با توجه به پیچدگی الگوریتم حل، دستیابی به جواب بهینه، حتی برای مسائل با ابعاد کوچک، مستلزم صرف وقت زیادی خواهد بود؛ بنابراین در این شرایط بهتر است که از روشهای ابتکاری/فراابتکاری برای حل مسأله استفاده شود. در این نوشتار از دو الگوریتم مبتنی بر شبیه سازی تبرید و الگوریتم مبتنی بر بهینهسازی انبوه ذرات استفاده میشود، و برای تعیین مقدار تابع هدف از الگوریتم ایجاد زمانبندی کامل استفاده میشود.
2 - 2 - 1 الگوریتم پیشنهادی ایجاد زمانبندی کامل ابتدا زمان در دسترسی کارها در مرحله اول را برابر صفر است.
با فرض مشخص بودن توالی مرحله اول، در مرحلة دوم با استفاده از قاعده FIFO توالی کارها تعیین میشود.
، زمان تکمیل کار j روی ماشین m در مرحله s و زمان آمادهسازی کار j روی ماشین m در مرحله s است. در صورتیکه کار قبل از کار j، به کار j روی ماشین mتغییر یابد، زمان تکمیل هر کار روی هر ماشین به ترتیب زیر محاسبه میشود و ماشینی انتخاب میشود که کمترین زمان تکمیل را داشته باشد : ماشین انتخاب شده را m* بنامید؛ سپس زمان در دسترس بودن ماشین m* در مرحله s و زمان در دسترسی کار j در مرحله s به روز میشود. زمان تکمیل کار j، را برابر زمان تکمیل کار j روی ماشین m* در مرحله s ( ) است. برای مرحله آخر و برای هر ماشین : توالی کارهایی است، که قرار است روی ماشین m پردازش شوند، و مجموعه کارهایی است، که بدون بیکاری و وقفه به صورت متوالی بر روی ماشین m بعد از کار j پردازش میشوند و جایگاه آخرین کار در گروه است و زیرمجموعه‍ای از گروه است که زودکرد دارند و برابر کمترین مقدار زودکرد در گروه و نشاندهندة j امین کار در توالی روی ماشین m است. نشان‍دهنده زمان بیکاری بعد از گروه است و از رابطه (19) محاسبه میشود:
(19) st نشان دهنده زمان شروع کار و C نشان دهنده زمان تکمیل است. در صورتیکه دو شرط زیر برقرار باشد : 1) 2) تعداد کارهای دارای زودکرد بیش از تعداد کارهای با دیرکرد باشد. کار j ام و گروه به اندازه t به سمت راست جابهجا می شود، که از رابطه (20) به دست می‍آید:
(20) سپس گروه ، مقادیر E، ، ، مجموع زودکرد و دیرکرد محاسبه شود. این روند تا زمانی که یکی از شرطها نقض شود، تکرار میشود. به این ترتیب یک برنامه زمانبندی کامل که متناسب با تابع هدف است، به دست می‍آید.
الگوریتم مبتنی بر شبیهسازی تبرید برای حل مدل پیشنهادی از الگوریتم مبتنی بر شبیهسازی تبرید استفاده میشود (جانیاک و همکاران،2007). در الگوریتم پیشنهادی، مراحل تعریف نحوة نمایش جواب، تولید جمعیت اولیه، جستجوی همسایگی، مکانیزم کاهش دما و پذیرش جواب و جستجوهای محلی، باید اجرا شوند: الف) نحوه نمایش جواب در اینجا برای نمایش جواب، توالی کارها در مرحله اول در نظر گرفته میشود. ب) تولید جمعیت اولیه برای تولید جمعیت اولیه سه روش تصادفی، مبتنی بر قاعدة EDD[6][7] و مبتنی بر الگوریتم NEH بررسی میشود. ج) جستجوی همسایگی برای پیمایش در فضای شدنی باید جواب شدنی دیگری با تغییر جواب فعلی ایجاد شود که جواب همسایه نامیده میشود. برای به دست آوردن جواب همسایه روشهای جابجایی[8] و جاسازی[9] بررسی میشود. طول جستجوی همسایگی برای مقادیر 5، 10 و 15 بررسی میشود.
د) مکانیزم کاهش دما و پذیرش جواب مکانیزم کاهش دما با استفاده از عبارت (21) تعیین میشود:که در آن α ضریب کاهش دما و ثابتی کمتر از یک است. n نشان دهنده تعداد دفعات کاهش دما است مکانیزم پذیرش جواب‍های تولید شده به این صورت است که اگر جواب بهتر شود آن جواب پذیرفته شود، در غیر این صورت با استفاده از عبارت (22) مقدار y محاسبه شود. سپس یک مقدار تصادفی تولید میشود و با مقدار y مقایسه میشود، اگر مقدار عدد تصادفی به دست آمده کمتر از y باشد جواب پذیرفته شود، در غیر این صورت جواب رد میشود. در این عبارت Z∆ برابر اختلاف بین جواب جاری و جواب همسایگی است و T بیانگر دمای جاری سیستم است. الگوریتم با مقادیر 1000، 1500 و 1800 برای دمای اولیه و نرخ کاهش دما با مقادیر 0.1، 0.2 و تحلیل میشود. که حداکثر تعداد تکرارها است. ه) جستجو محلی در الگوریتم پیشنهادی برای ارتقاء جواب‍های به دست آمده از این الگوریتم از جستجوهای محلی تصادفی استفاده میشود. به این منظور از دو نوع جستجوی همسایگی بر روی بهترین جواب به دست آمده از الگوریتم شبیه سازی تبرید استفاده میشود. یک جستجو بر روی مرحله اول و سپس جستجو بر روی مرحله آخر. جستجو بر روی مرحله اول به این علت اهمیت دارد که کوچکترین تغییر در زمانبندی مرحله اول می‍تواند تغییر قابل توجهی در زمانبندی کلی و مقدار تابع هزینه ایجاد کند. به این منظور در هر یک ازجستجو‍های محلی تصادفی، چهار همسایگی در نظر گرفته شده است: یک ماشین و دو کار که بر روی آن پردازش میشوند به صورت تصادفی انتخاب شده و با هم جابهجا میشوند. یک ماشین و یک کار که روی آن پردازش میشود انتخاب شده و کار در موقعیت دیگری به صورت تصادفی قرار میگیرد. دو ماشین و دو کار که بر روی آنها پردازش میشوند به صورت تصادفی انتخاب و دو کار با هم جابهجا میشوند. یک کار از ماشین اول به طور تصادفی انتخاب شده و در موقعیتی که به طور تصادفی روی ماشین دوم انتخاب شده است، جایگزین میشود. برای به دست آوردن برنامه زمانبندی کامل و تابع هدف از الگوریتم بخش 3-2-1 استفاده میشود. به منظور تعیین مقدار مناسب پارامترهای الگوریتمهای پیشنهادی از روش طراحی آزمایشهای تاگوچی استفاده میشود؛ مزیت این روش این است که میتوان با انجام آزمایشهای کمتر، مقدار پارامترهای الگوریتم را طوری تنظیم کرد که میزان تغییرپذیری جواب بهدستآمده از الگوریتم (متغیر پاسخ) کمینه شود. با توجه به نتایج حاصل از طراحی آزمایشهای تاگوچی پارامترهای الگوریتم پیشنهادی مبتنی بر شبیهسازی تبرید به شرح زیر است: روش تولید جمعیت اولیه مبتنی بر EDD، حداکثر تکرار ها 20، تعداد همسایگی 10، دمای اولیه 1500، نرخ کاهش دما . در شکل 1 شبه کد الگوریتم پیشنهادی مبتنی بر شبیهسازی تبرید ارائه شده است.
الگوریتم پیشنهادی مبتنی بر بهینه سازی انبوه ذرات کندی و ابرهارت (1995) الگوریتمی برای بهینهسازی مسائل با تابع هدف غیر خطی و متغیر تصمیم پیوسته ارائه کردند. این الگوریتم بر این اصل استوار است که در هر لحظه هر ذره مکان خود را در فضای جستجو با توجه به بهترین مکانی که تا کنون در آن قرار گرفته است و بهترین مکانی که در کل همسایگی‍اش وجود دارد، تنظیم میکند. در این الگوریتم هر ذره در فضای جستجو به دنبال نقطه بهینه حرکت میکند و دارای سرعت است. مسائل زمانبندی از نوع مسائل گسسته هستند و الگوریتم بهینهسازی انبوه ذرات ماهیتاً پیوسته است؛ بنابراین، از روش ارائه شده در تاسگیتایرن و همکاران (2004) استفاده میشود. برای به کارگیری الگوریتم پیشنهادی، مراحل زیر باید اجرا شوند:
شکل 1- شبه کد الگوریتم مبتنی بر شبیه سازی تبرید.
الف)تعریفنحوه نمایش جواب ها به منظور تبدیل مقادیر پیوسته به مقادیر گسسته از روش کوچکترین ارزش مکانی (SPV) استفاده میشود. هر ذره با یک بردار بیان میشود، که تعداد آرایه های این بردار برابر با تعداد کارها است. هر ذره بیانگر یک توالی از کارهاست و برای تعیین آن مقادیر تصادفی تولید شده برای هر یک از آرایههای این بردار به ترتیب صعودی مرتب میشوند. در جدول 1، مثالی از نحوه نمایش جواب برای پنج کار ارئه شده است؛ در این مثال به ازی هر کار یک مقدار تصادفی تولید شده است، که کوچکترین آنها مربوط به کار 5 است، لذا این کار در اولین موقعیت برای پردازش قرار میگیرد؛ موقعیت سایر کارها به همین ترتیب تعیین میشود.
.جدول 1 -نمایش جواب در الگوریتم مبتنی PSO
ب) تولید جمعیت اولیه در این مرحله، جمعیت اولیه به صورت تصادفی تولید میشود. الگوریتم با مقادیر 20، 30 و 40 برای اندازة جمعیت اولیه تحلیل میشود. ج)جستجو، تعیین موقعیت و سرعت ذرات هر ذره در جمعیت اولیه دارای سرعت صفر است. سرعت و موقعیت هر ذره با استفاده از عبارتهای (23) و (24) در هر تکرار به روز میشود..
مقادیر i، it، X وV به ترتیب نشان‍دهنده شماره ذره، شماره تکرار، بردار موقعیت ذره و بردار سرعت است. rand یک مقدار تصادفی بین صفر و یک است. نشان‍دهنده بهترین موقعیتی است که ذره تاکنون یافته است و بهترین موقعیتی است که ذرات موجود تاکنون به آن دست یافته‍اند. هر دوی این مقادیر بر اساس تابع برازندگی تعیین میشوند. برای تنظیم پارامترهای مربوط به موقعیت و سرعت ذرات الگوریتم با مقادیر ، و برای اختلاف بین حداقل و حداکثر موقعیت ذرات، و با مقادیر ، (و برای اختلاف بین حداقل و حداکثر سرعت ذرات، تحلیل میشود. و ضرایب یادگیری هستند. برای ایجاد توازن بین جستجوی محلی و جستجوی کلی، در محاسبه بردار سرعت از ضریب وزنی اینرسی(w) استفاده می شود. در این پژوهش این ضریب به صورت یک معادله خطی کاهشی به صورت w( درنظر گرفته شده است. الگوریتم با مقادیر 1، 25/1 و 2 برای ضرایب یادگیری ، و مقادیر 85/0، 9/0 و 99/0 برای و تعیین ضریب وزنی اینرسی، تحلیل میشود. د) عملگرهای جهش و تقاطع در الگوریتم پیشنهادی برای پیشگری از قرار گرفتن در بهینه محلی از عملگر جهش و تقاطع که در الگوریتم ژنتیک بهکار گرفته میشود، استفاده شده است. یکی از انواع عملگرهای تقاطع، عملگر OPX است (جانگواتاناکیت ؛ 2009). در این عملگر دو والد انتخاب میشود و دو نقطه به صورت تصادفی بر روی آنها انتخاب میشود، ژنهای موجود بین این دو نقطه از والد اول به فرزند اول منتقل میشود، و مقدار بقیه موقعیتها از والد دوم به ترتیب از چپ به راست، برای فرزند اول در نظر گرفته میشود؛ برای فرزند دوم نیز به صورت مشابه تعیین میشود الگوریتم با در نظر گرفتن مقادیر 6/0، 7/0 و 8/0 برای نرخ تقاطع و حالتهای زیر برای تعیین نوع عملگر تقاطع تحلیل میشود: 1) OPX 2) تکنقطهای 3) تکنقطهای / OPX
شکل 2- عملگر تقاطع تک نقطه‍ای اصلاح شده
در این الگوریتم عملگرهای جهش جابجایی، جهش معکوس و جهش احیاء (جدول 2)، نیز بررسی میشود. در جهش جابجایی ابتدا دو کار به صورت تصادفی انتخاب میشوند و با هم جابجا میشوند؛ در جهش معکوس دو نقطه در طول کروموزوم به صورت تصادفی انتخاب میشوند و توالی کارها بین این دو نقطه معکوس میشود در جهش احیاء[10] دو ژن به صورت تصادفی انتخاب میشود و دو عدد تصادفی جدید تولید شده و جایگزین اعداد قبلی میشود (جدول2). دراین الگوریتم نیز از روشهای جستجوی محلی به کار رفته درالگوریتم مبتنی بر شبیهسازی تبرید استفاده میشود.
جدول 2- جهش احیاء
همچنین، الگوریتم با در نظر گرفتن مقادیر 1/0، 2/0 و 3/0 برای نرخ جهش و حالتهای زیر برای تعیین نوع عملگر جهش تحلیل میشود: 1) جهش معکوس/ جابجایی 2) جهش احیاء / معکوس 3) جهش احیاء / جابجایی به منظور محاسبه تابع هزینه و به دست آوردن زمانبندی کامل از روش ابتکاری ارائه شده در بخش1.2.3 استفاده میشود. باتوجه به اینکه بعد از چندین تکرار جوابها به یک مقدار همگرا میشوند، حداکثر تعداد تکرارها به عنوان شرط توقف الگوریتم تعیین میشود. برای مسائل کوچک، متوسط و بزرگ به ترتیب حداکثر تعداد تکرارها 100، 200 و 350 در نظر گرفته شده است. با توجه به نتایج حاصل از طراحی آزمایشهای تاگوچی پارامترهای الگوریتم پیشنهادی مبتنی بر بهینهسازی انبوه ذرات به شرح زیر است: اندازه جمعیت اولیه 40، عملگر جهش معکوس/احیا، عملگر تقاطع OPX، نرخ جهش 3/0 ، نرخ تقاطع 7/0 ، برابر 2، برابر 99/0، برابر ، برابر . در شکل 3 شبه کد الگوریتم پیشنهادی مبتنی بر بهینهسازی انبو ه ذرات ارائه شده است.
نتایج محاسباتی به منظور ارزیابی عملکرد الگوریتم های ارائه شده 20 مسأله کوچک و 24 مسأله متوسط و بزرگ با پارامترهای مختلف تولید شده است. پارامترهای مسائل با استفاده از روابطی که جانگواتاناکیت و همکاران (2009) ارائه کردهاند، و از مقادیر تولید شده است. مجموعه مسائل متوسط و بزرگ شامل 12 ترکیب از تعداد کارها و تعداد مراحل است، که برای هر ترکیب 2 مسأله نمونه ایجاد شده است. و هر مسأله تولید شده 10 بار اجرا شده است. الگوریتم های پیشنهادی با متلب، کدنویسی شده، و همه مسائل بر روی رایانه پنتیوم آر دو هستهای، با 2.6 گیگاهرتز و 2 گیگابایت حافظه اجرا شدهاند. مسائل نمونه بیانشده در جدول 3 ابتدا با نرمافزار GAMS به صورت دقیق، و سپس با الگوریتمهای پیشنهادی حل شدهاند و نتایج محاسباتی در جدول 4 ارائه شدهاند. در ستونهای اول و دوم جدول 4 شمارة مسائل نمونه و اندازة مسأله (تعداد مرحله * تعداد کار) بیان شده است. به عنوان مثال اندازة مسألة نمونة 1 معادل با (3کار * 5مرحله) است. زمان (ثانیه) و مقدار تابع هدف به دست آمده از حل مسائل نمونه با نرمافزار GAMS در ستونهای سوم و چهارم، زمان(ثانیه) و مقدار تابع هدف به دست آمده از حل مسائل نمونه با استفاده از الگوریتم پیشنهادی مبتنی بر شبیه سازی تبرید در ستونهای پنجم و ششم، ارائه شده است که ستونهای مذکور با عنوان HSA مشخص شدهاند؛ زمان (ثانیه) و مقدار تابع هدف به دست آمده از حل مسائل نمونه با استفاده از الگوریتم پیشنهادی مبتنی بر بهینهسازی گروه ذرات در ستونهای هفتم و هشتم، ارائه شده است، و ستونهای مذکور با عنوان HPSO مشخص شدهاند.
جدول3- نحوه تولید پارامترهای مسائل نمونه
به منظور مقایسة الگوریتمها با یکدیگر، درصد انحراف نسبی (RPD[11]) محاسبه میشود. این معیار در بسیاری از پژوهشهای پیشین از جمله پژوهش بهنامیان و زندیه (2011)، از این معیار استفاده شده است. هرچه میزان درصد انحراف نسبی حاصل از اجرای الگوریتم کمتر باشد، عملکرد الگوریتم و کیفیت جواب بهتر است. میزان درصد انحراف نسبی (RPD) از رابطه (25) محاسبه میشود: که در آن sol مقدار جواب در یک اجرا است و کمترین مقدار جواب، بین همة اجراهای مربوط به یک مسأله است. برای مقایسة نتایج الگوریتمها از نظر زمان حل و کیفیت جواب، آزمون مقایسة زوجی با کمک نرمافزار مینی تب16[12] استفاده شد. برای صحت انجام آزمون مذکور لازم است که دادههای نامتعارف در نظر گرفته نشوند، از نرمال بودن دادهها اطمینان حاصل شود، و اندازة نمونة تصادفی باید به حدی باشد که بتوان اختلاف معنی دار بین میانگین مقادیر زمان حل و کیفیت جوابها را تشخیص داد. همانطور که در جدول 5 مشاهده میشود در مقادیر مربوط به زمانهای حل و همچنین مقادیر درصد انحراف نسبی (RPD) دادههای نامتعارف وجود ندارد؛ همچنین، چون تعداد مسائل نمونه بیشتر از 20 است نیازی به انجام آزمون نرمال بودن نیست و دادههای جمعآوری شده برای شناسایی اختلاف معنیدار بین میانگین زمانهای حل و میانگین کیفیت جواب‍های حاصل از دو الگوریتم، کافی است.
جدول 4 -نتایج حاصل از اجرای الگوریتم ها و نرمافزار GAMS
با توجه به نتایج تحلیل آماری انجام شده؛ با سطح اطمینان 95درصد، میانگین زمان حل الگوریتم مبتنی بر بهینهسازی گروه ذرات از میانگین زمان حل الگوریتم مبتنی بر شبیهسازی تبرید کمتر است، و با سطح اطمینان 95درصد میانگین درصد انحراف نسبی (RPD) الگوریتم مبتنی بر بهینهسازی گروه ذرات از میانگین درصد انحراف نسبی (RPD) الگوریتم مبتنی بر شبیهسازی تبرید بزرگتر است است؛ به عبارت دیگر کیفیت جواب الگوریتم مبتنی بر شبیهسازی تبرید بهتر از کیفیت جواب الگوریتم مبتنی بهینهسازی گروه ذرات است.
3- نتیجه گیری در این مقاله، ابتدا یک مدل ریاضی، برای مسأله زمانبندی جریان کارگاهی انعطافپذیر با در نظر گرفتن زمانهای آمادهسازی وابسته به توالی و تابع هدف مجموع زودکرد و دیرکرد، ارائه شد.
جدول 5- نتایج اجرای الگوریتمهای پیشنهادی
این مسأله از نظر پیچیدگی محاسباتی در دستة مسائل نامعین سخت (NP-Hard) قرار میگیرد. لذا برای حل مسأله مورد نظر، الگوریتمهای مبتنی بر بهینهسازی گروه ذرات و شبیهسازی تبرید ارائه شد. ابتدا چندین مسأله در ابعاد کوچک و بزرگ طراحی و سپس نتایج حاصل از اجرای روشهای پیشنهادی مقایسه شد. نتایج محاسباتی نشان می‍دهد که گرچه الگوریتم مبتنی بر بهینهسازی انبوه از الگوریتم مبتنی بر شبیهسازی تبرید زمان حل کمتری دارد ولی از نظر کیفیت جواب الگوریتم مبتنی بر شبیهسازی تبرید نسبت به الگوریتم مبتنی بر بهینهسازی انبوه ذرات بهتر عمل میکند. به طور متوسط میزان درصد انحراف نسبی، نتایج آزمایشهای محاسباتی الگوریتم مبتنی بر بهینهسازی ذرات 4.4 درصد، و الگوریتم مبتنی بر شبیهسازی 2.3 درصد است. در نهایت پیشنهاد میشود به منظور بهبود کیفیت جواب حاصل از الگوریتمهای پیشنهادی و کاهش زمان حل روشهای بهتری برای تعیین برنامة زمانبندی کامل توسعه یابد، و یا از الگوریتمهای ابتکاری و فراابتکاری کارآمدتری برای حل مسأله استفاده شود. همچنین، برای دستیابی به نتایج واقعیتر توصیه میشود که محدودیتها و مفروضات دیگر که در مسائل دنیای واقعی مطرح است، مانند در نظر گرفتن محدودیت ظرفیت انبارهای میانی، در نظر گرفته شود. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| مراجع | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Alaykyran, K., Engin, O., & Doyen, A. (2007). Using ant colony optimization to solve hybrid flow shop scheduling problems. Int J Adv Manuf Techno, 35, 541-550. Behnamian, J., & Zandieh, M. (2011). A discrete colonial competitive algorithm for hybrid flowshop scheduling to minimize earliness and quadratic tardiness penalties. Expert Systems with Applications, 38, 14490-14498. Botta-Genoulaz, V. (2000). Hybrid flow shop scheduling with precedence constraints and time lags to minimize maximum lateness. Int. J. Production Economics, 64, 101-111. Crowder, B. (2006). Minimizing the Makespan in a Flexible Flowshop with Sequence Dependent Setup Times, Uniform Machines, and Limited Buffers. West Virginia University. Gupta, J. N. D. (1998). Two-stage hybrid flow shop scheduling problem. Journal of the Operational Research Society, 39(4), 359–364. Janiak, A., Kozan, E., Lichtenstein, M., & Oguz, C. (2007). Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion. International Journal of Production Economics, 105(2), 407–424. Jenabi, M., Fatemi-Ghomi, S. M. T., Torabi, S. A., & Karimi, B. (2007). Two hybrid metaheuristics for the finite horizon elsp in flexible flow lines with unrelated parallel machines. Applied Mathematics and Computation, 186(1), 230–245. Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., & Werner, F. (2005). An Evaluation of Sequencing Heuristics for Flexible Flowshop Scheduling Problems with Unrelated Parallel Machines and Dual Criteria. Otto-von-Guericke-Universitat Magdeburg, 28(5), 1-23. Jungwattanakit, J., Reodecha,M., Chaovalitwongse, P., Werner, F. (2009). A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Computers and Operations Research 36(2), 358–378. Kennedy, J., Eberhart, R., (1995). Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks IV 1942–1948 Khalouli, S., Ghedjati, F., Hamzaoui, A.,. (2010). A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop. Engineering Applications of Artificial Intelligence, 23, 765-771. Liao, C.-J., Tsengb, C.-T., & Luarn, P. (2007). A discrete version of particle swarm optimization for flowshop scheduling problems. Computers & Operations Research, 34, 3099-3111. Liu, C. Y., & Chang, S. C. (2000). Scheduling flexible flow shops with sequence-dependent setup effects. IEEE Transactions on Robotics and Automation, 16(4), 408–419. Tasgetiren, M. F., Sevkli, M., Liang, Y.-C., & Gencyilmaz, G. (2004). Particle Swarm Optimization Algorithm for Single Machine Total Weighted Tardiness Problem. Proceeding of IEEE Evolutionary Computation Congress. Tran, T. H., & Ming ng, K. (2011). A water-flow algorithm for flexible flow shop scheduling with intermediate buffers. J Sched, 14, 483-500. Urlings, T., and Ruiz, R., & Şerifoğlu, F. S. (2010). Genetic algorithms with different representation schemes for complex hybrid flexible flow line problems. Int. J. Metaheuristics, 1(1), 30-54. Yaurima, V., Burtseva, L., & Tchernykh, A. (2009). Hybrid flowshop with unrelated machines, sequence-dependent setup time, availability constraints and limited buffers. Computers and Industrial Engineering, 56(4), 1452–1463. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
آمار تعداد مشاهده مقاله: 4,121 تعداد دریافت فایل اصل مقاله: 1,557 |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||