بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
زمانبندي سيستم کار کارگاهي منعطف با درنظر گرفتن معيارهاي پايداري و پايايي به هنگام رخداد وقفه
بوسيله الگوريتم بهينه سازي جغرافياي زيستي
چکيده
اين مقاله به زمانبندي چند مرحله اي مسئله چند هدفه کار کارگاهي منعطف با در نظر گيري مفاهيم پايداري و پايايي در محيط وجود وقفه هايي از نوع شکست تصادفي ماشين ها مي پردازد. توابع هدف در نظر گرفته شده در اين تحقيق معيار پايداري و حداقل زمان تکميل برنامه مي باشند. از آنجا که مسئله زمانبندي کار کارگاهي منعطف ١ (FJSP) حتي در حالت کلاسيک خود در دسته مسائل NP-hard قرار مي گيرد، براي حل اين مسئله از يک الگوريتم فراابتکاري به نام جغرافياي زيستي ٢ (BBO) استفاده شده است . الگوريتم پيشنهادي شامل دو مرحله است . در مرحله اول ، هدف حداقل سازي زمان تکميل برنامه (makespan) با فرض قطعي بودن تمام اطلاعات و بدون وجود وقفه بهينه مي شود. مرحله دوم که يک تابع دو هدفه را بهينه مي سازد- که شامل دو معيار حداقل سازي زمان تکميل برنامه و پايداري است -و به بررسي زير مسئله هاي تخصيص ماشين ها و توالي عمليات با در نظر گرفتن شکست تصادفي ماشين پرداخته و براي توليد شکست از شبيه ساز استفاده شده است . در پايان نتايج بدست آمده از الگوريتم پيشنهادي و الگوريتم ژنتيک ارائه شده اند.
واژگان کليدي
الگوريتم جغرافياي زيستي(BBO)، زمان تکميل برنامه (makespan)، مسئله زمانبندي کار کارگاهي منعطف (FJSP)، پايداري ٣، پايايي ٤، شکست ماشين ٥، ميانگين زمان بين هر دو خرابي (MTBF)، ميانگين زمان تعمير(MTTR).
١. مقدمه
مسائل زمانبندي کار کارگاهي جزء پيچيده ترين مسائل ترکيبي هستند که در ادبيات به آن پرداخته شده است و تا اين اواخر، با فرض از پيش معين بودن تمام پارامترهاي مسئله مورد مطالعه قرار مي گرفتند. اگرچه ، چنين فرضي قادر به انعکاس رويدادهاي پيش بيني نشده سيستم هاي توليد واقعي نيست . بنابراين ، يک زمانبندي بهينه که بر اساس معيار هاي قطعي توليده شده ممکن است عملکرد ضعيف تري در يک سيستم کارگاهي واقعي ارائه نمايد (لئون و همکاران ٦ ١٩٩٤). به همين دليل تاکيد بيشتري متوجه زمانبندي هايي شد که مي توانند با عدم اطمينان ناشي از وقفه هاي تصادفي مقابله کنند. در حوزه زمانبندي در شرايط عدم قطعيت کارهاي متعددي انجام شده که همگي به مطالعه مسائل تک ماشين ٧ تصادفي ٨ با زمان هاي پردازش کار نامعلوم پرداختند. ليا و همکاران (b٢٠٠٧) با استفاده از الگوريتم تجزيه ، مسئله زمانبندي تک ماشين با شکست تصادفي ماشين مورد بررسي قرار دادند. لئون و همکاران (١٩٩٤) يک معيار پايايي مبتني برزمان شناوري براي تحليل اثر شکست ماشين ارائه نمودند. مهتا و يوزسوي ٩(١٩٩٨) يک الگوريتم مبتني بر نمايش گراف انفصالي براي يکپارچه سازي شکست هاي تصادفي ماشين ها ارائه کردند. شافعي و بران ١٠ (٢٠٠٠،١٩٩٩) از رويکرد زمان چرخشي به منظور دستيابي به پايايي زمانبندي کارگاه استفاده کردند. جنسن ١١(a ٢٠٠١ ،٢٠٠٣) پايايي و انعطاف پذيري زمانبندي کار کارگاهي را بهبود بخشيد و يک معيار سنجش پايايي بر اساس همسايگي معرفي نمود. پاليسلا و همکاران (٢٠٠٥،٢٠٠٤) يک فرآيند دو مرحله اي براي ايجاد زمانبندي منعطف پايا با سفارش بخشي معرفي نمودند و سرانجام ال - هيناي و المکوي ١٢ (٢٠١١) از يک الگوريتم ژنتيک هيبريدي براي دستيابي به يک زمانبندي کارکارگاهي منعطف پايدار و پايا با شکست تصادفي ماشين ها استفاده کردند. آنها نشان دادند که معيار پايداري آنها (رابطه ١) در مقايسه با ساير روشهاي موجود در ادبيات ، بهترين معيار پايداري بوده و همچنين پايايي را به ميزان تنزل makespan زمانبندي پس از مواجه با وقفه مربوط دانستند. در واقع هرچقدر اين ميزان کمتر باشد الگوريتم پاياتر است . در مقاله حاضر، معيارهاي پايداري و پايايي بصورت مذکور مورد استفاده قرار گرفته است .
(1)
که در آن نشان دهنده زمان تکميل عمليات j از کار i وP وR به ترتيب به معني پيشگويانه ١٣(زمانبندي قبل از شکست ) و واقعي ١٤(زمانبندي پس از شکست ) مي باشند.
الگوريتم BBO يک الگوريتم نشات گرفته شده از طبيعت است که البته تفاوتهاي عمده اي با الگوريتم هاي موجود جمعيتي و بر پايه طبيعت مثل GA يا PSO دارد. به عنوان مثال ، در اين الگوريتم اعضاي جمعيت اوليه از بين نمي روند بلکه تک به تک توسط مفهوم مهاجرت به روز مي شوند. همچنين در اين الگوريتم تابع برازندگي به طور مستقيم براي اصلاح جمعيت استفاده نمي شود، بلکه ميزان برازندگي در محاسبه نرخ مهاجرت ورودي و خروجي که دو تا از اصلي ترين اپراتورهاي BBO هستند به کار مي رود. در اين الگوريتم ، ايده مهاجرت گونه هاي زيستي١٥ که قسمتي از علم جغرافياي زيستي است براي حل مسائل بهينه سازي استفاده مي شود. الگوريتم BBO براي اولين بار توسط سيمون ١٦ (٢٠٠٨) ارائه شد که در اولين مقاله خود در اين زمينه ، تعاريف و مراحل اجرايي الگوريتم BBO را شرح داد. وي در کار بعدي خود (سيمون ، ٢٠٠٩) توسط نسخه اي ساده تر الگوريتم خود را بيشتر و ساده تر شرح داد و با استفاده از تئوري احتمالات بررسي هايي را روي الگوريتم انجام داد. او همچنين نشان داد که الگوريتم BBO با وجود درصدي جهش ميتواند الگوريتم GA را روي مسائل به کار برده شده مغلوب کند. از آن زمان مقالات مختلفي از BBO براي حل مسائل خود استفاده کردند و در نهايت رحمتي و زنديه (٢٠١١) به حل مسئله FJSP با استفاده از اين الگوريتم پرداختند.
نظر به آنچه بيان شد بر خلاف محيط هاي تک ماشين و کار کارگاهي کلاسيک ، زمانبندي کار کارگاهي منعطف اتفاقي ١٧ کمتر مورد توجه قرار گرفته و بر اساس بهترين اطلاعات در دسترس ، به غير از ال -هيناي و المکوي(٢٠١١) مطالعه اي در اين حوزه انجام نشده است . هدف اين مقاله دستيابي به يک زمانبندي پيشگويانه مي باشد که اثر شکست ماشين را روي عملکرد کل سيستم مانند حفظ زمان تکميل برنامه و افزايش ميزان پايداري زمانبندي حداقل نمايد. رويکرد مورد استفاده در اين مقاله ابتدا بوسيله ال - هيناي و المکوي (٢٠١١) براي حل مسئله FJSP توسعه داده شده و برخلاف آنها که تمام شکست هاي ممکن را بصورت يکپارچه در نظر گرفته اند، در تحقيق حاضر از الگوريتم شبيه ساز به منظور توليد تصادفي شکست ماشين استفاده شده که به واقعيت نزديک تر مي باشد. به منظور حل مسئله مذکور از الگوريتم بهينه سازي جغرافياي زيستي دو مرحله اي استفاده شده است . مرحله اول که در آن تمام داده هاي مورد بررسي قطعي بوده و هيچ وقفه اي رخ نخواهد داد، تابع اوليه کمينه سازي زمان تکميل برنامه را بهينه مي نمايد. مرحله دوم يک تابع دو هدفه را با تعيين توالي عمليات با شکست تصادفي ماشين ها در فضاي رمز گشايي بهينه مي سازد. در انتها نتايج حاصل از الگوريتم مذکور و مقادير بدست آمده از حل مسئله فوق با استفاده از الگوريتم ژنتيک ارائه . مقايسه شده است .
در ادامه در بخش ٢ فرضيات مسئله زمانبندي کارکارگاهي، تعاريف پايايي و پايداري، الگوريتم شبيه ساز شکست و توضيح مدل و الگوريتم BBO مورد استفاده در اين تحقيق ارائه شده است . در بخش ٣ به بيان يافته هاي تحقيق پرداخته و سرانجام در بخش ٤ بطور خلاصه به نتيجه گيري تحقيق انجام شده مي پردازيم .
٢. داده ها و روش شناسي تحقيق
٢-١. بيان مدل FJSP
مسئله زمانبندي کار کارگاهي منعطف مدل عمومي شده مسئله کلاسيک زمانبندي کار کارگاهي (JSP) است بوده و زماني شکل مي گيرد که مسيرهاي توليد جايگزين براي عمليات وجود داشته باشد. FJSP به صور حتم جزء مسائل NP-hard مي باشد زيرا علاوه بر زير مسئله تعيين توالي عمليات ، موظف به حل زير مسئله تخصيص مي باشد. همچنين افزودن عدم قطعيت مانند شکست تصادفي ماشين ها، اين مسئله را پيچيده تر خواهد نمود. در يک مسئله FJSP قطعي، n کار مستقل وجود دارند که با انديس i نمايش داده مي شوند و تمامي کارها در زمان صفر آماده شروع هستند. هر کار i ، عمليات دارد که توالي عمليات
آنها بصورت نمايش داده مي شود. M ماشين با انديس k داريم که هميشه بدون هيچ خرابي در دسترس
هستند. براي هر عمل ، يک مجموعه از ماشين ها با قابليت انجام آن کار وجود دارد (ماشين هاي قابل ١٨)که با نمايش داده مي شود و . زمان پردازش يک عمل روي ماشين k از پيش تعريف شده و با نمايش داده مي شود. زمان تنظيم هر عمل يک توالي مستقل است و در زمان پردازش آن گنجانده شده است . کار شروع شده قابل توقف نيست . هر ماشين در هر زمان حداکثر يک کار مي تواند انجام دهد. اولويت محدوديتهاي عمليات در يک کار مي تواند براي هر جفت از عمليات تعريف شود. هدف پيدا کردن يک زمان بندي با کمترين مقدار زمان تکميل کار است .
در محيط هاي توليدي واقعي، وقفه ها و رويدادهاي پيش بيني نشده رخ مي دهد. بنابراين ، يک زمانبندي ساخته شده بر پايه اطلاعات قطعي، غير کاربردي بوده و ممکن است منجر به عملکرد عملکرد ضعيف سيستم گردد. در اين تحقيق ، فرض شده که وقفه هاي تصادفي از نوع شکست ماشين با زمان رخداد و مدت تعمير نامعين در سيستم وجود دارد و به اين منظور از يک الگوريتم شبيه ساز شکست استفاده شده است .
٢-٢. پايداري و پايايي در مسائل زمانبندي
در ادبيات موضوع تعاريف مختلفي براي مفهوم پايداري و پايايي ارائه شده است . اما طبق تعريف جنسن (٢٠٠٣) که تمامي 19 تعاريف را در بر مي گيرد، زمانبندي پايا است که در هنگام مواجه با وقفه ها و در زمان استفاده از استرانژي انتقال به راست به عنوان الگوريتم زمانبندي مجدد، هزينه کمي به سيستم تحميل کند. همچنين تعاريف متفاوتي از مفهوم پايداري ارائه شده و در برخي از آنها انعطاف پذيري را در معناي مشابه پايداري استفاده شده است . کامل ترين تعريف موجود از زمانبندي پايدار ارائه شده توسط جنسن (a٢٠٠١) بيان مي کندکه زمانبندي پايدار است که در هنگام مواجه با وقفه ها و در زمان استفاده از متدهاي زمانبندي مجدد( بجز انتقال به راست )، خوب عمل کند.
٢-٣. مدل پيشنهادي
الگوريتم مورد استفاده در اين تحقيق شامل دو مرحله است . در مرحله الگوريتم BBO، تابع هدف حداقل سازي زمان تکميل برنامه را با فرض قطعي بودن تمام پارامتر هاي مساله بهينه مي سازد و پس از رسيدن به تعداد معيني از نسلها به مرحله دوم خواهد رفت . اين مرحله با گرفتن آخرين نسل مرحله اول به عنوان جمعيت اوليه آغاز و پس از اجراي الگوريتم شبيه ساز شکست روي آن به تعداد NB بار براي هر عضو از جمعيت ، به تعداد معيني از نسل ها تابع هدف را که ترکيب وزني کمينه سازي
makespan و معيار پايداري M٢ مي باشد بهينه مي کند. پس ازهر بار اعمال اپراتورهاي BBO موجه بودن جواب بررسي مي گردد. سپس ، الگوريتم شبيه ساز شکست براي تمام اعضاي هر نسل اجرا و بر اساس مقدار تابع برازش ، جمعيت مرتب شده و
بهترين فرد به عنوان جواب بهينه گزارش مي گردد. رابطه (٢)، تابع هدف مورد استفاده در مرحله دوم را نمايش مي دهد.
(2)
٢-٣-١. الگوريتم شبيه ساز شکست ماشين
از آنجا که شکست ماشين ها به شکل تصادفي رخ مي دهند، نيازمند يک شبيه ساز مي باشيم تا به ماشين ها اجازه توقف در
عمليات دهند. MTBF بيان کننده ميانگين زمانهاي بين هر دو خرابي و MTTR بيان کننده ميانگين مدت زمان تعميرمي
باشند که هر دو از توزيع نمايي پيروي مي کنند. مقدار انتخابي براي MTTR برابر است با ، و که در آن نشان دهنده ميانگين کل زمان پردازش يک کار است . مقدار MTBF بر اساس مقادير مختلفي که معيار Ag در يک شکست در مساله مي گيرد تعيين مي شود(MTTR+MTBF)Ag=MTTR. در واقع نشان دهنده سطح شکست کارگاه مي باشد(زنديه و غلامي٢٠٠٩). مدت زمان بين هر دو رخداد شکست به عنوان طول عمر ماشين در نظر گرفته شده و مدت زمان تعمير هر ماشين به زمان تکميل کار مربوطه افزوده خواهد شد.
٢-٣-٢. الگوريتم بهينه سازي جغرافياي زيستي (BBO)
در الگوريتم BBO هر منطقه زيستي ٢٠ به عنوان يک عضو منفرد شناخته مي شود و داراي شـاخص ميـزان مطلوبيـت زنـدگي٢١ HSI مخصوص به خود است . در اين الگوريتم جواب (منطقه زيستي) با HSI بالاتر نشان دهنده جواب خـوب مـي باشـد. در ايـن الگوريتم ، خواص از مناطق با HSI پايين ، با گرفتن خواص از مناطقي با HSI بالا، خود را شبيه آنها کرده و ارتقـاء مـي دهنـد.
دراين الگوي مهاجرت دو نوع عملگر وجود دارد، مهاجرت خروجي ٢٢ و مهاجرت ورودي ٢٣. مهاجرت خروجي بـراي جـوابي مطـرح مي شود که HSI بالايي دارد و خواص خود را به اشتراک مي گذارد و به طور مشابه مهاجرت ورودي براي جوابي مطرح مي شـود که HSI پاييني دارد و خواص را مي پذيرد. در حقيقت الگوريتم BBO به دنبال جواب هايي است کـه HSI را حـداکثر نماينـد.
قابل ذکر است که هر کدام از اين دو نوع مهاجرت نرخ خاص خود را دارند که با نام هاي نرخ ورود و نرخ خـروج شـناخته مي شوند(رحمتي و زنديه ،٢٠١١).
٢-٣-٢-١. رمزگذاري و رمز گشايي زيستگاه ها
اگرچه در اين الگوريتم هر فرد يک زيستگاه (منطقه زيستي) معرفي مي شود اما نمـايش و سـاختار يـک فـرد دقيقـا شـبيه يـک کروموزوم در GA است . در تحقيق حاضر از يک نمايش مبتني بر جايگشت ، استفاده شده است . نمايش مورد استفاده ، متشـکل از يک رشته شامل سه گانه (k, i, j) براي هر عمليات مي باشدکه در نهايت يک کروموزوم را تشکيل مي دهند، بطوريکه k نمايانگر ماشين تخصيص داده شده به عمليات ،i نشان دهنده کار جاري و j شماره تصاعدي عمليات در کار i است . درشـکل (٢) نمـايش شماتيک يک کروموزوم بر اساس جدول (١) آورده شده است .
