بخشی از مقاله
خلاصه
در سیستم تولید جریان کارگاهی، فضای ذخیرهسازی میان دو ماشین متوالی میتواند محدود و یا صفر باشد که این وضعیت منجر به ایجاد انسداد در روند تولید میگردد. در برخی از محیطهای تولیدیِ متغیر، ممکن است شاهد انواع مختلف انسداد باشیم. ازآنجاییکه پیچیدگی این مسائل از نوع نمایی بوده، لذا برای حل آن در زمان معقول نیاز است از الگوریتمهای ابتکاری و فرا ابتکاری استفاده شود. در این مقاله به حل مسئلهی زمانبندی جریان کارگاهی همراه با محدودیت انسداد ترکیبی، با استفاده از الگوریتم فرا ابتکاری زنبور عسل خواهیم پرداخت. مقایسهی جواب بهدستآمده با جواب بهینه و میزان خطا، نشاندهندهی کارایی مناسب الگوریتم پیشنهادی میباشد.
کلمات کلیدی: جریان کارگاهی، انسداد ترکیبی، الگوریتم فرا ابتکاری زنبور عسل
.1مقدمه
زمانبندی جریان کارگاهی* شاخه ای از علم توالی عملیات است که در آن بایستی توالی پردازش چند کار بر روی ماشینها مشخص شود. مسیر انجام فعالیتها برای تمامکارها یکسان است .[1]در سال 1996 هال و سریسکاندراجا [2] ثابت نمودند که جریان کارگاهی برای وقتیکه تعداد کارها بیشتر از 2 است یک مسئله Np-hard است. جهت کاربردی نمودن این دسته از مسائل تصمیمگیری محدودیتها و فرضهایی به آن اضافه میشود. ازجمله این فرضها،در نظر گرفتن محدودیت فضای ذخیرهسازی بین دو ماشین و یا محدودیت کمبود اپراتور جهت پردازش بیوقفه کارها در فرایند تولید است.
هر زمان که این موارد پیش بیاید گفته میشود که انسداد رخداده است. کاربردهایی از بهکارگیری این فرض در صنایع شیمیایی [3]، آهن و استیل [4]، فرایند سریسازی تولید [5] گزارش شده است. در سال 1972 ردی و رامامورثی [6] نشان دادند که مسئله دو ماشین همراه با محدودیت انسداد حالت خاصی از مسئله فروشندهی دور گرده است. پاپادمیتریو و همکارش [7] در سال 1980 نشان دادند که مسئله دو ماشین همراه با انسداد، Np-hard است.در مسئلهی جریان کارگاهی کلاسیک، اگر فرایند پردازش یک کار به پایان برسد، آن کار منجر به توقف ماشین فعلی نمیشود، در انبار میانی ذخیره میشود و بهمحض اینکه ماشین بعدی بیکار شد به آن انتقال مییابد به این حالت WB یا بدون انسداد گفته میشود. انواع دیگر انسداد به شرح زیر است:
: RSb* -1 متوقف ماندن یک ماشین توسط یک کار تا زمانی که این کار بتواند بلافاصله بر روی ماشین بعدی شروع به کار کند.
: RCb* - 2 در این حالت یک کار بر روی یک ماشین تا زمانی که کار قبلی روی ماشین بعدی تمام نشود شروع نمیشود.[8]
: RCb -3 در این حالت یک کار بر روی یک ماشین تا زمانی که کار قبلی روی ماشین بعدی تمام نشود و آن را ترک نکند، شروع نمیشود. [9]
در محیط تولیدی وابسته به تعداد اپراتور، ویژگی ماشین و نوع فرایند تولیدی ممکن است با انسدادهای مختلفی روبرو شویم. در این مقاله ترکیبی از انسدادها در محیط تولیدی در نظر گرفتهشده است .در شکل 1 شماتیک کلی از انسداد ترکیبی قابل مشاهده است.
.2 تعریف مساله
در مسائل برنامهریزی جریان کارگاهی کلاسیک، جریانی از n کار بر روی m ماشین که باید زمان پردازش معینی را به ترتیب بر روی همهی ماشینها بگذرانند برقرار است. در این مقاله، با اضافه کردن محدودیت انسداد ترکیبی به مسئلهی جریان کارگاهی کلاسیک باهدف کمینه کردن مجموع زمان تکمیل پردازش کل کارها به دنبال نزدیکتر کردن محیط تولیدی به دنیای واقعی هستیم. بر اساس نمادگذاری گراهام و همکارانش [26] مسئلهی پیشنهادی بهصورت∑ بیان میشود. ازآنجاییکه مسئلهی جریان کارگاهی همراه با محدودیت انسداد Np-hard است ، لذابرای حل مسئلهی پیشنهادی در زمان معقول از الگوریتمهای ابتکاری و فرا ابتکاری استفاده خواهیم کرد.
. 2.1 مدل برنامهریزی خطی عدد صحیح
مدلسازی، تعریف تعامل بین اجزای نظامها و کارکرد آنها در قالبی قابلدرک است تا بتوان به تجزیهوتحلیل و اتخاذ تصمیمها برای بهتر کردن نتایج مورد انتظار از عملکرد آنها پرداخت. مدل سازیهای مختلفی برای این منظور وجود دارد که یکی از آنها مدلسازی ریاضی است. مدلسازی ریاضی تعامل بین اجزاء و کارکرد آنها را به زبان ریاضی بیان مینماید.در این مقاله از مدل ارائهشده توسط ترابلسی و همکاران [27] برای مسائل کارگاه جریانی با انسداد ترکیبی ارائه کردند، استفاده خواهیم کرد با این تفاوت که تابع هدف مورداستفاده در این مقاله حداقل کردن زمان تکمیل همهی کارها است.
.3 روش حل پیشنهادی
پیچیدگی حاصل از افزایش تعداد ماشینها و کارها منجر به طولانی شدن زمان حل مسئلههای جریان کارگاهی که دارای پیچیدگی از نوع Np-hard هستند و روی کار آمدن الگوریتمهای فرا ابتکاری میشود. یکی از این الگوریتمها، الگوریتم زنبورعسل میباشد. این الگوریتم مبتنی بر هوش دستهجمعی - SI - است کهنوعاً از یک گروه از عوامل ساده
