بخشی از مقاله
چکیده
در دهه های اخیر توجه اکثر محققان به مسئله کار کارگاهی انعطاف پذیر و استفاده از آن در دنیای صنعت می باشد همچنین در اکثر مدلهای زمان بندی کار کارگاهی انعطاف پذیر فرض بر این است که ماشین ها در تمام اوقات در دسترس هستند و زمان های حمل و نقل نادیده گرفته میشود در حالیکه دو مورد از مفروضات واقع بینانه در زمینه زمانبندی در نظر گرفتن محدودیت نگهداری و تعمیرات و زمان های حمل و نقل کارها بین ماشین ها می باشد. در این پژوهش به بررسی روش حل مسائل کار کارگاهی انعطاف پذیر با در نظر گرفتن محدودیت نگهداری و تعمیرات و زمان های حمل نقل در جهت بدست آوردن بهترین حالت توالی کارها و بهترین تخصیص ماشینها و با در نظر گرفتن معیارهای زمان تکمیل کل عملیاتها ، زمان انجام عملیات در ماشین بحرانی ، مجموع زمان تاخیرات کارها و با هدفی جدید به نام کمینه سازی بیشترین تعداد تعویض قالبهای همزمان پرداخته می شود. در ابتدا مساله را به صورت یک مدل ریاضی فرموله کرده ایم. به دلیل پیچیدگی مسئله و اثبات NP-HARD بودن آن در ادبیات دو××الگوریتم× ژنتیک مرتب سازی نامغلوب و الگوریتم ژنتیک رتبه بندی نامغلوب را×توسعه×داده شده است.×در×پایان ×به×وسیله× توسعه چند مسئله از مدل مربوطه،×عملکرد الگوریتم×های×ارائه×شده را به صورت آماری مقایسه شده است؟نتایج موید این قضیه می باشد که الگوریتم ژنتیک مرتب سازی نامغلوب نتایج قابل قبولتری را برای این مسئله به ارمغان می آورد.
کلمات کلیدی: مسئله کار کارگاهی انعطاف پذیر، الگوریتم ژنتیک مرتب سازی نامغلوب - NSGA-II - ، الگوریتم ژنتیک رتبه بندی نامغلوب - - NRGA، محدودیت نگهداری و تعمیرات، زمانهای حمل و نقل ، بیشترین تعداد تعویض قالبهای همزمان
-1 مقدمه
بازار رقابتی امروز به سمت تولید محصولات متنوعتر گام بر داشته که این تحول منجر به ایجاد تجهیزات انعطاف پذیر شده است همچنین تنها تجهیزات انعطاف پذیر جوابگوی محیط رقابتی نمی باشد و نیاز به برنامه ریزی انعطاف پذیر نیز دارند . براکرو و اسچیل [1] برای اولین بار مسائل کارکارگاهی انعطاف پذیر را معرفی کرده اند. در ادبیات تحقیق، اکثر مقالات به ارائه روش های حل برای مسئله مذکور پرداخته اند .در این میان، برخی از مطالعات، این دو زیر مسئله را به صورت جداگانه بهینه سازی کرده اند. این رویکرد به رویکرد سلسله مراتبی معروف است و درآن یک مسئله پیچیده به دو زیر مسئله ساده تر تقسیم می شود .براندی مارت [2] نخستین فردی بود که از تجزیه i در بهینه سازی مسئله زمانبندی کار کارگاهی منعطف استفاده نمود. او زیر مسئله مسیر یابی - مسئله تخصیص - را با استفاده از قوانین توزیع موجود حل نمود و سپس بر زیر مسئله زمان بندی تمرکز کرد و از روش ابتکاری جستجوی ممنوع i i بهره برد. بارنز و چمبرز [3] از الگوریتم جستجوی ممنوعه برای حل این مسئله استفاده نمودند. هارینک و دستیارانش [4 ] - 1994 - الگوریتم جستجوی ممنوعه را برای حل مسئله کار کارگاهی انعطاف پذیر استفاده نمودند. چن و همکارانش [5] یک الگوریتم ژنتیک i i iبرای مسئله زمان بندی کار کارگاهی انعطاف پذیر طراحی نمودند .
آن ها یک نمایش کروموزومi v جواب را به دو بخش تقسیم کردند، اولین بخش مربوط به تخصیص عملیات ها به ماشین ها - سیاست مسیر یابی - را معین می نمود و دومین بخش توالی عملیات ها را بر روی هر ماشین مشخص می نمود. ماسترولیلی و گامبوردلا [6] الگوریتم جستجوی ممنوعه برای حل مسئله زمان بندی کار کارگاهی انعطاف پذیر طراحی نمودند. کاسم و همکارانش [7] یک الگوریتم ژنتیک کنترل شده به وسیله یک مدل تخصص یافته برای این مسئله بهبود دادند. آن ها از بهینه سازی مبتنی بر نگرش پارتو که حاصل تلفیق منطق فازی و الگوریتم های تکاملی بود استفاده کردند. آن ها از نمایش کرومزومی استفاده نمودند که اطلاعات تخصیص و توالی را با هم ترکیب کند و رویکردی را با عنوان محلی سازی طراحی کردند تا تخصیص های اولیه مناسب را پیدا نماید. سپس از قوعد توزیع در تعیین توالی عملیات استفاده نمودند. همچنین از عملگرهای تقاطع و جهش مناسب برای بهبود جواب استفاده کردند. سعیدی مهرآباد و فتاحی [8] یک الگوریتم جستجوی ممنوع را برای حل مسئله کار کارگاهی انعطاف پذیر با هدف کمینه سازی زمان تکمیل کارها پیشنهاد دادند.
گائو و همکاران[9] مسئله کار کارگاهی انعطاف پذیر را تحت نگهداری و تعمیرات پیشگیرانه v با فرض اینکه فعالیت های تعمیراتی می توانند در طول یک بازه زمانی تعیین شده از قبل صورت پذیرند مورد بررسی قرار دادند و با سه تابع هدف کمینه سازی زمان تکمیل کارها، کمینه سازی بیشترین حجم کار ماشین و کمینه سازی مجموع حجم کاری روی ماشین ها مورد پژوهش قرار دادند و یک الگوریتم ژنتیک تلفیقی با جستجوی محلی برای حل مسئله پیشنهاد نمودند. نادری و همکاران [10] مسئله زمانبندی کارگاه جریانی را با زمان های توالی و حمل و نقل مورد بررسی قرار داده اند . در این پژوهش یک سیستم انتقال دهنده با بافرهای نامحدود بین هر دو ماشین در نظر گرفته شده است. یزدانی و همکاران [11] vi الگوریتم VNS موازی - PVNS - را جهت این مسئله توسعه دادند. در این الگوریتم ها در عملکرد جستجویی شبیه به الگوریتم شبیه سازی تبرید ، ساختارهای مختلف همسایگی با نظم خاصی وارد فرایند جستجو شده تا الگوریتم را در گیر کردن در بهینه های محلی نجات دهد. وانگ و یو [12] مسئله زمان بندی کار کارگاهی انعطاف پذیر را تحت نگهداری و تعمیرات پیشگیرانه در دو حالت مورد پژوهش قرار دادند.
در حالت اول زمان های انجام فعالیتهای تعمیراتی می تواند در طول یک بازه زمانی از پیش تعیین شده متغییر باشد و در حالت دوم زمان های فعالیتهای نگهداری و تعمیرات از قبل معین و ثابت است. آن ها برای اولین بار محدودیت منابع تعمیراتی vi i را در طول افق برنامه ریزی برای این مسئله مورد بررسی قرار دادند. رحمتی و زندیه [13] vi i i الگوریتم بهینه سازی بر پایه بایو جغرافیای زیستی - BBO - i x را برای حل این مسئله ارائه نمودند. در این الگوریتم اصول مهاجرت گونه های زیستی مبنای فرایند بهینه سازی می باشد. رحمتی و همکاران [14] دو الگویتم چند هدفه NSGAIIx و NRGAxi را برای مسئله کار کارگاهی چند هدفه توسعه دادند. احمدی و همکاران [15] زمانبندی در محیط کار کارگاهی انعطاف پذیر با تایع هدف چند گانه تحت شرایط خرابی تصادفی ماشین ها را مورد بررسی قرار دادند.
یزدانی و همکاران [16] مسئله کار کارگاهی انعطاف پذیر را همراه با محدودیت های نیروی انسانی و ماشین مدلسازی کردند و توسط دو الگوریتم SAxi i و VDOxiii حل نمودند که از الگوریتم VDO نتایج بهتری برای این مسئله بدست آورد. کریمی و همکاران [17] مدلسازی کار کارگاهی انعطاف پذیر را با زمان های حمل و نقل و با فرض نامحدود بودن وسایل نقلیه را با استفاده از الگوریتم رقابت استعماری مورد بررسی قرار دادند. در این پژوهش به بررسی روش حل مسائل کار کارگاهی انعطاف پذیر با در نظر گرفتن محدودیت نگهداری و تعمیرات و زمان های حمل نقل در جهت بدست آوردن بهترین حالت توالی کارها و بهترین تخصیص ماشینها می پردازیم.
در ابتدا مساله را به صورت یک مدل ریاضی فرموله خواهیم کرد همچنین ما از معیارهای زمان تکمیل کل عملیاتها ، زمان انجام عملیات در ماشین بحرانی ، مجموع زمان تاخیرات کارها و با هدف جدیدی به با عنوان کمینه سازی بیشترین تعداد تعویض قالبهای همزمانxi v به عنوان معیارهایی جهت ارزیابی استفاده خواهیم نمود. اما قابل پیش بینی است که حل دقیق مساله، در اندازه های کوچک قابل اجرا باشد و به دلیل پیچیدگی مسئله و اثبات NP-HARD بودن آن در ادبیات مسئله ،برای حل از الگوریتمهای فراابتکاری چند هدفه استفاده خواهیم نمود از آنجا که خروجی الگوریتم های فرا ابتکاری به شدت وابسته به ورودی های الگوریتم می باشد برای تنظیم پارامترهای الگوریتم توسعه داده شده از متدولوژی رویه پاسخ - RSM - استفاده می نمائیم. در نهایت برای اثبات عملکرد مناسب روش های حل ارائه شده در مدل های مربوطه، این روش ها بر روی مسائل آزمایشی تولید شده با ابعاد مختلف مورد تجزیه و تحلیل قرار خواهد گرفت و به مقایسه آماری الگوریتم ها خواهیم پرداخت.
-1-2 فرضیات مسئله
1. هر وسیله حمل و نقل توانایی حمل تنها یک کار را در هر زمان مشخص دارد.
2. زمان های نگهداری و تعمیرات توسط یک پنجره زمانی از پیش تعیین شده ایی مشخص شده اند.
3. ماشین ها توانایی انجام هیچ کاری را در زمان نگهداری و تعمیرات آن ماشین ندارند.
4. زمان آماده سازی ماشین نادیده گرفته شده است.
5. زمان پردازش هر عملیات وابسته به ماشینی است که روی آن انجام می شود. در واقع زمان انجام یک عملیات توسط ماشین های مختلف می تواند متفاوت باشد.
6. زمان حمل و نقل وابسته به نوع وسیله حمل و نقل ونوع کار و همچنین ماشین هایی که حمل و نقل بین آن ها صورت می پذیرد می باشد
7. تعمیرات و نگهداری برای وسایل حمل و نقل در نظر گرفته نشده است.
8. تعداد کارها و ماشین ها و وسایل حمل و نقل مشخص می باشد. با توجه به موارد گفته شده مدل این مسئله به صورت زیر قابل ارائه است.
-2-2 نمادها
