پژوهش - ارشددانلود

کلیه حقوق مادی و معنوی مرتبت بر نتایج پایان نامه متعلق به دانشگاه و انتشار نتایج نیز تابع مقرارت دانشگاهی است و با موافقت استاد راهنما به شرح زیر، بلامانع است:
بهره‌برداری از این پایان‌نامه برای همگان بلامانع است.
بهره‌برداری از این پایان‌نامه با اخذ مجوز از استاد راهنما، بلامانع است.
بهره‌برداری از این پایان‌نامه تا تاریخ .................................... ممنوع است.
نام استاد راهنما:
تاریخ:
امضا:

تقدیم به
پدر و مادر عزیزم

سپاسگزاری:
سپاس خدا را که هر چه هست از اوست و اینکه نیازم را بی‌پاسخ نگذارد و مرا یاری نمود تا قسمتی از عمر خود را در راه تحصیل علم و دانش سپری نمایم.
سپاس خدا را که خانواده را کانون امن جهت تربیت و پیشرفت انسان، و تکیه‌گاهی مطمئن برای فرزندان قرار داد.
سپاس خدای را که همواره استادانی دلسوز و فرزانه را راهنمایم قرار داد تا در راه دراز و بی‌پایان تحصیل علم، تسکینی بر عطش سیری ناپذیرم باشند.
بر خود لازم می‌دانم که از تمامی عزیزانی که در مراحل مختلف انجام این تحقیق مرا یاری نمودند، تشکر و قدردانی نمایم.
با تشکر از یاوران همیشگی‌ام
پدر و مادرم
و
برادرانم
با تشکر از مشوقان واقعی راه علم:
استاد ارجمند جناب آقای دکتر کاظمی،
استاد گرانقدر جناب آقای دکتر خرمی‌زاده
استاد گرامی جناب آقای دکتر اکبری
چکیده
حل مسأله زمان‌بندی جریان‌کارگاهی با فرض عدم‌توقف‌ به روش ابتکاری
نگارش:
وحید ریاحی
در سال‌های اخیر ارائه الگوریتم‌های کارا برای زمان‌بندی جریان‌کارگاهی مورد توجه مدیران واحدهای تولیدی قرارگرفته است. مسأله زمان‌بندی جریان‌کارگاهی با محدودیت عدم‌توقف و با هدف کمینه‌سازی طولانی‌ترین زمان تکمیل، یک مسأله NP-سخت است. به همین دلیل در تحقیقات اخیر الگوریتم‌های فراابتکاری زیادی برای حل آن ارائه شده است. در این پایان نامه سه الگوریتم فراابتکاری برپایه الگوریتم مورچگان برای حل این مساله ارائه شده است. تفاوت الگوریتم‌های ارائه شده در نحوه استفاده از الگوریتم جستجوی محلی می‌باشد. در الگوریتم های ارائه شده، الگوریتم‌های جابجایی، الحاقی، شبیه‌سازی تبرید و الگوریتم اصلاح شده بر اساس الگوریتم‌های جابجایی و الحاقی برای حل مسئله پیشنهاد شده است. الگوریتم‌های پیشنهادی بر روی مسائل نمونه که در ادبیات این موضوع وجود دارد، پیاده سازی شده است. مقایسه الگوریتم‌های ارائه شده با یکدیگر نشان‌دهنده کارا بودن الگوریتم‌ اصلاح شده می‌باشد. همچنین مقایسه نتایج بدست امده با نتایج به چاپ رسیده در سال‌های اخیر نشان‌دهنده دقت و رقابت‌پذیری بالای الگوریتم‌های پیشنهادی نسبت به سایر الگوریتم‌های موجود برای حل مساله مورد بحث، می‌باشد.
کلمات کلیدی: جریان‌کارگاهی، محدودیت عدم‌توقف، الگوریتم مورچگان، الگوریتم جستجوی محلی

فهرست مطالب
عنوان صفحه
TOC o "1-3" h z u فصل 1 مقدمه PAGEREF _Toc407019130 h 11-1 توالی عملیات و زمان‌بندی PAGEREF _Toc407019131 h 21-2 آشنایی با مفاهیم زمان‌بندی PAGEREF _Toc407019132 h 31-2-1 نمادگذاری PAGEREF _Toc407019133 h 41-2-2 سلسله مراتب پیچیدگی PAGEREF _Toc407019134 h 91-3 راهنمای فصل‌های رساله PAGEREF _Toc407019135 h 12فصل 2 جریان‌کارگاهی PAGEREF _Toc407019136 h 142-1 مسئله جریان‌کارگاهی PAGEREF _Toc407019137 h 152-2 مرور ادبیات جریان‌کارگاهی PAGEREF _Toc407019138 h 172-3 الگوریتم‌های ابتکاری PAGEREF _Toc407019139 h 182-3-1 مروری بر الگوریتم‌های ابتکاری در حوزه جریان‌کارگاهی PAGEREF _Toc407019140 h 192-3-2 الگوریتم جانسون PAGEREF _Toc407019141 h 212-3-3 الگوریتم پالمر PAGEREF _Toc407019142 h 232-3-4 الگوریتم NEH PAGEREF _Toc407019143 h 242-4 جمع بندی PAGEREF _Toc407019144 h 26فصل 3 جریان‌کارگاهی با محدودیت عدم‌توقف PAGEREF _Toc407019145 h 273-1 جریان‌کارگاهی با محدودیت عدم‌توقف PAGEREF _Toc407019146 h 283-2 مرور ادبیات جریان‌کارگاهی با محدودیت ‌عدم‌توقف PAGEREF _Toc407019147 h 303-3 مدل ریاضی عدد صحیح جریان‌کارگاهی با محدودیت عدم‌توقف PAGEREF _Toc407019148 h 333-4 مروری بر الگوریتم‌های ابتکاری مسئله جریان‌کارگاهی با محدودیت عدم‌توقف PAGEREF _Toc407019149 h 353-5 مروری بر الگوریتم‌های فراابتکاری مسئله جریان‌کارگاهی با محدودیت عدم‌توقف PAGEREF _Toc407019150 h 393-6 تشریحی بر بهترین الگوریتم در ادبیات موضوع PAGEREF _Toc407019151 h 423-7 جمع بندی PAGEREF _Toc407019152 h 44فصل 4 الگوریتم و روش حل پیشنهادی PAGEREF _Toc407019153 h 454-1 الگوریتم فراابتکاری مورچگان PAGEREF _Toc407019154 h 464-2 بکارگیری الگوریتم مورچگان در حل مسائل جریان‌کارگاهی PAGEREF _Toc407019155 h 474-3 الگوریتم پیشنهادی مورچگان PAGEREF _Toc407019156 h 474-3-1 مقداردهی اولیه فرومون PAGEREF _Toc407019157 h 484-3-2 قاعده تغییر حالت PAGEREF _Toc407019158 h 484-3-3 قاعده به‌هنگام کردن محلی PAGEREF _Toc407019159 h 494-3-4 قاعده به‌هنگام کردن نهایی PAGEREF _Toc407019160 h 504-3-5 به هنگام کردن فرومون‌های بیشینه و کمینه PAGEREF _Toc407019161 h 504-3-6 جستجوی محلی PAGEREF _Toc407019162 h 514-3-7 الگوریتم شبیه سازی تبرید PAGEREF _Toc407019163 h 534-3-8 الگوریتم مورچگان اصلاح شده PAGEREF _Toc407019164 h 554-4 نتایج پیاده‌سازی الگوریتم پیشنهادی PAGEREF _Toc407019165 h 584-4-1 مسائل نمونه PAGEREF _Toc407019166 h 584-4-2 پارامترهای الگوریتم PAGEREF _Toc407019167 h 594-4-3 نتایج PAGEREF _Toc407019168 h 59فصل 5 جمع‌بندی و پیشنهاد تحقیقات آتی PAGEREF _Toc407019169 h 685-1 نتایج بدست آمده PAGEREF _Toc407019170 h 695-2 زمینه‌های تحقیقاتی PAGEREF _Toc407019171 h 70مراجع PAGEREF _Toc407019172 h 71پیوست 1: داده‌های مسائل نمونه PAGEREF _Toc407019173 h 78واژه نامه فارسی به انگلیسی PAGEREF _Toc407019174 h 80واژه نامه انگلیسی به فارسی PAGEREF _Toc407019175 h 82

فهرست جدول‌ها
عنوان صفحه
TOC h z c "جدول" جدول ‏21: داده های مثال مسأله جریان‌کارگاهی PAGEREF _Toc409738064 h 16جدول ‏22: گام اول محاسبه Cmax برای مثال جریان‌کارگاهی PAGEREF _Toc409738065 h 16جدول ‏23: گام اول محاسبه Cmax برای مثال جریان‌کارگاهی PAGEREF _Toc409738066 h 17جدول ‏41: اطلاعات مسائل نمونه PAGEREF _Toc409738067 h 58جدول ‏42: مقدار پارامترهای الگوریتم پیشنهادی PAGEREF _Toc409738068 h 59جدول ‏43: مقایسه سه الگوریتم پیشنهادی و ارائه شده PAGEREF _Toc409738069 h 60جدول ‏44 مقایسه سه الگوریتم پیشنهادی و ارائه شده بر اساس تعداد جواب‌های تولید شده PAGEREF _Toc409738070 h 61جدول ‏45: نتایج 7 الگوریتم‌ بر پایه جست و جوی محلی برای مسائل نمونه کارلیر PAGEREF _Toc409738071 h 65جدول ‏46: نتایج الگوریتم‌ ارائه شده با بهترین الگوریتم یافت شده در ادبیات مسائل نمونه کارلیر PAGEREF _Toc409738072 h 65جدول ‏47: نتایج الگوریتم‌های بر پایه جستجوی محلی برای مسائل بزرگ و متوسط PAGEREF _Toc409738073 h 66جدول ‏48: مقایسه الگوریتم اصلاح شده با یهترین الگوریتم‌های موجود در ادبیات PAGEREF _Toc409738074 h 67

فهرست شکل‌ها
عنوان صفحه
TOC h z c "شکل" شکل ‏11: شمایی از محیط تک ماشینه PAGEREF _Toc409019543 h 5شکل ‏12: شمایی از محیط جریان‌کارگاهی PAGEREF _Toc409019544 h 5شکل ‏13: شمایی از محیط جریان‌کارگاهی انعطاف پذیر PAGEREF _Toc409019545 h 6شکل ‏14: سلسله پیچیدگی تابع هدف PAGEREF _Toc409019546 h 10شکل ‏15 : سلسله پیچیدگی محیط ماشین PAGEREF _Toc409019547 h 11شکل ‏16: سلسله پیچیدگی محدودیت های عملیات PAGEREF _Toc409019548 h 11شکل ‏21: نمودار گانت مثال جریان‌کارگاهی PAGEREF _Toc409019549 h 17شکل ‏31: شمایی از مسئله جریان کارگاهی با محدودیت عدم‌توقف PAGEREF _Toc409019550 h 28شکل ‏41: شبه کد الگوریتم مورچگان اولیه PAGEREF _Toc409019551 h 52شکل ‏42: شبه کد الگوریتم شبیه‌سازی تبرید PAGEREF _Toc409019552 h 55شکل ‏43: شبه کد الگوریتم جستجوی محلی اصلاح شده PAGEREF _Toc409019553 h 56شکل ‏44: شبه کد الگوریتم مورچگان اصلاح شده PAGEREF _Toc409019554 h 57شکل ‏45: درصد بهبود برای الگوریتم‌های ارائه شده PAGEREF _Toc409019555 h 62شکل ‏46: مقایسه نتایج الگوریتم اصلاح شده با الگوریتم DPSOVND برای مسائل ریورز PAGEREF _Toc409019556 h 64

فهرست کلمات اختصاری
عبارت کامل مخفف
Ant Colony optimization : ACO
Ant Colony Sys-- : ACS
Batching : Batch
Blocking : Block
Breakdown : Brkdwn
First Come First Servised : FCFS
Flexible Flowshop : FFc
job Family : FMLs
Flowshop Scheduling : FS
Longest Processing Time : LPT
Mix-Integer Programing : MIP
No-Wiat Flowshop Scheduling : NWFS
Precint : Prec
Preemption : Prmp
Permutation : Prmu
Particle Swarm Optimization : PSO
Reciculation : Rcrc
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

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *