از آنجا که غالب مسائل مطرح شده در حوزه زمان­بندی که باعث بسط و گسترش این علم نیز گردیده­اند با نگاهی به مسایل واقعی در محیط­های صنعتی بوده ­اند، واژه­ های بکار رفته در این حوزه علمی نیز عموما برخاسته از محیط­های صنعتی خواهند بود. براین اساس، در بیان مسائل زمان­بندی از لفظ ماشین در معنای منبع و از واژه کار به عنوان فعالیت نام برده می­ شود. در نتیجه این تعاریف می­توان گفت در یک مسئله زمان­بندی غالبا کارها روی مجموعه ­ای از ماشین­ها که در ایستگاه­های کاری با نظم و اولویت­ بندی خاصی چیده شده ­اند پردازش می­شوند.

مسائل زمان­بندی بسته به تعداد و نحوه چیدمان ماشین­ها به شاخه­ های متعددی تقسیم می­ شود. ساده­ترین حالت، زمان­بندی تک ماشین است. این مسئله اگرچه ساده به نظر می­رسد اما پایه و اساس مسائل پیچیده­تر را تشکیل می­دهد.
همگام با گسترش سیستم­های تولیدی مسائل زمان­بندی نیز پیچیدگی بیشتری پیدا کردند. در یک تقسیم ­بندی کلی چیدمان ماشین­آلات در یک فضای صنعتی می ­تواند به صورت سری^[۲](جریانی)، موازی^[۳] و یا ترکیبی از این دو حالت باشد. در حالت سری هر کار باید از همه یا تعدادی از ماشین­هایی که به طور سری قرار گرفته­اند عبور کند. در حالت چیدمان موازی، تعدادی ماشین با عملکرد مشابه یا غیر مشابه به صورت موازی چیده شده ­اند. در این محیط مفهوم تخصیص کار به ماشین­ها اهمیت پیدا خواهد کرد. در حالت آخر که البته به دنیای واقعی نزدیک­تر است مفهوم ایستگاه­های کاری نمود بیشتری می­یابد. در یک سیستم ترکیبی عموما چندین ایستگاه کاری وجود دارد که در هریک از آنها چندین ماشین با چیدمان­های متفاوت اعم از سری و موازی وجود دارند.
در این تحقیق، مسئله یافتن توالی بهینه کارها در سیستم تولیدی جریانی بدون انتظار^[۴] منعطف^[۵] مورد بررسی قرار می­گیرد. این سیستم تولیدی مدل بسط یافته روش تولیدی سری است. در این سیستم ایستگاه­های کاری که به طور متوالی قرار گرفته­اند، هر کدام حاوی چند ماشین هستند که به صورت موازی چیده شده ­اند. در ادامه فصل، مسئله مذکور به طور کامل تشریح می­ شود.
۱-۲. تعریف مسئله
سیستم تولید جریانی منعطف حالت تعمیم یافته­ای از سیستم تولید جریانی است. در این حالت ایستگاه­های کاری به صورت متوالی قرار می­گیرند و هر ایستگاه حاوی تعدادی ماشین با عملکرد یکسان یا غیر یکسان است. هر کار به محض ورود به ایستگاه کاری باید با استراتژی مشخصی به یکی از ماشین­ها تخصیص یابد. البته انتخاب یکی از ماشین­ها یک ضرورت نیست و در برخی مسائل یک کار می ­تواند در اثنای عمل پردازش ماشین خود را تغییر دهد.
در یک سیستم تولید جریانی ممکن است بین تمام شدن کار در یک ایستگاه تا ورود کار به ایستگاه بعدی به دلیل مشغول بودن ایستگاه بعدی، خرابی آن یا دلایل دیگر وقفه زمانی وجود داشته باشد. اما برخی ویژگی­های حاکم بر کارها ممکن است با چنین وقفه­هایی در تضاد باشد. از این رو بسیاری از سیستم­های تولیدی شرط سیستم جریانی بدون انتظار را به دلیل محدودیت­هایی که در تولید کارها وجود دارد به کار می­برند [۲۸]. برای مثال، در تولید محصولات فولادی، فلز ذوب شده باید بدون هیچ اتلاف زمانی از ایستگاه ذوب فلز به ایستگاه های بعدی منتقل شود چرا که در غیر این صورت دمای مذاب به سرعت کاهش یافته و برای شکل­دهی مناسب نخواهد بود. بسیاری از صنایع مهم نظیر صنایع ذوب فلز و آلیاژ، پلاستیک، فرایندهای پتروشیمی و … از این سیستم تبعیت می­ کنند.
یکی از مهم­ترین مسائل در مدیریت تولید^[۶] و به طبع آن زمان­بندی یک سیستم تولیدی تعیین استراتژی تولید است. به این معنی که محصول تولیدی برای برآورده کردن نیاز یک مشتری خاص ساخته می­ شود یا به عبارتی تولید برای سفارش^[۷] است یا برای تامین نیازهای بازار ساخته می­ شود و پس از تولید به انبار می­رود یا به عبارتی تولید برای ذخیره^[۸] است. از آنجا که زمان رسیدن سفارش در سیستم تولید برای سفارش در دست مشتریان است، تحویل به موقع و چرخه تولید کوتاه و واقعی به عنوان فاکتورهای رقابتی اصلی برای بردن سهم بیشتری از بازار شناخته می­شوند در حالی که در سیستم­های تولید برای ذخیره بالا بودن نرخ بهره ­برداری، نرخ خروجی، و نرخ رسیدن محصول از فاکتورهای رقابتی اصلی هستند [۱۶]. امروزه در غالب محیط­های صنعتی تلفیقی از دو استراتژی­ مورد استفاده قرار می­گیرد. در این میان چالش اصلی زمان­بندی همزمان تمامی کارها است به نحوی که هم نیازهای بازار و هم نیازهای مشتریان به بهترین شکل برآورده شود.
هر سیستم تولیدی به صورت معمول توانایی تولید یک یا چند محصول را دارد. در استراتژی تولید برای سفارش ممکن است سفارش تحویل شده به مرکز تولیدی به یکی از چند حالت زیر باشد: یا سفارش براساس همان محصولات قابل تولید برای سیستم تعریف شده باشد، که در این حالت سفارش دهنده ترکیبی از محصولات استاندارد تولیدی کارخانه را سفارش داده و موعد تحویل مشخصی را برای آنها تعیین می­ کند. یا سفارش برای تولید نیاز به انجام تغییراتی در خط تولید معمول سیستم دارد. به عبارت بهتر مشتری خواهان مقداری شخصی سازی در سفارش است. در این صورت ممکن است در زمان­های پردازش یا در تعداد عملیات­های تولید تغییراتی حاصل شود. و حالت سوم که ترکیبی از دو حالت قبلی است، به این معنی که مشتری تعدادی محصول بدون تغییر و تعدادی محصول همراه با تغییر را سفارش می­دهد. از آنجا که سیستم تولیدی مورد بحث در این پژوهش تولید جریانی بدون انتظار بوده و محصولات تولیدی توسط این سیستم نظیر قطعات فولادی یا مواد پتروشیمی عموما دارای استانداردهای بین ­المللی هستند، لذا در این پژوهش استراتژی تولید برای سفارش نوع اول مورد بررسی قرار می­گیرد.
امروزه با توجه به مختصات بازارهای جهانی و لزوم حفظ توانایی رقابتی برای محیط­های تولیدی مفهوم تولید به موقع^[۹] به خوبی پذیرفته شده است. تولید به موقع به معنای در نظر گرفتن همزمان هزینه­ های ناشی از تولید زودتر از موعد یا زودکرد^[۱۰] و هزینه­ های دیرکرد^[۱۱] است. از آنجا که مفاهیم مربوط به تولید به موقع در غالب هزینه بیان می­شوند، به کارگیری این مفاهیم در مسائل زمان­بندی اغلب در توابع هدف مدل ریاضی نمود می­یابند.
در این تحقیق، مسئله زمان­بندی سیستم تولید جریانی بدون انتظار منعطف با محدودیت زمانی ظرفیت تولید روی ماشین آلات و درنظر گرفتن استراتژی ترکیبی تولید برای سفارش و تولید برای ذخیره با هدف حداقل کردن مجموع هزینه­ های ناشی از رد سفارشات، تحویل ناقص سفارشات و زودکرد و دیرکرد وزنی مورد بررسی قرار می­گیرد. یک مدل برنامه ریزی غیرخطی برای این مسئله ارائه می­ شود. همچنین دو الگوریتم فراابتکاری^[۱۲] سیستم ایمنی مصنوعی^[۱۳] و تبرید شبیه­سازی شده با رویکرد تئوری ابری^[۱۴] برای حل این مسئله ارائه می­گردد.
۱-۳. اهداف تحقیق
از آنجا که سیستم تولید جریانی بدون انتظار برای تولید محصولات استراتژیکی همچون صنایع فولاد و ذوب فلزات و پتروشیمی کاربرد دارد، تلاش در جهت بهره ­برداری کارا از سیستم تولیدی ضروری به نظر می­رسد. براین اساس، این تحقیق با هدف کاهش فاصله میان مطالعات تئوریک حوزه زمان­بندی و مسائل واقعی دنیای صنعت انجام می­گردد. لذا، یک مدل ریاضی جدید برای مسئله سیستم تولید جریانی منعطف بدون انتظار با محدودیت ظرفیت تولید و استراتژی ترکیبی مدیریت تولید ارائه می­ شود. به علاوه جهت یافتن توالی بهینه کارها دو الگوریتم فراابتکاری سیستم ایمنی مصنوعی و تبرید شبیه­سازی شده با رویکرد ابری برای مسئله مذکور پیاده­سازی می­شوند.
۱-۴. مفروضات مسئله
مفروضات حاکم بر مدل ریاضی ارائه شده برای مسئله مورد بحث به شرح زیر است:
تمام ماشین­آلات در لحظه صفر در دسترس خواهند بود و برای آنها هیچ­گونه خرابی متصور نیست.
بیکاری ماشین­الات مجاز است.
هر ماشین در هر لحظه تنها توانایی پردازش یک کار را دارد.
ماشین­های موجود در هر ایستگاه کاری از نظر عملکرد و سرعت کاملا یکسان هستند.
ماشین­های موجود در هر ایستگاه کاری دارای محدودیت زمانی هستند. به این معنی که در زمان مشخصی پس از لحظه صفر از دسترس خارج می­شوند. در نتیجه هر ایستگاه کاری دارای محدودیت زمانی مشخصی است.
کارهایی که تحت استراتژی تولید برای ذخیره ساخته می­شوند در لحظه صفر در دسترس خواهند بود.
سفارشات در لحظه تحویل به سیستم تولیدی در دسترس خواهند بود.
هر کار در تمام مدت پرداش خود در هر ایستگاه تنها مجاز به حضور روی یک ماشین است و برش کارها مجاز نخواهد بود.
زمان­های پردازش، نصب و ضرایب هزینه­ های زودکرد، دیرکرد و رد یا ناقص بودن سفارشات معین هستند.
۱-۵. جنبه­ های نوآوری تحقیق
تحقیق موجود از دو جهت تعریف مسئله و روش حل نسبت به تحقیقات پیشین دارای نوآوری است. در این پژوهش با وارد کردن استراتژی ترکیبی تولید در مسئله زمان­بندی سیستم تولید جریانی بدون انتظار منعطف و نیز محدودیت زمانی تولید، تعریف مسئله جدیدی ارائه شده است. در ادامه مدل ریاضی جدیدی برای مسئله مذکور تهیه و اعتبارسنجی گردیده است. از منظر روش حل نیز دو الگوریتم فراابتکاری سیستم ایمنی مصنوعی و تبرید شبیه­سازی شده با رویکرد تئوری ابری با عملکردهای متفاوت برای حل کارای این مسئله ارائه شده ­اند.
۱-۶. محتویات تحقیق
مطالب ارائه شده در این تحقیق در شش فصل سازماندهی می­شوند: فصل اول به بیان کلیات تحقیق می ­پردازد. در فصل دوم مرور ادبیات تحقیق و حاصل پژوهش­های قبلی گرداوری می­­شود. فصل سوم به ارائه، تشریح و اعتبار­سنجی مدل ریاضی اختصاص می­یابد. در فصل چهارم الگوریتم­های فراابتکاری ارائه شده برای حل مسئله به طور مفصل ارائه و نتایج حاصل از بکارگیری الگوریتم­های فراابتکاری ارائه می­شوند. و فصل آخر به نتیجه ­گیری و بیان پیشنهادات جهت پژوهش­های آتی می ­پردازد.
فصل دوم
ادبیات تحقیق
۲-۱. مقدمه
امروزه زمان­بندی به مفهوم بدنه­ای کامل از علمی است که شامل مدل­ها و تکنیک­ها است و به مسائل موجود در سیستم­های واقعی می­­پردازد [۲]. بسط مفاهیم تئوری زمان­بندی و شکل گرفتن مدل­ها و تکنیک­های بهینه­سازی در زمان­بندی را می­توان همزمان با وقوع جنگ جهانی دوم دانست. در دهه ۱۹۵۰ میلادی تحقیقاتی بر روی ویژگی­های مربوط به توالی­های خاص کاری نظیر چیدمان کارها براساس قاعده زودترین زمان تحویل^[۱۵]، یا قاعده کوتاهترین زمان پردازش^[۱۶] و … و تفاوت آنها از نظر معیارهای اندازه ­گیری با توالی­های کاری دیگر انجام شد و در نتیجه آن مقالاتی در این زمینه به چاپ رسید. در این دهه چشمگیر­ترین تحقیقات توسط هنری گانت^[۱۷] انجام شد. دهه ۶۰ میلادی نیز به گسترش این تحقیقات گذشت اما پژوهش­های انجام شده در این دو دهه از نظر کاربردی برای مسائل واقعی نظیر مسائل دولتی و صنعتی مناسب نبود به همین جهت با ورود به دهه ۷۰ میلادی تمرکز بیشتری بر کاربردی بودن تحقیقات شد که دو مورد از بهترین کارهای انجام شده در دهه­های ۷۰ و ۸۰ میلادی تحقیق کافمن^[۱۸] (۱۹۷۶) [۳] و فرنچ^[۱۹] (۱۹۸۲) [۴] بوده ­اند. تا این زمان تقریبا تمام پژوهش­های انجام شده بر روی مدل­های با زمان­های قطعی انجام شده بود و تنها روش­های حل موجود استفاده از ابزارهایی نظیر برنامه­ ریزی خطی^[۲۰] و سایر روش­های دقیق بود. رشد سریع صنایع در عصر صنعتی شدن اروپا ناکارامدی این روش­ها در حل مسائل واقعی و ابعاد بزرگ مسئله را بیش از پیش روشن نمود. در نتیجه جستجو برای روش­های حل جایگزین در دهه ۹۰ میلادی مورتون^[۲۱] و پینتیکو^[۲۲] (۱۹۹۳) [۵] روش­های ابتکاری را برای اولین بار در حل مسائل زمان­بندی به کار برده و آن را به جهان علم عرضه کردند. با ورود به قرن بیستم نیز پیندو^[۲۳] (۲۰۰۱) [۶] نتایج مطالعات مفصلی پیرامون مدل­های احتمالی در زمان­بندی را منتشر کرد. از آن پس پژوهش­های متنوعی در حوزه زمان­بندی در جریان بوده است که باعث شده در حال حاضر حجم مطالعاتی که در این حوزه برای تحقیق وجود دارد بسیار بالا می­باشد.
گسترش علم­زمان­بندی لزوم ایجاد زبانی مشترک جهت مشخص نمودن ابعاد و ویژگی­های مسئله را برای استفاده و ارجاع ساده­تر ضروری کرد در نتیجه گراهام^[۲۴] و همکارانش [۲۳] روش نمایش سه جزیی مسایل به فرم را تهیه کردند. در این روش نحوه پیکر­بندی ماشین آلات را نشان می­دهد و عموما شامل یک نماد است. بخش دوم که با نماد نشان داده می­ شود نمایشگر نحوه پردازش کارها و ویژگی­های حاکم بر محیط تولیدی است و ممکن است شامل یک یا چند جز باشد و یا حتی خالی باشد. و در نهایت بخش سوم با نماد نشان­دهنده تابع هدف مسئله بهینه­سازی است و می ­تواند یک یا جند جز داشته باشد اما عمدتا یک جزیی است. جداول(۲-۱)، (۲-۲) و (۲-۳) به ترتیب لیست نمادهای متداول در هریک از بخش­های این نحوه نمایش را نشان می­ دهند.
جدول ۱ جدول ۲-۱. نمادهای متداول برای .