SPT

Traveling Saleman Problem

:

TSP

مقدمه
امروزه در عرصه صنعت بدلیل تفاوت و گوناگونی نیازهای مشتریان شاهد تنوع محصول‌ها، کوتاه شدن عمرشان و رقابت بالای تولیدکنندگان می‌باشیم. از این‌رو اهمیت به کارگیری روش‌هایی کارا جهت استفاده موثر از منابع بیش‌تر از گذشته نیاز می‌شود تا سازمان‌ها بتوانند قدرت پاسخگویی سریع به نیازهای مشتریان را داشته باشند. تکنیک‌های توالی عملیات و زمان‌بندی از جمله ابزار موثر در این رابطه است.
در ادامه این فصل، ابتدا مقدمه‌ای از اهمیت و ضرورت زمان‌بندی تولید و توالی عملیات گفته می‌شود و سپس با مفاهیم توالی عملیات و نمادگذاری انواع مختلف مسائل آشنا خواهیم شد.
توالی عملیات و زمان‌بندی
تعیین توالی‌کارها[1] و زمان‌بندی[2] به معنی تخصیص منابع محدود به فعالیتهایی است که به آن منابع نیاز دارند. از این‌رو می توان آن را نوعی فرایند تصمیم‌گیری دانست که با هدف بهینهسازی یک و یا چند هدف انجام میگیرد. این امر نقش بسیار مهمی در کاهش هزینه‌ها، افزایش بهره‌وری، افزایش رضایت مشتری و به طور کلی افزایش سودآوری شرکت‌ خواهد داشت.
آغاز علم زمان‌بندی را بدون شک باید در تلاش‌های هنری گانت[3] در دو دهه ابتدایی قرن بیستم جستجو کرد. اما شروع تحقیقات جدی و گسترده در این زمینه و مرتبط ساختن آن با تحقیق در عملیات به اوایل دهه 1950 بر می‌گردد. اولین الگوریتم زمان‌بندی که به صورت مستقیم مسائل زمان‌بندی را به تحقیق در عملیات مرتبط ساخت، در سال 1954 توسط جانسون [1] ارائه شد و تقریبا برای اولین بار جواب بهینه یک مسأله زمان‌بندی بوسیله آن بدست آمد. پس از آن مسائل متعددی در زمینه توالی عملیات معرفی و الگوریتم‌های متنوعی برای حل آنها توسعه داده شد.
در مسأله زمان‌بندی موجود در سیستم‌های صنعتی (خدماتی)، با یک سری از منابع، عمدتا ماشین‌ها و یک تعداد کار که باید بر روی (از) این ماشین‌ها (خدمت دهنده‌ها) پردازش شوند (خدمت بگیرند) و یک سری از محدودیت‌ها سروکار داریم که با توجه به آنها در صدد بهینه کردن یک یا چند تابع هدف هستیم.
شاخه‌ای از علم توالی عملیات به نام زمان‌بندی جریان‌کارگاهی[4] نامیده می شود. زمان‌بندی جریان‌کارگاهی یکی از مدل‌های سنتی زمان‌بندی و توالی عملیات است که طیف وسیعی از مسائل عملی زمان‌بندی را در خود جای می‌دهد. در مدل جریان‌کارگاهی تعدادی کار و ماشین وجود دارد که این کارها هر یک با مسیر یکسان باید بر روی تمام ماشین‌ها پردازش شوند. در این مدل، عملیات هر کار به ترتیب بر روی ماشین اول، ماشین دوم و تا ماشین آخر انجام می‌گردد و همچنین هر ماشین فقط یک کار را در هر زمان انجام می‌دهد و هدف انجام تمامی کارها با کمترین هزینه می‌باشد. در واقع در مدل جریان‌کارگاهی جریان پیوسته‌ای از کارها وجود دارد که بایستی توسط چند ماشین پردازش شوند و به همین دلیل به نام جریان‌کارگاهی نامیده می‌شود.
آشنایی با مفاهیم زمان‌بندی
منابع و کارها در یک سازمان می‌توانند صورت‌های مختلفی داشته باشند. برای نمونه، منابع می‌توانند ماشین‌های یک کارگاه، باندهای پرواز در یک فرودگاه، خدمه‌ها در یک محل احداث بنا و یا واحدهای پردازش در یک محیط محاسباتی باشند. همچنین کارها می‌توانند عملیات در یک فرایند تولیدی، بلند شدن و نشستن هواپیما در یک فرودگاه، مراحل یک پروژه تولیدی و یا اجرای برنامه‌های رایانه‌ای باشند. هر کار نیز می‌تواند دارای یک سطح اولویت یا اهمیت خاص، زودترین زمان ممکن برای شروع پردازش و یک موعد تحویل باشد. تابع هدف نیز می‌تواند به صورت‌های مختلف تعریف شود. برای نمونه تابع هدف می‌تواند کمینه کردن زمان اتمام پردازش آخرین کار و یا کمینه کردن تعداد کارهایی که پردازش آنها بعد از موعد تحویلشان به پایان می‌رسد، باشد [2].
در ادامه این قسمت در ابتدا با نمادگذاری مسائل زمان‌بندی آشنا خواهیم شد و پس از آن پیچیدگی مسائل زمان‌بندی مورد بحث قرار خواهد گرفت.
نمادگذاری
به دلیل تنوع مدلهای زمانبندی و توالی‌عملیات و به منظور تفکیک مناسب این مسائل از یکدیگر چنیدن روش نمادگذاری معرفی شده است. برای اولین بار کانوی و همکاران[3] از یک نمادگذاری 4 تایی بصورت برای مسائل زمان‌بندی استفاده نمودند. با این‌حال نمادگذاری که امروزه از آن استفاده می‌شود نخستین بار توسط گراهام و همکاران [4] در 1979 معرفی شده است. در این شیوه، یک مسأله زمان‌بندی با یک 3 تایی نشان داده میشود که قسمت α محیط ماشینها[5] را توصیف میکند و فقط شامل یک نماد است. قسمت β خصوصیات پردازش و محدودیتهای موجود را شرح می‌دهد که این قسمت میتواند شامل هیچ نماد و یا چند نماد باشد. قسمت تابع(های) هدفی که باید بهینه شود را توصیف میکند. لازم به ذکر است که این نمادگذاری بعدها توسط پیندو [2] به‌روز شده است. در ادامه به مقادیر مختلفی که هر کدام از اجزای این نمادگذاری می توانند داشته باشند، خواهیم پرداخت و در پایان برای روشن شدن موضوع چندین مثال معرفی خواهد شد.
حالتهای مختلف محیط ماشینها
در دنیای واقعی انواع گوناگونی از محیطهای تولیدی و خدماتی شامل تک ماشینه، ماشینهای موازی، جریان‌کارگاهی، کار کارگاهی و کارگاه باز به شرح زیر وجود دارد. نماد مرتبط با هر مشخصه در مقابل آن در داخل پرانتز آورده شده است.
محیط تک ماشینه[6] (1): در محیط تک ماشینه همانطور که از نام آن پیداست یک ماشین وجود دارد که تعدادی کار به وسیله‌ی این ماشین پردازش می‌شوند.
شکل ‏1‑1: شمایی از محیط تک ماشینه
محیط جریان‌کارگاهی (Fm): دریک محیط جریان‌کارگاهی، n کار برروی m ماشین به ترتیب پردازش میشوند. در این محیط توالی پردازش کارها بر روی ماشینهای مختلف یکسان است. به عبارت دیگر، همه کارها ابتدا روی ماشین اول، سپس روی ماشین دوم و به همین ترتیب تا ماشین m ام پردازش می‌شوند. پس از اتمام پردازش یک کار روی یک ماشین، آن کار به صف پردازش ماشین بعدی می‌پیوندد. اغلب فرض میشود که تمامی صفها بر اساس قانون [7] کار میکنند، یعنی هیچ کاری نمیتواند از کار دیگری که در صف انتظار است سبقت بگیرد. شمایی از محیط جریان‌کارگاهی، در شکل زیر نشان داده شده است. در این شکل، نشان دهنده ماشین ام کارگاه بوده و نیز نشان دهنده‌ی ظرفیت فضای قبل از ماشین iام است. صف کارها برای پردازش روی هر ماشین در فضای قبل از آن ماشین شکل میگیرد. ظرفیت فضای قبل از هر ماشین میتواند هر عددی از صفر تا بی‌نهایت باشد.
شکل ‏1‑2: شمایی از محیط جریان‌کارگاهی
محیط جریان‌کارگاهی انعطاف پذیر[8] (FFc) : در شرایطی که در یک محیط جریان‌کارگاهی در برخی از ایستگاهها بیش از یک ماشین برای پردازش کارها وجود داشته باشد، به این محیط، محیط جریان‌کارگاهی انعطافپذیر گفته می‌شود. در این محیط، کار تنها با شروع از ایستگاه اول پردازش میشوند و برای پردازش آنها تا ایستگاه ام ادامه خواهد داشت. در این محیط هر کار تنها توسط یکی از ماشینهای موازی هر ایستگاه پردازش میشود. در شکل زیر شمایی از محیط جریان‌کارگاهی انعطاف پذیر، نشان داده شده است.
شکل ‏1‑3: شمایی از محیط جریان‌کارگاهی انعطاف پذیر
محیط کار کارگاهی[9] (Jm): یک کارگاه با شیوه تولید کار کارگاهی از آرایش یک سری ماشین‌آلات با استفاده عام که مورد استفاده یک حرفه خاص هستند، پدید میآید. مثلا یک سری ماشین‌آلات تراش، فرز، دریل، آهنگری و … تولید هر یک از محصولات در این شیوه با تولید محصول دیگر متفاوت است و هر یک نیاز به طی مسیر تولیدی خاص خود را دارند.
کارگاه باز[10] (Om): در این حالت ماشین وجود دارد و هر کار باید حداقل یک بار روی هر یک از ماشین پردازش شود. اما زمان پردازش یک کار روی برخی از ماشینها میتواند صفر باشد. هیچ محدودیتی نیز در مورد توالی پردازش یک کار روی ماشینها وجود ندارد. به عبارت دیگر، تفاوت کارگاه باز با کار کارگاهی در این است که برخلاف کار کارگاهی، مسیر پردازش کارها روی ماشینها ثابت و از پیش تعیین شده نیست و بر اساس ماهیت تابع هدف، مسیر پردازش هر کار روی ماشینها را تعیین کند. در نتیجه مسیر پردازش کارهای مختلف میتواند متفاوت باشد.
محدودیت‌های پردازش و محیط
در محیطهای تولیدی و خدماتی، محدودیتهای متفاوتی ممکن است وجود داشته باشد که حل مسأله زمانبندی نیازمند رعایت این محدودیتها است. تعدادی از این محدودیتها به قرار زیر هستند:
زمانهای آماده‌سازی وابسته به توالی[11] () : در برخی موارد، ماشینها پیش از شروع پردازش یک کار نیازمند آماده‌سازی هستند که این زمان آمادهسازی وابسته به کار اول () و کار دوم () است. در صورتی که زمان آماده‌سازی برای ماشینهای مختلف، متفاوت باشد، زمان آماده‌سازی وابسته به توالی با نماد نمایش داده میشود که به معنی زمان آمادهسازی ماشین ام پیش از پردازش کار و پس از پردازش کار j است.

7

6

4

Max{13,7} +2 = 15

Max{7,6} + 6= 13

4+3=7

به همین ترتیب برای کار سه و چهار می توان مقادیر را بدست آورد. در شکل 2-4 برای ترتیب داده شده نمودارگانت ترسیم شده است.
شکل ‏2‑1: نمودار گانت مثال جریان‌کارگاهی
همانگونه که در نمودار فوق دیده می شود، تابع هدف که عبارت است از زمان تکمیل آخرین کار ()، برای ترتیب داده شده 29 می‌باشد.
مرور ادبیات جریان‌کارگاهی
اولین مقاله در زمینه FS توسط آقای جانسون [1] در 1954 منتشر شد. از آن زمان تاکنون مقاله‌های متعددی در این زمینه در مجله‌های معتبر علمی به چاپ رسیده است. با وجود اینکه مفهوم مدل زمان‌بندی توسط آقای جانسون معرفی شده است، لیکن عنوان برای نخستین بار در 1965 در مقاله ایگنال و اسچارج [6] به کار گرفته شد. در 1996 هال و سریکاندراجا [7] ثابت نمودند که مساله جریان‌کارگاهی برای بیش از دوماشین یک مساله است. در سال 2006 گوپتا و همکاران [8] در مقاله خود مقاله‌های چاپ شده در این حوزه را به 5 دوره تقسیم کردند. بیشتر تحقیقات دوره اول مرتبط با مسائل ریاضی همان مدل اولیه آقای جانسون است و بیشتر روی 2 یا 3 ماشین بحث می‌نماید.
در دوره دوم بین 1965 تا 1974 شاهد ایجاد راه حل‌های متفاوت از یک سو و همچنین در نظر گرفتن توابع غیر از زمان کل از سوی دیگر بود. در این دوره موضوع عمده مقاله‌ها، ارائه روش‌های بهینه برای حل مسائل مختلف بود.
در دوره سوم به علت پیچدگی روش‌های بهینه، روش‌های ابتکاری متعددی برای حل این نوع مسائل ابداع گردند. در این دهه بود که مدل‌سازی احتمالی این نوع مسائل نیز مطرح گردید.
در دوره چهارم ( 1985 تا1994) مسائل زمان‌بندی ترکیبی مطرح گردید. در این دهه از انواع روش‌های فراابتکاری استفاده شده است. به علت استفاده از فرضیات مرتبط با زمان‌های مستقل و وابسته، هوش مصنوعی و سیستم‌های پشتیبان تصمیم‌گیری دوره چهارم را می‌توان پر فروغ‌ترین دوره تحقیقات مسأله زمان‌بندی جریان‌کارگاهی دانست.
در دوره آخر که تاکنون ادامه دارد شاهد تنوع مسأله، توابع هدف و ابداع روش‌های متفاوت بسیاری بوده‌ایم و پیوندها با دیگر مسائل برنامه ریزی تولید، در این دوره انجام گردیده است.
الگوریتم‌های ابتکاری
پیچیدگی حاصل از افزایش تعداد ماشین‌ها و کارها و عدم وجود روشهای دقیق برای آنها، محققان را به سمت استفاده و گسترش الگوریتم‌های ابتکاری سوق داده است. این موضوع مهم‌ترین دلیل وجود تعداد بالای الگوریتم‌های ابتکاری در ادبیات این موضوع می‌باشد. در ادامه مروری جامع بر الگوریتم‌های ابتکاری در حوزه جریان‌کارگاهی خواهیم داشت و خواهیم دید که الگوریتم‌های ابتکاری در این حوزه را می‌توان به‌طور کلی در سه الگوریتم جانسون، پالمر و تقسیم نمود و در انتها با این سه الگوریتم آشنا می‌شویم.
مروری بر الگوریتم‌های ابتکاری در حوزه جریان‌کارگاهی
الگوریتم جانسون [1] اولین الگوریتم شناخته شده برای مسأله جریان‌کارگاهی می‌باشد. با استفاده از این الگوریتم مقدار بهینه در حالتی که تنها دو ماشین وجود دارد، به دست آورده می‌شود. پیچیدگی این الگوریتم می‌باشد.
الگوریتم جانسون را می‌توان برای حالتی که در آن تعداد ماشین‌ها بیش از دو است تعمیم داد. در این زمینه الگوریتم‌های متعددی معرفی شده است. دودک و تئوتون [9] برپایه الگوریتم جانسون، قانونی m مرحله‌ای را استفاده کردند که مجموع زمان اتلاف روی آخرین ماشین در صورتی که پردازش هر کار از رویکرد جانسون انجام شود را کمینه می‌کرد. کمپل و همکاران [10] الگوریتمی را پیشنهاد نمودند که نیازمند m-1 مرحله محاسبات بود. در این الگوریتم هر m ماشین واقعی در هر مرحله به دو گروه ماشین مجازی افراز شده و سپس طبق الگوریتم جانسون محاسبات صورت می‌پذیرفت. پیچیدگی محاسباتی این الگوریتم می‌باشد. گوپتا [11] یک الگوریتم ابتکاری برای کمینه کردن زمان اتلاف به نام و دو الگوریتم ابتکاری برای کمینه‌کردن طولانی‌ترین زمان تکمیل به نام‌های و ارائه نمود. مقایسه نتایج بدست آمده نشان‌دهنده بهبود کیفیت و کاهش زمان حل نسبت به الگوریتم پیشنهادی کمپل بود.
در الگوریتم ابتکاری که توسط پالمر [12] پیشنهاد شده است، برای هر کار شاخصی معین می‌گردد و کارها براساس این شاخص زمان‌بندی می‌شوند. شاخص تعریف شده توسط پالمر نام دارد. پیچیدگی محاسبات این الگوریتم می‌باشد. بونی و گوندری [13] مجموع زمان‌های پردازش هر کار بر روی تمام ماشین‌ها را به عنوان معیار هرکار درنظر گرفته‌اند. هوندال و راجگوپال [14] با معرفی دو شاخص جدید و استفاده از شاخص پالمر سه زمان‌بندی برای هر مسئله معرفی نمودند. پیچیدگی محاسبات این الگوریتم، مشابه با الگوریتم پالمر می‌باشد. داننبریج [15] الگوریتمی ابتکاری براساس الگوریتم‌های ابتکاری جانسون و پالمر ارائه نمود. در این الگوریتم، مشابه با الگوریتم کمپل، ماشین‌ها به صورت ماشین‌های مجازی دوتایی فرض شده و سپس با استفاده از مقدارهای به‌دست آمده، شاخصی جهت هر کار تعیین می‌گردد.
نواز و همکاران [16] الگوریتم ابتکاری را ارائه کردند که این الگوریتم بهترین الگوریتم ارائه شده برای مسائل جریان‌کارگاهی می‌باشد. در این الگوریتم اولویت به کارهایی داده می‌شود که زمان پردازش بیشتری دارند. پیچیدگی محاسبات این الگوریتم O(n3m) می‌باشد. راجندران [17] الگوریتم ابتکاری به نام ارائه نمود که بسیار شبیه الگوریتم است که تنها تفاوت آن، در شرط اولیه برای بدست آوردن توالی اولیه می‌باشد. وی برای هر کار، مجموع زمان پردازش وزن‌داری را معرفی می‌کند.
سارین و لفوکا [18] الگوریتمی ابتکاری در نظر گرفتند که ایده‌ی آن کمینه کردن زمان اتلاف روی آخرین ماشین بود. این ایده باعث کاهش طولانی‌ترین زمان تکمیل می‌شود. در این الگوریتم، اولویت با کارهایی است که کمترین مجموع زمان پردازش روی همه‌ی ماشین‌ها را دارا هستند. مقایسه نتایج بدست آمده از این الگوریتم نسبت به الگوریتم در مسائلی با بیش از150کار بهتر است.
راجندران و زیگلر [19] الگوریتم ابتکاری ارائه نمودند که در آن در ابتدا به هر کار وزنی تخصیص داده می‌شد. سپس برای هر کار مجموع زمان پردازش وزن‌دار محاسبه شده و بر اساس مقادیر بدست آمده دو توالی نزولی و صعودی تعیین می‌گردد. از بین دو توالی، هر کدام که مقدار تابع هدف بهتری داشته باشد، به عنوان توالی اولیه انتخاب و سپس از الگوریتم استفاده می‌گردد.
وو و ییم [20] الگوریتمی ابتکاری مشابه با الگوریتم Raj ارائه نمودند. در الگوریتم ارائه شده نیازی به توالی اولیه نیست. در ابتدا مجموع زمان پردازش کارها محاسبه شده و سپس همانند الگوریتم و توالی بهینه بدست خواهد آمد. نتایج نشان می‌دهد که این الگوریتم برای تابع هدف کمینه‌کردن مجموع زمان جریان از الگوریتم های ، و کمپل بهتر عمل می‌کند. پیچیدگی محاسبات این الگوریتم O(n4m) می‌باشد.

14

12

6

گام اول : لیست اولیه کارها را بر اساس مجموع زمان پردازش مرتب می‌کنیم : 6-2-5-3-4-1
گام دوم : کار 1 و 4 را در نظر می‌گیریم و برای توالی‌های ممکن یعنی 1-4 و 4-1 مقدار تابع هدف را محاسبه می‌کنیم که داریم : 210 و 236. در نتیجه توالی 1-4 را انتخاب می‌کنیم.
گام سوم : کار بعدی یعنی کار 3 را در نظر می‌گیریم و برای توالی‌های ممکن 3-1-4 ، 1-3-4 و 1-4-3 مقدار تابع هدف را محاسبه می‌کنیم که بعد از محاسبه، توالی 1-3-4 با مقدار 231 را انتخاب می‌کنیم. و با ادامه این روند، توالی بهینه یعنی توالی 4-3-1-5-2-6 با مقدار تابع 322 بدست می‌آید.
جمع‌بندی
در این فصل ابتدا با مسئله جریان‌کارگاهی و سپس با اهمیت آن در علم توالی عملیات و زمان‌بندی آشنا شدیم. در ادامه مروری بر ادبیات این مسئله انجام شد و سپس به مرور روش‌های ابتکاری حل مسئله جریان‌کارگاهی پرداختیم . در این فصل همچنین نشان دادیم که ایده اکثر الگوریتم‌های ابتکاری مسئله جریان‌کارگاهی بر پایه سه الگوریتم جانسون، پالمر و می‌باشد. و در انتها سه الگوریتم ابتکاری مهم مسئله جریان‌کارگاهی را با مثال تشریح کردیم.

جریان‌کارگاهی با محدودیت عدم‌توقف
در این فصل، ابتدا تعریفی جامع بر مسئله جریان‌کارگاهی با محدودیت عدم‌توقف خواهیم داشت. و خواهیم دید که این محدودیت در دنیای واقعی چه اثرگذاری دارد. در ادامه مروری بر پژوهش‌های انجام شده در حوزه مسئلهی مورد بررسی ، الگوریتم‌های ابتکاری و الگوریتم‌های فراابتکاری خواهیم داشت. در گام بعد، به بررسی مدل ریاضی مسئله و اثبات آن می‌پردازیم.
جریان‌کارگاهی با محدودیت عدم‌توقف
مسأله مورد بررسی در این رساله، تعیین توالی و زمان‌بندی در یک محیط جریان‌کارگاهی با محدودیت عدم‌توقف[33] است که به اختصار خوانده می‌شود. منظور از عدم‌توقف این است که هر کار پس از شروع پردازش بر روی اولین ماشین، به صورت پیوسته بر روی دیگر ماشین‌ها تا آخرین ماشین پردازش می‌شود و هیچ توقفی بین پایان عملیات بر روی یک ماشین و شروع عملیات بر روی ماشین بعدی وجود نداشته باشد. به بیان دیگر، زمان تکمیل پردازش یک کار بر روی یک ماشین دقیقا برابر با زمان شروع پردازش آن کار بر روی ماشین بعدی است. از این‌رو زمان شروع یک کار بر روی ماشین اول بایستی به نوعی زمان‌بندی شود تا این محدودیت رعایت گردد.
شکل ‏3‑1: شمایی از مسئله جریان کارگاهی با محدودیت عدم‌توقف
دلایل عمده به وجود آمدن محدودیت عدم‌توقف را به می‌توان به شرح زیر مطرح کرد [7]:
فناوری تولید:
در برخی از فرایند‌ها، برخی از مشخصه‌های مواد از نظیر دما یا چسبناکی این محدودیت را ایجاب می‌کند که عملیات متوالی بر روی ماشین‌ها بدون وقفه انجام شود. به عنوان نمونه این شرایط در فرایند تولید فولاد هنگامی که فولاد ذوب شده و مسیرهایی را به منظور قالب‌گیری، گرم‌کردن مجدد، خیساندن، نورد اولیه و… طی می‌کند، اتفاق می‌افتد. همچنین در صنایع پلاستیک و دارو‌سازی، تعدادی از فرایندها باید بدون وقفه و به صورت متوالی انجام شوند. در صنایع غذایی، فرایند قوطی‌ریزی مواد غذایی، باید دقیقا پس از آماده شدن مواد غذایی انجام شود تا مواد غذایی سالم بمانند. در صنایع تولیدی مدرن از جمله تولید ‌به ‌هنگام و سیستم‌های تولیدی انعطاف‌پذیر نیز محدودیت عدم‌توقف دیده می‌شود.
کمبود و یا عدم وجود انبارهای میانی بین ماشین‌های متوالی:
دلیل دوم برای به‌وجود آمدن محدودیت عدم‌توقف، کمبود انبارهای میانی بین ماشین‌ها و یا ایستگاه‌ها میباشد.
در این مسأله فرض می‌شود که کار در یک محیط جریان‌کارگاهی با ماشین، پردازش می‌شوند. با توجه به ویژگی‌ مسئله، ترتیب پردازش کارها بر روی ماشین‌ها یکسان می‌باشد. هدف از بررسی و حل این مسأله یافتن بهترین توالی پردازش کارها بر روی ماشین‌ها به گونه‌ای است که زمان اتمام پردازش آخرین کار () کمینه شود.
نماد مسأله مورد بررسی با استفاده از نمادهای مسائل [2] به صورت Fm/nwt/Cmax می‌باشد. در این نماد، قسمت اول که با Fm نشان داده شده است، نشان‌دهنده محیط جریان‌کارگاهی با ماشین است. نماد در بخش دوم محدودیت عدم‌توقف را نشان می‌دهد و بخش سوم نیز بیان‌کننده تابع هدف مورد بررسی که طولانی‌ترین زمان تکمیل است می‌باشد.
فرضیه‌های در نظر گرفته شده در این مسأله به شرح زیر است:
n کار برای پردازش بر روی ماشین در دست است؛
پردازش هر کار بر روی هر ماشین تا اتمام آن بدون وقفه صورت می‌پذیرد؛
زمان شروع یک کار برروی یک ماشین برابر با زمان اتمام آن بر روی ماشین قبلی است؛
زمان پردازش کارها بر روی ماشین‌ها قطعی و از قبل مشخص است؛
کلیه کارها در زمان صفر در دسترس است.
هال و سریکاندراجا [7] خلاصه‌ای از پژوهش‌های انجام شده تا سال 1996 در حوزه مسائل زمان‌بندی با محدودیت عدم‌توقف در محیط‌های جریان‌کارگاهی، کارکارگاهی و کارگاه باز را ارائه داده‌اند. آنها علاوه بر معرفی چندین روش ابتکاری برای حل مسأله، به بررسی پیچیدگی حالت‌های خاصی از این گروه مسائل پرداخته‌اند.
مرور ادبیات جریان‌کارگاهی با محدودیت ‌عدم‌توقف
سهنی و چو [24] مسأله زمانبندی با محدودیت عدم‌توقف را در محیطهای جریان‌کارگاهی، کار کارگاهی و کارگاه باز با تابع هدف کمینه کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و نشان میدهند که این گروه مسائل از نوع هستند. همچنین در این تحقیقات نشان داده می‌شود که مسائل کارکارگاهی و کارگاه باز در حالت دو ماشینه حتی هنگامی که هیچ کاری با زمان پردازش صفر بر روی یکی از ماشین ها وجود نداشته باشد هستند.
پانوالکر و وولام [25] حالت خاصی از مسأله را با تابع هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و قضیه‌هایی را در مورد مقدار بهینه تابع هدف مسأله مورد بحث مطرح کرده و اثبات میکنند.
مون و همکارای [26] مسأله زمان‌بندی جریان‌کارگاهی با محدودیت عدم‌توقف را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و مدل ریاضی خطی– عدد صحیح را برای حل آن ارائه میدهند. در مسأله مورد نظر، زمانهای حمل و نقل و زمانهای آمادهسازی وابسته به توالی ماشینها در نظر گرفته میشود. همچنین به منظور بررسی عملکرد مدل ریاضی این مسئله ، نمونههایی از مسأله مورد بررسی حل شده و نتایج آن با مدلهای پیشین مقایسه میشود.
آیدوسان [27] مسأله را در حالت دو ماشینه و با فرض زمانهای آمادهسازی ماشینها با هدف کمینه کردن مجموع زمان تکمیل پردازش کارها مطرح کرده و الگوریتم ابتکاری برای حل آن را ارائه می‌دهد. در این روش حد پایینی برای مسأله مورد بحث توسعه داده شده و از آن در روش شاخه و کران که به منظور ارزیابی الگوریتم ابتکاری ارائه شده، استفاده میشود.

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

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

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

در این روابط، ضریب اینرسی، و اعدادی تصادفی در بازه [0,1] با توزیع یکنواخت و همچنین، و ضرایب یادگیری هستند. و باعث می‌شوند که نوعی گوناگونی در جواب‌ها به‌وجود بیاید و به این نحو جستجوی کاملی روی فضا انجام پذیرد. ، ضریب یادگیری مربوط به تجارب شخصی هر ذره و ضریب یادگیری مربوط به تجارب کل جمع می‌باشد. از معادله بالا می‌توان به این نتیجه رسید که، هر ذره به هنگام حرکت، (الف) جهت حرکت قبلی خود، (ب) بهترین موقعیتی که در آن قرار داشته است و (پ) بهترین موقعیتی را که به وسیله کل جمع تجربه شده است، در نظر می‌گیرد.
بعد از انجام حرکت در فضای جستجو توسط تمامی ذرات یک مرجله از الگوریم به پایان می‌رسد.
جمع‌بندی
مسئله جریان‌کارگاهی با محدودیت عدم‌توقف کاربرد بسیار زیادی در سیستم‌های تولیدی و خدماتی دارد. با توجه به اهمیت این مسئله در دنیای واقعی ارائه الگوریتم کارا برای حل مسئله بسیار مهم می باشد.
تاکنون برای حل مسئله مورد بررسی الگوریتم‌های ابتکاری متعددی ارائه شده است که تمامی آنها قابلیت بدست آوردن جوابی خوب در کمترین زمان را دارا می‌باشند. در سال‌های اخیر استفاده از روش‌های فراابتکاری برای حل مسئله با توجه به قابلیت‌های این الگوریتم‌ها رو به رشد می‌باشد. در این فصل مروری کامل بر روش ‌های‌ابتکاری و فراابتکاری ارائه شده برای حل مسئله جریان‌کارگاهی با محدودیت عدم‌توقف پرداختیم و همچنین بهترین الگوریتم ارائه شده برای حل مسئله در ادبیات را مورد بررسی قرار دادیم.

الگوریتم و روش حل پیشنهادی
در این فصل، سه الگوریتمی فراابتکاری بر پایه الگوریتم مورچگان برای حل مسئله جریان‌کارگاهی با محدودیت عدم‌توقف ارائه می‌شود. تفاوت این الگوریتم ها در نحوه استفاده از الگوریتم جست‌وجوی محلی است. در پایان نتایج بدست آمده گزارش شده است.
الگوریتم فراابتکاری مورچگان
الگوریتم پیشنهادی که در این پایان‌نامه ارائه شده است، بر پایه الگوریتم بهینه‌سازی مورچگان است. این الگوريتم از رفتار مورچه‌ها در طبيعت الهام گرفته شده است. كاربرد اين الگوريتم در حل مسائل بهينه‌سازي تركيبي و مقايسة نتايج حاصل از آن با ديگر الگوريتم‌ها نشان دهندة كارايي بالاي اين الگوريتم مي‌باشد. مطرح کننده این الگوریتم مارکو دوریگو [70] است که در سال 1992 در قالب رساله دکتری آن را برای حل مسأله فروشنده دوره‌گرد[44] در 75 شهر، با نام سیستم مورچگان[45] () به عنوان مدل اولیه الگوریتم عرضه کرد. دوریگو وهمکاران در سال 1997 [71] در مقاله خود به معرفی الگوریتم سیستم کلونی مورچگان[46] () پرداختند. در الگوريتم ‌از تعدادي مورچة مصنوعي استفاده ميشود كه اين مورچه‌ها از طريق مبادلة‌ اطلاعات با يكديگر، در ساختن جواب همكاري مي‌كنند. اين الگوريتم علي‌رغم آنكه در حل مسائل فروشنده دوره‌گرد با نمونه‌هاي كوچك (كمتر از 30 شهر) دارای کیفیت جواب خوبی بود، اما استفاده از اين روش به دليل نیاز به زمان زياد در حل مسائل بزرگ، كاربرد آنرا محدود مي‌ساخت. به همين دليل تغييراتي بر روي اين الگوريتم به منظور افزايش كارايي آن انجام گرفت كه مي توان از الگوريتم‌هاي [72] و [71] نام برد.
بکارگیری الگوریتم مورچگان در حل مسائل جریان‌کارگاهی
استالتز در سال 1998 [73] اولین الگوریتم برای حل مسائل جریان‌کارگاهی جایگشتی[47] با تابع هدف کمینه‌سازی زمان تکمیل آخرین کار، به نام را ارائه کرد. این الگوریتم در واقع کاربرد روش بود که استالتز و هوس [74] در سال 1997 ارائه کردند. راجندران و زیگلر [75] در سال 2004 دو الگوریتم برای مسائل جریان‌کارگاهی جایگشتی با تابع هدفهای زمان تکمیل آخرین کار و زمان در جریان کلی[48] ارائه کردند. الگوریتم اول در واقع ترکیبی از الگوریتم وSummation Rule (ارائه شده توسط مرکل و میدن‌دور [76] ) بود. همچنین آنها یک روش جست‌وجوی محلی جدید به نام را نیز با این الگوریتم ترکیب کردند. ینگ و لیاو [77] در سال 2004 برای مسائل جریان‌کارگاهی، الگوریتم دیگری که کاربردی از بود را ارائه نمودند. الگوریتم دیگری توسط رانجندران و زیگلر [78] در سال 2006 برای مسائل جریان‌کارگاهی با تابع هدف کمینه سازی زمان تکمیل همه کارهای مختلف ارائه کردند. تعداد دیگری از محققان الگوریتم‌های مشابهی با تابع هدف‌های چندگانه نیز ارائه کرده‌اند[79] .
در سال 2012 احمدی‌زار [80] الگوریتم جدیدی به نام برای مسائل جریان‌کارگاهی با تابع هدف زمان تکمیل آخرین کار ارائه کرد. در این الگوریتم بر خلاف اکثر روش‌ها که یک عدد ثابت اولیه را به همه فرومون‌های اولیه اختصاص می‌دهند، از یک ترتیب اولیه برای مقداردهی اولیه به فرومون‌ها استفاده شده است.
الگوریتم پیشنهادی مورچگان
در الگوریتم مورچگان پیشنهادی، ایده تغییر فرومون برپایه روش است. در این روش مقدار فرومون‌ها بین دو مقدار کمینه و بیشینه تغییر می‌کنند. الگوریتم مورچگان شامل گام‌های مقداردهی اولیه فرومون‌ها، قاعده تغییر حالت، قاعده به‌هنگام کردن محلی، قاعده به‌هنگام کردن نهایی و جست‌وجوی محلی است. این گام‌ها در ادامه توضیح داده می‌شود.
مقداردهی اولیه فرومون
در الگوریتم پیشنهادی، تابع فرمون نشان دهنده اهمیت قرار گیری کار ام در مکان ام تعریف شده است. مقدار فرومون نشان‌گر درجه تمایل انجام فرایند کار ام در مکان ام است. برخلاف روشی که عموما برای مقدار دهی اولیه فرومون ارائه می‌شود، در اینجا از یک ترتیب اولیه استفاده می‌شود. ترتیب اولیه با استفاده از الگوریتم راجندران [40]، که در بخش 3-4 توضیح داده شده است، ایجاد می‌شود. با ایجاد ترتیب اولیه، مقدار فرمون اولیه ها از رابطه 4-1 بدست می‌آید: