علمی : حل مسأله زمان‌بندی جریان‌کارگاهی با فرض عدم‌توقف‌ به روش ابتکاری- قسمت 17

علمی :
حل مسأله زمان‌بندی جریان‌کارگاهی با فرض عدم‌توقف‌ به روش ابتکاری- قسمت 17

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

جریان‌کارگاهی با محدودیت عدم‌توقف

در این فصل، ابتدا تعریفی جامع بر مسئله جریان‌کارگاهی با محدودیت عدم‌توقف خواهیم داشت. و خواهیم دید که این محدودیت در دنیای واقعی چه اثرگذاری دارد. در ادامه مروری بر پژوهش‌های انجام شده در حوزه مسئلهی مورد بررسی ، الگوریتم‌های ابتکاری و الگوریتم‌های فراابتکاری خواهیم داشت. در گام بعد، به بررسی مدل ریاضی مسئله و اثبات آن می‌پردازیم.
جریان‌کارگاهی با محدودیت عدم‌توقف
مسأله مورد بررسی در این رساله، تعیین توالی و زمان‌بندی در یک محیط جریان‌کارگاهی با محدودیت عدم‌توقف[33] است که به اختصار خوانده می‌شود. منظور از عدم‌توقف این است که هر کار پس از شروع پردازش بر روی اولین ماشین، به صورت پیوسته بر روی دیگر ماشین‌ها تا آخرین ماشین پردازش می‌شود و هیچ توقفی بین پایان عملیات بر روی یک ماشین و شروع عملیات بر روی ماشین بعدی وجود نداشته باشد. به بیان دیگر، زمان تکمیل پردازش یک کار بر روی یک ماشین دقیقا برابر با زمان شروع پردازش آن کار بر روی ماشین بعدی است. از این‌رو زمان شروع یک کار بر روی ماشین اول بایستی به نوعی زمان‌بندی شود تا این محدودیت رعایت گردد.
شکل ‏3‑1: شمایی از مسئله جریان کارگاهی با محدودیت عدم‌توقف
دلایل عمده به وجود آمدن محدودیت عدم‌توقف را به می‌توان به شرح زیر مطرح کرد [7]:
فناوری تولید:
در برخی از فرایند‌ها، برخی از مشخصه‌های مواد از نظیر دما یا چسبناکی این محدودیت را ایجاب می‌کند که عملیات متوالی بر روی ماشین‌ها بدون وقفه انجام شود. به عنوان نمونه این شرایط در فرایند تولید فولاد هنگامی که فولاد ذوب شده و مسیرهایی را به منظور قالب‌گیری، گرم‌کردن مجدد، خیساندن، نورد اولیه و… طی می‌کند، اتفاق می‌افتد. همچنین در صنایع پلاستیک و دارو‌سازی، تعدادی از فرایندها باید بدون وقفه و به صورت متوالی انجام شوند. در صنایع غذایی، فرایند قوطی‌ریزی مواد غذایی، باید دقیقا پس از آماده شدن مواد غذایی انجام شود تا مواد غذایی سالم بمانند. در صنایع تولیدی مدرن از جمله تولید ‌به ‌هنگام و سیستم‌های تولیدی انعطاف‌پذیر نیز محدودیت عدم‌توقف دیده می‌شود.
کمبود و یا عدم وجود انبارهای میانی بین ماشین‌های متوالی:
دلیل دوم برای به‌وجود آمدن محدودیت عدم‌توقف، کمبود انبارهای میانی بین ماشین‌ها و یا ایستگاه‌ها میباشد.
در این مسأله فرض می‌شود که کار در یک محیط جریان‌کارگاهی با ماشین، پردازش می‌شوند. با توجه به ویژگی‌ مسئله، ترتیب پردازش کارها بر روی ماشین‌ها یکسان می‌باشد. هدف از بررسی و حل این مسأله یافتن بهترین توالی پردازش کارها بر روی ماشین‌ها به گونه‌ای است که زمان اتمام پردازش آخرین کار () کمینه شود.
نماد مسأله مورد بررسی با استفاده از نمادهای مسائل [2] به صورت Fm/nwt/Cmax می‌باشد. در این نماد، قسمت اول که با Fنشان داده شده است، نشان‌دهنده محیط جریان‌کارگاهی با ماشین است. نماد در بخش دوم محدودیت عدم‌توقف را نشان می‌دهد و بخش سوم نیز بیان‌کننده تابع هدف مورد بررسی که طولانی‌ترین زمان تکمیل است می‌باشد.
فرضیه‌های در نظر گرفته شده در این مسأله به شرح زیر است:
n کار برای پردازش بر روی ماشین در دست است؛
پردازش هر کار بر روی هر ماشین تا اتمام آن بدون وقفه صورت می‌پذیرد؛
زمان شروع یک کار برروی یک ماشین برابر با زمان اتمام آن بر روی ماشین قبلی است؛
زمان پردازش کارها بر روی ماشین‌ها قطعی و از قبل مشخص است؛
کلیه کارها در زمان صفر در دسترس است.
هال و سریکاندراجا [7] خلاصه‌ای از پژوهش‌های انجام شده تا سال 1996 در حوزه مسائل زمان‌بندی با محدودیت عدم‌توقف در محیط‌های جریان‌کارگاهی، کارکارگاهی و کارگاه باز را ارائه داده‌اند. آنها علاوه بر معرفی چندین روش ابتکاری برای حل مسأله، به بررسی پیچیدگی حالت‌های خاصی از این گروه مسائل پرداخته‌اند.
مرور ادبیات جریان‌کارگاهی با محدودیت ‌عدم‌توقف
سهنی و چو [24] مسأله زمانبندی با محدودیت عدم‌توقف را در محیطهای جریان‌کارگاهی، کار کارگاهی و کارگاه باز با تابع هدف کمینه کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و نشان میدهند که این گروه مسائل از نوع هستند. همچنین در این تحقیقات نشان داده می‌شود که مسائل کارکارگاهی و کارگاه باز در حالت دو ماشینه حتی هنگامی که هیچ کاری با زمان پردازش صفر بر روی یکی از ماشین ها وجود نداشته باشد هستند.
پانوالکر و وولام [25] حالت خاصی از مسأله را با تابع هدف کمینه‌کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و قضیه‌هایی را در مورد مقدار بهینه تابع هدف مسأله مورد بحث مطرح کرده و اثبات میکنند.
مون و همکارای [26] مسأله زمان‌بندی جریان‌کارگاهی با محدودیت عدم‌توقف را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار مورد بررسی قرار داده و مدل ریاضی خطی– عدد صحیح را برای حل آن ارائه میدهند. در مسأله مورد نظر، زمانهای حمل و نقل و زمانهای آمادهسازی وابسته به توالی ماشینها در نظر گرفته میشود. همچنین به منظور بررسی عملکرد مدل ریاضی این مسئله ، نمونههایی از مسأله مورد بررسی حل شده و نتایج آن با مدلهای پیشین مقایسه میشود.
آیدوسان [27] مسأله را در حالت دو ماشینه و با فرض زمانهای آمادهسازی ماشینها با هدف کمینه کردن مجموع زمان تکمیل پردازش کارها مطرح کرده و الگوریتم ابتکاری برای حل آن را ارائه می‌دهد. در این روش حد پایینی برای مسأله مورد بحث توسعه داده شده و از آن در روش شاخه و کران که به منظور ارزیابی الگوریتم ابتکاری ارائه شده، استفاده میشود.
لین و همکاران [28] مسأله در حالت دو ماشینه را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار، مورد بررسی قرار میدهند. آنها فرض گروههای کاری و زمانهای آمادهسازی ماشین‌ها قبل از شروع پردازش یک گروه از کارها را نیز در نظر گرفته و پیچیدگی مسأله مورد بحث را بررسی میکنند.
دیلیپان [29] مسأله در حالت دو ماشینه را در حالتی که تابع هدف وابسته به زمان تحویل بوده را با هدف کمینه کردن بیشینه دیرکرد کارها مورد بررسی قرار میدهد و قضایای تئوری برای آن را مطرح کرده و اثبات میکند. او همچنین حالتهای خاصی از مسأله مذکور را مورد بررسی قرار می‌دهد.
سو و لی [30] مسأله زمان‌بندی جریان‌کارگاهی با محدودیت عدم‌توقف در حالت دو ماشینه را با هدف کمینه‌کردن مجموع زمان تکمیل پردازش کارها مورد بررسی قرار میدهند. آنها در حل مسئله خود، فرض زمانهای آماده‌سازی ماشینها با استفاده از یک خدمت‌دهنده به منظور آمادهسازی ماشینها در نظر میگیرند. بدین معنی که آماده‌سازی دو ماشین به صورت همزمان غیرممکن است، زیرا تنها یک خدمت‌دهنده برای این منظور وجود دارد. آنها برای بدست آوردن جواب بهینه (حداکثر 65 کار) از روش شاخه و کران استفاده میکنند.
هنگ و همکاران [31] مسأله انعطاف پذیر دومرحلهای را با هدف کمینه‌کردن مجموع زمان تکمیل پردازش کارها و با فرض زمانهای آماده‌سازی ماشینها مورد بررسی قرار میدهند. آنها یک مدل برنامه ریزی خطی- عدد صحیح برای مسأله موردنظر توسعه میدهند.
ژاو و تانگ [32] مسأله در حالت دو ماشینه را با هدف کمینه کردن زمان تکمیل پردازش آخرین کار و با فرض زمان خرابی و تعمیر ماشینها مورد بررسی قرار میدهند. آنها زمان پردازش کارها را تابعی از زمان شروع کارها در نظر میگیرند. همچنین فرض زمان خرابی و تعمیر ماشینها را تنها برای یک ماشین در نظر گرفته و قضیههایی را به صورت تئوری برای این مسأله مطرح و اثبات میکنند.
جنابی و همکاران [33] مسأله را با هدف کمینه کردن همزمان دو تابع هدف زمان پردازش آخرین کار و مجموع دیرکرد کارها بررسی میکنند. آنها دو مدل ریاضی برنامه ریزی خطی- عدد صحیح برای حل نمونههای کوچک مسأله ارائه میدهند و از رویکرد تصمیمگیری چند معیاره برای حل مدل ریاضی مذکور استفاده میکنند.
آیدیلک و علی‌اله‌وردی [34] به مسأله حداقل‌سازی زمان کل پردازش توالی با در نظر گرفتن عدم‌توقف تولید بین ماشین‌آلات مختلف پرداختند. آنها همچنین فرض کردند که موعد‌تحویل هر محصول دارای حد بالای مفروضی است. آنها 5 الگوریتم ، ، ، و را برای حل مساله ارائه نمودند.
سلماسی و عرب‌عامری [35] به بررسی مسائل زمان‌بندی جریان‌کارگاهی با محدودیت عدم‌توقف با هدف کمینه‌کردن زودکرد و دیرکرد با استفاده از چند الگوریتم ابتکاری پرداختند و الگوریتم‌های کارا را برای مسائلی در ابعاد کوچک، متوسط و بزرگ مشخص کردند.
لیو و همکارانش [36] به مقایسه الگوریتم‌های ، ، و سه الگوریتم ابتکاری دیگر برای مسئله زمان‌بندی FS با محدودیت عدم‌توقف با هدف حداقل‌کردن دیرکرد پرادختهاند و نتایج، نشان‌دهنده‌ی کاراتر و بهتر بودن الگوریتم نسبت به پنج الگوریتم دیگر است.
دونالد ‌داوندرا و همکارانش [37] در مطالعه خود به مسئله حداقل‌سازی طولانی‌ترین زمان تکمیل با در نظر گرفتن فرض عدم‌توقف تولید بین ماشین‌آلات مختلف پرداختند. آنها الگوریتم‌های ابتکاری و را برای حل مسئله با الگوریتم مقایسه نمودند که نتایج حاصل از کار آنها برتری الگوریتم نسبت به دو الگوریتم دیگر را نشان می‌دهد.
مدل ریاضی عدد صحیح جریان‌کارگاهی با محدودیت عدم‌توقف
مسائل عمومی جریان‌کارگاهی را می‌توان به صورت مدلهای برنامه‌ریزی عدد صحیح[34] فرموله کرد. در ادامه مدلی را که برای مسائل جریان‌کارگاهی با محدودیت عدم‌توقف ارائه شده است، توضیح می‌دهیم. پارامترها و متغیرهای استفاده شده در این مدل به شرح زیر می‌باشند.

این مطلب را هم بخوانید :  حل مسأله زمان‌بندی جریان‌کارگاهی با فرض عدم‌توقف‌ به روش ابتکاری- قسمت 24

دانلود متن کامل این پایان نامه در سایت abisho.ir

مدیر سایت