Volume 48, Number 4, October-December 2014
|Page(s)||595 - 614|
|Published online||11 July 2014|
An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem∗
1 School of Economic and Management,
Shenyang Ligong University, 110159
2 College of Information Science and Engineering, Northeastern University, 110819 Shenyang, P.R. China
3 Laboratory of Advanced Manufacture and Equipment of Liaoning, Shenyang Ligong University, 110159 Shenyang, P.R. China
Accepted: 22 April 2014
Many real-world scheduling problems can be modeled as Multi-mode Resource Constrained Project Scheduling Problems (MRCPSP). However, the MRCPSP is a strong NP-hard problem and very difficult to be solved. The purpose of this research is to investigate a more efficient alternative based on ant algorithm to solve MRCPSP. To enhance the generality along with efficiency of the algorithm, the rule pool is designed to manage numerous priority rules for MRCPSP. Each ant is provided with an independent thread and endowed with the learning ability to dynamically select the excellent priority rules. In addition, all the ants in the ant algorithm have the prejudgment ability to avoid infeasible routes based on the branch and bound method. The algorithm is tested on the well-known benchmark instances in PSPLIB. The computational results validate the effectiveness of the proposed algorithm.
Mathematics Subject Classification: 68M20 / 90C59
Key words: Operations Research / Mathematical Programming
This work was supported by National Science Foundation of China under Grant No. 71071100; the National Science Foundation for Distinguished Young Scholars of China under Grant No. 71325002; the Liaoning BaiQianWan Talents Program under No. 2013921033; the Human Resources Development Fundation of Shenyang under No. 2012141203022.
© EDP Sciences, ROADEF, SMAI 2014
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.