منابع پایان نامه با موضوع
حل مسئله

منابع پایان نامه با موضوع حل مسئله

آذر ۷, ۱۳۹۷ 0 By admin3

ح داده مي شود. در فصل دوم، ادبيات موضوع مرتبط با مساله تحقيق مرور شده و توانمندي روش هاي استفاده شده مورد تجزيه و تحليل قرار مي گيرد. در فصل سوم،حل مساله به صورت تک هدفه مد نظر مي باشد. هفت الگوريتم هاي ابتکاري پيشنهاد شده و نتايج حاصله در ادامه فصل آورده شده است. در فصل چهارم الگوريتم هاي فراابتکاري ژنتيک هيبريدي و شبيه سازي تبريد هيبريدي براي مساله مورد مطالعه، معرفي مي شوند و نتايج هر يک از آنها در ادامه فصل آورده شده است. در فصل پنجم به منظور تخصيص موعد هاي تحويل منطقي براي کارها، مدل عصبي فازي تطبيق پذير به منظور پيش بيني ماکزيمم زمان اتمام کارها معرفي شده است و نتايج حاصل از مقايسه اين مدل پيشنهادي با رگرسيون خطي در ادامه فصل براي برخي معيارهاي ارزيابي عملکرد در پيش بيني آورده شده است. در فصل ششم حل مساله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه چند هدفه با در نظر گرفتن توابع مينيمم سازي ماکزيمم زمان اتمام کارها و مينيمم سازي ماکزيمم تاخير کارها مورد مطالعه قرار گرفته شده و ۳ رويکرد متفاوت در تابع برازندگي با استفاده از الگوريتم شبيه سازي تبريد براي اين مساله معرفي شده است و در انتهاي فصل نتايج حاصل از مقايسه ميان رويکرد هاي پيشنهادي آورده شده است. و در نهايت ، فصل هفتم، خلاصه و جمع بندي تحقيق انجام شده را بيان مي کند و پيشنهادهايي براي تحقيقات آتي ارائه مي شود.
جمع بندي
در اين فصل، مسئله زمان بندي جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه به عنوان مسئله تحقيق معرفي، و ضرورت انجام تحقيق در اين خصوص بيان شد. با توجه به ساختار و سطح پيچيدگي مسئله انتخابي، رو ش هاي پيشنهادي جهت حل مسئله به همراه ساختار انجام تحقيق مطرح گرديد. در فصل بعد، تحقيقات انجام شده مرتبط با موضوع تحقيق بحث و بررسي خواهد شد.
مرور ادبيات و پيشينه تحقيق
مقدمه
در اين فصل به مرور ادبيات و بررسي پيشينه تحقيق، پرداخته مي شود. تحقيقات انجام شده پيرامون مسئله تحقيق بررسي شده و خلاء تحقيقاتي موجود معرفي مي گردد.
مساله تک هدفه جريان کارگاهي بدون وقفه
مسائل زمان‌بندي جريان كارگاهي
در اين بخش تاريخچه خلاصه‌اي از كارهاي صورت گرفته مسائل در زمان‌بندي جريان كارگاهي و همچنين تاريخچه‌اي از تحقيقات صورت گرفته در مسائل جريان كارگاهي انعطاف‌پذير و روشهايي كه براي حل اين مسائل به كار رفته است، مرور خواهيم كرد.
مسئله جريان كارگاهي ساده
اين مسئله يكي از رايج‌ترين انواع مسائل جريان كارگاهي است كه در مرور ادبيات موضوع جريان كارگاهي به وفور ديده مي‌شود. در سال ۱۹۵۴ جانسون [۸] يك الگوريتم براي حل مسئله دو ماشينه جريان كارگاهي كه بدون هيچ‌گونه محدوديتي بوده ارائه نمود. از آن موقع به بعد كارهاي زيادي در اين حوزه انجام گرفته و كه شامل الگوريتم‌هاي ابتكاري، الگوريتم‌هاي دقيق براي چندين مسئله با ابعاد گوناگون و محدوديت‌هاي متنوع مي‌باشند. ثابت شده است كه مسئله با تعدناد ماشين‌هاي بيشتر يا مساوي با ۳ يك مسئله Np-hard مي‌باشد. كارهاي بسيار زيادي در اين حوزه صورت گرفته ولي با توجه به اينكه تحقيق انجام شده از طرف ما بصورت مستقيم به اين مسئله مربوط نمي‌شود مرور ادبيات موضوع مربوط به مسائل جريان كارگاهي را به خوانندگان اين پژوهش‌ واگذار مي‌نمائيم. براي مطالعه بيشتر در اين خصوص به منبع [۹] مراجعه فرمائيد.
مسئله جريان كارگاهي انعطاف‌پذير
اين مسئله در ادبيات موضوع معمولاً تحت عنوان مسئله جريان كارگاهي با ماشين‌هاي موازي و يا مسئله جريان كارگاهي هيبريدي نيز شناخته مي‌شود. مسئله جريان كارگاهي انعطاف پذير در واقع حالت عمومي مسئله جريان كارگاهي است با اين تفاوت كه m ماشين به صورت موازي تبديل به S مرحله به صورت موازي مي شود که در هر مرحله تعدادي ماشين به صورت موازي موجود است. مرور ادبيات موضوع مربوط به مسائل جريان كارگاهي انعطاف پذير در منبع [۱۱،۱۰] به طور مفصل شرح داده شده است. خلاصه‌اي كارهاي انجام شده با استفاده از روشهاي حل متعدد در ادامه ارائه شده است.
الف ) مسئله جريان كارگاهي انعطاف‌پذير دو مرحله‌اي
آرتاناري و راماسوامي ۱۹[۱۲] اولين بار مسئله جريان كارگاهي انعطاف‌پذير دو مرحله‌اي را معرفي نمودند. آنها حالت خاصي از اين مسئله را كه در مرحله اول و در مرحله دوم بود براي ۱۰ كار با استفاده از روش شاخه و كران حل نمودند. اين مسئله توسط محققان ديگري نيز مورد مطالعه قرار گرفته است. [۱۴،۱۳]
گوپتا۲۰ [۱۳] استفاده از قاعده جانسون را براي تخصيص دادن كار به ترتيب در مرحله‌ اول و بعد از انجام مرحله اول آن در مرحله دوم پيشنهاد داد. بلازويچ و همكاران۲۱ [۱۴] نشان دادند كه مي‌توان اثبات كرد كه استفاده از قاعده جانسون و يا قاعده بزرگترين زمان پردازش به طي منجر مي‌شود كه يا جواب بهينه است و يا نزديك به جواب بهينه مي‌باشد.
ناراسيمهان و پانواكر۲۲ [۱۵] حالتي كه در آن چندين ماشين موازي در مرحله اول و چندين ماشين با سرعت‌هاي متفاوت در مرحله دوم وجود دارند را مورد بررسي قرار دادند. آنها يك الگوريتم ابتكاري ارائه دادند كه در هر تكرار از ميان كارهاي زمان‌بندي نشده، كارهايي كه افزايش مجموع زمان‌هاي بيكاري و انتظار ميان مراحل را مينيمم مي‌كند، يكي را انتخاب مي‌كنند.
وس۲۳ [۱۶] يك متدلوژي براي حل مسئله جريان كارگاهي دو مرحله‌اي با زمان‌هاي آماده‌سازي وابسته ارائه داد كه در تحقيق وي تعداد ماشين‌هاي مرحله دوم يك عدد بود. او از الگوريتم جستجوي ممنوع براي بهبود جواب‌ها استفاده نمود. جاينت و همكاران۲۴ [۱۷] مسئله جريان كارگاهي انعطاف‌پذير دو مرحله‌اي را بصورت يك مسئله برنامه‌ريزي اعداد صحيح مختلط فرمول‌بندي كردند و سه حد پائين براي پيش‌بيني جواب بهينه ارائه دادند. در روش آنها ابتدا توالي به دست آمده و سپس عمل تخصيص به ماشين‌ها صورت مي‌گيرد.
ب ) مسئله جريان كارگاهي انعطاف‌پذير چند مرحله‌اي
مسئله جريان كارگاهي چند مرحله‌اي انعطاف‌پذير شامل تعدادي مرحله‌ است كه در هر مرحله ۱ يا بيشتر از ۱ ماشين موازي وجود دارند (حداقل يكي از مراحل بايد بيشتر از يك ماشين داشته باشد) از انجائي كه در اكثر حالت‌هاي دنياي واقعي با اينگونه مسائل روبرو هستيم اين مسئله مورد توجه بسياري از محققان قرار گرفته است. با توجه به اينكه اين مسئله جزو مسائل NP-hard در حوزه مسائل زمان‌بندي است تكنيكهاي تقريبي و روشهاي حل فراواني براي اينگونه مسائل ارائه شده است.
براه و هانساكر۲۵ [۱۸] و راجندران و چادهوري۲۶ [۱۹] الگوريتم‌هاي شاخه و كران براي مسئله ارائه دادند. هر دو تحقيق فقط قادر به حل مسائل با سايز كوچك هستند. پورتمن و همكاران۲۷ [۲۰] هم روي همين مسئله مطالعه نمودند. آنها حد پائين ارائه شده توسط براه و هانساكر را بهبود دارند و تعداد شاخه‌هايي كه در درخت جستجو استفاده مي‌شد را كاهش دادند. آنها همچنين از الگوريتم ژنتيك براي بهبود فرايند جستجو استفاده نمودند. نتايج محاسباتي آنها نشان داد كه جواب بهينه‌اي كه از الگوريتم شاخه و كران بدست مي‌آمد در اكثر حالات الگوريتم ژنتيك نيز به آن مي‌رسد. به طوري كه فقط در %۳ نتايج با روش شاخه و‌كران اختلاف داشت.
مدل‌هاي زمان‌بندي جريان كارگاهي بدون وقفه
جريان كارگاهي بدون وقفه
در سالهاي اخير علاقه بسياري از محققان به سوي مسائل بدون وقفه معطوف شده است.اين علاقه بيشتر از كاربردهاي اين مسائل در صنعت ناشي مي‌شود. يك مسئله زمان‌بندي بدون وقفه، در محيط‌هاي توليدي اتفاق مي‌افتد كه يك كار از ابتدا تا انتهاي مراحل پردازش بايد بدون وقفه روي ماشين‌ها قرار بگيرد و مراحل پردازش آن پشت سرهم و بدون هيچ‌گونه تاخيري انجام گيرد. به عبارت ديگر تفاوت ميان زمان اتمام هر كار و زمان شروع هر كار در محيط‌هاي توليدي بدون وقفه برابر مجموع زمان‌هاي پردازش مي‌باشد.
در بسياري از صنايع براي مثال در صنايع شيميايي و پتروشيمي، صنايع فولاد، صنعت شيشه و صنايع مرتبط با كاغذ در فرآيند توليد يك محدوديت وجود دارد. هنگامي كه زمان پردازش يك كار شروع مي‌شود فرآيندهاي بعدي بايد بدون تاخير از يك ماشين به ماشين بعد انجام شوند. حتي در صورت لزوم شروع كار در مرحله قبل بايد به اندازه‌اي به تاخير بيفتد كه فرآيندهاي بعدي بدون تاخير آغاز شوند. اين نوع از مسائل به اصطلاح، جريان کارگاهي بدون وقفه۲۸ و يا جريان کارگاهي انتظار صفر۲۹ ناميده مي شوند. يكي از دو دليل اصلي بروز اين گونه مسائل (بدون وقفه) در محيط‌هاي توليدي به ماهيت فرايندها و ماهيت تكنولوژي به كار گرفته شده، باز مي‌گردد. در بعضي از فرايندها، براي جلوگيري از تغييرات نامطلوب در مواد دما يا خصوصيات ديگر مواد (مثلا چسبندگي) نياز به انجام كارها به صورت پشت سرهم و بدون وقفه دارند چون در غير اينصورت به نتيجه دلخواه نخواهيم رسيد. وضعيت‌هاي مشابهي در صنايع گوناگون رخ مي‌دهند مثل صنايع فولاد، پلاستيك و صنايع شيميايي و پتروشيمي. يكي ديگر از مثال‌هاي ملموسي براي توصيف اين وضعيت در صنايع غذايي رخ مي‌دهد. هنگامي كه مواد پروسه پخت را طي نمودند عمليات كنسرو كرن و يا بسته‌بندي اين محصولات بايد بدون وقفه انجام گيرد چرا كه در غير اينصورت مدت زمان مصرف محصولات كاهش خواهد يافت. و سرانجام يك محيط بدون وقفه مي‌تواند در صنايع خدماتي نيز استفاده شود. كاربرد اين مسئله در صنايع خدماتي وقتي توجيه پيدا مي‌كند كه زمان انتظار براي مشتريان و ارائه دهنده خدمات هزينه زيادي را در برداشته باشد. دومين دليل بروز محيط‌هاي بدون وقفه به دليل فقدان وجود انبار ميان ماشين‌ها يا ايستگاه‌هاي كاري است. به غير از مثال‌هاي ذكر شده، با مسئله مورد مطالعه در سيستم‌هاي توليدي به هنگام۳۰ يا سيستم‌هاي كششي نيز رو به رو مي‌شويم. به عبارت ديگر هر گاه جرياني از كارها به طور متوالي و بدون انباشت مياني انجام شوند در آن سيستم مدل كارگاهي بدون وقفه وجود دارد. مسئله جريان كارگاهي بدون وقفه در دهه‌هاي گذشته مورد مطالعه قرار گرفته است. كاربردهاي گوناگون اين مسئله در صنعت، علاقه زيادي را به منظور مدل‌سازي و ارائه روش‌هاي حل در محققان ايجاد نموده است. براي مثال چندين مقاله كه به دهه ۷۰ ميلادي باز مي‌گردند، پيچيدگي محاسباتي اينگونه مسائل را مورد بررسي قراردادند. همچنين در سالهاي اخير اكثر تحقيقات در زمينه روش‌هاي ابتكاري و فرا ابتكاري براي حل اين نوع از مسائل ارائه شده است.
با توجه به اطلاعات و دانش ما يكي از اولين مطالعات صورت گرفته در اين زمينه توسط آقاي گيلمور و گوموري۳۱ [۲۱] انجام شده است. آنها از يك الگوريتم زمان نمايي استفاده كردند و مسئله جريان كارگاهي دو ماشينه بدون وقفه را حل كردند. ردي و رامامورتي۳۲ [۲۲] و ويسمر۳۳ [۲۳] جزو اولين كساني بودند كه مسئله m ماشينه جريان كارگاهي بدون وقفه با تاريخ هدف مينيمم كردن آخرين زمان اتمام كار را حل كردند. ردي و رامامورتي ساهني و چو ۳۴[۲۴] فهميدند كه مسئله جريان كارگاهي دو ماشينه با تابع هدف ماکزيمم زمان اتمام کارها پيچيدگي محاسباتي دارد. پاپا ديميمتريو و كانلاكيس۳۵ [۲۵] تحقيقي بر روي مسئله جريان كارگاهي تك مرحله‌اي با چهار ماشين انجام دادند. نتايج حاصل از تحقيق آنها نشان داد مسئله مورد مطالعه آنها از نظر محاسباتي پيچيده است. راك۳۶ [۲۶] نتيجه مشابهي براي مسئله جريان كارگاهي سه ماشينه بدون وقفه به دست آورد او همچنين نشان داد كه مسئله جريان كارگاهي دو ماشينه بدون وقفه با در نظر گرفتن تابع هدف متوسط زمان در گردش كار۳۷ پيچيدگي محاسباتي دارد.
اسريسكانداراجا و لادت۳۸ [۲۷] مسئله جريان كارگاهي دو مرحله‌اي بدون

مطلب مشابه :  منبع پایان نامه درباره SPD، همسطح.، کانال‌های، پرسکاری