14138

14138

جانمايي تسهيلات با استفاده از نظريه گراف بر پايه الگوريتم هاي كاوشي و فراكاوشي

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

مهندسي و مديريت ساخت

شهريور ماه 1392

شهريور ماه 1392

دكتر علي كاوه

عمران

چكيده مسئله جانمايي تسهيلات، چيدمان قرارگيريتمام موارد مورد نياز براي توليد كالا و يا ارائه خدمات است. جانـمايي تاثير قابل توجهي بر هزينه هاي توليد، كار در جريان، زمان اتمام فرآيند و همچنين بهره‌وري دارد. متاسفانه اين مسئله به طور كلي جزو مسائل "حل نشدني درزمان چندجمله‌اي"(NP-Hard) شناخته مي‌شود و بنابراين حل آن به صورت دقيق فقط براي مسائل كوچك ممكن بوده و در مسائل با اندازه متوسط و بزرگ تقريبا ناممكن است، بنابراين در سال‌هاي اخير روش‌ها و پيشنهادهاي مختلفي براي حل اين مشكل مطرح شده است. روش نظريه گراف به دليل سادگي مفاهيم و قابليت نمايش آسان براي اين مسئله بارها مورد استفاده قرار گرفته است. همچنين روش‌هاي كاوشي و فراكاوشي نيز توانسته‌اند به جواب‌هاي نزديك به بهينه در مسائل متوسط و بزرگ دست يابند. در اين پايان نامه سعي شده است به كمك نظريه گراف و روش فراكاوشي تركيبي و ارتقا يافته "سيستم جستجوي ذرات باردار" (CSS) بتوان مسائل مختلفي از جمله پيدا كردن گراف مسطح حداكثر در جانمايي تسهيلات توسط نظريه گراف، جانماييتسهيلاتيكرديفي (SRFLP) و مسئلهتخصيصدرجهدوم (QAP) را حل نمود. روش تحقيق مورد استفاده با توجه به ماهيت مسئله، برنامه نويسي انتخاب گرديد. نهايتا روش پيشنهادي توانست در اكثر مسائل محك، به نتايج قابل قبولي نسبت به بهترين نتايج موجود در جديدترين مقالات دست يابد. واژه‌هاي كليدي:جانمايي تسهيلات، الگوريتم جسـتجوي ذرات باردار (CSS) ، نظريه گراف، مسائلجانماييتسهيلاتيكرديفي (SRFLP)،مسئلهتخصيصدرجهدوم (QAP).