تجزيه و تحليل روش شاخه و كران DH براي حل مسائل زمانبندي پروژه با محدوديت منابع چندگانه و ارائه يك مدل ساختمان داده و تهيه برنامه كامپيوتري آن

اصفهان : دانشگاه صنعتي اصفهان . دانشكده صنايع و مركز برنامه ريزي سيستم ها

كارشناسي ارشد

مساله زمانبندي پروژه با منابع محدود )RCPSP(كه از نوع مسائل NP- Completeاست . توسعه اي از مدل زمانبندي كار كارگاهي )Jop shop(مي باشد. هر روشي كه بتواند اينگونه مسائل را حل نمايد، قادر است تمام مسائل زمانبندي را حل كند. تا كنون روشهاي دقيق و ابتكاري زيادي جهت حل اين مسائل ارائه شده است . متداولترين روش براي حل بهينه مسايل از اين نوع ، روش شاخه و كران مي باشد. در اين تحقيق از يك رويه شاخه و كران براي زمانبندي بهينه فعاليتهاي پروژه با محدوديتهاي پيشنيازي و منابع در حالت چند منبع استفاده مي شود كه هدف مي نيمم كردن مدت زمان انجام پروژه مي باشد. اين رويه توسط دموليميستر و هروئلن (1992) ارائه شده و به روش DHمشهور شده است . برتري اين روش نسبت به ساير روشها در ايجاد و استفاده از قواعدي است كه با بكارگيري آنها در زمان جستجوي درخت شاخه و كران ، كاهش قابل ملاحظه اي مشاهده مي شود. با توجه به پيچيدگي اين قواعد و اكتفابه اشاره كلي آن در متون منتشره ، جهت بهبود يا توسعه در ابتدا نياز به تجزيه تحليل دقيق و پياده سازي اين روش مي باشد. هدف اين پايان نامه تجزيه تحليل و تشريح كامل اين روش بوده كه سعي شده است با ايجاد نمودارهاي جريان و با استفاده از علائم رياضي نتايج اين تحليل ارائه شود. در تحليل انجام شده در اين تحقيق ، از قسمتهايي از الگوريتم رفع اشكال و يا رفع ابهام شده است . در گام 2 الگوريتم شاخه و كران لازم است جواب پيدا شده ذخيره شود. در گام 3 الگوريتم در صورت وجود شرايط قضيه 2، زودترين زمان شروع فعاليتهاي مجموعه برشي برابر با زمان ختم يكي از دو فعاليت در حال اجرا مي باشد كه پس از بررسي تعيين مي شود. در گام 5 در صورت فزوني و يا برابري حد پايين از حد بالا، قبل از رفتن به گام 7 (برگشت به عقب ) ميبايست سطح درخت را كاهش داد. در حالتهاي خاص ممكن است نياز به موارد فوق نباشد...

8415

([مهندسي صنايع])

مهندسي صنايع و سيستم ها

دانشگاه صنعتي اصفهان

محمدرضا زماني