پژوهش – طراحی یک مدل ریاضی وحل آن با الگوریتم های ابتکاری و … |
 |
برنامه ریزی خطی
R| |
ونگ و همکاران
R| |+
آکیول و همکاران
تبرید شبیهسازی شده
R| , |
چن
۲-۴-۳. مسائل جریان کارگاهی:
در یک مسأله جریان کارگاهی m ماشینه، تعداد m مرحله عملیات به صورت متوالی بر روی کارها صورت میگیرد. هر کدام از کارها بر روی همه ماشینها با توالی یکسان پردازش میشوند. در مسائل جریان کارگاهی منعطف حداقل در یکی از مراحل بیش از یک ماشین برای پردازش کارها وجود دارد و در واقع در این مرحله خاص، یکی از انواع مختلف مسائل ماشینهای موازی به وقوع میپیوندد.
مسأله جریان کارگاهی برای اولین بار توسط جانسون[۳۶] با دو ماشین و تابع هدف زمان تکمیل کار بیشینه بررسی شد. تمامی مدلهای موجود در تحقیقات بعدی توسعه این مدل بشمار میآیند. در مسائل کلاسیک یک بافر نامحدود[۲۹] که کارها روی ماشینها یا در بین دو ماشین متوالی در حال انتظار باشند، مفروض است. با این وجود در مسائل جریان کارگاهی بدون انتظار[۳۰] این فرض منظور نمیشود و کارها بدون وقفه از ابتدا تا انتهای زمان پردازش خود بر روی ماشینها پردازش میشوند [۳۰]. زمانیکه بافر واسطه بین ماشینها وجود ندارد، مسائل بدون بافر[۳۱] به وجود میآیند. مسائل بدون انتظار و مسائل بدون بافر با ماشین در حالتی که زمانهای نصب ماشین جزئی از زمان پردازش کارها هستند، معادل هم میباشند. برای حالت زمان نصب مجزا دو حالت مختلف برای مسائل بدون بافر وجود دارد: در حالت اول تا زمانی که کار جاری ماشین اول را ترک نکند، به کار بعدی اجازه نصب داده نمیشود و در حالت دوم به محض این که پردازش کار جاری بر روی ماشین اول به اتمام برسد، نصب کار بعدی آغاز میشود[۳] .
کروین اسوگبو [۱۶] مسأله جریان کارگاهی دو ماشینه را با توجه به معیار زمان تکمیل کار بیشینه و محدودیت زمان نصب وابسته به توالی بر روی ماشین اول و زمان نصب مستقل از توالی بر روی ماشین دوم و بالعکس،آدرسدهی نمودند.آنها با استفاده از زمانبندی جایگشتی به جواب بهینه دست یافتند و همچنین برای این مسأله یک مدل برنامهریزی پویا طراحی نمودند.گوپتا و دارو [۲۹] مسأله مشابهی را با محدودیت زمان وابسته به توالی برای هر دو ماشین بررسی نمودند و خاطرنشان نمودند که مسأله حتی برای حالت یک ماشین با زمان نصب وابسته به توالی در کلاس مسائلStrongly NP-hard قرار میگیرد.ریوس مرکادو و بارد [۵۰] برای مسأله جریان کارگاهی با m ماشین و تابع هدف زمان تکمیل کار بیشینه یک الگوریتم شاخه و کران به همراه حد بالا و پائین [۳۲]و معیار حذف مغلوب ارائه نمودند.
در دهههای اخیر مسائل زمانبندی جریان کارگاهی منعطف توجه بسیاری از محققان را به خود جلب نمودهاست. دلیل این امر را میتوان ماهیت نسبتاً پیچیده این مسائل و کاربرد فراوان آنها در محیط صنعتی دانست [۴۹]. این نوع مسائل با محدودیت زمان نصب ماشین وابسته به توالی در کلاس Np-hard قرار میگیرند [۴۱]. کرز و آسکین [۴۲] با توجه به دشواری حل مسأله با استفاده از برنامهریزی عددصحیح، یک الگوریتم ژنتیک با کلیدهای تصادفی[۳۳] را برای حل مسأله توسعه دادند. آنها حدهای پایین را برای مسأله تولید و از آن برای ارزیابی الگوریتم استفاده نمودند. جانگواتاکی و همکارانش [۳۷] مسأله را در حالت ماشینهای نامرتبط و با تابع هدف مجموع وزنی تعداد کارهای با تأخیر و زمان تکمیل کار بیشینه مورد توجه قرار دادند.آنها الگوریتمهای ژنتیک و تبرید شبیهسازی شده بکار رفته در مسائل جریان کارگاهی را برای حالت منعطف تطابق دادند و با ارائه نتایج محاسباتی خاطرنشان نمودند که الگوریتم ژنتیک عملکرد مناسبتری نسبت به الگوریتم تبرید شبیهسازی شده از خود نشان میدهد.
در یکی از آخرین تحقیقات صورت گرفته در مسائل جریان کارگاهی منعطف، بهنامیان و همکارانش [۹] ترکیبی از الگوریتم ژنتیک و روش جستجوی همسایگی متغیر را برای یک تابع دو هدفه با معیارهای زمان تکمیل کار بیشینه و هزینههای تخصیص منابع بکار گرفتند و کارایی الگوریتم پیشنهادی خود را برای اندازههای بزرگ مسأله نشان دادند.
زندیه و غلامی [۴۷] در زمانبندی جریان کارگاهی منعطف با زمان آمادهسازی وابسته به توالی به منظور کمینهسازی زمان پایان کار ماکسیمم،از الگوریتم ایمنی[۳۴] استفاده نمودهاند.بدین ترتیب که آنها یک الگوریتم فرا ابتکاری[۳۵] مبتنی بر سیستم ایمنی توسعه دادند و برای ارزیابی این الگوریتم، دادههایی مطابق با تحقیق کرز و آسکین [۴۲] را تولید و نتایج را با الگوریتم پیشنهادی خود مقایسه نمودند. جدول (۲-۳) خلاصهای از آنچه که در این بخش عنوان شد را نمایش میدهد.
جدول۲-۳٫ مسائل جریان کارگاهی با محدودیت زمان نصب ماشین
| رویکردها | توابع و محدودیتها | نویسندگان |
| برنامهریزی پویا و زمانبندی جایگشتی | | | | کروین و اسوگبو |
فرم در حال بارگذاری ...
|
[شنبه 1399-09-22] [ 03:57:00 ق.ظ ]
|
