راه‌حل‌هاي موجود، به يافتن حل نزديك به بهينه مي‌پردازد كه از جمله آنها روش‌هاي فرا ابتكاري و تجزيه مسائل مي‌باشند كه در بسياري از تحقيقات جديد از روش‌هاي فرا ابتكاري مانند الگوريتم جستجوي ممنوع13، شبيه‌سازي تبريد14، الگوريتم ژنتيك، كلني مورچه‌ها15، جستجوي پراكنده16 و… جهت حل مسائل زمانبندي استفاده شده است. در بسياري از اين تحقيقات كارايي روش‌هاي مذكور به اثبات رسيده و مي‌توان نتيجه گرفت كه به شرط طراحي صحيح يك الگوريتم فرا ابتكاري مي‌توان به نتايج قابل توجهي جهت حل مسائل با ابعاد بالا دست يافت
مسئله جريان کارگاهي انعطاف پذير دو مرحله اي بدون وقفه
به طور کلي اين مدل حالت خاصي از مسئله جريان کارگاهي است. مسئله مورد مطالعه به شرح زير مي باشد. يک مجموعه شامل n کار است که قرار است پردازش شوند. هر کار نياز به دو عمليات دارد که بايد در دو مرحله متوالي و و بدون وقفه پردازش شوند. مرحله اول شامل ماشين يکسان و مشابه آن مرحله دو شامل ماشين يکسان است. اولين و دومين عمليات مربوط به کار بايد به ترتيب روي ماشين هاي مرحله اول و دوم با زمان هاي پردازش و و به ترتيب و بدون وقفه انجام شوند. اين مسئله را مي توانيم به صورت نمايش دهيم. مسئله مورد مطالعه در اين تحقيق به صورت شماتيک در شکل (1-2) نمايش داده شده است. همانطور که در شکل نيز ميبينيم هر کار حالت ممکن براي قرار گرفتن روي ماشين هاي مرحله اول و دوم دارد و همچنين n کار موجود حالت ممکن براي توالي دارند. به اين ترتيب در اين مسئله با توجه به ابعاد مسئله برنامه زماني مختلف مي توانيم داشته باشيم که تست کردن کليه اين برنامه ها بسيار سخت و پيچيده است. بنابراين هدف ما در گام اول ارائه يکي از برنامه هاي زماني در بينحالت مختلف است که کارايي مناسبي نيز نسبت به ساير الگوريتم هاي هيوريستيک موجود داشته باشد. و در گام دوم ارائه جواب هاي پارتو به اين منظور که تصميم گيرنده گزينه هاي بيشتري براي زمان بندي در اختيار داشته باشد.

نماي شماتيک مسئله
کاربردهاي مدل
مسائل زمان‌بندي بدون انتظار در آن دسته از محيط‌هاي توليدي رخ مي‌دهد كه در آن يك كار مي‌بايست از آغاز تا پايان بر روي يك ماشين يا در بين ماشينها بدون وقفه مورد پردازش قرار گيرد. علت وقوع چنين محيطهايي نوع فن‌آوري و يا فقدان توانايي ذخيره‌سازي بين ماشينها و ايستگاههاي كاري است. بطور نمونه عامل دما، غلظت و يا ديگر عوامل باعث مي‌شود هر عملياتي، عمليات پيش از خود را بلافاصله دنبال كند. در توليد فولاد، هنگامي كه فولاد مذاب در برابر يكسري عمليات متوالي مانند ريخته‌گري، ذوب و نورد قرار مي‌گيرد. چنين وضعيتي رخ مي‌دهد،. همچنين در صنايع غذايي، عمليات قرار دادن محصولات غذايي داخل قوطي هاي کنسرو بايد بلافاصله بعد از پخت انجام شود تا از تازه بودن اين محصولات اطمينان حاصل نمائيم. در صنايع دارويي، شيميايي، پتروشيمي و صنايع خدماتي و… چنين مواردي رخ مي‌دهد. محيط‌هاي توليدي جديد مانند توليد به هنگام17، سيستمهاي توليدي انعطاف‌پذير18 و سلولهاي روباتيك فرآيند توليدي منطبق با مسايل زمان‌بندي بدون انتظار را فراهم مي‌كنند.
بيان مسئله و سوال تحقيق
در اين تحقيق، مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه با هدف تعيين توالي توليد بهينه (نزديک بهينه) با توجه به اهداف کمينه سازي و بيشينه سازي مورد بررسي قرار مي گيرد. هم چنين، ارائه الگوريتم هاي کارا و مبتني بر رويکرد هاي ابتکاري و فراابتکاري در دستور کار قرار گرفته است که با استفاده از آن بتوان به مجموعه جواب هاي مناسب رسيد.
ضرورت انجام تحقيق و اهميت تحقيق
با توجه به کاربردهاي عنوان شده براي مسئله برنامه زمان بندي جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه از يک طرف و تحقيقات بسيار محدود انجام شده در اين زمينه از طرف ديگر، ضروري است تحقيقات بيش تري با هدف ارائه روش هاي کاراتر انجام پذيرد. از اين رو، اين موضوع به عنوان موضوع تحقيقي مورد نظر اين پايان نامه در نظر گرفته شده است.
اهداف تحقيق
به طور کلي اهداف اصلي اين تحقيق به شرح زير مي باشد:
گسترش مدل و سازگار نمودن هرچه بيش تر آن با مسائل دنياي واقعي با درنظر گرفتن چندين تابع هدف و در نظر گرفتن محدوديت زمان در دسترس بودن کارها
ارائه الگوريتم هاي ابتکاري براي مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
اتخاذ رويکردي فراابتکاري در حل مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
پيش بيني ماکزيمم زمان انجام کارها در مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه به منظور تخصيص منطقي زمان هاي موعد تحويل توسط شبکه عصبي فازي تطبيق پذير
حل مسئله چند هدفه جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه
ساختار انجام تحقيق
اين پايان نامه، با بررسي پيشينه و مطالعات صورت گرفته در رابطه مدل تحقيق، به تعيين خلاء هاي موجود در اين زمينه پرداخته و مسئله توسط روش هاي ابتکاري با در نظر گرفتن چندين تابع هدف (به صورت تک هدفه) و اضافه نمودن محدوديت زمان آماده به کار حل مي شود. در ادامه مسئله توسط روش هاي فراابتکاري الگوريتم ژنتيک هيبريدي و الگوريتم شبيه سازي تبريد هيبريدي حل مي شود. نتايج حاصله از الگوريتم ابتکاري و فرا ابتکاري با الگوريتم هاي ارائه شده در مطالعات قبلي مقايسه مي شود.. شکل (1-3) ساختار تحقيق را به صورت شماتيک نش
ان مي دهد.

ساختار تحقيق به صورت شماتيک

ساختار پايان نامه به شرح زير مي باشد:
در فصل اول، کليات تحقيق بيان شده ، مساله مورد مطالعه تعريف شده و اهدف تحقيق به تفصيل توضيح داده مي شود. در فصل دوم، ادبيات موضوع مرتبط با مساله تحقيق مرور شده و توانمندي روش هاي استفاده شده مورد تجزيه و تحليل قرار مي گيرد. در فصل سوم،حل مساله به صورت تک هدفه مد نظر مي باشد. هفت الگوريتم هاي ابتکاري پيشنهاد شده و نتايج حاصله در ادامه فصل آورده شده است. در فصل چهارم الگوريتم هاي فراابتکاري ژنتيک هيبريدي و شبيه سازي تبريد هيبريدي براي مساله مورد مطالعه، معرفي مي شوند و نتايج هر يک از آنها در ادامه فصل آورده شده است. در فصل پنجم به منظور تخصيص موعد هاي تحويل منطقي براي کارها، مدل عصبي فازي تطبيق پذير به منظور پيش بيني ماکزيمم زمان اتمام کارها معرفي شده است و نتايج حاصل از مقايسه اين مدل پيشنهادي با رگرسيون خطي در ادامه فصل براي برخي معيارهاي ارزيابي عملکرد در پيش بيني آورده شده است. در فصل ششم حل مساله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه چند هدفه با در نظر گرفتن توابع مينيمم سازي ماکزيمم زمان اتمام کارها و مينيمم سازي ماکزيمم تاخير کارها مورد مطالعه قرار گرفته شده و 3 رويکرد متفاوت در تابع برازندگي با استفاده از الگوريتم شبيه سازي تبريد براي اين مساله معرفي شده است و در انتهاي فصل نتايج حاصل از مقايسه ميان رويکرد هاي پيشنهادي آورده شده است. و در نهايت ، فصل هفتم، خلاصه و جمع بندي تحقيق انجام شده را بيان مي کند و پيشنهادهايي براي تحقيقات آتي ارائه مي شود.
جمع بندي
در اين فصل، مسئله زمان بندي جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه به عنوان مسئله تحقيق معرفي، و ضرورت انجام تحقيق در اين خصوص بيان شد. با توجه به ساختار و سطح پيچيدگي مسئله انتخابي، رو ش هاي پيشنهادي جهت حل مسئله به همراه ساختار انجام تحقيق مطرح گرديد. در فصل بعد، تحقيقات انجام شده مرتبط با موضوع تحقيق بحث و بررسي خواهد شد.

مرور ادبيات و پيشينه تحقيق

مقدمه
در اين فصل به مرور ادبيات و بررسي پيشينه تحقيق، پرداخته مي شود. تحقيقات انجام شده پيرامون مسئله تحقيق بررسي شده و خلاء تحقيقاتي موجود معرفي مي گردد.
مساله تک هدفه جريان کارگاهي بدون وقفه
مسائل زمان‌بندي جريان كارگاهي
در اين بخش تاريخچه خلاصه‌اي از كارهاي صورت گرفته مسائل در زمان‌بندي جريان كارگاهي و همچنين تاريخچه‌اي از تحقيقات صورت گرفته در مسائل جريان كارگاهي انعطاف‌پذير و روشهايي كه براي حل اين مسائل به كار رفته است، مرور خواهيم كرد.

مسئله جريان كارگاهي ساده
اين مسئله يكي از رايج‌ترين انواع مسائل جريان كارگاهي است كه در مرور ادبيات موضوع جريان كارگاهي به وفور ديده مي‌شود. در سال 1954 جانسون [8] يك الگوريتم براي حل مسئله دو ماشينه جريان كارگاهي كه بدون هيچ‌گونه محدوديتي بوده ارائه نمود. از آن موقع به بعد كارهاي زيادي در اين حوزه انجام گرفته و كه شامل الگوريتم‌هاي ابتكاري، الگوريتم‌هاي دقيق براي چندين مسئله با ابعاد گوناگون و محدوديت‌هاي متنوع مي‌باشند. ثابت شده است كه مسئله با تعدناد ماشين‌هاي بيشتر يا مساوي با 3 يك مسئله Np-hard مي‌باشد. كارهاي بسيار زيادي در اين حوزه صورت گرفته ولي با توجه به اينكه تحقيق انجام شده از طرف ما بصورت مستقيم به اين مسئله مربوط نمي‌شود مرور ادبيات موضوع مربوط به مسائل جريان كارگاهي را به خوانندگان اين پژوهش‌ واگذار مي‌نمائيم. براي مطالعه بيشتر در اين خصوص به منبع [9] مراجعه فرمائيد.
مسئله جريان كارگاهي انعطاف‌پذير
اين مسئله در ادبيات موضوع معمولاً تحت عنوان مسئله جريان كارگاهي با ماشين‌هاي موازي و يا مسئله جريان كارگاهي هيبريدي نيز شناخته مي‌شود. مسئله جريان كارگاهي انعطاف پذير در واقع حالت عمومي مسئله جريان كارگاهي است با اين تفاوت كه m ماشين به صورت موازي تبديل به S مرحله به صورت موازي مي شود که در هر مرحله تعدادي ماشين به صورت موازي موجود است. مرور ادبيات موضوع مربوط به مسائل جريان كارگاهي انعطاف پذير در منبع [11،10] به طور مفصل شرح داده شده است. خلاصه‌اي كارهاي انجام شده با استفاده از روشهاي حل متعدد در ادامه ارائه شده است.
الف ) مسئله جريان كارگاهي انعطاف‌پذير دو مرحله‌اي
آرتاناري و راماسوامي 19[12] اولين بار مسئله جريان كارگاهي انعطاف‌پذير دو مرحله‌اي را معرفي نمودند. آنها حالت خاصي از اين مسئله را كه در مرحله اول و در مرحله دوم بود براي 10 كار با استفاده از روش شاخه و كران حل نمودند. اين مسئله توسط محققان ديگري نيز مورد مطالعه قرار گرفته است. [14،13]
گوپتا20 [13] استفاده از قاعده جانسون را براي تخصيص دادن كار به ترتيب در مرحله‌ اول و بعد از انجام مرحله اول آن در مرحله دوم پيشنهاد داد. بلازويچ و همكاران21 [14] نشان دادند كه مي‌توان اثبات كرد كه استفاده از قاعده جانسون و يا قاعده بزرگترين زمان پردازش به طي منجر مي‌شود كه يا جواب بهينه است و يا نزديك به جواب بهينه مي‌باشد.
ناراسيمهان و پانواكر22 [15] حالتي كه در آن چندين ماشين موازي در مرحله اول و چندين ماشين با سرعت‌هاي متفاوت در مرحله دوم وجود دارند را مورد بررسي قرار دادند. آنها يك الگوريتم ابتكاري ارائه دادند كه
در هر تكرار از ميان كارهاي زمان‌بندي نشده، كارهايي كه افزايش مجموع زمان‌هاي بيكاري و انتظار ميان مراحل را مينيمم مي‌كند، يكي را انتخاب مي‌كنند.
وس23 [16] يك متدلوژي براي حل مسئله جريان كارگاهي دو مرحله‌اي با زمان‌هاي آماده‌سازي وابسته ارائه داد كه در تحقيق وي تعداد ماشين‌هاي مرحله دوم يك عدد بود. او از الگوريتم جستجوي ممنوع براي بهبود جواب‌ها استفاده نمود. جاينت و همكاران24 [17] مسئله جريان كارگاهي انعطاف‌پذير دو مرحله‌اي را بصورت يك مسئله برنامه‌ريزي اعداد صحيح مختلط فرمول‌بندي كردند و سه حد پائين براي پيش‌بيني جواب بهينه ارائه دادند. در روش آنها ابتدا توالي به دست آمده و سپس عمل تخصيص به ماشين‌ها صورت مي‌گيرد.
ب ) مسئله جريان كارگاهي انعطاف‌پذير چند مرحله‌اي

مسئله جريان كارگاهي چند مرحله‌اي انعطاف‌پذير شامل تعدادي مرحله‌ است كه در هر مرحله 1 يا بيشتر از 1 ماشين موازي وجود دارند (حداقل يكي از مراحل بايد بيشتر از يك ماشين داشته باشد) از انجائي كه در اكثر حالت‌هاي دنياي واقعي با اينگونه مسائل روبرو هستيم اين مسئله مورد توجه بسياري از محققان قرار گرفته است. با توجه به اينكه اين مسئله جزو مسائل NP-hard در حوزه مسائل زمان‌بندي است تكنيكهاي تقريبي و روشهاي حل فراواني براي اينگونه مسائل ارائه شده است.
براه و هانساكر25 [18] و راجندران و چادهوري26 [19] الگوريتم‌هاي شاخه و كران براي مسئله ارائه دادند. هر دو تحقيق فقط قادر به حل مسائل با سايز كوچك هستند. پورتمن و همكاران27 [20] هم روي همين مسئله مطالعه نمودند. آنها حد پائين ارائه شده توسط براه و هانساكر را بهبود دارند و تعداد شاخه‌هايي كه در درخت جستجو استفاده مي‌شد را كاهش دادند. آنها همچنين از الگوريتم ژنتيك براي بهبود فرايند جستجو استفاده نمودند. نتايج محاسباتي آنها نشان داد كه جواب بهينه‌اي كه از الگوريتم شاخه و كران بدست مي‌آمد در اكثر حالات الگوريتم ژنتيك نيز به آن مي‌رسد. به طوري كه فقط در %3 نتايج با روش شاخه و‌كران اختلاف داشت.
مدل‌هاي زمان‌بندي جريان كارگاهي بدون وقفه
جريان كارگاهي بدون وقفه
در سالهاي اخير علاقه بسياري از محققان به سوي مسائل بدون وقفه معطوف شده است.اين علاقه بيشتر از كاربردهاي اين مسائل در صنعت ناشي مي‌شود. يك مسئله زمان‌بندي بدون وقفه، در محيط‌هاي توليدي اتفاق مي‌افتد كه يك كار از ابتدا تا انتهاي مراحل پردازش بايد بدون وقفه روي ماشين‌ها قرار بگيرد و مراحل پردازش آن پشت سرهم و بدون هيچ‌گونه تاخيري انجام گيرد. به عبارت ديگر تفاوت ميان زمان اتمام هر كار و زمان شروع هر كار در محيط‌هاي توليدي بدون وقفه برابر مجموع زمان‌هاي پردازش مي‌باشد.
در بسياري از صنايع براي مثال در صنايع شيميايي و پتروشيمي، صنايع فولاد، صنعت شيشه و صنايع مرتبط با كاغذ در فرآيند توليد يك محدوديت وجود دارد. هنگامي كه زمان پردازش يك كار شروع مي‌شود فرآيندهاي بعدي بايد بدون تاخير از يك ماشين به ماشين بعد انجام شوند. حتي در صورت لزوم شروع كار در مرحله قبل بايد به اندازه‌اي به تاخير بيفتد كه فرآيندهاي بعدي بدون تاخير آغاز شوند. اين نوع از مسائل به اصطلاح، جريان کارگاهي بدون وقفه28 و يا جريان کارگاهي انتظار صفر29 ناميده مي شوند. يكي از دو دليل اصلي بروز اين گونه مسائل (بدون وقفه) در محيط‌هاي توليدي به ماهيت فرايندها و ماهيت تكنولوژي به كار گرفته شده، باز مي‌گردد. در بعضي از فرايندها، براي جلوگيري از تغييرات نامطلوب در مواد دما يا خصوصيات ديگر مواد (مثلا چسبندگي) نياز به انجام كارها به صور


دیدگاهتان را بنویسید