کلمات کلیدی: جریان‌کارگاهی، محدودیت عدم‌توقف، الگوریتم مورچگان، الگوریتم جستجوی محلیفهرست مطالب فصل 1 مقدمه11-1 توالی عملیات و زمانبندی21-2 آشنایی با مفاهیم زمانبندی31-2-1 نمادگذاری41-2-2 سلسله مراتب پیچیدگی91-3 راهنمای فصل‌های رساله13فصل 2 جریان‌کارگاهی152-1 مسئله جریان‌کارگاهی162-2 مرور ادبیات جریان‌کارگاهی182-3الگوریتم‌های ابتکاری192-3-1 مروری بر الگوریتم‌های ابتکاری در حوزه جریان‌کارگاهی202-3-2 الگوریتم جانسون222-3-3 الگوریتم پالمر242-3-4 الگوریتم NEH252-4 جمع بندی27فصل 3 جریان‌کارگاهی با محدودیت عدم‌توقف283-1 جریان‌کارگاهی با محدودیت عدم‌توقف293-2 مرور ادبیات جریان‌کارگاهی با محدودیت عدم‌توقف313-3 مدل ریاضی عدد صحیح جریان‌کارگاهی با محدودیت عدم‌توقف343-4 مروری بر الگوریتم‌های ابتکاری مسئله جریان‌کارگاهی با محدودیت عدم‌توقف363-5 مروری بر الگوریتم‌های فراابتکاری مسئله جریان‌کارگاهی با محدودیت عدم‌توقف403-6تشریحیبر بهترین الگوریتم در ادبیات موضوع433-7 جمع بندی45فصل 4 الگوریتم و روش حل پیشنهادی464-1 الگوریتم فراابتکاری مورچگان474-2بکارگیری الگوریتم مورچگان در حل مسائل جریان‌کارگاهی484-3الگوریتمپیشنهادی مورچگان484-3-1 مقداردهی اولیه فرومون494-3-2 قاعده تغییر حالت494-3-3 قاعده به‌هنگام کردن محلی504-3-4 قاعده به‌هنگام کردن نهایی514-3-5 به هنگام کردن فرومون‌های بیشینه و کمینه514-3-6 جستجوی محلی524-3-7 الگوریتم شبیه سازی تبرید544-3-8 الگوریتم مورچگان اصلاح شده564-4 نتایج پیاده‌سازی الگوریتم پیشنهادی594-4-1 مسائل نمونه594-4-2 پارامترهای الگوریتم604-4-3 نتایج 60فصل 5 جمع‌بندی و پیشنهاد تحقیقات آتی695-1 نتایج بدست آمده705-2 زمینه‌های تحقیقاتی71مراجع72پیوست 1: داده‌های مسائل نمونه79واژه نامه فارسی به انگلیسی81واژه نامه انگلیسی به فارسی83 فهرست جدول‌ها عنوان صفحه جدول 2‑1: داده های مثال مسأله جریان‌کارگاهی17جدول 2‑2: گام اول محاسبه Cmax برای مثال جریان‌کارگاهی17جدول 2‑3: گام اول محاسبه Cmax برای مثال جریان‌کارگاهی18جدول 4‑1: اطلاعات مسائل نمونه59جدول 4‑2: مقدار پارامترهای الگوریتم پیشنهادی60جدول 4‑3: مقایسه سه الگوریتم پیشنهادی و ارائه شده61جدول 4‑4 مقایسه سه الگوریتم پیشنهادی و ارائه شده بر اساس تعداد جواب‌های تولید شده62جدول 4‑5: نتایج 7 الگوریتم بر پایه جست و جوی محلی برای مسائل نمونه کارلیر66جدول 4‑6: نتایج الگوریتم ارائه شده با بهترین الگوریتم یافت شده در ادبیات مسائل نمونه کارلیر66جدول 4‑7: نتایج الگوریتم‌های بر پایه جستجوی محلی برای مسائل بزرگ و متوسط67جدول 4‑8: مقایسه الگوریتم اصلاح شده با یهترین الگوریتم‌های موجود در ادبیات68 فهرست شکل‌ها عنوان صفحه شکل 1‑1: شمایی از محیط تک ماشینه5شکل 1‑2: شمایی از محیط جریان‌کارگاهی5شکل 1‑3: شمایی از محیط جریان‌کارگاهی انعطاف پذیر6شکل 1‑4: سلسله پیچیدگی تابع هدف11شکل 1‑5 : سلسله پیچیدگی محیط ماشین11شکل 1‑6: سلسله پیچیدگی محدودیت های عملیات12شکل 2‑1:نمودار گانت مثال جریان‌کارگاهی18شکل 3‑1: شمایی از مسئله جریان کارگاهی با محدودیت عدم‌توقف29شکل 4‑1:شبه کد الگوریتم مورچگان اولیه53شکل 4‑2: شبه کد الگوریتم شبیه‌سازی تبرید56شکل 4‑3: شبه کد الگوریتم جستجوی محلی اصلاح شده57شکل 4‑4: شبه کد الگوریتم مورچگان اصلاح شده58شکل 4‑5:درصد بهبود برای الگوریتم‌های ارائه شده63شکل 4‑6: مقایسه نتایج الگوریتم اصلاح شده با الگوریتم DPSOVNDبرای مسائل ریورز65 فهرست کلمات اختصاری عبارت کاملمخففAnt Colony optimization:ACOAnt Colony System:ACSBatching:BatchBlocking:BlockBreakdown:BrkdwnFirst Come First Servised:FCFSFlexible Flowshop:FFcjob Family:FMLsFlowshop Scheduling:FSLongest Processing Time:LPTMix-Integer Programing:MIPNo-Wiat Flowshop Scheduling:NWFSPrecint:PrecPreemption:PrmpPermutation:PrmuParticle Swarm Optimization:PSOReciculation:RcrcSimulated Annealing:SAShortest Processing Time:SPTTraveling Saleman Problem:TSP فصل 1 امروزه در عرصه صنعت بدلیل تفاوت و گوناگونی نیازهای مشتریان شاهد تنوع محصول‌ها، کوتاه شدن عمرشان و رقابت بالای تولیدکنندگان می‌باشیم. از این‌رو اهمیت به کارگیری روش‌هایی کارا جهت استفاده موثر از منابع بیش‌تر از گذشته نیاز میشود تا سازمان‌ها بتوانند قدرت پاسخگویی سریع به نیازهای مشتریان را داشته باشند. تکنیک‌های توالی عملیات و زمانبندی از جمله ابزار موثر در این رابطه است.در ادامه این فصل، ابتدا مقدمه‌ای از اهمیت و ضرورت زمانبندی تولید و توالی عملیات گفته میشود و سپس با مفاهیم توالی عملیات و نمادگذاری انواع مختلف مسائل آشنا خواهیم شد.تعیین توالی‌کارها[1]و زمانبندی[2] به معنی تخصیص منابع محدود به فعالیتهایی است که به آن منابع نیاز دارند. از این‌رو می توان آن را نوعی فرایند تصمیم‌گیری دانست که با هدف بهینهسازی یک و یا چند هدف انجام میگیرد. این امر نقش بسیار مهمی در کاهش هزینه‌ها، افزایش بهره‌وری، افزایش رضایت مشتری و به طور کلی افزایش سودآوری شرکت خواهد داشت.آغاز علم زمانبندی را بدون شک باید در تلاش‌های هنری گانت[3]در دو دهه ابتدایی قرن بیستم جستجو کرد. اما شروع تحقیقات جدی و گسترده در این زمینه و مرتبط ساختن آن با تحقیق در عملیات به اوایل دهه 1950 بر می‌گردد. اولین الگوریتم زمانبندی که به صورت مستقیم مسائل زمانبندی را به تحقیق در عملیات مرتبط ساخت، در سال 1954 توسط جانسون [1] ارائه شد و تقریبا برای اولین بار جواب بهینه یک مسأله زمانبندی بوسیله آن بدست آمد. پس از آن مسائل متعددی در زمینه توالی عملیات معرفی و الگوریتم‌های متنوعی برای حل آنها توسعه داده شد.در مسأله زمانبندی موجود در سیستم‌های صنعتی (خدماتی)، با یک سری از منابع، عمدتا ماشینها و یک تعداد کار که باید بر روی (از) این ماشینها (خدمت دهنده‌ها) پردازش شوند (خدمت بگیرند) و یک سری از محدودیتها سروکار داریم که با توجه به آنها در صدد بهینه کردن یک یا چند تابع هدف هستیم.شاخه‌ای از علم توالی عملیات به نام زمانبندی جریان‌کارگاهی[4] نامیده می شود. زمانبندی جریان‌کارگاهی یکی از مدلهای سنتی زمانبندی و توالی عملیات است که طیف وسیعی از مسائل عملی زمانبندی را در خود جای می‌دهد. در مدل جریان‌کارگاهی تعدادی کار و ماشین وجود دارد که این کارها هر یک با مسیر یکسان باید بر روی تمام ماشینها پردازش شوند. در این مدل، عملیات هر کار به ترتیب بر روی ماشین اول، ماشین دوم و تا ماشین آخر انجام می‌گردد و همچنین هر ماشین فقط یک کار را در هر زمان انجام می‌دهد و هدف انجام تمامی کارها با کمترین هزینه می‌باشد. در واقع در مدل جریان‌کارگاهی جریان پیوسته‌ای از کارها وجود دارد که بایستی توسط چند ماشین پردازش شوند و به همین دلیل به نام جریان‌کارگاهی نامیده میشود.منابع و کارها در یک سازمان می‌توانند صورت‌های مختلفی داشته باشند. برای نمونه، منابع می‌توانند ماشینهای یک کارگاه، باندهای پرواز در یک فرودگاه، خدمه‌ها در یک محل احداث بنا و یا واحدهای پردازش در یک محیط محاسباتی باشند. همچنین کارها می‌توانند عملیات در یک فرایند تولیدی، بلند شدن و نشستن هواپیما در یک فرودگاه، مراحل یک پروژه تولیدی و یا اجرای برنامه‌های رایانه‌ای باشند. هر کار نیز میتواند دارای یک سطح اولویت یا اهمیت خاص، زودترین زمان ممکن برای شروع پردازش و یک موعد تحویل باشد. تابع هدف نیز میتواند به صورت‌های مختلف تعریف شود. برای نمونه تابع هدف میتواند کمینه کردن زمان اتمام پردازش آخرین کار و یا کمینه کردن تعداد کارهایی که پردازش آنها بعد از موعد تحویلشان به پایان می‌رسد، باشد [2].در ادامه این قسمت در ابتدا با نمادگذاری مسائل زمانبندی آشنا خواهیم شد و پس از آن پیچیدگی مسائل زمانبندی مورد بحث قرار خواهد گرفت.به دلیل تنوع مدلهای زمانبندی و توالی‌عملیات و به منظور تفکیک مناسب این مسائل از یکدیگر چنیدن روش نمادگذاری معرفی شده است. برای اولین بار کانوی و همکاران[3]از یک نمادگذاری 4 تایی بصورت برای مسائل زمانبندی استفاده نمودند. با این‌حال نمادگذاری که امروزه از آن استفاده میشود نخستین بار توسط گراهام و همکاران [4] در 1979 معرفی شده است. در این شیوه، یک مسأله زمانبندی با یک 3 تایی نشان داده میشود که قسمت α محیط ماشینها[5] را توصیف میکند و فقط شامل یک نماد است. قسمت βخصوصیات پردازش و محدودیتهای موجود را شرح می‌دهد که این قسمت میتواند شامل هیچ نماد و یا چند نماد باشد. قسمت تابع(های) هدفی که باید بهینه شود را توصیف میکند. لازم به ذکر است که این نمادگذاری بعدها توسط پیندو [2] به‌روز شده است. در ادامه به مقادیر مختلفی که هر کدام از اجزای این نمادگذاری می توانند داشته باشند، خواهیم پرداخت و در پایان برای روشن شدن موضوع چندین مثال معرفی خواهد شد.در دنیای واقعی انواع گوناگونی از محیطهای تولیدی و خدماتی شامل تک ماشینه، ماشینهای موازی، جریان‌کارگاهی، کار کارگاهی و کارگاه باز به شرح زیر وجود دارد. نماد مرتبط با هر مشخصه در مقابل آن در داخل پرانتز آورده شده است.شکل 1‑1: شمایی از محیط تک ماشینهشکل 1‑2: شمایی از محیط جریانکارگاهیشکل 1‑3: شمایی از محیط جریان‌کارگاهی انعطاف پذیردر محیطهای تولیدی و خدماتی، محدودیتهای متفاوتی ممکن است وجود داشته باشد که حل مسأله زمانبندی نیازمند رعایت این محدودیتها است. تعدادی از این محدودیتها به قرار زیر هستند:مسدود شدن[12] (): در صورتی که در یک محیط تولیدی و یا خدماتی انبارهای میانی بین دو ماشین متوالی محدود باشد، با تکمیل شدن ظرفیت انبار بین دو ماشین، پس از اتمام پردازش یک کار بر روی یک ماشین، این کار تا بیکار شدن ماشین بعد، بر روی ماشین قبلی منتظر خواهد بود. در این حالت به اصطلاح گفته میشود که ماشین اول بلوکه شده است.