مقاله درمورد حل مسأله و الگوریتم

(1)
Widget not in any sidebars

(2)
(3)
(4)
(5)
(6)
(7)
در ادامه به توضیح هر یک از محدودیت‌های این مدل می‌پردازیم.
محدودیت شماره 1 : این محدودیت کنترل می‌کند که هر کار تنها در یک مکان از توالی قرار گیرد.
محدودیت شماره 2: این محدودیت بیان ‌می‌کند هر مکان توالی تنها به یک کار تخصیص داده شود.
محدودیت شماره 3: بیان می‌کند که زمان اتمام پردازش کار در مکان j+1ام روی ماشین r، حداقل برابر است با مجموع زمان اتمام پردازش کار در مکان jام روی همان ماشین و زمان پردازش کار در مکان j+1ام روی ماشین rام .
محدودیت شماره 4: نشان می‌دهد که زمان اتمام پردازش کار در مکان j روی ماشین r+1ام برابر است با مجموع زمان اتمام پردازش کار در مکان jام روی ماشین rام و زمان پردازش کار در مکان jام روی ماشین r+1. این محدودیت موجب میگردد که عملیات هر کار بدون توقف از اولین تا آخرین ماشین انجام گیرد.
محدودیت شماره 5: این محدودیت نشان می‌دهد که همه‌ی کارها در لحظه‌ی صفر دردسترس‌اند.
محدودیت شماره 6: زمان اتمام کارها نمی‌تواند منفی باشد.
محدودیت شماره 7: متغیر یک متغیر صفر و یک است. مساوی یک است اگر کار iام در مکان jام توالی کارها قرارگیرد و در غیر اینصورت صفر است.
مروری بر الگوریتم‌های ابتکاری مسئله جریان‌کارگاهی با محدودیت عدم‌توقف
همان طور که در فصل قبل گفته شد، پیچیدگی حاصل از افزایش تعداد ماشینها و کارها و عدم وجود روشهای دقیق برای آنها، محققان را به سمت استفاده و گسترش الگوریتمهای ابتکاری سوق میدهد و این مهمترین دلیل وجود تعداد بالای این الگوریتم ها در ادبیات این موضوع می باشد. در ادامه الگوریتمی که برای مسائل عدم‌توقف طراحی شده است را معرفی میکنیم.
ردی و رامامورتی [38] مسأله را با هدف کمینه کردن زمان پردازش آخرین کار در نظر گرفته و کاربردهای این مسأله را در سیستمهای کامپیوتری خاطر نشان میکنند. آنها نشان میدهند که مسأله مورد بحث قابل تبدیل به یک مسأله فروشنده دوره گرد است و از این طریق روشی ابتکاری برای حل آن ارائه میدهند که در ادامه مورد بررسی قرار خواهد گرفت.
(3-1)
در این روش از پارامتری به نام استفاده می‌شود که بیانگر فاصله زمانی شروع کار ام بعد از اتمام کار ام روی ماشین اول می‌باشد که از رابطه‌ی 3-1 بدست می‌آید:
در این رابطه زمان پردازش کار jام روی ماشین iام است. این رابطه فاصله زمانی بین اتمام کار ام روی ماشین اول و شروع کار ام را بهگونه‌ای مشخص می‌کند که هیچ توفقی برای کار ام ایجاد نشود.
با توجه به رابطه 3-1 تابع هدف طولانی‌ترین زمان تکمیل به صورت رابطه 3-2 محاسبه می‌شود:
(3-2)
ون‌دروین و همکاران [39] مسأله را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار و با در نظر گرفتن ساختار خاصی برای پردازش کارها روی ماشینها مورد بررسی قرار داده و یک روش ابتکاری برای حل آن با استفاده از روش حل مسأله فروشنده دوره گرد ارائه میدهند.
در سال 1993 راجندران [40] الگوریتم ابتکاری با الهام از الگوریتم برای مسأله جریان‌کارگاهی با محدودیت عدم‌توقف با تابع هدف کمینهکردن زمان تکمیل پردازش آخرین کار ارائه میدهد. تفاوت الگوریتم ارائه شده با الگوریتم ، در گام اولیه آن یعنی تولید توالی ابتدایی می باشد. در این الگوریتم برای تولید توالی اولیه از رابطه 3-3 استفاده شده است.
(3-3)