Affiliations: Department of Computer and Communication Engineering,
National Kaohsiung First University of Science and Technology, No. 2, Jhuoyue
Rd., Nanzih District, Kaohsiung City 811, Taiwan | Institute of Engineering Science and Technology,
National Kaohsiung First University of Science and Technology, No. 2, Jhuoyue
Rd., Nanzih District, Kaohsiung City 811, Taiwan | Department of Information Engineering, Kun Shan
University, No. 949, Da-Wan Rd., Yung-Kang, Tainan County 71003, Taiwan
Note: [] Corresponding author
Abstract: An effective algorithm capable of solving the multi-mode
resource-constrained project scheduling problem (MRCPSP) is an essential
component for project planning and control since it can fully exploit the
available resources and minimize the makespan of a given project. The MRCPSP is
extremely complex and is known to be NP-hard in the strong sense. On the basis
of the principles of ant colony optimization (ACO), we therefore propose a
constructive-oriented iterative algorithm to acquire satisfactory solutions of
the MRCPSP within a reasonable amount of computation time. The proposed
algorithm, namely ACO-MRCPSP, attempts to identify a project schedule with
minimum completion time without violating precedence and resource constraints.
ACO-MRCPSP is characterized by its use of a self-adaptive parameter control
strategy to guide artificial ants to effectively construct feasible solutions
for the MRCPSP. The performance of the proposed algorithm is evaluated by
comparing it against other existing metaheuristic implementations, such as
simulated annealing (SA) and genetic algorithms (GAs), in terms of overall
completion time for a set of project instances obtained form the Project
Scheduling Library (PSPLIB). Experimental results indicate that ACO-MRCPSP is a
significant improvement compared with the previous attempts at solving the
MRCPSP.
