ارائۀ يك الگوريتم رقابت استعماري كارآمد براي حل مسئلۀ زمان‌بندي پروژه با محدوديت منابع

An Efficient Imperialist Competitive Algorithm for Resource Constrained Project Scheduling Problem

در اين مقاله، الگوريتم جديدي براساس چارچوب الگوريتم رقابت استعماري براي حل مسئلۀ زمان‌بندي پروژه با محدوديت منابع ارائه مي­ شود. در اين مسئله، فعاليت‌هاي پروژه با توجه به محدوديت‌هاي منابع و روابط پيش‌نيازي، به‌گونه‌اي زمان‌بندي مي‌شوند كه زمان پروژه حداقل شود. در الگوريتم پيشنهادي، به‌منظور مدل‌سازي عملگر جذب، از عملگر تقاطع يكنواخت استفاده شده و براي جلوگيري از همگرايي ناقص الگوريتم، دو عملگر انقلاب يك ­نقطه‌اي و چندنقطه‌اي پيشنهاد شده است. همچنين به ­منظور جست­ و جوي بهتر فضاي جواب، دو الگوريتم بهبود پيشرو - پس­رو و الگوريتم جست‌وجوي محلي مبتني­بر جايگشت به­ كار رفته است. پارامترهاي الگوريتم، به‌وسيلۀ طراحي آزمايش تاگوچي تنظيم و كارايي الگوريتم با حل مجموعه مسائل PSPLIB ارزيابي شده است. نتايج محاسبات و مقايسۀ آن‌ها با الگوريتم‌هاي موجود نشان مي‌دهد كه الگوريتم پيشنهادي، قابليت يافتن جواب‌هاي نزديك به بهينه در مسائل كوچك و توليد جواب‌هاي رقابتي در مسائل بزرگ را دارد.

In this paper, a new algorithm based on the framework of the imperialist competitive algorithm for solving resource constrained project scheduling problem (RCPSP) will be proposed. In this problem, the activities are scheduled based on the resource and precedence relationships constraints in a way that the makes pan will be minimized. In order to model the assimilation process, a uniform crossover has been used, and to avoid premature convergence of the proposed algorithm, two revolution operators including one point revolution and multi-point revolution will be introduced. Also, in order to enhance the exploitation ability, a combined local search including permutation based local search (PBLS) and forward-backward improvement (FBI) is performed. The algorithm parameters are determined by designing Taguchi experiment, and the efficiency of proposed ICA is demonstrated by solving PSPLIB problems. Computational results and comparisons with some existing algorithms show that the proposed algorithm can produce near-optimal solution for small problems and competitive solution for large ones.