بخشی از مقاله
خلاصه
در سیستم تولید جریان کارگاهی، فضای ذخیرهسازی میان دو ماشین متوالی میتواند محدود و یا صفر باشد که این وضعیت منجر به ایجاد انسداد در روند تولید میگردد . در برخی از محیطهای تولیدی بسته به شرایط حاکم ، شاهد ایجاد انواع مختلفی از انسداد خواهیم بود که هرکدام از آنها می توانند بهنوعی منجر به طولانی شدن فرایند تولید شوند. ازآنجاییکه پیچیدگی این مسائل از نوع نمایی بوده، لذا برای حل آن در زمان معقول نیاز است از الگوریتمهای ابتکاری و فرا ابتکاری استفاده شود. در این مقاله به حل مسئلهی زمانبندی جریان کارگاهی همراه با محدودیت انسداد ترکیبی، با استفاده از الگوریتم فرا ابتکاری جستوجوی پراکنده خواهیم پرداخت . مقایسهی جواب به دست آمده با جواب بهینه و میزان خطا، نشاندهندهی کارایی مناسب الگوریتم پیشنهادی می باشد.
کلمات کلیدی: جریان کارگاهی، انسداد ترکیبی، الگوریتم جستوجوی پراکنده
.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 تا 5 نمای شماتیک انسدادها بر روی ماشین نمایش دادهشده است.
