منابع پایان نامه با موضوع
جريان، الگوريتم، كارگاهي

منابع پایان نامه با موضوع جريان، الگوريتم، كارگاهي

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

وقفه با تابع هدف ماکزيمم زمان اتمام کارها در حالتي كه در مرحله اول يک ماشين مركزي و در مرحله دوم دو يا بيشتر از دو ماشين موازي داشته باشيم مورد بررسي قرار دادند و متوجه شدند كه اين مسئله پيچيدگي محاسباتي دارد.
گيلمور و گوموري [۲۱] يك جواب بهينه براي مسئله جريان كارگاهي دو ماشينه بدون وقفه بدست آوردند كه براي رسيدن به آن به مرحله نياز بود. گويال و اسريسکانداراجا۳۹ [۲۸] براي مسئله خاص جريان كارگاهي دو ماشينه بدون وقفه كه زمان پردازش به طور خطي با زمان انتظار كارها قبل از پردازششان روي ماشين دوم رابطه دارد، يك الگوريتم ابتكاري به منظور مينيمم نمودن ماکزيمم زمان اتمام کارها ارائه دادند.
. يكي از اولين تحقيقات صورت گرفته در زمينه جريان كارگاهي بدون انبارهاي مياني توسط لونر۴۰ ‍ [29] انجام شد. وي يك الگوريتم شاخه و كران به منظور مينيمم نمودن ماکزيمم زمان اتمام کارها ارائه داد.ون دمان و بيكر۴۱ [۳۰] همچنين يك روش شاخه و كران به منظور مينيمم نمودن ميانگين زمان در گردش كار براي مسئله جريان كارگاهي بدون انبارهاي مياني ارائه دادند.
براي به دست آوردن يك برنامه‌زماني خوب، مسئله زمان‌بندي جريان كارگاهي بدون وقفه به شكل مسئله فروشنده دوره‌گرد فرموله شده است. برخلاف تحقيقات سنتي صورت گرفته در جريان كارگاهي كه روي استفاده از تكنيكهاي شمارشي – برنامه‌ريزي رياضي و روشهاي ابتكاري براي رسيدن به يك جواب بهينه و يا نزديك بهينه استفاده مي‌كنند، تبديل و فرموله‌بندي كردن مسئله جريان كارگاهي بدون وقفه به مسئله فروشنده دوره گرد از رويكرد متفاوتي استفاده مي‌كند. ابتدا تاخيرهاي زمان پردازش بين كارها و ماشين‌ها را تبديل به ماتريس فاصله براي مسئله TSP مي‌كند. سپس از تكنيكهاي حل معمول كه براي حل اين مسئله به كار مي‌روند، استفاده مي‌شود. محققان مسئله جريان كارگاهي تك پردازنده را به مسئله TSP تعميم دادند. اگرچه آنها همچنين مسئله جريان كارگاهي چند پردازنده را تبديل به چند مسئله TSP كرده و سپس چند مسئله TSP را تبديل به يك مسئله TSP نمودند.
اولين كار انجام شده در تبديل مسئله جريان كارگاهي بدون وقفه به مسئله TSP توسط گيلمورو گوموري [۲۱] در سال ۱۹۶۴ انجام شد. آنها مسئله جريان كارگاهي دو مرحله‌اي تك پردازنده را تبديل به مسئله TSP كردند. آنها دريافتند كه بواسطه بكارگيري الگوريتم شاخه و كران براي مسئله TSP يك جواب بهينه به سرعت براي مسئله جريان كارگاهي بدون وقفه به دست مي‌آيد. اين روش مورد توجه بسيراي از محققان قرار گرفته است. مشابه وضعيت الگوريتم جانسون در مسائل عمومي جريان كارگاهي روش گيلمور و گوموري بارها مورد استفاده محققان در تركيب با روشهاي ابتكاري براي بهبود جواب مينيمم نمئدن ماکزيمم زمان اتمام کارها و يا ساير توابع هدف قرار گرفته است. گويال و ناسريسكانداراجا [۲۸] استراتژي تقسيم و غلبه۴۲ را به كار گرفتند. آنها مسئله جريان كارگاهي m ماشينه را به مسئله جريان كارگاهي m-1 ماشينه كاهش داده و سپس به منظور پيدا كردن جواب خوب از روش گيلمورو گوموري استفاده نمودند. اين تبديل امكان استفاده محدوده وسيعي از تكنيهاي حل امكان‌پذير براي مسئله جريان كارگاهي بدون وقفه را فراهم آورد. اگرچه مسئله هنوز پيچيدگي محاسباتي خود را حفظ كرد.
مسئله TSP معمولاً توسط يك ماتريس فاصله نمايش داده مي‌شود كه حاوي فاصله سفر ميان شهرهاي موجود است.
ايگنيزيو وكاوالير۴۳ [۳۱] مسئله فروشنده دوره گردن به اين صورت تشريح كردند: يك فروشنده كه از شهر خود شروع به حركت مي‌كند و بايد از تمامي شهرهاي موجود در ليست عبور كند و در انتها به شهر خود بازگردد. هدف در اين مسئله مينيمم كردن مجموع فواصل طي شده توسط فروشنده دوره گرد است.
گوپتا۴۴ [۳۲] يك مدل بر اساس مدل ردي و رامامورتي توسعه داد. او يك الگوريتم ابتكاري ارائه داد كه عملكرد آن بهتر از الگوريتم ويسمر بود. بر اساس دانش ناشي از تحقيقات صورت گرفته، بعضي از محققان شروع به توسعه الگوريتم‌هاي جديد براي مسئله جريان كارگاهي بدون وقفه به خوبي تحقيقات صورت گرفته در مورد TSP نمونه آنها همچنين از تكنيكهاي الگوريتميك و برنامه‌ريزي رياضي براي ارزيابي كردن الگوريتم‌هايشان، استفاده كردند. بوني و گاندري۴۵ [۳۳] روش ابتكاري به نام جور كردن شيبدار هم بر اساس شكل كارها در برنامه توسعه دادند. الگوريتم شكل‌هايي با كشيدن خط ميان شروع و پايان عمليات‌ها از يك ماشين به ماشين ديگر ايجاد مي‌كرد. الگوريتم جور كردن شيدار تلاش كرد كه شكل دوكار متوالي را متناسب كند. آنها همچنين از فرمولاسيون TSP بر اساس زمان شناوري بين كارها استفاده كردند و دو روش ارائه شده خود را با دو روش ابتكاري رايج مقايسه كردند و نشان دادند روش جور كردن شيبدار۴۶ عملكرد بهتري دارد. كينگ و اسپاچيس۴۷ [۳۴] نشان دادند كه الگوريتم‌هايي كه در محيط بدون وقفه عملكرد خوبي ندارند لزوماً عملكرد مناسبي در محيط انبارهاي مياني نامحدود از خود نشان نمي‌دهند.
كالاهان۴۸ [۳۵] يك تحقيق در صنعت فولاد روي فرآيندهاي بدون وقفه انجام دارد. وي يك مدل صف براي آناليز چندين مسئله استفاده نمود. در ادامه آزمون‌هاي محاسباتي را براي بررسي پيشنهاداتش به كار گرفت سالوادور۴۹ [۳۶] يك الگوريتم را كه نشأت گرفته شده از يك محيط توليدي نايلون بود توسعه داد.هدف وي مينيمم كردن ماكزيمم زمان انجام كارها براي يك مجموعه شامل n كار با تعيين توالي بهينه و تعيين زمان شروع كارها براي توالي بهينه بود. رويكرد به كار گرفته شده توسط وي برنامه‌ريزي پويا بود. وي از برنامه‌ريزي پويا براي پيدا كردن حدود پائين براي استفاده در روش شاخه و كران كمك گرفت. استفاده از نتايج به دست آمده توسط كارخانه حداكثر ظرفيت توليد كارخانه را به ميزان قابل قبولي افزايش داد.
جريان کارگاهي انعطاف پذير بدون وقفه
در جريان كارگاهي با ماشين‌هاي موازي، هر مرحله داراي ماشين يكسان است.که لزوما تعداد ماشين ها در تمامي مراحل يکسان نيست.
كوريان۵۰ [۳۷] يك حالت خاص در نظر گرفت كه در آن و بود هدف وي مينيمم كردن ماكزيمم زمان اتمام كارها بود. وي يك بدترين عملكرد مرز۵۱ توسعه داد. همچنين نشان‌ داد اگر از ليست LPT استفاده شود، حد به بهبود مي‌يابد. نتايج حاصل از پژوهش كوريان و ركلايتيس۵۲ [۳۸] نشان داد كه اكثر الگوريتم‌هاي ابتكاري كالا تقريباً مشابه توالي توليد شده توسط LPT هستند كه با استفاده از يك جستجو در همسايگي تكميل مي‌شود. كوريان و ركلايتيس براي يك مسئله جريان كارگاهي دو مرحله‌اي انعطاف‌پذير بدون وقفه دو الگوريتم ابتكاري ارائه دادند.
رامودين و راتليف۵۳ [۳۹] مسئله جريان كارگاهي دو مرحله‌اي انعطاف‌‌پذير بدون وقفه ‌را با تابع هدف ماكزيمم كردن مجموع وزني سفارشات مشتريان در طول ۸ ساعت شيفيت روزانه حل كردند.
مسئله حل شده توسط آنها را مي‌توان به صورت نشان داد. آنها مسئله را بصورت يك برنامه‌رياضي فرموله كردند و براي تبديل مسئله به چند زير سماله از آزادسازي لاگرانژين استفاده نمودند. بعضي از جواب‌هاي نشدني توسط الگوريتم جستجوي محلي حذف مي‌شوند. سپس توسط يك كارشناس خبره و به صورت تعاملي الگوريتم به يك جواب مناسب هدايت مي‌شود.
اسريسكانداراجا [۴۰] از يك بدترين حد تنگ و با استفاده از يك توالي دلخواه براي مسئله استفاده كرد. در اين الگوريتم كارها به ترتيبي كه بصورت تصادفي توليد شده بودند، زمان بندي مي‌شوند. اگر كارهاي سفارشي داده شده به صورت غير صعودي (براي زمان پردازش مرحله دوم) مرتب شوند در اينصورت به جواب‌هاي بهتري خواهيم رسيد. فريبرز جولاي و همکاران [۴۱] يک مسئله جريان کارگاهي چند مرحله اي بدون وقفه را با در نظر گرفتن محدوديت اتمام کارها در يک زمان از پيش تعيين شده يک مدل برنامه ريزي عدد صحيح مختلط خطي را پيشنهاد داده و مدل پيشنهادي با الگوريتم ژنتيک مقايسه شد. در مسئله مورد مطالعه آنها با توجه به محدوديت در نظر گرفته شده ممکن است بعضي از کارها رد شوند.تابع هدف در نظر گرفته شده در اين تحقيق تابع هدف در نظر گرفته شده، ماکزيمم سود حاصله مي باشد.
جريان كارگاهي انعطاف‌پذير دو مرحله‌اي بدون وقفه
گوپتا و همکاران [۴۲] يک طبقه بندي جامع از پيچيدگي مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه همراه با زمان هاي آماده سازي و تغيير مکان به منظور مينيمم نمودن مجموع زمان هاي اتمام کار ارائه دادند ليو ژيژين۵۴ [۴۳] و همکاران يک مسئله جريان کارگاهي دو مرحله اي انعطاف پذير بدون وقفه با اين شرايط که يک ماشين در مرحله اول و تعدادي ماشين که تعداد انها بزرگتر از يک است در مرحله دوم قرار دارند. يک الگوريتم ابتکاري با عنوان۵۵ LD طراحي شده و عملکرد بدترين حد آن مورد بررسي قرار گرفت. الگوريتم پيشنهادي انها پيچيدگي محاسباتي بسيار کمي را داراست و اجراي ان ساده مي باشد بنابراين با توجه به نتايج حاصله انها پيشنهاد دادند که با توجه به خصوصيات الگوريتم پيشنهادي، به کارگيري اين الگوريتم در کاربردهاي دنياي واقعي مي تواند سودمند باشد. ژونلين چانگ و همکاران۵۶ [۴۴] روي مسئله جريان کارگاهي هيبريدي دو مرحله اي بدون وقفه را با در نظر گرفتن زمان هاي راه اندازي و انتقال به صورت مجزا مطالعه نمودند.با توجه به NP-complete بودن مسئله مورد مطالعه و از آنجائي که هيچ الگوريتم شناخته شده اي که با زمان نمايي قادر به حل اين مسئله باشد ، وجود نداشت، آنها از يک رويکرد حل تقريبي براي اين مسئله استفاده نموده و دو الگوريتم ابتکاري براي حل اين مسئله پيشنهاد نمودند.همچنين آنها براي مقايسه رويکرد پيشنهادي خود، جواب هاي به دست آمده را با حد پائين توسعه داده شده، مقايسه نمودند.نتايج حاصله نشان داد که اين الگوريتم به طور کارايي قابليت حل مسائل را با پيچيدگي محاسباتي کم داراست.جينکسينگ ژي و ژيجون وانگ۵۷[۴۵] روي مسئله جريان کارگاهي انعطاف پذير دو مرحله اي بدون وقفه با تابع هدف مينيمم نمودن ماکزيمم زمان اتمام کارها مطالعه نمودند. آنها يک الگوريتم ابتکاري به نام ۵۸MDA براي حل اين مسئله پيشنهاد داده و الگوريتم پيشنهادي خودشان را با الگوريتم هاي ارائه شده در پيشينه تحقيق مقايسه نمودند. نتايج حاصل از مقايسه نشان داد الگوريتم MDA در اغلب موارد جواب بهتري نسبت به ساير الگوريتم ها به دست مي آورد. آخرين پژوهش انجام شده در اين حوزه توسط رونگ هوا هانگ و همکاران۵۹ [۴۶] انجام شده است. آنها مسئله جريان کارگاهي انعطاف پذير دو مرحله اي انعطاف پذير بدون وقفه را با در نظر گرفتن زمان راه اندازي به صورت مجزا و با تابع هدف مينيمم نمودن مجموع زمان اتمام کارها برررسي نمودند. انها يک مدل برنامه ريزي عدد صحيح مختلط غير خطي براي حل اين مساله ارائه دادند. همچنين الگوريتم بهينه سازي کلوني مورچگان براي اين مسئله پيشنهاد شد و براي سايز هاي مختلف اين رويکردها با يکديگر مقايسه شد.نتايج به دست آمده برتري در زمان حل،نيرومندي و کيفيت جواب به دست آمده براي الگوريتم بهينه سازي کلوني مورچگان را نشان داد. برای مطالعه بیشتر در خصوص ادبیات موضوع مسائل بدون وقفه توصیه می شود به [۴۷] مراجعه شود.
پيش بيني ماکزيمم زمان اتمام کارها
تخصيص موعد تحويل يکي از مهمترين فعاليت هاي مراکز کنترل کارخانه است. معيار هاي مرتبط با موعد تحويل از کيفيت موعد تحويل تخصيص يافته تاثير مي پذيرند. در زمينه تخصيص موعد تحويل در برخي حوزه ها مطالعاتي صورت گرفته است ولي با توجه به اهميت اين موضوع، تعدد و کيفيت اين کارها با اهميت اين موضوع سنخيت ندارد. در مسئله جريان کارگاهي بدون وقفه چندين ترکيب از توالي کارها وتخصيص ماشين ها وجود دارد. از اينرو پيش بيني زمان اتمام کارها در

مطلب مشابه :  پایان نامه ارشد درباره ملانوم، بدخیم،، سارکم، تیروئید،