Simulated Annealing : SA
Shortest Processing Time : SPT
Traveling Saleman Problem : TSP
مقدمه
امروزه در عرصه صنعت بدلیل تفاوت و گوناگونی نیازهای مشتریان شاهد تنوع محصول‌ها، کوتاه شدن عمرشان و رقابت بالای تولیدکنندگان می‌باشیم. از این‌رو اهمیت به کارگیری روش‌هایی کارا جهت استفاده موثر از منابع بیش‌تر از گذشته نیاز می‌شود تا سازمان‌ها بتوانند قدرت پاسخگویی سریع به نیازهای مشتریان را داشته باشند. تکنیک‌های توالی عملیات و زمان‌بندی از جمله ابزار موثر در این رابطه است.
در ادامه این فصل، ابتدا مقدمه‌ای از اهمیت و ضرورت زمان‌بندی تولید و توالی عملیات گفته می‌شود و سپس با مفاهیم توالی عملیات و نمادگذاری انواع مختلف مسائل آشنا خواهیم شد.
توالی عملیات و زمان‌بندیتعیین توالی‌کارها و زمان‌بندی به معنی تخصیص منابع محدود به فعالیتهایی است که به آن منابع نیاز دارند. از این‌رو می توان آن را نوعی فرایند تصمیم‌گیری دانست که با هدف بهینهسازی یک و یا چند هدف انجام میگیرد. این امر نقش بسیار مهمی در کاهش هزینه‌ها، افزایش بهره‌وری، افزایش رضایت مشتری و به طور کلی افزایش سودآوری شرکت‌ خواهد داشت.
آغاز علم زمان‌بندی را بدون شک باید در تلاش‌های هنری گانت در دو دهه ابتدایی قرن بیستم جستجو کرد. اما شروع تحقیقات جدی و گسترده در این زمینه و مرتبط ساختن آن با تحقیق در عملیات به اوایل دهه 1950 بر می‌گردد. اولین الگوریتم زمان‌بندی که به صورت مستقیم مسائل زمان‌بندی را به تحقیق در عملیات مرتبط ساخت، در سال 1954 توسط جانسون ADDIN EN.CITE <EndNote><Cite><Author>Johnson</Author><Year>1954</Year><RecNum>1</RecNum><DisplayText>[1]</DisplayText><record><rec-number>1</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415113996">1</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Johnson, Selmer Martin</author></authors></contributors><titles><title>Optimal two‐and three‐stage production schedules with setup times included</title><secondary-title>Naval research logistics quarterly</secondary-title></titles><periodical><full-title>Naval research logistics quarterly</full-title></periodical><pages>61-68</pages><volume>1</volume><number>1</number><dates><year>1954</year></dates><isbn>1931-9193</isbn><urls></urls></record></Cite></EndNote>[1] ارائه شد و تقریبا برای اولین بار جواب بهینه یک مسأله زمان‌بندی بوسیله آن بدست آمد. پس از آن مسائل متعددی در زمینه توالی عملیات معرفی و الگوریتم‌های متنوعی برای حل آنها توسعه داده شد.
در مسأله زمان‌بندی موجود در سیستم‌های صنعتی (خدماتی)، با یک سری از منابع، عمدتا ماشین‌ها و یک تعداد کار که باید بر روی (از) این ماشین‌ها (خدمت دهنده‌ها) پردازش شوند (خدمت بگیرند) و یک سری از محدودیت‌ها سروکار داریم که با توجه به آنها در صدد بهینه کردن یک یا چند تابع هدف هستیم.
شاخه‌ای از علم توالی عملیات به نام زمان‌بندی جریان‌کارگاهی نامیده می شود. زمان‌بندی جریان‌کارگاهی یکی از مدل‌های سنتی زمان‌بندی و توالی عملیات است که طیف وسیعی از مسائل عملی زمان‌بندی را در خود جای می‌دهد. در مدل جریان‌کارگاهی تعدادی کار و ماشین وجود دارد که این کارها هر یک با مسیر یکسان باید بر روی تمام ماشین‌ها پردازش شوند. در این مدل، عملیات هر کار به ترتیب بر روی ماشین اول، ماشین دوم و تا ماشین آخر انجام می‌گردد و همچنین هر ماشین فقط یک کار را در هر زمان انجام می‌دهد و هدف انجام تمامی کارها با کمترین هزینه می‌باشد. در واقع در مدل جریان‌کارگاهی جریان پیوسته‌ای از کارها وجود دارد که بایستی توسط چند ماشین پردازش شوند و به همین دلیل به نام جریان‌کارگاهی نامیده می‌شود.
آشنایی با مفاهیم زمان‌بندیمنابع و کارها در یک سازمان می‌توانند صورت‌های مختلفی داشته باشند. برای نمونه، منابع می‌توانند ماشین‌های یک کارگاه، باندهای پرواز در یک فرودگاه، خدمه‌ها در یک محل احداث بنا و یا واحدهای پردازش در یک محیط محاسباتی باشند. همچنین کارها می‌توانند عملیات در یک فرایند تولیدی، بلند شدن و نشستن هواپیما در یک فرودگاه، مراحل یک پروژه تولیدی و یا اجرای برنامه‌های رایانه‌ای باشند. هر کار نیز می‌تواند دارای یک سطح اولویت یا اهمیت خاص، زودترین زمان ممکن برای شروع پردازش و یک موعد تحویل باشد. تابع هدف نیز می‌تواند به صورت‌های مختلف تعریف شود. برای نمونه تابع هدف می‌تواند کمینه کردن زمان اتمام پردازش آخرین کار و یا کمینه کردن تعداد کارهایی که پردازش آنها بعد از موعد تحویلشان به پایان می‌رسد، باشد ADDIN EN.CITE <EndNote><Cite><Author>Pinedo</Author><Year>2012</Year><RecNum>2</RecNum><DisplayText>[2]</DisplayText><record><rec-number>2</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415114269">2</key></foreign-keys><ref-type name="Book">6</ref-type><contributors><authors><author>Pinedo, Michael L</author></authors></contributors><titles><title>Scheduling: theory, algorithms, and sys--s</title></titles><dates><year>2012</year></dates><publisher>Springer</publisher><isbn>1461423619</isbn><urls></urls></record></Cite></EndNote>[2].
در ادامه این قسمت در ابتدا با نمادگذاری مسائل زمان‌بندی آشنا خواهیم شد و پس از آن پیچیدگی مسائل زمان‌بندی مورد بحث قرار خواهد گرفت.
نمادگذاریبه دلیل تنوع مدلهای زمانبندی و توالی‌عملیات و به منظور تفکیک مناسب این مسائل از یکدیگر چنیدن روش نمادگذاری معرفی شده است. برای اولین بار کانوی و همکاران ADDIN EN.CITE <EndNote><Cite><Author>Conway</Author><Year>1971</Year><RecNum>4</RecNum><DisplayText>[3]</DisplayText><record><rec-number>4</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415116656">4</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Conway, RW</author><author>Maxwell, WL</author><author>Miller, LW</author></authors></contributors><titles><title>Theory of scheduling, 1967</title><secondary-title>Addison-Wesley, Reading, Mass.[: 5] M. EISENBERG, TwO queues with changeover times, Operations Res.(2)</secondary-title></titles><periodical><full-title>Addison-Wesley, Reading, Mass.[: 5] M. EISENBERG, TwO queues with changeover times, Operations Res.(2)</full-title></periodical><pages>386-401</pages><volume>19</volume><dates><year>1971</year></dates><urls></urls></record></Cite></EndNote>[3] از یک نمادگذاری 4 تایی بصورتABCD برای مسائل زمان‌بندی استفاده نمودند. با این‌حال نمادگذاری که امروزه از آن استفاده می‌شود نخستین بار توسط گراهام و همکاران ADDIN EN.CITE <EndNote><Cite><Author>Graham</Author><Year>1979</Year><RecNum>3</RecNum><DisplayText>[4]</DisplayText><record><rec-number>3</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415115556">3</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Graham, Ronald L</author><author>Lawler, Eugene L</author><author>Lenstra, Jan Karel</author><author>Kan, AHG</author></authors></contributors><titles><title>Optimization and approximation in deterministic sequencing and scheduling: a survey</title><secondary-title>Annals of discrete Mathematics</secondary-title></titles><periodical><full-title>Annals of discrete Mathematics</full-title></periodical><pages>287-326</pages><volume>5</volume><dates><year>1979</year></dates><isbn>0167-5060</isbn><urls></urls></record></Cite></EndNote>[4] در 1979 معرفی شده است. در این شیوه، یک مسأله زمان‌بندی با یک 3 تایی α/β/γ نشان داده میشود که قسمت α محیط ماشینها را توصیف میکند و فقط شامل یک نماد است. قسمت β خصوصیات پردازش و محدودیتهای موجود را شرح می‌دهد که این قسمت میتواند شامل هیچ نماد و یا چند نماد باشد. قسمت γ تابع(های) هدفی که باید بهینه شود را توصیف میکند. لازم به ذکر است که این نمادگذاری بعدها توسط پیندو [2] به‌روز شده است. در ادامه به مقادیر مختلفی که هر کدام از اجزای این نمادگذاری می توانند داشته باشند، خواهیم پرداخت و در پایان برای روشن شدن موضوع چندین مثال معرفی خواهد شد.
حالتهای مختلف محیط ماشینهادر دنیای واقعی انواع گوناگونی از محیطهای تولیدی و خدماتی شامل تک ماشینه، ماشینهای موازی، جریان‌کارگاهی، کار کارگاهی و کارگاه باز به شرح زیر وجود دارد. نماد مرتبط با هر مشخصه در مقابل آن در داخل پرانتز آورده شده است.
محیط تک ماشینه (1): در محیط تک ماشینه همانطور که از نام آن پیداست یک ماشین وجود دارد که تعدادی کار به وسیله‌ی این ماشین پردازش می‌شوند.

شکل STYLEREF 1 s ‏1 SEQ شکل * ARABIC s 1 1: شمایی از محیط تک ماشینهمحیط جریان‌کارگاهی (Fm): دریک محیط جریان‌کارگاهی، n کار برروی m ماشین به ترتیب پردازش میشوند. در این محیط توالی پردازش کارها بر روی ماشینهای مختلف یکسان است. به عبارت دیگر، همه کارها ابتدا روی ماشین اول، سپس روی ماشین دوم و به همین ترتیب تا ماشین m ام پردازش می‌شوند. پس از اتمام پردازش یک کار روی یک ماشین، آن کار به صف پردازش ماشین بعدی می‌پیوندد. اغلب فرض میشود که تمامی صفها بر اساس قانون FCFS کار میکنند، یعنی هیچ کاری نمیتواند از کار دیگری که در صف انتظار است سبقت بگیرد. شمایی از محیط جریان‌کارگاهی، در شکل زیر نشان داده شده است. در این شکل، Mi نشان دهنده ماشینi ام کارگاه بوده و bi نیز نشان دهنده‌ی ظرفیت فضای قبل از ماشین iام است. صف کارها برای پردازش روی هر ماشین در فضای قبل از آن ماشین شکل میگیرد. ظرفیت فضای قبل از هر ماشین میتواند هر عددی از صفر تا بی‌نهایت باشد.
شکل STYLEREF 1 s ‏1 SEQ شکل * ARABIC s 1 2: شمایی از محیط جریان‌کارگاهیمحیط جریان‌کارگاهی انعطاف پذیر (FFc) : در شرایطی که در یک محیط جریان‌کارگاهی در برخی از ایستگاهها بیش از یک ماشین برای پردازش کارها وجود داشته باشد، به این محیط، محیط جریان‌کارگاهی انعطافپذیر گفته می‌شود. در این محیط، m کار تنها با شروع از ایستگاه اول پردازش میشوند و برای پردازش آنها تا ایستگاه c ام ادامه خواهد داشت. در این محیط هر کار تنها توسط یکی از ماشینهای موازی هر ایستگاه پردازش میشود. در شکل زیر شمایی از محیط جریان‌کارگاهی انعطاف پذیر، نشان داده شده است.

شکل STYLEREF 1 s ‏1 SEQ شکل * ARABIC s 1 3: شمایی از محیط جریان‌کارگاهی انعطاف پذیرمحیط کار کارگاهی (Jm): یک کارگاه با شیوه تولید کار کارگاهی از آرایش یک سری ماشین‌آلات با استفاده عام که مورد استفاده یک حرفه خاص هستند، پدید میآید. مثلا یک سری ماشین‌آلات تراش، فرز، دریل، آهنگری و ... تولید هر یک از محصولات در این شیوه با تولید محصول دیگر متفاوت است و هر یک نیاز به طی مسیر تولیدی خاص خود را دارند.
کارگاه باز (Om): در این حالت m ماشین وجود دارد و هر کار باید حداقل یک بار روی هر یک از m ماشین پردازش شود. اما زمان پردازش یک کار روی برخی از ماشینها میتواند صفر باشد. هیچ محدودیتی نیز در مورد توالی پردازش یک کار روی ماشینها وجود ندارد. به عبارت دیگر، تفاوت کارگاه باز با کار کارگاهی در این است که برخلاف کار کارگاهی، مسیر پردازش کارها روی ماشینها ثابت و از پیش تعیین شده نیست و بر اساس ماهیت تابع هدف، مسیر پردازش هر کار روی ماشینها را تعیین کند. در نتیجه مسیر پردازش کارهای مختلف میتواند متفاوت باشد.
محدودیت‌های پردازش و محیطدر محیطهای تولیدی و خدماتی، محدودیتهای متفاوتی ممکن است وجود داشته باشد که حل مسأله زمانبندی نیازمند رعایت این محدودیتها است. تعدادی از این محدودیتها به قرار زیر هستند:
زمانهای آماده‌سازی وابسته به توالی (sijk) : در برخی موارد، ماشینها پیش از شروع پردازش یک کار نیازمند آماده‌سازی هستند که این زمان آمادهسازی وابسته به کار اول (j) و کار دوم (k) است. در صورتی که زمان آماده‌سازی برای ماشینهای مختلف، متفاوت باشد، زمان آماده‌سازی وابسته به توالی با نماد sijkنمایش داده میشود که به معنی زمان آمادهسازی ماشین i ام پیش از پردازش کار k و پس از پردازش کار j است.
مسدود شدن (block): در صورتی که در یک محیط تولیدی و یا خدماتی انبارهای میانی بین دو ماشین متوالی محدود باشد، با تکمیل شدن ظرفیت انبار بین دو ماشین، پس از اتمام پردازش یک کار بر روی یک ماشین، این کار تا بیکار شدن ماشین بعد، بر روی ماشین قبلی منتظر خواهد بود. در این حالت به اصطلاح گفته میشود که ماشین اول بلوکه شده است.
عدم‌توقف (nwt) محدودیت عدم‌توقف نیز بدین معنی است که هر کار، پس از شروع پردازش بر روی اولین ماشین، بدون وقفه تا آخرین ماشین پردازش میشود. به عبارت دیگر زمان تکمیل پردازش یک کار بر روی یک ماشین برابر با زمان شروع پردازش آن بر روی ماشین بعد است.
از جمله سایر موارد در رابطه با محدودیت‌های پردازش و محیط می‌توان قطع کار (prmp) ، محدودیت حق تقدم (prec)، خانواده‌های کاری (fmls)، پردازش دسته‌ای (batch(b))، خرابی‌ها (brkdwn)، جایگشت (prmu) و باز گردش (rcrc) نام برد.
تابع هدف
تابع هدفهای مختلفی برای مسائل تعیین توالی کارها و زمان‌بندی در نظر گرفته میشوند که به دنبال بهینهسازی آنها هستیم تعدادی از پرکاربردترین تابع هدفهای مورد استفاده در مسألههای توالی عملیات به شرح زیر معرفی میشود:
کمینه کردن زمان تکمیل پردازش آخرین کار(Cmax)
کمینه کردن مجموع وزنی زمان تکمیل پردازش کارها (wjCj)
کمینه کردن بیشینه دیرکرد کارها(Lmax)
کمینه کردن مجموع وزنی زودکرد و دیرکرد کارها (+ wj''Tj wj'Ej)
کمینه کردن مجموع زمان در جریان (i=2nn+1-idi-1i+i=1nj=1mpij)
که در روابط فوق نمادهای بکاررفته به شرح زیر می‌باشند:
wj : وزن کار j که اهمیت آن را نسبت به باقی کارها در سیستم مورد بررسی نشان میدهد.
wj' : جریمه زودکرد کار j به ازای هر واحد زمان
wj'' : جریمه دیرکرد کار j به ازای هر واحد زمان
Cj : زمان تکمیل پردازش کار j بر روی ماشین آخر
Ej : مدت زمان زودکرد کار jTj : مدت زمان دیرکرد کار jPij : نمایانگر زمان پردازش کار j روی ماشین i است.
dj : زودترین موعد تحویل کار jCmax : زمان تکمیل پردازش آخرین‌کار
Lmax : بیشینه دیرکرد کارها
سلسله مراتب پیچیدگینظریه پیچیدگی محاسباتی شاخه‌ای از نظریه محاسبات، علوم‌نظری رایانه و ریاضی است که به بررسی دشواری حل مسائل به وسیله رایانه (به عبارت دقیق‌تر به صورت الگوریتمی) می‌پردازد. این نظریه بیان می‌کند کدام مسائل در زمانی قابل قبول برحسب اندازه مسئله قابل حل بوده و کدام مسائل را نمی‌توان در زمانی معقول به صورت بهینه حل نمود. معروف‌ترین کلاس‌های پیچیدگی، P و NP هستند که مساله‌ها را از نظر زمان مورد نیاز تقسیم‌بندی می‌کنند. به طور شهودی می‌توان گفت P کلاس مساله‌هایی است که الگوریتم‌های سریع برای پیدا کردن جواب آن‌ها وجود دارد. اماNP  شامل آن دسته از مساله‌هاست که ممکن است پیدا کردن جواب برای آن‌ها نیاز به زمان زیادی داشته باشد اما بررسی درستی جواب به وسیله یک الگوریتم سریع ممکن است. شاخه‌ای از مسائل NP که زمان حل آنها نمایی بوده به مسائل NP-Complete معروف هستند.
تعیین پیچیدگی مسائل توالی عملیات از جمله موضوعاتی است که در مقاله‌های متعددی به آن پرداخته شده است. تحلیل پیچیدگی این مسائل نشان می‌دهد که بسیاری از مسائل عملی در زمان‌بندی و توالی عملیات متعلق به رده مسائل NP-Complete هستند. از این‌رو نیاز است تا الگوریتم‌هایی کارا برای حل آنان بدست آورد تا جواب‌های مناسب را در زمانی قابل قبول بدست آورد.
با توجه به نمادگذاری مسائل توالی عملیات تقلیل آنها نیز از سه جنبه تابع هدف، محیط و محدودیت صورت می‌پذیرد. برای تعیین پیچیدگی هر یک از این سه موضوع از روش تقلیل استفاده می‌شود. گفته می‌شود مسئله A به مسئله B تقلیل‌پذیر است اگر هر نمونه از مسئله A را بتوان حالت خاصی از مسئله B دانست. این حالت به صورت AB نشان داده می‌شود. روشن است که مسئله A نمی‌تواند سخت‌تر از حل کردن مسئله B باشد.
در شکل 1-4 نحوه تقلیل تابع هدف‌های مختلف در مسائل توالی عملیات نشان داده شده است. به عنوان مثال ∑Cj را می‌توان حالت خاصی از ∑ wj Cj دانست که با نماد ∑Cj ∝ ∑ w jCj نشان داده می‌شود. در این شکل هر چه مسئله در رده بالاتری قرار داشته باشد پیچیدگی آن نیز بیشتر است.

شکل STYLEREF 1 s ‏1 SEQ شکل * ARABIC s 1 4: سلسله پیچیدگی تابع هدفدر شکل 1-5 چگونگی تقلیل محیط های مختلف ماشین در مسائل توالی عملیات نشان داده شده است. همانطور که در شکل مشخص است محیط تک ماشینه حات خاصی از سایر محیط‌های ماشین است؛ و Fm را می‌توان حالت خاصی از Jm دانست که با نمادFm ∝ Jm نشان داده می‌شود.همچنین مسایلی نیز وجود دارند که نمیتوان آنها را به یکدیگر تبدیل نمود. به عنوان مثال میزان پیچیدگی محیط کارگاه‌باز با سایر محیط‌ها قابل بحث کردن نمی‌باشد.

شکل STYLEREF 1 s ‏1 SEQ شکل * ARABIC s 1 5 : سلسله پیچیدگی محیط ماشیندر شکل 1-6 نحوه سلسله پیچیدگی محدودیت‌های عملیات نشان داده شده است. این شکل نشان می‌دهد که محدودیت‌های عملیات با یکدیگر قابل مقایسه نمی‌باشند و فقط می‌توان پیچیدگی یک مسئله را بعد از اعمال محدودیت با حالتی که مسئله محدودیتی ندارد مقایسه کرد.

شکل STYLEREF 1 s ‏1 SEQ شکل * ARABIC s 1 6: سلسله پیچیدگی محدودیت های عملیاتحال اگر مسئله‌ای از زمان‌بندی باشد که هر سه جزء آن تقلیل یافته حالت‌های دیگری باشد گفته می‌شود که آن مساله تقلیل یافته مساله دوم است. به عنوان مثال داریم:
1 || ∑Cj ∝1 || ∑ wj Cj∝Pm || ∑ wj Cj∝pm |prec| ∑ wj Cjدر رابطه بالا نشان داده شده است که مسئله pm |prec| ∑ wj Cj چطور به مسئله 1 || ∑Cj قابل تقلیل است. ابتدا Pm || ∑ wj Cj∝pm |prec| ∑ wj Cj زیرا با توجه به شکل 1-6 مسئله‌ای با محدودیت prec قابل تبدیل به مسئله‌ای بدون محدودیت می‌باشد. سپس نشان داده شده است که 1 || ∑ wj Cj∝Pm || ∑ wj Cj . زیرا با توجه به شکل 1-5 محیط Pm قابل به محیط تک‌ماشینه می‌باشد. در انتها نیز قابل تبدیل بودن 1 || ∑Cj ∝1 || ∑ wj Cj نشان داده شده است که با توجه به شکل 1-4 کاملا قابل توجیه می‌باشد.
راهنمای فصل‌های رسالهاین رساله شامل 5 فصل و 1 پیوست می‌باشد. در فصل 1 ابتدا مقدمه‌ای از اهمیت و ضرورت زمان‌بندی تولید و نقش جریان‌کارگاهی گفته شد سپس مسأله جریان‌کارگاهی به طور خلاصه توضیح داده شد. همچنین به نمادگذاری مسائل زمان‌بندی پرداخته شد و هر یک از قسمت‌های محیط‌های ماشین، محدودیت‌های عملیات و تابع هدف به تفصیل بیان شد. در انتها سلسله مراتب پیچیدگی مسائل مورد بررسی قرار گرفته است.
در فصل 2 به تفصیل جریان‌کارگاهی را مورد بررسی قرار دادیم. در ابتدا تعریف جریان‌کارگاهی همراه با یک مثال بیان شد. سپس به مرور ادبیات جریان‌کارگاهی پرداختیم. سپس مروری بر الگوریتم‌های ابتکاری در این حوزه انجام شد. همچنین 3 الگوریتم پایه در مسئله جریان‌کارگاهی بررسی و همراه با مثال توضیح داده شد. الگوریتم‌هایی که در این فصل عنوان شده عبارتند از: الگوریتم جانسون، الگوریتم NEH، الگوریتم اسلوپ.
فصل 3 به مسائل جریان‌کارگاهی با محدودیت عدم‌توقف پرداخته است. در ابتدا محدودیت به طور کامل تعریف و به دلایل ایجاد این محدودیت پرداختیم. سپس مروری بر پژوهش‌های انجام شده در این حوزه از ابتدا تاکنون انجام و به روش‌های حل این مسئله پرداخته شد. سپس مدل برنامه‌ریزی عدد صحیح جریان‌کارگاهی با محدودیت عدم‌توقف آورده شد. در نهایت بهترین الگوریتم موجود در ادبیات به طور کامل تشریح می‌شود.
در فصل 4 به معرفی الگوریتم‌های پیشنهادی در این رساله می‌پردازیم. در قسمت بعد به بررسی سه الگوریتم پیشنهادی که ترکیبی از الگوریتم‌های ابتکاری راجندران، الگوریتم فراابتکاری مورچگان و جست‌وجوی محلی می باشد به تفصیل بیان شده است. سپس نتایج الگوریتم و مقایسه آن با نتایج موجود آورده شد و کارایی الگوریتم‌های پیشنهادی بررسی شد.
در فصل 5 جمع‌بندی مطالب و نتایج رساله ذکر شده است. در انتهای این فصل، پیشنهادهایی مطرح شده است تا زمینه تحقیق‌های آتی محققان گردد.
در پیوست 1 تعدادی از داده‌های مسئله استفاده شده جهت اجرای الگوریتم آورده شده است.

جریان‌کارگاهی
در صنایع تولیدی و مونتاژ، هر کار می‌بایست مسیر مشخصی از عملیات را طی کند. در صورتی که این عملیات برای تمامی کارها با مسیری یکسان در بین ماشین‌هایی که پشت سر یکدیگر قرار گرفته‌اند، انجام پذیرد به آن سیستم جریان‌کارگاهی گفته می‌شود. در این فصل، مسئله جریان‌کارگاهی را تعریف کرده و سپس مروری جامع بر مقاله‌های چاپ شده در این حوزه خواهیم داشت.
مسئله جریان‌کارگاهیدر مسائل برنامه‌ریزی جریان‌کارگاهی، یک مجموعه n تایی از کارها J={J1 , J2 , …, Jn} و یک مجموعه m تایی از ماشین‌ها M={M1, M2 ,… ,Mm} وجود دارد. هر کار Jj 1<j<n ) (بایستی عملیات O1j، O2j ، ....، Omj و را به ترتیب بر روی ماشین‌هایM1 ، M2 و ... وMm. انجام دهد. عملیات Oij نیاز به زمان اجرایی pij روی ماشینMi∈M دارد. توابع هدف گوناگونی برای مسائل جریان‌کارگاهی از جمله زمان جریان کل ، زمان اتمام میانگین ، تأخیر کل، بیشینه های زودکرد و دیرکرد مورد بررسی قرار گرفته است. بیشترین تابع هدفی که در مقاله‌ها از آن استفاده می‌شود تابع هدف طولانی‌ترین زمان تکمیل یا Cmax می‌باشد. همچنین محدودیت‌های زیادی از جمله انسداد، بدون انتظار، جایگشت، زمان آماده به کار و ... در مقالات مورد بررسی قرار گرفته‌اند. بیکر ADDIN EN.CITE <EndNote><Cite><Author>Baker</Author><Year>1974</Year><RecNum>5</RecNum><DisplayText>[5]</DisplayText><record><rec-number>5</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415119025">5</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Baker, Kenneth R</author></authors></contributors><titles><title>Scheduling full-time and part-time staff to meet cyclic requirements</title><secondary-title>Operational Research Quarterly</secondary-title></titles><periodical><full-title>Operational Research Quarterly</full-title></periodical><pages>65-76</pages><dates><year>1974</year></dates><isbn>0030-3623</isbn><urls></urls></record></Cite></EndNote>[5] در 1976 در کتاب خود فرضیه‌های متعددی که برای مسائل جریان‌کارگاهی متداول بود را مطرح کرد که در این رساله نیز در نظر گرفته شده است. این فرضیه‌ها به شرح زیر است:
هر ماشین تنها یک کار را در هر زمانی انجام می‌دهد.
عملیات یک کار نمی‌تواند به طور همزمان روی چند ماشین انجام شود.
توقف کار مجاز نیست. به عنوان مثال فرایند کارi روی ماشین j نمی‌تواند دچار وقفه شود.
همه کارها مستقل هستند و در زمان صفر جهت عملیات در دسترس هستند.
زمان آماده سازی کارها روی ماشین‌ها جزئی بوده و قابل اغماض هستند.
ماشین‌ها به طور پیوسته در دسترس هستند.
در جدول 2-1 مقادیر pij مساله F3││Cmax که شامل 3 ماشین و 4 کار است آورده شده است.
جدول STYLEREF 1 s ‏2 SEQ جدول * ARABIC s 1 1: داده های مثال مسأله جریان‌کارگاهیM1M2M11 2 4 J12 6 3 J23 2 4 J38 5 1 J4اگر به عنوان نمونه ترتیب 4،3،2،1 برای پردازش کارها انتخاب شود، آنگاه زمان اتمام عملیات کار یک بر روی هر سه ماشین، Cij، به سادگی قابل محاسبه است:
جدول STYLEREF 1 s ‏2 SEQ جدول * ARABIC s 1 2: گام اول محاسبه Cmax برای مثال جریان‌کارگاهیC3,jC2,jC1,j7=1+6 6=2+4 4 J1برای تعیین زمان خاتمه عملیات کار 2 بر روی ماشین یک، به دلیل اینکه بلافاصله پس از اتمام عملیات کار یک بر روی ماشین اول، این ماشین در اختیار است پس زمان شروع به عملیات همان زمان اتمام کار یک بر روی ماشین اول است. اما محاسبه زمان شروع عملیات کار دو بر روی ماشین دوم کمی متفاوت است و باید بزرگترین زمان از بین زمان‌های اتمام همین کار بر روی ماشین قبل و زمان اتمام کار قبلی بر روی همین ماشین، به عنوان زمان شروع عملیات برگزیده شود. این روند برای ماشین‌های بعدی نیز ادامه خواهد داشت.
جدول STYLEREF 1 s ‏2 SEQ جدول * ARABIC s 1 3: گام اول محاسبه Cmax برای مثال جریان‌کارگاهیC3,jC2,jC1,jj7 6 4 J1Max{13,7} +2 = 15 Max{7,6} + 6= 13 4+3=7 J2به همین ترتیب برای کار سه و چهار می توان مقادیر Cij را بدست آورد. در شکل 2-4 برای ترتیب داده شده نمودارگانت ترسیم شده است.

شکل STYLEREF 1 s ‏2 SEQ شکل * ARABIC s 1 1: نمودار گانت مثال جریان‌کارگاهیهمانگونه که در نمودار فوق دیده می شود، تابع هدف که عبارت است از زمان تکمیل آخرین کار (makespan,Cmax)، برای ترتیب داده شده 29 می‌باشد.
مرور ادبیات جریان‌کارگاهیاولین مقاله در زمینه FS توسط آقای جانسون ADDIN EN.CITE <EndNote><Cite><Author>Johnson</Author><Year>1954</Year><RecNum>1</RecNum><DisplayText>[1]</DisplayText><record><rec-number>1</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415113996">1</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Johnson, Selmer Martin</author></authors></contributors><titles><title>Optimal two‐and three‐stage production schedules with setup times included</title><secondary-title>Naval research logistics quarterly</secondary-title></titles><periodical><full-title>Naval research logistics quarterly</full-title></periodical><pages>61-68</pages><volume>1</volume><number>1</number><dates><year>1954</year></dates><isbn>1931-9193</isbn><urls></urls></record></Cite></EndNote>[1] در 1954 منتشر شد. از آن زمان تاکنون مقاله‌های متعددی در این زمینه در مجله‌های معتبر علمی به چاپ رسیده است. با وجود اینکه مفهوم مدل زمان‌بندی توسط آقای جانسون معرفی شده است، لیکن عنوان FS برای نخستین بار در 1965 در مقاله ایگنال و اسچارج ADDIN EN.CITE <EndNote><Cite><Author>Ignall</Author><Year>1965</Year><RecNum>6</RecNum><DisplayText>[6]</DisplayText><record><rec-number>6</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134066">6</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Ignall, Edward</author><author>Schrage, Linus</author></authors></contributors><titles><title>Application of the branch and bound technique to some flow-shop scheduling problems</title><secondary-title>Operations research</secondary-title></titles><periodical><full-title>Operations research</full-title></periodical><pages>400-412</pages><volume>13</volume><number>3</number><dates><year>1965</year></dates><isbn>0030-364X</isbn><urls></urls></record></Cite></EndNote>[6] به کار گرفته شد. در 1996 هال و سریکاندراجا ADDIN EN.CITE <EndNote><Cite><Author>Hall</Author><Year>1996</Year><RecNum>7</RecNum><DisplayText>[7]</DisplayText><record><rec-number>7</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134166">7</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Hall, Nicholas G</author><author>Sriskandarajah, Chelliah</author></authors></contributors><titles><title>A survey of machine scheduling problems with blocking and no-wait in process</title><secondary-title>Operations research</secondary-title></titles><periodical><full-title>Operations research</full-title></periodical><pages>510-525</pages><volume>44</volume><number>3</number><dates><year>1996</year></dates><isbn>0030-364X</isbn><urls></urls></record></Cite></EndNote>[7] ثابت نمودند که مساله جریان‌کارگاهی برای بیش از دوماشین یک مساله NP-hard است. در سال 2006 گوپتا و همکاران ADDIN EN.CITE <EndNote><Cite><Author>Gupta</Author><Year>2006</Year><RecNum>8</RecNum><DisplayText>[8]</DisplayText><record><rec-number>8</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134216">8</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Gupta, Jatinder ND</author><author>Stafford Jr, Edward F</author></authors></contributors><titles><title>Flowshop scheduling research after five decades</title><secondary-title>European Journal of Operational Research</secondary-title></titles><periodical><full-title>European Journal of Operational Research</full-title></periodical><pages>699-711</pages><volume>169</volume><number>3</number><dates><year>2006</year></dates><isbn>0377-2217</isbn><urls></urls></record></Cite></EndNote>[8] در مقاله خود مقاله‌های چاپ شده در این حوزه را به 5 دوره تقسیم کردند. بیشتر تحقیقات دوره اول مرتبط با مسائل ریاضی همان مدل اولیه آقای جانسون است و بیشتر روی 2 یا 3 ماشین بحث می‌نماید.
در دوره دوم بین 1965 تا 1974 شاهد ایجاد راه حل‌های متفاوت از یک سو و همچنین در نظر گرفتن توابع غیر از زمان کل از سوی دیگر بود. در این دوره موضوع عمده مقاله‌ها، ارائه روش‌های بهینه برای حل مسائل مختلف بود.
در دوره سوم به علت پیچدگی روش‌های بهینه، روش‌های ابتکاری متعددی برای حل این نوع مسائل ابداع گردند. در این دهه بود که مدل‌سازی احتمالی این نوع مسائل نیز مطرح گردید.
در دوره چهارم ( 1985 تا1994) مسائل زمان‌بندی ترکیبی مطرح گردید. در این دهه از انواع روش‌های فراابتکاری استفاده شده است. به علت استفاده از فرضیات مرتبط با زمان‌های مستقل و وابسته، هوش مصنوعی و سیستم‌های پشتیبان تصمیم‌گیری دوره چهارم را می‌توان پر فروغ‌ترین دوره تحقیقات مسأله زمان‌بندی جریان‌کارگاهی دانست.
در دوره آخر که تاکنون ادامه دارد شاهد تنوع مسأله، توابع هدف و ابداع روش‌های متفاوت بسیاری بوده‌ایم و پیوندها با دیگر مسائل برنامه ریزی تولید، در این دوره انجام گردیده است.
الگوریتم‌های ابتکاریپیچیدگی حاصل از افزایش تعداد ماشین‌ها و کارها و عدم وجود روشهای دقیق برای آنها، محققان را به سمت استفاده و گسترش الگوریتم‌های ابتکاری سوق داده است. این موضوع مهم‌ترین دلیل وجود تعداد بالای الگوریتم‌های ابتکاری در ادبیات این موضوع می‌باشد. در ادامه مروری جامع بر الگوریتم‌های ابتکاری در حوزه جریان‌کارگاهی خواهیم داشت و خواهیم دید که الگوریتم‌های ابتکاری در این حوزه را می‌توان به‌طور کلی در سه الگوریتم جانسون، پالمر و NEH تقسیم نمود و در انتها با این سه الگوریتم آشنا می‌شویم.
مروری بر الگوریتم‌های ابتکاری در حوزه جریان‌کارگاهیالگوریتم جانسون ADDIN EN.CITE <EndNote><Cite><Author>Johnson</Author><Year>1954</Year><RecNum>1</RecNum><DisplayText>[1]</DisplayText><record><rec-number>1</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415113996">1</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Johnson, Selmer Martin</author></authors></contributors><titles><title>Optimal two‐and three‐stage production schedules with setup times included</title><secondary-title>Naval research logistics quarterly</secondary-title></titles><periodical><full-title>Naval research logistics quarterly</full-title></periodical><pages>61-68</pages><volume>1</volume><number>1</number><dates><year>1954</year></dates><isbn>1931-9193</isbn><urls></urls></record></Cite></EndNote>[1] اولین الگوریتم شناخته شده برای مسأله جریان‌کارگاهی می‌باشد. با استفاده از این الگوریتم مقدار بهینه در حالتی که تنها دو ماشین وجود دارد، به دست آورده می‌شود. پیچیدگی این الگوریتم O(nlogn) می‌باشد.
الگوریتم جانسون را می‌توان برای حالتی که در آن تعداد ماشین‌ها بیش از دو است تعمیم داد. در این زمینه الگوریتم‌های متعددی معرفی شده است. دودک و تئوتون ADDIN EN.CITE <EndNote><Cite><Author>Dudek</Author><Year>1964</Year><RecNum>9</RecNum><DisplayText>[9]</DisplayText><record><rec-number>9</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134275">9</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Dudek, Richard A</author><author>Teuton Jr, Ottis Foy</author></authors></contributors><titles><title>Development of m-stage decision rule for scheduling n jobs through m machines</title><secondary-title>Operations Research</secondary-title></titles><periodical><full-title>Operations research</full-title></periodical><pages>471-497</pages><volume>12</volume><number>3</number><dates><year>1964</year></dates><isbn>0030-364X</isbn><urls></urls></record></Cite></EndNote>[9] برپایه الگوریتم جانسون، قانونی m مرحله‌ای را استفاده کردند که مجموع زمان اتلاف روی آخرین ماشین در صورتی که پردازش هر کار از رویکرد جانسون انجام شود را کمینه می‌کرد. کمپل و همکاران ADDIN EN.CITE <EndNote><Cite><Author>Campbell</Author><Year>1970</Year><RecNum>10</RecNum><DisplayText>[10]</DisplayText><record><rec-number>10</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134306">10</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Campbell, Herbert G</author><author>Dudek, Richard A</author><author>Smith, Milton L</author></authors></contributors><titles><title>A heuristic algorithm for the n job, m machine sequencing problem</title><secondary-title>Management science</secondary-title></titles><periodical><full-title>Management science</full-title></periodical><pages>B-630-B-637</pages><volume>16</volume><number>10</number><dates><year>1970</year></dates><isbn>0025-1909</isbn><urls></urls></record></Cite></EndNote>[10] الگوریتمی را پیشنهاد نمودند که نیازمند m-1 مرحله محاسبات بود. در این الگوریتم هر m ماشین واقعی در هر مرحله به دو گروه ماشین مجازی افراز شده و سپس طبق الگوریتم جانسون محاسبات صورت می‌پذیرفت. پیچیدگی محاسباتی این الگوریتم O(m2n+mnlogn) می‌باشد. گوپتا ADDIN EN.CITE <EndNote><Cite><Author>Gupta</Author><Year>1972</Year><RecNum>11</RecNum><DisplayText>[11]</DisplayText><record><rec-number>11</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134359">11</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Gupta, Jatinder ND</author></authors></contributors><titles><title>Heuristic algorithms for multistage flowshop scheduling problem</title><secondary-title>AIIE Transactions</secondary-title></titles><periodical><full-title>AIIE Transactions</full-title></periodical><pages>11-18</pages><volume>4</volume><number>1</number><dates><year>1972</year></dates><isbn>0569-5554</isbn><urls></urls></record></Cite></EndNote>[11] یک الگوریتم ابتکاری برای کمینه کردن زمان اتلاف به نام MINIT و دو الگوریتم ابتکاری برای کمینه‌کردن طولانی‌ترین زمان تکمیل به نام‌های MICOT و MINIMAX ارائه نمود. مقایسه نتایج بدست آمده نشان‌دهنده بهبود کیفیت و کاهش زمان حل نسبت به الگوریتم پیشنهادی کمپل بود.
در الگوریتم ابتکاری که توسط پالمر ADDIN EN.CITE <EndNote><Cite><Author>Palmer</Author><Year>1965</Year><RecNum>12</RecNum><DisplayText>[12]</DisplayText><record><rec-number>12</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134415">12</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Palmer, DS</author></authors></contributors><titles><title>Sequencing jobs through a multi-stage process in the minimum total time--a quick method of obtaining a near optimum</title><secondary-title>OR</secondary-title></titles><periodical><full-title>OR</full-title></periodical><pages>101-107</pages><dates><year>1965</year></dates><isbn>1473-2858</isbn><urls></urls></record></Cite></EndNote>[12] پیشنهاد شده است، برای هر کار شاخصی معین می‌گردد و کارها براساس این شاخص زمان‌بندی می‌شوند. شاخص تعریف شده توسط پالمر “slope index” نام دارد. پیچیدگی محاسبات این الگوریتم O(nm+nlogn) می‌باشد. بونی و گوندری ADDIN EN.CITE <EndNote><Cite><Author>Bonney</Author><Year>1976</Year><RecNum>13</RecNum><DisplayText>[13]</DisplayText><record><rec-number>13</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134453">13</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Bonney, MC</author><author>Gundry, SW</author></authors></contributors><titles><title>Solutions to the constrained flowshop sequencing problem</title><secondary-title>Operational Research Quarterly</secondary-title></titles><periodical><full-title>Operational Research Quarterly</full-title></periodical><pages>869-883</pages><dates><year>1976</year></dates><isbn>0030-3623</isbn><urls></urls></record></Cite></EndNote>[13] مجموع زمان‌های پردازش هر کار بر روی تمام ماشین‌ها را به عنوان معیار هرکار درنظر گرفته‌اند. هوندال و راجگوپال ADDIN EN.CITE <EndNote><Cite><Author>Hundal</Author><Year>1988</Year><RecNum>14</RecNum><DisplayText>[14]</DisplayText><record><rec-number>14</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134502">14</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Hundal, Tejpal S</author><author>Rajgopal, Jayant</author></authors></contributors><titles><title>An extension of Palmer&apos;s heuristic for the flow shop scheduling problem</title><secondary-title>The International Journal Of Production Research</secondary-title></titles><periodical><full-title>The International Journal Of Production Research</full-title></periodical><pages>1119-1124</pages><volume>26</volume><number>6</number><dates><year>1988</year></dates><isbn>0020-7543</isbn><urls></urls></record></Cite></EndNote>[14] با معرفی دو شاخص جدید و استفاده از شاخص پالمر سه زمان‌بندی برای هر مسئله معرفی نمودند. پیچیدگی محاسبات این الگوریتم، مشابه با الگوریتم پالمر می‌باشد. داننبریج ADDIN EN.CITE <EndNote><Cite><Author>Dannenbring</Author><Year>1977</Year><RecNum>15</RecNum><DisplayText>[15]</DisplayText><record><rec-number>15</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134560">15</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Dannenbring, David G</author></authors></contributors><titles><title>An evaluation of flow shop sequencing heuristics</title><secondary-title>Management science</secondary-title></titles><periodical><full-title>Management science</full-title></periodical><pages>1174-1182</pages><volume>23</volume><number>11</number><dates><year>1977</year></dates><isbn>0025-1909</isbn><urls></urls></record></Cite></EndNote>[15] الگوریتمی ابتکاری براساس الگوریتم‌های ابتکاری جانسون و پالمر ارائه نمود. در این الگوریتم، مشابه با الگوریتم کمپل، ماشین‌ها به صورت ماشین‌های مجازی دوتایی فرض شده و سپس با استفاده از مقدارهای به‌دست آمده، شاخصی جهت هر کار تعیین می‌گردد.
نواز و همکاران ADDIN EN.CITE <EndNote><Cite><Author>Nawaz</Author><Year>1983</Year><RecNum>16</RecNum><DisplayText>[16]</DisplayText><record><rec-number>16</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134630">16</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Nawaz, Muhammad</author><author>Enscore Jr, E Emory</author><author>Ham, Inyong</author></authors></contributors><titles><title>A heuristic algorithm for the&lt; i&gt; m&lt;/i&gt;-machine,&lt; i&gt; n&lt;/i&gt;-job flow-shop sequencing problem</title><secondary-title>Omega</secondary-title></titles><periodical><full-title>Omega</full-title></periodical><pages>91-95</pages><volume>11</volume><number>1</number><dates><year>1983</year></dates><isbn>0305-0483</isbn><urls></urls></record></Cite></EndNote>[16] الگوریتم ابتکاری NEH را ارائه کردند که این الگوریتم بهترین الگوریتم ارائه شده برای مسائل جریان‌کارگاهی می‌باشد. در این الگوریتم اولویت به کارهایی داده می‌شود که زمان پردازش بیشتری دارند. پیچیدگی محاسبات این الگوریتم O(n3m) می‌باشد. راجندران ADDIN EN.CITE <EndNote><Cite><Author>Rajendran</Author><Year>1993</Year><RecNum>17</RecNum><DisplayText>[17]</DisplayText><record><rec-number>17</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134721">17</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Rajendran, Chandrasekharan</author></authors></contributors><titles><title>Heuristic algorithm for scheduling in a flowshop to minimize total flowtime</title><secondary-title>International Journal of Production Economics</secondary-title></titles><periodical><full-title>International Journal of Production Economics</full-title></periodical><pages>65-73</pages><volume>29</volume><number>1</number><dates><year>1993</year></dates><isbn>0925-5273</isbn><urls></urls></record></Cite></EndNote>[17] الگوریتم ابتکاری به نام Raj ارائه نمود که بسیار شبیه الگوریتم NEH است که تنها تفاوت آن، در شرط اولیه برای بدست آوردن توالی اولیه می‌باشد. وی برای هر کار، مجموع زمان پردازش وزن‌داری را معرفی می‌کند.
سارین و لفوکا ADDIN EN.CITE <EndNote><Cite><Author>Sarin</Author><Year>1993</Year><RecNum>18</RecNum><DisplayText>[18]</DisplayText><record><rec-number>18</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134773">18</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Sarin, S</author><author>Lefoka, M</author></authors></contributors><titles><title>Scheduling heuristic for the&lt; i&gt; n&lt;/i&gt;-job&lt; i&gt; m&lt;/i&gt;-machine flow shop</title><secondary-title>Omega</secondary-title></titles><periodical><full-title>Omega</full-title></periodical><pages>229-234</pages><volume>21</volume><number>2</number><dates><year>1993</year></dates><isbn>0305-0483</isbn><urls></urls></record></Cite></EndNote>[18] الگوریتمی ابتکاری در نظر گرفتند که ایده‌ی آن کمینه کردن زمان اتلاف روی آخرین ماشین بود. این ایده باعث کاهش طولانی‌ترین زمان تکمیل می‌شود. در این الگوریتم، اولویت با کارهایی است که کمترین مجموع زمان پردازش روی همه‌ی ماشین‌ها را دارا هستند. مقایسه نتایج بدست آمده از این الگوریتم نسبت به الگوریتم NEH در مسائلی با بیش از150کار بهتر است.
راجندران و زیگلر ADDIN EN.CITE <EndNote><Cite><Author>Rajendran</Author><Year>1997</Year><RecNum>19</RecNum><DisplayText>[19]</DisplayText><record><rec-number>19</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134840">19</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Rajendran, Chandrasekharan</author><author>Ziegler, Hans</author></authors></contributors><titles><title>An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs</title><secondary-title>European Journal of Operational Research</secondary-title></titles><periodical><full-title>European Journal of Operational Research</full-title></periodical><pages>129-138</pages><volume>103</volume><number>1</number><dates><year>1997</year></dates><isbn>0377-2217</isbn><urls></urls></record></Cite></EndNote>[19] الگوریتم ابتکاری ارائه نمودند که در آن در ابتدا به هر کار وزنی تخصیص داده می‌شد. سپس برای هر کار مجموع زمان پردازش وزن‌دار محاسبه شده و بر اساس مقادیر بدست آمده دو توالی نزولی و صعودی تعیین می‌گردد. از بین دو توالی، هر کدام که مقدار تابع هدف بهتری داشته باشد، به عنوان توالی اولیه انتخاب و سپس از الگوریتم NEH استفاده می‌گردد.
وو و ییم ADDIN EN.CITE <EndNote><Cite><Author>Woo</Author><Year>1998</Year><RecNum>20</RecNum><DisplayText>[20]</DisplayText><record><rec-number>20</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134891">20</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Woo, Hoon-Shik</author><author>Yim, Dong-Soon</author></authors></contributors><titles><title>A heuristic algorithm for mean flowtime objective in flowshop scheduling</title><secondary-title>Computers &amp; Operations Research</secondary-title></titles><periodical><full-title>Computers &amp; Operations Research</full-title></periodical><pages>175-182</pages><volume>25</volume><number>3</number><dates><year>1998</year></dates><isbn>0305-0548</isbn><urls></urls></record></Cite></EndNote>[20] الگوریتمی ابتکاری مشابه با الگوریتم Raj ارائه نمودند. در الگوریتم ارائه شده نیازی به توالی اولیه نیست. در ابتدا مجموع زمان پردازش کارها محاسبه شده و سپس همانند الگوریتم NEH و Raj توالی بهینه بدست خواهد آمد. نتایج نشان می‌دهد که این الگوریتم برای تابع هدف کمینه‌کردن مجموع زمان جریان از الگوریتم های NEH، Raj و کمپل بهتر عمل می‌کند. پیچیدگی محاسبات این الگوریتم O(n4m) می‌باشد.
حمید داوودپور ADDIN EN.CITE <EndNote><Cite><Author>Pour</Author><Year>2001</Year><RecNum>21</RecNum><DisplayText>[21]</DisplayText><record><rec-number>21</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134927">21</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Pour, Hamid Davoud</author></authors></contributors><titles><title>A new heuristic for the n-job, m-machine flow-shop problem</title><secondary-title>Production Planning &amp; Control</secondary-title></titles><periodical><full-title>Production Planning &amp; Control</full-title></periodical><pages>648-653</pages><volume>12</volume><number>7</number><dates><year>2001</year></dates><isbn>0953-7287</isbn><urls></urls></record></Cite></EndNote>[21] الگوریتمی مشابه با الگوریتم NEH با هدف کمینه‌کردن حداکثر دیرکرد ارائه نمود. وی الگوریتم ارائه شده را روی 2000 مسأله مختلف با اندازه‌های مختلف تست نمود. مقایسه جواب‌های بدست آمده با الگوریتم های NEH، کمپل و پالمر نشان داد که این الگوریتم برای مسائلی با تعداد ماشین‌های بزرگ جواب‌های خوبی را بدست می‌آورد.
فرامین ADDIN EN.CITE <EndNote><Cite><Author>Framinan</Author><Year>2003</Year><RecNum>22</RecNum><DisplayText>[22]</DisplayText><record><rec-number>22</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415135003">22</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Framinan, JM</author><author>Leisten, R</author></authors></contributors><titles><title>An efficient constructive heuristic for flowtime minimisation in permutation flow shops</title><secondary-title>Omega</secondary-title></titles><periodical><full-title>Omega</full-title></periodical><pages>311-317</pages><volume>31</volume><number>4</number><dates><year>2003</year></dates><isbn>0305-0483</isbn><urls></urls></record></Cite></EndNote>[22] نشان داد که الگوریتم NEH که فقط برای مسائلی با تابع هدف طولانی‌ترین زمان تکمیل بکار می‌رفت، اگر برای مسائلی با تابع هدف کمینه‌کردن مجموع زمان جریان نیز به کار رود، بهترین جواب‌ها را در زمان‌های کمتر بدست می‌دهد. همچنین نشان می‌دهد که اگر الگوریتم NEH برای توالی اولیه خود کارها را بر اساس مجموع زمان پردازش هر کار و به ترتیب صعودی قرار دهد یعنی اولویت با کارهایی باشد که مجموع زمان پردازش کمتری دارند، جواب‌های بهتری نسبت به NEH اصلی بدست می‌آید.
الگوریتمی که توسط لاها و سارین ADDIN EN.CITE <EndNote><Cite><Author>Laha</Author><Year>2009</Year><RecNum>23</RecNum><DisplayText>[23]</DisplayText><record><rec-number>23</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415135060">23</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Laha, Dipak</author><author>Sarin, Subhash C</author></authors></contributors><titles><title>A heuristic to minimize total flow time in permutation flow shop</title><secondary-title>Omega</secondary-title></titles><periodical><full-title>Omega</full-title></periodical><pages>734-739</pages><volume>37</volume><number>3</number><dates><year>2009</year></dates><isbn>0305-0483</isbn><urls></urls></record></Cite></EndNote>[23] برای مسأله‌ای با تابع هدف کمینه‌کردن مجموع زمان جریان بر پایه الگوریتم ابتکاری ارائه شده بر پایه الگوریتم ابتکاری فرامین ADDIN EN.CITE <EndNote><Cite><Author>Framinan</Author><Year>2003</Year><RecNum>22</RecNum><DisplayText>[22]</DisplayText><record><rec-number>22</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415135003">22</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Framinan, JM</author><author>Leisten, R</author></authors></contributors><titles><title>An efficient constructive heuristic for flowtime minimisation in permutation flow shops</title><secondary-title>Omega</secondary-title></titles><periodical><full-title>Omega</full-title></periodical><pages>311-317</pages><volume>31</volume><number>4</number><dates><year>2003</year></dates><isbn>0305-0483</isbn><urls></urls></record></Cite></EndNote>[22] است. تفاوت آن با الگوریتم فرامین آن است که پس از تعیین دو کار اول، کارهای بعد می توانند در هر کجای ترتیب بدست آمده قرار گیرند.
الگوریتم جانسونالگوریتم جانسون اولین الگوریتم ارائه شده برای مسائل جریان‌کارگاهی است، که یک جواب بهینه برای F2| | Cmax به دست می‌آورد. این الگوریتم دارای پیچیدگی (O(nlogn)) می‌باشد. جانسون مسئله کارگاه جریان دو‌ماشینه را با تابع هدف حداقل‌کردن طولانی‌ترین زمان تکمیل بررسی کرد و با ارائه الگوریتمی کارا توانست جواب بهینه این مسئله را با فرضیات پایه، به سادگی محاسبه نماید.
گام‌های الگوریتم جانسون را می‌توان به شرح زیر بیان نمود:
گام اول کارها را به دو گروه N1 و N2تقسیم می‌کنیم بگونه‌ای که در گروهN1 کارهایی قرار گیرند که برای آنهاpi1<pi2 و در گروهN2 کارهایی که برای آنهاpi2<pi1 برقرار است. کارهایی که برای آنها pi2=pi1 است می‌توانند در هر دو گروه جای گیرند.
گام دوم کارهای موجود در گروه N1 در ابتدا و به ترتیب صعودی قرار می‌گیرند (SPT).
گام سوم کارهای موجود در گروهN2 پس از کارهای گروه N1 و به ترتیب نزولی قرار می‌گیرند (LPT).
گام چهارم توالی بهینه با کنار هم قرار دادن مجموعه‌ی N1 و به‌دنبال آن مجموعه‌ی N2 بدست می‌آید.
مثال: با الگوریتم جانسون مسأله جریان‌کارگاهی زیر را حل‌کنید.
8 7 6 5 4 3 2 1 jobi5 7 3 6 7 1 2 5 t1j1 2 7 6 5 2 6 2 t2jگام اول: با توجه به گام 1 دو مجموعه زیر تشکیل می‌شود:
N1={2,3,6} و N2={1,4,5,7,8}گام دوم : مجموعه‌ی N1 را مرتب می‌کنیم :
Job i :3 2 6t1j :1 2 3 گام سوم : مجموعه‌ی N2 را مرتب می‌کنیم :
Job i :5 4 7 1 8t2j :6 5 2 2 1 گام چهارم : توالی بهینه، {3,2,6,5,4,7,1,8} می‌باشد.
الگوریتم پالمردر الگوریتم ابتکاری که توسط پالمر [41] پیشنهاد شده است، برای هر کار شاخصی معین می‌گردد و کارها براساس این شاخص زمان‌بندی می‌شوند. شاخص تعریف شده توسط پالمر “slope index” نام دارد. مراحل الگوریتم پالمر به‌صورت زیر می‌باشد.
گام اول: برای هر کار ضریب اسلوپ بر اساس رابطه زیر محاسبه می‌شود.
(2-1) Aj=-i=1m(m-(2i-1)pijگام دو: کارها را مطابق ضریب اسلوپ آنها، به صورت نزولی مرتب می‌کنیم.
ایده این الگوریتم بسیار ساده است در واقع هدف این است که کارهایی با زمان پردازش کم در ماشین‌های اول و با زمان پردازش بالا در ماشین‌های آخر هر چه زودتر انجام شوند. همچنین کارهایی با زمان پردازش بالا در ماشین‌های اول و با زمان پردازش کم در ماشین‌های آخر هرچه دیرتر پردازش شوند.
1118870330835p3jp2jp1jJj4 8 1 1
5 4 2 2
8 2 6 3
2 9 3 4
00p3jp2jp1jJj4 8 1 1
5 4 2 2
8 2 6 3
2 9 3 4
مثال: با روش پالمر مسأله جریان‌کارگاهی زیر را حل کنید.
برای هر کار بر اساس رابطه (2-1) ضریب اسلوپ محاسبه می‌شود.
s1= -2*1+0*8+2*4=6s2= -2*2+0*4+2*5=6s3= -2*6+0*2+2*8=4s4=-2*3+0*9+2*2=-2و در نتیجه توالی بدست آمده به صورت زیر می‌باشد :
J1,J2, J3,J4 و J2,J1, J3,J4الگوریتم NEH
این الگوریتم یکی از شناخته شده‌ترین الگوریتم‌های ابتکاری برای مسائل زمان‌بندی جریان‌کارگاهی می‌باشد و اولین بار توسط نواز و همکاران ADDIN EN.CITE <EndNote><Cite><Author>Nawaz</Author><Year>1983</Year><RecNum>16</RecNum><DisplayText>[16]</DisplayText><record><rec-number>16</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134630">16</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Nawaz, Muhammad</author><author>Enscore Jr, E Emory</author><author>Ham, Inyong</author></authors></contributors><titles><title>A heuristic algorithm for the&lt; i&gt; m&lt;/i&gt;-machine,&lt; i&gt; n&lt;/i&gt;-job flow-shop sequencing problem</title><secondary-title>Omega</secondary-title></titles><periodical><full-title>Omega</full-title></periodical><pages>91-95</pages><volume>11</volume><number>1</number><dates><year>1983</year></dates><isbn>0305-0483</isbn><urls></urls></record></Cite></EndNote>[16] ارائه شده است. این الگوریتم علاوه بر سادگی محاسباتی، کارامد نیز است. در هر مرحله از این الگوریتم، کاری که بیشترین مجموع زمان پردازش را داشته و تاکنون زمان‌بندی نشده است را انتخاب می‌کنیم. سپس توالی کارفعلی را در بین سایر کارهای انتخاب شده به گونه‌ای تعیین می‌کنیم که جواب ناتمام فعلی بهترین زمان اتمام را پیدا کند. مراحل این الگوریتم را می توان به شرح زیر بیان نمود:
گام اول: برای هر کار pj را بر اساس رابطه زیر محاسبه کنید.
(2-2) pj=i=1mpijگام دوم: کارها را مطابق pj آنها به صورت نزولی مرتب ‌کنید.
گام سوم: دو کار اول لیست گام دو را انتخاب کنید و زمان تابع هدف هر دو حالت ممکن توالی را حساب کنید وتوالی بهتر را انتخاب و در گام‌های بعدی نیز آن را تغییر ندهید. i را مساوی 3 قرار دهید.
گام چهارم: i امین کار لیست گام دو را انتخاب و در iمکان ممکن بین کارهای ترتیب ناتمام فعلی قرار دهید به گونه‌ای که ترتیب نسبی کارهای قرارداده شده حفظ شده و ترتیب با تابع هدف کمینه را انتخاب کنید.
گام پنجم: اگرn=i بود الگوریتم را خاتمه دهید در غیر اینصورت i=i+1 و به گام چهارم برگردید.
مثال : با الگوریتم NEH مسأله جریان‌کارگاهی زیر را حل‌کنید.
pij4 3 2 1 Job
162 40 52 45 25 1
136 66 22 41 7 2
150 21 33 55 41 3
158 48 24 12 74 4
146 52 72 15 7 5
80 32 22 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 بدست می‌آید.
جمع‌بندیدر این فصل ابتدا با مسئله جریان‌کارگاهی و سپس با اهمیت آن در علم توالی عملیات و زمان‌بندی آشنا شدیم. در ادامه مروری بر ادبیات این مسئله انجام شد و سپس به مرور روش‌های ابتکاری حل مسئله جریان‌کارگاهی پرداختیم . در این فصل همچنین نشان دادیم که ایده اکثر الگوریتم‌های ابتکاری مسئله جریان‌کارگاهی بر پایه سه الگوریتم جانسون، پالمر و NEH می‌باشد. و در انتها سه الگوریتم ابتکاری مهم مسئله جریان‌کارگاهی را با مثال تشریح کردیم.
جریان‌کارگاهی با محدودیت عدم‌توقف
در این فصل، ابتدا تعریفی جامع بر مسئله جریان‌کارگاهی با محدودیت عدم‌توقف خواهیم داشت. و خواهیم دید که این محدودیت در دنیای واقعی چه اثرگذاری دارد. در ادامه مروری بر پژوهش‌های انجام شده در حوزه مسئلهی مورد بررسی ، الگوریتم‌های ابتکاری و الگوریتم‌های فراابتکاری خواهیم داشت. در گام بعد، به بررسی مدل ریاضی مسئله و اثبات NP-hard آن می‌پردازیم.
جریان‌کارگاهی با محدودیت عدم‌توقف6604004451985شکل STYLEREF 1 s ‏3 SEQ شکل * ARABIC s 1 1: شمایی از مسئله جریان کارگاهی با محدودیت عدم‌توقف0شکل STYLEREF 1 s ‏3 SEQ شکل * ARABIC s 1 1: شمایی از مسئله جریان کارگاهی با محدودیت عدم‌توقف890270290893500مسأله مورد بررسی در این رساله، تعیین توالی و زمان‌بندی در یک محیط جریان‌کارگاهی با محدودیت عدم‌توقف است که به اختصار NWFS خوانده می‌شود. منظور از عدم‌توقف این است که هر کار پس از شروع پردازش بر روی اولین ماشین، به صورت پیوسته بر روی دیگر ماشین‌ها تا آخرین ماشین پردازش می‌شود و هیچ توقفی بین پایان عملیات بر روی یک ماشین و شروع عملیات بر روی ماشین بعدی وجود نداشته باشد. به بیان دیگر، زمان تکمیل پردازش یک کار بر روی یک ماشین دقیقا برابر با زمان شروع پردازش آن کار بر روی ماشین بعدی است. از این‌رو زمان شروع یک کار بر روی ماشین اول بایستی به نوعی زمان‌بندی شود تا این محدودیت رعایت گردد.
دلایل عمده به وجود آمدن محدودیت عدم‌توقف را به می‌توان به شرح زیر مطرح کرد ADDIN EN.CITE <EndNote><Cite><Author>Hall</Author><Year>1996</Year><RecNum>7</RecNum><DisplayText>[7]</DisplayText><record><rec-number>7</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134166">7</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Hall, Nicholas G</author><author>Sriskandarajah, Chelliah</author></authors></contributors><titles><title>A survey of machine scheduling problems with blocking and no-wait in process</title><secondary-title>Operations research</secondary-title></titles><periodical><full-title>Operations research</full-title></periodical><pages>510-525</pages><volume>44</volume><number>3</number><dates><year>1996</year></dates><isbn>0030-364X</isbn><urls></urls></record></Cite></EndNote>[7]:
فناوری تولید:
در برخی از فرایند‌ها، برخی از مشخصه‌های مواد از نظیر دما یا چسبناکی این محدودیت را ایجاب می‌کند که عملیات متوالی بر روی ماشین‌ها بدون وقفه انجام شود. به عنوان نمونه این شرایط در فرایند تولید فولاد هنگامی که فولاد ذوب شده و مسیرهایی را به منظور قالب‌گیری، گرم‌کردن مجدد، خیساندن، نورد اولیه و... طی می‌کند، اتفاق می‌افتد. همچنین در صنایع پلاستیک و دارو‌سازی، تعدادی از فرایندها باید بدون وقفه و به صورت متوالی انجام شوند. در صنایع غذایی، فرایند قوطی‌ریزی مواد غذایی، باید دقیقا پس از آماده شدن مواد غذایی انجام شود تا مواد غذایی سالم بمانند. در صنایع تولیدی مدرن از جمله تولید ‌به ‌هنگام و سیستم‌های تولیدی انعطاف‌پذیر نیز محدودیت عدم‌توقف دیده می‌شود.
کمبود و یا عدم وجود انبارهای میانی بین ماشین‌های متوالی:
دلیل دوم برای به‌وجود آمدن محدودیت عدم‌توقف، کمبود انبارهای میانی بین ماشین‌ها و یا ایستگاه‌ها میباشد.
در این مسأله فرض می‌شود که n کار در یک محیط جریان‌کارگاهی با m ماشین، پردازش می‌شوند. با توجه به ویژگی‌ مسئله، ترتیب پردازش کارها بر روی ماشین‌ها یکسان می‌باشد. هدف از بررسی و حل این مسأله یافتن بهترین توالی پردازش کارها بر روی ماشین‌ها به گونه‌ای است که زمان اتمام پردازش آخرین کار (Makespan) کمینه شود.
نماد مسأله مورد بررسی با استفاده از نمادهای مسائل ADDIN EN.CITE <EndNote><Cite><Author>Pinedo</Author><Year>2012</Year><RecNum>2</RecNum><DisplayText>[2]</DisplayText><record><rec-number>2</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415114269">2</key></foreign-keys><ref-type name="Book">6</ref-type><contributors><authors><author>Pinedo, Michael L</author></authors></contributors><titles><title>Scheduling: theory, algorithms, and sys--s</title></titles><dates><year>2012</year></dates><publisher>Springer</publisher><isbn>1461423619</isbn><urls></urls></record></Cite></EndNote>[2] به صورت Fm/nwt/Cmax می‌باشد. در این نماد، قسمت اول که با Fm نشان داده شده است، نشان‌دهنده محیط جریان‌کارگاهی با m ماشین است. نماد nwt در بخش دوم محدودیت عدم‌توقف را نشان می‌دهد و بخش سوم نیز بیان‌کننده تابع هدف مورد بررسی که طولانی‌ترین زمان تکمیل است می‌باشد.
فرضیه‌های در نظر گرفته شده در این مسأله به شرح زیر است:
n کار برای پردازش بر روی m ماشین در دست است؛
پردازش هر کار بر روی هر ماشین تا اتمام آن بدون وقفه صورت می‌پذیرد؛
زمان شروع یک کار برروی یک ماشین برابر با زمان اتمام آن بر روی ماشین قبلی است؛
زمان پردازش کارها بر روی ماشین‌ها قطعی و از قبل مشخص است؛
کلیه کارها در زمان صفر در دسترس است.
هال و سریکاندراجا ADDIN EN.CITE <EndNote><Cite><Author>Hall</Author><Year>1996</Year><RecNum>7</RecNum><DisplayText>[7]</DisplayText><record><rec-number>7</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415134166">7</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Hall, Nicholas G</author><author>Sriskandarajah, Chelliah</author></authors></contributors><titles><title>A survey of machine scheduling problems with blocking and no-wait in process</title><secondary-title>Operations research</secondary-title></titles><periodical><full-title>Operations research</full-title></periodical><pages>510-525</pages><volume>44</volume><number>3</number><dates><year>1996</year></dates><isbn>0030-364X</isbn><urls></urls></record></Cite></EndNote>[7] خلاصه‌ای از پژوهش‌های انجام شده تا سال 1996 در حوزه مسائل زمان‌بندی با محدودیت عدم‌توقف در محیط‌های جریان‌کارگاهی، کارکارگاهی و کارگاه باز را ارائه داده‌اند. آنها علاوه بر معرفی چندین روش ابتکاری برای حل مسأله، به بررسی پیچیدگی حالت‌های خاصی از این گروه مسائل پرداخته‌اند.
مرور ادبیات جریان‌کارگاهی با محدودیت ‌عدم‌توقفسهنی و چو ADDIN EN.CITE <EndNote><Cite><Author>Sahni</Author><Year>1979</Year><RecNum>24</RecNum><DisplayText>[24]</DisplayText><record><rec-number>24</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415135191">24</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Sahni, Sartaj</author><author>Cho, Yookun</author></authors></contributors><titles><title>Complexity of scheduling shops with no wait in process</title><secondary-title>Mathematics of Operations Research</secondary-title></titles><periodical><full-title>Mathematics of Operations Research</full-title></periodical><pages>448-457</pages><volume>4</volume><number>4</number><dates><year>1979</year></dates><isbn>0364-765X</isbn><urls></urls></record></Cite></EndNote>[24] مسأله زمانبندی با محدودیت عدم‌توقف را در محیطهای جریان‌کارگاهی، کار کارگاهی و کارگاه باز با تابع هدف کمینه کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و نشان میدهند که این گروه مسائل از نوع NP-hard هستند. همچنین در این تحقیقات نشان داده می‌شود که مسائل کارکارگاهی و کارگاه باز در حالت دو ماشینه حتی هنگامی که هیچ کاری با زمان پردازش صفر بر روی یکی از ماشین ها وجود نداشته باشد NP-hard هستند.
پانوالکر و وولام ADDIN EN.CITE <EndNote><Cite><Author>Panwalkar</Author><Year>1980</Year><RecNum>25</RecNum><DisplayText>[25]</DisplayText><record><rec-number>25</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415135275">25</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Panwalkar, SS</author><author>Woollam, CR</author></authors></contributors><titles><title>Ordered flow shop problems with no in-process waiting: Further results</title><secondary-title>Journal of the Operational Research Society</secondary-title></titles><periodical><full-title>Journal of the Operational Research Society</full-title></periodical><pages>1039-1043</pages><dates><year>1980</year></dates><isbn>0160-5682</isbn><urls></urls></record></Cite></EndNote>[25] حالت خاصی از مسأله NWFS را با تابع هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و قضیه‌هایی را در مورد مقدار بهینه تابع هدف مسأله مورد بحث مطرح کرده و اثبات میکنند.
مون و همکارای ADDIN EN.CITE <EndNote><Cite><Author>Moon</Author><Year>1996</Year><RecNum>26</RecNum><DisplayText>[26]</DisplayText><record><rec-number>26</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415135354">26</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Moon, Sungdeuk</author><author>Park, Sunwon</author><author>Lee, Won Kook</author></authors></contributors><titles><title>New MILP models for scheduling of multiproduct batch plants under zero-wait policy</title><secondary-title>Industrial &amp; engineering chemistry research</secondary-title></titles><periodical><full-title>Industrial &amp; engineering chemistry research</full-title></periodical><pages>3458-3469</pages><volume>35</volume><number>10</number><dates><year>1996</year></dates><isbn>0888-5885</isbn><urls></urls></record></Cite></EndNote>[26] مسأله زمان‌بندی جریان‌کارگاهی با محدودیت عدم‌توقف را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و مدل ریاضی خطی– عدد صحیح را برای حل آن ارائه میدهند. در مسأله مورد نظر، زمانهای حمل و نقل و زمانهای آمادهسازی وابسته به توالی ماشینها در نظر گرفته میشود. همچنین به منظور بررسی عملکرد مدل ریاضی این مسئله ، نمونههایی از مسأله مورد بررسی حل شده و نتایج آن با مدلهای پیشین مقایسه میشود.
آیدوسان ADDIN EN.CITE <EndNote><Cite><Author>Aldowaisan</Author><Year>2001</Year><RecNum>27</RecNum><DisplayText>[27]</DisplayText><record><rec-number>27</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415135508">27</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Aldowaisan, Tariq</author></authors></contributors><titles><title>A new heuristic and dominance relations for no-wait flowshops with setups</title><secondary-title>Computers &amp; Operations Research</secondary-title></titles><periodical><full-title>Computers &amp; Operations Research</full-title></periodical><pages>563-584</pages><volume>28</volume><number>6</number><dates><year>2001</year></dates><isbn>0305-0548</isbn><urls></urls></record></Cite></EndNote>[27] مسأله NWFS را در حالت دو ماشینه و با فرض زمانهای آمادهسازی ماشینها با هدف کمینه کردن مجموع زمان تکمیل پردازش کارها مطرح کرده و الگوریتم ابتکاری برای حل آن را ارائه می‌دهد. در این روش حد پایینی برای مسأله مورد بحث توسعه داده شده و از آن در روش شاخه و کران که به منظور ارزیابی الگوریتم ابتکاری ارائه شده، استفاده میشود.
لین و همکاران ADDIN EN.CITE <EndNote><Cite><Author>Lin</Author><Year>2001</Year><RecNum>45</RecNum><DisplayText>[28]</DisplayText><record><rec-number>45</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415137087">45</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Lin, Bertrand MT</author><author>Cheng, TC</author></authors></contributors><titles><title>Batch scheduling in the no-wait two-machine flowshop to minimize the makespan</title><secondary-title>Computers &amp; Operations Research</secondary-title></titles><periodical><full-title>Computers &amp; Operations Research</full-title></periodical><pages>613-624</pages><volume>28</volume><number>7</number><dates><year>2001</year></dates><isbn>0305-0548</isbn><urls></urls></record></Cite></EndNote>[28] مسأله NWFS در حالت دو ماشینه را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار، مورد بررسی قرار میدهند. آنها فرض گروههای کاری و زمانهای آمادهسازی ماشین‌ها قبل از شروع پردازش یک گروه از کارها را نیز در نظر گرفته و پیچیدگی مسأله مورد بحث را بررسی میکنند.
دیلیپان ADDIN EN.CITE <EndNote><Cite><Author>Dileepan</Author><Year>2004</Year><RecNum>29</RecNum><DisplayText>[29]</DisplayText><record><rec-number>29</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415135872">29</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Dileepan, Parthasarati</author></authors></contributors><titles><title>A note on minimizing maximum lateness in a two-machine no-wait flowshop</title><secondary-title>Computers &amp; Operations Research</secondary-title></titles><periodical><full-title>Computers &amp; Operations Research</full-title></periodical><pages>2111-2115</pages><volume>31</volume><number>12</number><dates><year>2004</year></dates><isbn>0305-0548</isbn><urls></urls></record></Cite></EndNote>[29] مسأله NWFS در حالت دو ماشینه را در حالتی که تابع هدف وابسته به زمان تحویل بوده را با هدف کمینه کردن بیشینه دیرکرد کارها مورد بررسی قرار میدهد و قضایای تئوری برای آن را مطرح کرده و اثبات میکند. او همچنین حالتهای خاصی از مسأله مذکور را مورد بررسی قرار می‌دهد.
سو و لی ADDIN EN.CITE <EndNote><Cite><Author>Su</Author><Year>2008</Year><RecNum>30</RecNum><DisplayText>[30]</DisplayText><record><rec-number>30</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415135943">30</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Su, Ling-Huey</author><author>Lee, Yuan-Yu</author></authors></contributors><titles><title>The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time</title><secondary-title>Computers &amp; Operations Research</secondary-title></titles><periodical><full-title>Computers &amp; Operations Research</full-title></periodical><pages>2952-2963</pages><volume>35</volume><number>9</number><dates><year>2008</year></dates><isbn>0305-0548</isbn><urls></urls></record></Cite></EndNote>[30] مسأله زمان‌بندی جریان‌کارگاهی با محدودیت عدم‌توقف در حالت دو ماشینه را با هدف کمینه‌کردن مجموع زمان تکمیل پردازش کارها مورد بررسی قرار میدهند. آنها در حل مسئله خود، فرض زمانهای آماده‌سازی ماشینها با استفاده از یک خدمت‌دهنده به منظور آمادهسازی ماشینها در نظر میگیرند. بدین معنی که آماده‌سازی دو ماشین به صورت همزمان غیرممکن است، زیرا تنها یک خدمت‌دهنده برای این منظور وجود دارد. آنها برای بدست آوردن جواب بهینه (حداکثر 65 کار) از روش شاخه و کران استفاده میکنند.
هنگ و همکاران ADDIN EN.CITE <EndNote><Cite><Author>Huang</Author><Year>2009</Year><RecNum>31</RecNum><DisplayText>[31]</DisplayText><record><rec-number>31</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415136174">31</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Huang, Rong-Hwa</author><author>Yang, Chang-Lin</author><author>Huang, Yau-Chi</author></authors></contributors><titles><title>No-wait two-stage multiprocessor flow shop scheduling with unit setup</title><secondary-title>The International Journal of Advanced Manufacturing Technology</secondary-title></titles><periodical><full-title>The International Journal of Advanced Manufacturing Technology</full-title></periodical><pages>921-927</pages><volume>44</volume><number>9-10</number><dates><year>2009</year></dates><isbn>0268-3768</isbn><urls></urls></record></Cite></EndNote>[31] مسأله NWFS انعطاف پذیر دومرحلهای را با هدف کمینه‌کردن مجموع زمان تکمیل پردازش کارها و با فرض زمانهای آماده‌سازی ماشینها مورد بررسی قرار میدهند. آنها یک مدل برنامه ریزی خطی- عدد صحیح برای مسأله موردنظر توسعه میدهند.
ژاو و تانگ ADDIN EN.CITE <EndNote><Cite><Author>Zhao</Author><Year>2011</Year><RecNum>32</RecNum><DisplayText>[32]</DisplayText><record><rec-number>32</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415136265">32</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Zhao, Chuanli</author><author>Tang, Hengyong</author></authors></contributors><titles><title>A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints</title><secondary-title>Optimization Letters</secondary-title></titles><periodical><full-title>Optimization Letters</full-title></periodical><pages>183-190</pages><volume>5</volume><number>1</number><dates><year>2011</year></dates><isbn>1862-4472</isbn><urls></urls></record></Cite></EndNote>[32] مسأله NWFS در حالت دو ماشینه را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار و با فرض زمان خرابی و تعمیر ماشینها مورد بررسی قرار میدهند. آنها زمان پردازش کارها را تابعی از زمان شروع کارها در نظر میگیرند. همچنین فرض زمان خرابی و تعمیر ماشینها را تنها برای یک ماشین در نظر گرفته و قضیههایی را به صورت تئوری برای این مسأله مطرح و اثبات میکنند.
جنابی و همکاران ADDIN EN.CITE <EndNote><Cite><Author>Jenabi</Author><Year>2010</Year><RecNum>33</RecNum><DisplayText>[33]</DisplayText><record><rec-number>33</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415136360">33</key></foreign-keys><ref-type name="Conference Proceedings">10</ref-type><contributors><authors><author>Jenabi, Masoud</author><author>Naderi, Bahman</author><author>Ghomi, SMT Fa--i</author></authors></contributors><titles><title>A bi-objective case of no-wait flowshops</title><secondary-title>Bio-Inspired Computing: Theories and Applications (BIC-TA), 2010 IEEE Fifth International Conference on</secondary-title></titles><pages>1048-1056</pages><dates><year>2010</year></dates><publisher>IEEE</publisher><isbn>1424464374</isbn><urls></urls></record></Cite></EndNote>[33] مسأله NWFS را با هدف کمینه کردن همزمان دو تابع هدف زمان پردازش آخرین کار و مجموع دیرکرد کارها بررسی میکنند. آنها دو مدل ریاضی برنامه ریزی خطی- عدد صحیح برای حل نمونههای کوچک مسأله ارائه میدهند و از رویکرد تصمیمگیری چند معیاره برای حل مدل ریاضی مذکور استفاده میکنند.
آیدیلک و علی‌اله‌وردی ADDIN EN.CITE <EndNote><Cite><Author>Aydilek</Author><Year>2012</Year><RecNum>34</RecNum><DisplayText>[34]</DisplayText><record><rec-number>34</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415136450">34</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Aydilek, Harun</author><author>Allahverdi, Ali</author></authors></contributors><titles><title>Heuristics for no-wait flowshops with makespan subject to mean completion time</title><secondary-title>Applied Mathematics and Computation</secondary-title></titles><periodical><full-title>Applied Mathematics and Computation</full-title></periodical><pages>351-359</pages><volume>219</volume><number>1</number><dates><year>2012</year></dates><isbn>0096-3003</isbn><urls></urls></record></Cite></EndNote>[34] به مسأله حداقل‌سازی زمان کل پردازش توالی با در نظر گرفتن عدم‌توقف تولید بین ماشین‌آلات مختلف پرداختند. آنها همچنین فرض کردند که موعد‌تحویل هر محصول دارای حد بالای مفروضی است. آنها 5 الگوریتم HA، SA ، mSA، HH1 و HH2 را برای حل مساله ارائه نمودند.
سلماسی و عرب‌عامری ADDIN EN.CITE <EndNote><Cite><Author>Arabameri</Author><Year>2013</Year><RecNum>35</RecNum><DisplayText>[35]</DisplayText><record><rec-number>35</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415136511">35</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Arabameri, Sedighe</author><author>Salmasi, Nasser</author></authors></contributors><titles><title>Minimization of weighted earliness and tardiness for no-wait sequence-dependent setup times flowshop scheduling problem</title><secondary-title>Computers &amp; Industrial Engineering</secondary-title></titles><periodical><full-title>Computers &amp; Industrial Engineering</full-title></periodical><pages>902-916</pages><volume>64</volume><number>4</number><dates><year>2013</year></dates><isbn>0360-8352</isbn><urls></urls></record></Cite></EndNote>[35] به بررسی مسائل زمان‌بندی جریان‌کارگاهی با محدودیت عدم‌توقف با هدف کمینه‌کردن زودکرد و دیرکرد با استفاده از چند الگوریتم ابتکاری پرداختند و الگوریتم‌های کارا را برای مسائلی در ابعاد کوچک، متوسط و بزرگ مشخص کردند.
لیو و همکارانش ADDIN EN.CITE <EndNote><Cite><Author>Liu</Author><Year>2013</Year><RecNum>36</RecNum><DisplayText>[36]</DisplayText><record><rec-number>36</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415136557">36</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Liu, Gengcheng</author><author>Song, Shiji</author><author>Wu, Cheng</author></authors></contributors><titles><title>Some heuristics for no-wait flowshops with total tardiness criterion</title><secondary-title>Computers &amp; Operations Research</secondary-title></titles><periodical><full-title>Computers &amp; Operations Research</full-title></periodical><pages>521-525</pages><volume>40</volume><number>2</number><dates><year>2013</year></dates><isbn>0305-0548</isbn><urls></urls></record></Cite></EndNote>[36] به مقایسه الگوریتم‌های MNEH، SPT ، EDD و سه الگوریتم ابتکاری دیگر برای مسئله زمان‌بندی FS با محدودیت عدم‌توقف با هدف حداقل‌کردن دیرکرد پرادختهاند و نتایج، نشان‌دهنده‌ی کاراتر و بهتر بودن الگوریتم MNEH نسبت به پنج الگوریتم دیگر است.
دونالد ‌داوندرا و همکارانش ADDIN EN.CITE <EndNote><Cite><Author>Davendra</Author><Year>2013</Year><RecNum>37</RecNum><DisplayText>[37]</DisplayText><record><rec-number>37</rec-number><foreign-keys><key app="EN" db-id="pfpxvfffwv0xdze0ef6xd2el5se5vzerr205" timestamp="1415136601">37</key></foreign-keys><ref-type name="Journal Article">17</ref-type><contributors><authors><author>Davendra, Donald</author><author>Zelinka, Ivan</author><author>Bialic-Davendra, Magdalena</author><author>Senkerik, Roman</author><author>Jasek, Roman</author></authors></contributors><titles><title>Discrete self-organising migrating algorithm for flow-shop scheduling with no-wait makespan</title><secondary-title>Mathematical and Computer Modelling</secondary-title></titles><periodical><full-title>Mathematical and Computer Modelling</full-title></periodical><pages>100-110</pages><volume>57</volume><number>1</number><dates><year>2013</year></dates><isbn>0895-7177</isbn><urls></urls></record></Cite></EndNote>[37] در مطالعه خود به مسئله حداقل‌سازی طولانی‌ترین زمان تکمیل با در نظر گرفتن فرض عدم‌توقف تولید بین ماشین‌آلات مختلف پرداختند. آنها الگوریتم‌های ابتکاری F&V و DPSOVND را برای حل مسئله با الگوریتم DSOMA مقایسه نمودند که نتایج حاصل از کار آنها برتری الگوریتم DSOMA نسبت به دو الگوریتم دیگر را نشان می‌دهد.
مدل ریاضی عدد صحیح جریان‌کارگاهی با محدودیت عدم‌توقفمسائل عمومی جریان‌کارگاهی را می‌توان به صورت مدلهای برنامه‌ریزی عدد صحیح فرموله کرد. در ادامه مدلی را که برای مسائل جریان‌کارگاهی با محدودیت عدم‌توقف ارائه شده است، توضیح می‌دهیم. پارامترها و متغیرهای استفاده شده در این مدل به شرح زیر می‌باشند.
پارامترها:
N: تعداد کارهایی که باید پردازش شود.

Related posts:

این نوشته در فرستاده شده.