مقاله زمانبندی سیستم های تولیدکارگاهی انعطاف پذیر با استفاده از الگوریتم جستجوی فاخته بهبودیافته با خوشه بندی مارکوف و پرواز لوی

بخشی از مقاله

چکیده

با توجه به پیچیدگی بالای مسائل زمانبندی، روش های کلاسیک جوابگوی حل این مسأله نیستند، بنابراین امروزه از الگوریتم های فرااکتشافی در حل آن استفاده میشود. در این مقاله الگوریتم بهینه سازی فاخته به عنوان یکی از جدیدترین و قویترین روش های بهینه سازی تکاملی برای حل مساله زمانبندی کار کارگاهی انعطاف پذیر استفاده شده است. در الگوریتم پیشنهادی برای بهبود پاسخها، ترتیب ورود جمعیت اولیه براساس الگوریتم NEH-D ،که مبتنی بر کاهش زمان اجرای هر یک از کارها است، تعیین شده است.

سپس ماشین های فعال توسط خوشهبندی مارکوف گروهبندی میگردند، تا در هر مرحله از عملیات، انتخاب ماشین از بین ماشین های فعال صورت گیرد. بنابراین تعداد جواب های انتخابی برای الگوریتم جستجوی فاخته محدود میگردد، تا سرعت اجرای الگوریتم فاخته افزایش یابد. در نهایت نیز از الگوریتم جستجوی فاخته برای تخصیص ماشین ها به کارها و از پرواز لوی برای بهبود در الگوریتم فاخته جهت جستجوی سراسری در کنار جستجوی محلی بهره بردهایم. الگوریتم پیشنهادی بر روی مجموعه داده استاندارد Kacem، Brandimarte و داده های مقالات مرتبط مقایسه شده است. نتایج تجربی نشان میدهد که الگوریتم پیشنهادی سرعت بالاتری در رسیدن به جواب نهایی و همچنین همگرایی بالایی در جواب ها دارد.

-1 مقدمه

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

[1] زمانبندی سیستم تولید کارگاهی انعطاف پذیر1شامل زمانبندی n کار روی m ماشین است. هر کار دارای تعدادی عملیات است و برای هر عملیات، امکان استفاده از یک مجموعه ماشین وجود دارد. زمانبندی سیستم های تولید کارگاهی انعطاف پذیر به دلیل جایگاه ویژه آن در مراکز تولیدی مورد توجه زیاد مدیران واحدهای تولیدی است. شکل ساده مسأله زمانبندی تولید کارگاهی انعطاف پذیر مسأله زمانبندی تولید کارگاهی کلاسیک است، که به صورت زمانبندی n  کار J1, J2 ,...,Jn روی مجموعه M از ماشینها شامل m ماشینM1,M2,...,Mm  تعریف میشود. هرکار دارای Oj عملیات است که بایستی به ترتیب انجام گردند. هدف زمانبندی این مسأله، تعیین توالی عملیات برای هر ماشین است، به نحوی که یک تابع هدف از قبل مشخص شده مثل دوره ساخت، بهینه گردد.[2] 

ادبیات مطرح شده در زمینه سیستمهای تولید کارگاهی انعطاف پذیر بسیار گسترده است. بروکر و همکاران [3] اولین افرادی بودند که این مسأله را مورد بررسی قرار دادند. آنها یک الگوریتم چندوجهی برای حل مسأله کارگاهی انعطاف پذیر با دو کار ارائه کردند. روشهای فراابتکاری توسعه داده شده در سالهای اخیر، روشهای جایگزین بسیار مناسب و جذاب برای حل مسائل زمانبندی جریان کارگاهی به حساب میآیند.

در سال2010، زینگ[4] الگوریتم بهینه سازی مورچگان مبتنی بر دانش را برای مسئله زمانبندی فروشگاه کار انعطاف پذیر پیشنهاد کرده است. الگوریتم 2KBACOادغام مدل بهینه سازی مورچگان و مدل مبتنی بر دانش است. در الگوریتم آنها مدل دانش، برخی از دانش بهینه سازی مورچگان را یاد میگیرد و سپس دانش موجود را برای هدایت جستجوی اکتشافی فعلی اعمال میکند. تکنگ در سال [5]2012 الگوریتم جهش قورباغه برای حل مسئله زمانبندی کار کارگاهی انعطاف پذیر پیشنهاد کردهاست. مدل پیشنهادی این مقاله ترکیبی از الگوریتم جهش قورباغه و مفهوم منطق فازی است.

در سال 2012 ، ژانگ[6] الگوریتم رقابت استعماری را برای مسائل زمانبندی کار کارگاهی پیشنهاد کرده است و عملیات جستجوی محلی را برای بهبود کیفیت راه حل ها اجرا کرده است. در سال 2012، جولای[7] یک الگوریتم رقابت استعماری ترکیبی برای مسئله زمانبندی فروشگاه جریان انعطاف پذیر با در نظر گرفتن زمان راه اندازی، به منظور به حداقل رساندن حداکثر زمان اتمام برنامه ارائه کرده است. برنوال در سال [8]2013 روشی مبتنی بر جستجوی فاخته برای بهینه سازی زمانبندی سیستم های تولید انعطاف پذیر با به حداقل رساندن هزینه پنالتی با توجه به تاخیر تولید و به حداکثر رساندن زمان استفاده از ماشین توسعه داده است.

بابوکارتیک در سال [9]2012 الگوریتم ترکیبی از ACO3 و جستجوی فاخته برای مسئله زمانبندی کار پیشنهادکرده است. جستجوی فاخته میتواند جستجوی محلی موثرتر انجام دهد و زمان کل را حداقل کرده و زمانبندی را میتوان در محاسبات علمی ومحاسبات قدرت بالا استفاده کرد. در 2014 ، العبیدی[10] الگوریتم جستجوی تابو بر اساس جستجوی فاخته پیشنهاد کرده است. الگوریتم جستجوی تابو براساس جستجوی فاخته بستگی به ذخیره سازی بهترین همسایه فعلی در بهترین لیست راه حل دارد.

با توجه به اینکه در برخی تحقیقات گذشته الگوریتم جستجوی فاخته به شکل موثری برای مساله زمانبندی استفاده شده است، در این مقاله روشی مبتنی بر بهبود الگوریتم فاخته به منظور حل مساله زمانبندی کار کارگاهی پیشنهاد شده است. در روش پیشنهادی استفاده از الگوریتم NEH-D جهت بهبود مقداردهی اولیه و تسریع همگرایی پیشنهاد شده است. همچنین از خوشه بندی مارکوف بر روی ماشینها جهت کاهش فضای پاسخ و پرواز لوی جهت افزایش تنوع پاسخها استفاده شده است. ادامه این مقاله به صورت زیر سازماندهی شده است. در بخش 2 ابتدا مساله زمانبندی کار کارگاهی انعطاف پذیر معرفی می گردد. در بخش 3 ابزارهای پایه و اولیه مورد استفاده در روش پیشنهادی ذکر شده است. بخش 4 روش پیشنهادی را معرفی کرده است. ارزیابی روش پیشنهادی در بخش 5 و جمع بندی و نتیجه گیری در بخش 6 ارائه شده است.

-2 طرح مسأله

مساله زمانبندی کار کارگاهی انعطاف پذیر شامل تخصیص مجموعه ای از کارها به مجموعه ای از ماشین ها با شرایط خاص می باشد، و در رده مسایل NP-hard قرار میگیرد.[2] F-JSSP حالت توسعه یافته زمانبندی کار کارگاهی - JSSP - 4 است، که در آن هر ماشین توانایی ارائه بیش از یک عملیات را دارد. بر طبق[5]، انعطاف پذیری در کار کارگاهی به انعطاف پذیری ماشین اشاره دارد که ممکن است جزئی - مساله زمانبندی کار کارگاهی انعطاف پذیر جزئی PF- - - 5 - JSSP یا کلی - مساله زمانبندی کار کارگاهی انعطاف پذیر کلی - 6 - TF-JSSP - باشد. PF-JSSP یک حالت خاص از F-JSSP می باشد، که در آن امکان استفاده از برخی از ماشین ها برای انجام عملیات وجود دارد.

در PF-JSSP تعدادی مشخص از ماشین های چندمنظوره در سراسر کارگاه توزیع شده است که انعطاف پذیری و چندکاره بودن آن یکسان نیست. این ویژگی قادر می سازد که یک قطعه خاص حداقل توسط یک ماشین از میان مجموعه ماشین های موجود پردازش شود. در PF-JSSP، m ماشین برای پردازش n کار وجود دارد که هر کار j شامل nj عملیات می باشد که باید توسط ماشین های موجود انجام شود.

هر عملیاتOj,i می تواند روی تعدادی از ماشین های مشابه یا غیرمشابه پردازش شود و زمان پردازش می تواند براساس مشخصات ماشین متفاوت باشد. اصلی ترین هدف این تحقیق زمانبندی کارها و اختصاص آن ها به ماشین ها است بطوری که زمان اتمام کل7 یعنی مجموع زمان لازم برای انجام همهی کارها - که همهی کارها تمام شده اند - در آن ها به حداقل برسد. همگرایی به جواب بهینه بطوریکه حرکت کلی به سمت راه حل بهینه باشد و رسیدن به حداقل بار کاری8 و بار کاری ماشین بحرانی9 - حداکثر بار کاری - از دیگر اهداف این تحقیق می باشد.

مفروضات زیر برای مسئله در نظر گرفته شده است:

1.    کارها مستقل هستند و هیچ اولویتی در تخصیص کارها وجود ندارد.

2.    ماشین ها مستقل هستند.

3.    تمام ماشین ها در زمان صفر در دسترس هستند.

4.    زمان پردازش قطعی و مطلق است.

5.    زمان راه اندازی ماشین ها صرف نظر شده است.

6.    زمان انتقال بین عملیات صرفنظر شده است.

7.    هر ماشین ظرفیت پردازش یک عملیات در هر زمان را دارد.

8.    هر عملیات حداکثر در یک ماشین در یک زمان اجرا میشود.

9.    همپوشانی عملیات مجاز نیست.

.10 هیچ شکافی در زمان پردازش وجود ندارد.

. 11 تمام ماشین ها برای تمام مدت زمانبندی در دسترس هستند.

-3 ابزارها و روشها

در این بخش روشهای پایه برای پیاده سازی الگوریتم پیشنهادی به تفصیل بیان شده است.

-1-3 الگوریتم NEH-D

الگوریتم NEH-D توسعه یافته الگوریتمNEH10 میباشد که براساس انحراف معیار بهبود یافته است. NEH اکتشافی شامل دو مرحله است: در مرحله اول، کارها توسط مقدار نزولی از زمان پردازش خود طبقه بندی شدهاند و درمرحله دوم، دنباله کار، با ارزیابی زمانبندی نشات گرفته از برنامه اولیه ازفاز اول، به ترتیب ساخته میشود. در پیاده سازی، الگوریتم مرتب سازی پشته در فاز اول انتخاب شده است. برای درج کار در فاز دوم، کارهمیشه به موقعیت اول با زمان کل حداقل، اضافه میگردد.