چکیده:
مسئلۀ زمانبندی پروژه با محدودیت منابع (RCPSP) جزء مسائل غیرچندجملهای سخت (NP-Hard) است که برای حل آن، روشهای ابتکاری و فراابتکاری در مقایسه با راهحلهای دقیق، کارایی بیشتری دارند. در این تحقیق از الگوریتم رقابت استعماری اصلاحشده برای حل مسئلۀ زمانبندی پروژه با محدودیت منابع در حالت تکحالته و همچنین از الگوریتم محاسبۀ جواب موجه ابتدایی برای افزایش سرعت الگوریتم رقابت استعماری اصلاحشده با استفاده از حذف فضای غیرموجه جستوجو، استفاده شده است. الگوریتم ارائهشده در این مقاله بر روی مجموعۀ مسائل استاندارد کتابخانۀ PSPLIB آزمایش و از نظر کارایی با تعدادی از روشهای موجود مقایسه شده است. نتایج آزمایشها، کارایی و امکانپذیری الگوریتم پیشنهادی را در حل مسائل استاندارد زمانبندی پروژه با محدودیت منابع نشان میدهد. بهمنظور بررسی عملکرد الگوریتم در حل مسائل با دادههای واقعی، دو پروژۀ انجامگرفته توسط شرکت قدس نیرو در قالب مسئلۀ مدلسازی و با استفاده از الگوریتم پیشنهادی حل شد.
The scheduling problems are the non-polynomial problems-hard (NP-Hard), is to solve it, and meta-heuristic innovative method compared with the exact method require less time and memory.In this research, developed imperialistic competitive algorithm used to solving the single-mode resource-constrained project scheduling problem.also the basic feasible solution algorithm used in order to increase the rate of developed imperialist competetive algorithm by remove the unfeasible search space. The proposed algorithm is tested on a set of standard problems PSPLIB Library and the performance is compared with some existing methods. Test results of the proposed algorithm show effectiveness and feasibility of algorithm to solve standard problems. To evaluate the performance of algorithms for solving problems in real field, two projects that carried out by the Quds Force (supplies petrochemicals project in Kermanshah, Kermanshah Petrochemical Project Setup Utility) are modeling in RCPSP and solved by using the proposed algorithm.
خلاصه ماشینی:
حل مسائل زمان بندي پروژه با محدوديت منابع (RCPSP) با استفاده از الگوريتم رقابت استعماري اصلاح شده (DICA) حسين صفري ١، عليرضا فقيه ٢ مسئلة زمان بندي پروژه با محدوديت منـابع (RCPSP) جـزء مسـائل غيرچندجملـه اي سخت (NP-Hard) است که براي حـل آن ، روش هـاي ابتکـاري و فراابتکـاري در مقايسـه بـا راه حل هاي دقيق ، کارايي بيشتري دارند.
در اين تحقيق از الگوريتم رقابت استعماري اصلاح شده براي حل مسئلة زمان بندي پروژه با محدوديت منابع در حالت تک حالته و همچنين از الگـوريتم محاسبة جواب موجه ابتدايي براي افزايش سرعت الگوريتم رقابـت اسـتعماري اصـلاح شـده بـا استفاده از حذف فضاي غيرموجه جست وجو، استفاده شده است .
تاکنون محققان بسياري با به کـارگيري روش هاي مختلف براي حل مسائل زمان بندي پروژه با محدوديت منابع تلاش کرده اند، اما آنچـه جاي خالي آن هنوز حس مي شود يافتن روشي است که با زمان و صرف هزينة کمتر، جواب بهتر و کاربردي تري را براي اين گونه مسائل بيابد.
عيب اصلي اين روش ها اين است که نمي توان يـک قاعـدة کلي براي مرتب کردن فعاليت ها ارائه کـرد و مطلوبيـت جـواب حاصـل از قواعـد اولويـت دهـي مختلف ، به شبکة فعاليت هاي پروژه بستگي دارد و بدين معناست کـه اگـر قاعـده اي بـراي يـک مسئلة خاص ، جواب بهينه را به دست دهد، لزوما هميشه موفق نخواهـد بـود.
Computers & Operations Research, 38(1): 44–50.
Heuristic Algorithms for Solving the Resource- Constrained Project Scheduling Problem: Classification and Computational Analysis.