حل مسأله زمان بندی جریان کارگاهی به روش ابتکاری با فرض عدم توقف‌- قسمت 22

حل مسأله زمان بندی جریان کارگاهی به روش ابتکاری با فرض عدم توقف‌- قسمت 22

در این روش از پارامتری به نام استفاده می‌شود که بیانگر فاصله زمانی شروع کار ام بعد از اتمام کار ام روی ماشین اول می‌باشد که از رابطه‌ی 3-1 بدست می‌آید:
در این رابطه زمان پردازش کار jام روی ماشین iام است. این رابطه فاصله زمانی بین اتمام کار ام روی ماشین اول و شروع کار ام را بهگونه‌ای مشخص می‌کند که هیچ توفقی برای کار ام ایجاد نشود.
با توجه به رابطه 3-1 تابع هدف طولانی‌ترین زمان تکمیل به صورت رابطه 3-2 محاسبه می‌شود:

برای دانلود متن کامل پایان نامه به سایت zusa.ir مراجعه نمایید.

(3-2)

ون‌دروین و همکاران [39] مسأله را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار و با در نظر گرفتن ساختار خاصی برای پردازش کارها روی ماشینها مورد بررسی قرار داده و یک روش ابتکاری برای حل آن با استفاده از روش حل مسأله فروشنده دوره گرد ارائه میدهند.
در سال 1993 راجندران [40] الگوریتم ابتکاری با الهام از الگوریتم برای مسأله جریان‌کارگاهی با محدودیت عدم‌توقف با تابع هدف کمینهکردن زمان تکمیل پردازش آخرین کار ارائه میدهد. تفاوت الگوریتم ارائه شده با الگوریتم ، در گام اولیه آن یعنی تولید توالی ابتدایی می باشد. در این الگوریتم برای تولید توالی اولیه از رابطه 3-3 استفاده شده است.

(3-3)

بعد از تولید توالی اولیه از رابطه 3-3، دیگر مراحل همانند الگوریتم می‌باشد. بدین ترتیب که کارها بر اساس قرارگیری در توالی اولیه انتخاب شده به طوری که تمامی حالتها آن بررسی و بهترین حالت حفظ می‌شود تا توالی بهینه بدست آید.
این الگوریتم، با توجه به رابطه 3-3، تاکید بر این موضوع دارد که کارهایی که زمان پردازش آنها بر ماشینهای اولیه کمتر است، بر سایر کارها اولویت دارند، زیرا اولویت کارهایی که زمان پردازش آنها بر روی ماشینهای ابتدایی بیشتر است، باعث انسداد بیشتری برای شروع کار بعدی می‌شود که این مطلب از تعریف مسئله جریان‌کارگاهی با عدم‌توقف نیز قابل برداشت است.
برتولیسی [41] مسأله را با هدف کمینه کردن مجموع زمان تکمیل پردازش کارها در نظر گرفته و یک روش ابتکاری برای حل آن ارائه میدهند. گلاس و همکاران [42] مسأله در حالت دو ماشینه را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و فرض می‌کنند زمان پردازش تعدادی از کارها برروی ماشین دوم صفر است. آنها یک روش ابتکاری برای حل مسأله مورد بحث ارائه می‌دهند.
سیدنی و همکاران [43] مسأله در حالت دو ماشینه را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار و با فرض زمانهای آماده‌سازی ماشین بدون حضور کار مورد بررسی قرار می‌دهند. آنها یک الگوریتم ابتکاری برای حل مسأله مورد نظر ارائه میدهند. برتولیسی [41] الگوریتم ابتکاری برای حل مسأله به منظور کمینه‌کردن مجموع زمان تکمیل پردازش کارها ارائه میدهد.
الله وردی و آیدوسان [44] مسأله در حالت سه‌ماشینه را با فرض زمانهای آماده سازی مستقل از توالی کارها و با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار میدهند. آنها جواب بهینه را برای حالتهای خاصی مورد بررسی بدست آورده و برای حالت کلی مسأله یک روش ابتکاری ارائه میدهند.
لین و چنگ [28] مسأله را در حالت دو ماشینه با تابع هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار میدهند. آنها فرض زمان خرابی یا تعمیر ماشینها را در مسأله مورد بررسی در نظر گرفته، پیچیدگی را بررسی کرده و روشهای ابتکاری برای حل آن ارائه میدهند. الله وردی و آیدوسان [44] مسأله در حالت دو ماشینه را با فرض زمانهای آمادهسازی وابسته به توالی ماشینها و با هدف کمینه‌کردن زمان تکمیل پردازش کار مورد بررسی قرار میدهند.
چنگ و لیو [45] مسأله در حالت دو ماشینه را با محدودیت زمان خرابی یا تعمیر ماشین‌ها و با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و یک الگوریتم ابتکاری برای حل تقریبی آن ارائه میدهند.
آیدوسان و الله وردی [46] روش ابتکاری برای حل مسأله تابع هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار ارائه میدهند. کوبزین و استراسویچ [47] مسأله در حالت دو ماشینه را با فرض خرابی ماشینها و با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار در نظر میگیرند و یک روش ابتکاری برای حل آن ارائه میدهند. وانگ و همکاران [48] مسأله انعطاف‌پذیر دو مرحله ای را مورد برررسی قرار میدهند. آنها پیچیدگی مسأله را مورد بحث قرار داده و الگوریتم ابتکاری برای حل آن ارائه میدهند. بوقارد و همکاران [49] مسأله را با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرارداده و روشی تقریبی برای حل آن ارائه میدهند.
لی و همکاران [50] مسأله را با تابع هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و یک الگوریتم ابتکاری برای حل آن ارائه میدهند.
کالشینسکی و کامبوروسکی [51] مسأله را با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار را مورد بررسی قرار میدهند و یک الگوریتم ابتکاری برای حل آن ارائه میدهند و نشان می‌دهند این الگوریتم قابل استفاده برای مسأله جریان‌کارگاهی انعطافپذیر نیز میباشد و یک حد پایینی برای آن تعیین میکنند.
رویز و الله وردی [52] یک الگوریتم ابتکاری برای مسأله با تابع‌های کمینه‌کردن زمان تکمیل پردازش آخرین کار و کمینه‌کردن حداکثر دیرکرد ارائه کرده و نشان دادند این الگوریتم الهام گرفته از الگوریتم ژنتیک است که جواب‌های با کیفیتی را بدست میدهد.
فرامین و همکاران [53] مسأله را با هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده، یک الگوریتم ابتکاری برای حل آن ارائه داده و نشان دادند که این الگوریتم قابلیت اجرا به عنوان یک جستجوی محلی را دارا می باشد.
مروری بر الگوریتم‌های فراابتکاری مسئله جریان‌کارگاهی با محدودیت عدم‌توقف
الگوریتم‌های فراابتکاری دارای چارچوبی از پیش تعیین شده هستند که برای حل هر مسأله بهینه‌سازی کافی است که آن مسأله را در قالب چارچوب الگوریتم فراابتکاری درآورد. در اغلب مقاله‌های که الگوریتم‌هایی برای حل مسائل بهینه‌سازی پیچیده با استفاده از الگوریتم‌های فراابتکاری ارائه شده، جواب‌هایی با کیفیت بالا در زمان کوتاهی بدست آمده است. در صورتی که جواب‌های ابتکاری همواره به یک جواب مشخص می‌رسند، الگوریتم های فراابتکاری بدلیل ماهیت تصادفی خود، قابلیت ایجاد جواب‌های متنوع را خواهند داشت. به همین دلیل شانس بیشتری در دستیابی به جواب‌هایی با کیفیت در مقایسه با الگوریتم‌های ابتکاری را دارند. برای حل مسأله جریان‌کارگاهی با محدودیت عدم‌توقف نیز الگوریتم‌های فراابتکاری متعددی از جمله الگوریتم جستجوی پراکنده، الگوریتم ژنتیک[35]، الگوریتم جست وجوی ممنوع[36] و الگوریتم مورچگان ارائه شده است.

این مطلب را هم بخوانید :  توسعه یک مدل بهینه سازی چند هدفه برای طراحی شبکه زنجیره تأمین در شرایط ...

مدیر سایت