است)
 
فصل اول
مقدمه و کلیات تحقیق
1-1. مقدمه
زمان­بندی[1]، فرآیند تخصیص منابع به فعالیت­ها با در نظر گرفتن دوره­های زمانی مربوط به آن­ها به منظور بهینه­سازی یک یا چند تابع هدف می­باشد. این فرآیند به عنوان یک  فرآیند تصمیم ­گیری مبنای کار بسیاری از صنایع تولیدی و خدماتی محسوب می­شود. زمان­بندی کارای فعالیت­ها زمینه­ساز بهبود عملکرد سیستم­های تولیدی می­باشد و ضرورتی برای بقا در فضای رقابتی بازار به شمار می­آید. امروزه، مدیریت منابع موضوع به طور فزاینده مهمی برای سازمان­ها می­باشد و تعیین توالی[2] و زمان­بندی یک شکل از تصمیم ­گیری است که نقش حیاتی در صنایع تولیدی و خدماتی بازی می­ کند. زمان­بندی ابزاری است که استفاده از منابع در دسترس را بهینه می­ کند.
به­طور کلی، منابع، فعالیت­ها و توابع هدف عناصر کلیدی زمان­بندی محسوب می­شوند. منابع برحسب قابلیت­های کمی و کیفی خود مشخص می­شوند. از سوی دیگر، فعالیت­ها بر حسب اطلاعاتی از قبیل منابع مورد نیاز، مدت زمان انجام، زمان آغاز و زمان پایان آن­ها توصیف می­شوند. توابع هدف نیز در برگیرنده هزینه­ های سیستم برای اجرای تصمیمات مربوط به تخصیص منابع به فعالیت­ها می­باشند. تصمیمات عمده در فرآیند زمان­بندی شامل بهره برداری کارا از منابع، پاسخگویی سریع به تقاضا و انطباق دقیق زمان­های تحویل با موعدهای تحویل[3] تعیین شده می­شوند.
در مسائل زمان­بندی هدف از یافتن توالی انجام فعالیت­ها ممکن است متفاوت باشد. تعدادی از اهداف متداول عبارتند از: کمینه­سازی زمان تکمیل کل کارها و یا کمینه­سازی تعداد کارهایی که دیرکرد دارند. یکی از مهم­ترین اهداف در بسیاری از صنایع تولیدی تحویل به موقع[4] کالا و خدمات می­باشد که در به­دست آوردن سود و یا هزینه­ های پایین­تر نقش دارد. در یک بازار رقابتی دیرکرد کارها با توجه به موعد تحویل آن­ها یک مقیاس عملکرد بسیار مهم برای محیط­های تولید متنوع است. تکمیل یک کار زودتر از موعد تحویل ممکن است هزینه­هایی از قبیل هزینه نگهداری موجودی به تولید کنندگان تحمیل کند، در حالیکه تکمیل یک کار دیرتر از موعد تحویل منجر به پرداخت جریمه­های قراردادی به مشتری و کاهش اعتبار تولید کننده می­شود. حداقل­سازی زودتر و دیرتر یکی از سیاست­های مسائل زمان­بندی بهنگام می­باشد.
انگیزه بسیاری از توسعه­ها و پیشرفت­های عملی در حوزه زمان­بندی برخاسته از محیط­های صنعتی است و به طور طبیعی در بیان مفاهیم زمان­بندی از واژه­های بکار رفته در صنعت استفاده می­شود. به همین خاطر منابع با عنوان ماشین به کار می­روند و به هر کدام از فعالیت­ها، کار اطلاق می­شود بطوریکه کارها اغلب به وسیله­ی مجموعه ­ای از ماشین­ها در ایستگاه­های مختلف کاری با توان مشخص پردازش می­شوند.
بطور کلی، مسائل زمان­بندی به صورت مسائل بهینه­سازی دارای محدودیت بیان می­شوند که در آن­ها به بررسی تصمیمات مربوط به تضمین ماشین­ها و توالی پردازش کارها پرداخته می­شود. در حالتی که تنها یک ماشین موجود است، تعیین توالی پردازش کارها یک برنامه زمانی کامل را تشکیل می­دهد. مسائل تک­ماشینه با وجود سادگی ذاتی، سنگ بنای درک فراگیر مفاهیم زمان­بندی را تشکیل می­ دهند. در مقابل، زمان­بندی مسائل چند ماشین شامل سیستم­های موازی، سیستم­های متوالی و سیستم­های ترکیبی می­باشد. در سیستم­های موازی، هر یک از کارها با انجام یک عملیات همانند مسائل تک­ماشینه بر روی یکی از ماشین­های موازی موجود پردازش می­شوند و به دنبال آن تخصیص ماشین­ها به کارها موضوعیت پیدا می­ کنند. این در حالی است که در سیستم­های متوالی و ترکیبی، کارها با انجام چند عملیات بر روی ماشین­ها پردازش می­شوند و مسائل مربوطه ساختار نسبتاً پیچیده­تری را تجربه می­ کنند.
در این تحقیق، به بررسی مسأله جریان کارگاهی انعطاف­پذیر[5] به عنوان دسته مهمی از مسائل زمان­بندی که دارای اهمیت فراوان از نقطه نظر تئوری و تجربی است، پرداخته می­شود. چنانچه ساختار سیستم تولیدی به شکل سری بوده و حداقل در یک مرحله چندین ماشین موازی وجود داشته باشد،در واقع با یک سیستم جریان کارگاهی انعطاف­پذیر مواجه هستیم که زمان­بندی این نوع سیستم­های خطی به دلیل کاربردی بودن آنها در سالهای اخیر در صنعت مورد توجه قرار گرفته است.
1-2. تعریف مسأله
دربرخی از صنایع تولیدی و خدماتی سفارش­ها تحت عنوان کارها به وسیله مجموعه ­ای از ماشین­ها که به صورت سری در ایستگاه­های کاری مختلف قرار گرفته­اند با توالی مشخص پردازش می­شوند. یعنی کارها مسیر یکسانی را دنبال می­ کنند و ماشین­ها به صورت سری، پشت سر هم قرار دارند. وضعیت تعمیم یافته­ا­­ی از این مسائل یعنی مسأله جریان ­کارگاهی منعطف می­باشد که در هر مرحله (حداقل یکی از مراحل) حداقل دو ماشین بصورت موازی موجود است. در این حالت هر یک از کار­ها بایستی به ترتیب در هر مرحله توسط یکی از ماشین­های موجود پردازش شده و به مرحله بعد برود.
بیشتر ادبیات نظریه زمان­بندی، و به همین دلیل بیشتر درک ما از مسائل زمان­بندی، مربوط به محاسبه زمان جریان کل، تعداد کارهایی که تأخیر دارند و تأخیر کل می­باشد. معیار مجموع تأخیر­ها، به طور خاص، به یک روش استاندارد برای اندازه ­گیری انطباق با تاریخ تحویل کارها تبدیل شده است، با این وجود عواقب کارهایی که زودتر از موعد تحویل، تکمیل می­شوند نادیده گرفته شده و تنها آن دسته از کارهایی که دیرکرد دارند، با جریمه مواجه شده ­اند. اما این معیار با رشد سهم تولید بهنگام شروع به تغییر کرد، با تأکید بر این نکته که زودکرد همانند دیرکرد باید نامناسب در نظر گرفته شود. در یک محیط زمان­بندی به­هنگام، کاری که زود تکمیل می شود تا تاریخ تحویل آن کار باید در موجودی انبار نگه­داری شود، در حالی که اگر یک کار پس از موعد تحویلش اتمام یابد ممکن است در برآوردن نیازهای مشتری اختلال ایجاد کند. بنابراین، یک زمان­بندی ایده­آل، زمان­بندی است که در آن همه کارها دقیقاً در تاریخ­هایی که به آن­ها اختصاص داده شده اتمام یابند. البته، زمان­بندی بهنگام شامل مجموعه ­ای بسیار گسترده­تر از اصولی است که مرتبط با موعد­های تحویل می­باشد، اما مدل­های زمان­بندی با هزینه زودکرد و دیر کرد (E / T) به یک بعد اساسی زمان­بندی رویکرد­های JIT آدرس دهی می­شوند.
مسأله زمان­بندی جریان کارگاهی اخیراً در صنعت بطور وسیعی در محیط­های صنعتی مورد استفاده قرار گرفته است، به همین دلیل در 50 سال اخیر به دقت بررسی شده است. مسأله مورد بررسی در این تحقیق، مسأله زمان­بندی جریان کارگاهی انعطاف­پذیر در محیط­های تولید بهنگام می­باشد.در برخی از کاربرد­های زمان­بندی مسأله جریان کارگاهی انعطاف­پذیر ماشین­ها دارای سطوح تکنولوژیکی متفاوتی هستند و لزوماً قادر به پردازش هریک از کارهای موجود در مجموعه کارها نمی­باشند. در نتیجه، هر کدام از کارها تنها بر روی زیر مجموعه­ا­ی از مجموعه ماشین­ها می­توانند پردازش شوند و اصطلاحاً پردازش کارها با دسترسی محدود به ماشین­ها[6] صورت می­پذیرد.
مسائل زمان­بندی غالباً به محیط­های کارگاهی می­پردازند که در آن­ها زمان نصب[7] ماشین نادیده گرفته می­شود و یا به عنوان بخشی از زمان پردازش کارها تلقی می­شود. این نوع محیط­های کارگاهی با این فرض مدل­سازی می­شوند که زمان­های نصب در مقایسه با زمان­های پردازش کوچک هستند، بنابراین می­توان آن­ها را نادیده گرفت و یا اینکه زمان­های نصب مستقل از توالی پردازش کارها بر روی ماشین­ها هستند، در نتیجه می­توان آن­ها را به زمان­های پردازش اضافه نمود. با این وجود، در بسیاری از محیط­های صنعتی یک زمان نصب وابسته به توالی[8] هنگام تعویض کارها بر روی ماشین­ها به وقوع می­پیوندد[6]. در این شرایط، زمان نصب به عنوان بخشی مجزا از زمان پردازش در نظر گرفته می­شود که مقدار آن علاوه بر نوع کاری که بر روی ماشین پردازش خواهد شد به نوع کار قبلی که بر روی آن ماشین پردازش شده نیز بستگی دارد.تلقی زمان نصب به صورت مجزا از زمان پردازش در بیشتر تکنیک­های مدیریت تولید نوظهور نظیر تولید بموقع[9]، تکنولوژی گروهی[10] و تولید سلولی[11] مورد استفاده قرار می­گیرد. همچنین در بعضی از مسائل ماشین­ها نیاز به زمان نصب برای پردازش کارها دارند، یعنی اگر یک کار به عنوان اولین کاری باشد که بر روی ماشین پردازش می­شود یک زمان نصب وابسته به ماشین[12] مجزا از زمان پردازش برای آن در نظر گرفته می­شود. تحقیقات زیادی در مورد مسأله جریان کارگاهی انعطاف­پذیر با فرض خرابی ماشین[13] خصوصاً هنگامیکه خرابی ماشین به کار انجام شده قبلی روی ماشین بستگی داشته باشد،انجام نشده است[46]. در بعضی از مسائل تمام کارها در ابتدای افق زمانی (لحظه صفر) در دسترس نیستند و زمان دسترسی[14] به هرکار مستقل از کارهای دیگر می­باشد.
در این تحقیق، مسأله زمان­بندی جریان کارگاهی انعطاف­پذیر با در نظر گرفتن محدودیت­های دسترسی به ماشین، زمان نصب وابسته به توالی و ماشین، خرابی ماشین و زمان دسترسی به کار با هدف کمینه­سازی زمان­های زودکرد و دیرکرد وزنی بررسی می­شود. یک مدل برنامه ­ریزی عدد صحیح برای این مسأله پیشنهاد می­شود. همچنین چندین روش فرابتکاری[15] برای حل آن ارائه می­گردد.
1-3. اهداف تحقیق
هدف ازاجرای این تحقیق طراحی یک مدل ریاضی وحل آن با  الگوریتم­های ابتکاری و فرا ابتکاری برای مسأله جریان کارگاهی منعطف با محدودیت و توابع هدف کمینه­سازی دیرکردها و زودکردهای وزنی و کمینه­سازی هزینه بیکاری ماشین­ها می­باشد، به علاوه چندین الگوریتم فراابتکاری به منظور حل این مدل در مقیاس کاربردی طراحی می­گردد.
1-4. مفروضات مسأله
مفروضات زیر در ارائه مدل مسأله در نظر گرفته می­شود:

کارها با توجه به زمان دسترسی خود در دسترس قرار می گیرند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
 

کارها با توجه زمان آماده سازی خود آماده می شوند و لزوماً در مبدأ زمان ( لحظه صفر ) برای پردازش آماده نیستند.
 

زمان نصب هر کدام از کارها وابسته به توالی آنها بر روی ماشین هاست.
 

هر ماشین در هر لحظه حداکثر می تواند یک کار را پردازش کند.
 

هر کار در هر لحظه حداکثر می تواند بر روی یک ماشین پردازش شود.
 

ماشین ها به طور پیوسته در دسترس نیستند.
 

برش کار به این مفهوم که پردازش یک کار قبل از پایان زمان پردازش آن قطع شود ودر زمان­های بعدی بر روی ماشین­های دیگر پردازش آن ادامه یابد، مجاز نمی باشد.
1-5. جنبه های نوآوری تحقیق
تحقیق موجود از دو جنبه صورت مسأله و روش حل نسبت به تحقیقات پیش دارای نوآوری می­باشد. در این تحقیق یک مدل ریاضی جدید برای مسأله زمان­بندی جریان کارگاهی انعطاف­پذیر با در نظر گرفتن محدودیت­های دسترسی به ماشین، زمان نصب وابسته به توالی وماشین، خرابی ماشین و زمان دسترسی به کارها ارائه شده است. همچنین دو رویکرد با استفاده الگوریتم­های ژنتیک[16]و رقابت استعماری[17] برای حل مسأله ارائه شده­است.
1-6. محتویات تحقیق
مطالب ارائه شده دراین تحقیق در پنج فصل سازماندهی می­شود: مقدمه و کلیات تحقیق در فصل اول ارائه شده­است. در فصل دوم به مرور ادبیات تحقیق زمان­بندی جریان کارگاهی منعطف پرداخته می­شود. در فصل سوم مدل ریاضی پیشنهادی تشریح و اعتبار سنجی می­گردد. فصل چهارم شامل معرفی الگوریتم­ها و رویکردهای پیشنهادی این تحقیق به همراه نتایج محاسباتی مربوط به آن می­باشد و نهایتاً، فصل پایانی تحقیق شامل نتیجه­گیری و پیشنهادات تحقیقات آتی می­باشد.
[1] Scheduling
[2] Sequence
[3] Due date