Particle swarm optimization with justification and designed mechanisms for resource-constrained project scheduling problem

• Published in: Expert systems with applications 2011-06, Vol.38 (6), p.7102-7111
• Main Author: Chen, Ruey-Maw
• Format: Article
• Language: English
• Subjects: Algorithms; Combinatorial analysis; Computer simulation; Expert systems; Justification; Optimization; Particle swarm optimization; Resource-constrained project scheduling problem; Schedules; Scheduling; Temporal logic
• ISSN: 0957-4174; 1873-6793
• DOI: 10.1016/j.eswa.2010.12.059

► This study generated schedules by both forward and backward scheduling particle swarms. ► This work applies justification technique to further shorten the makespan of the yield schedule. ► To synchronize the justified schedules, a mapping scheme is adopted to modify the particle. ► To enhance the performance, the latest finish time heuristic is used in particles’ initialization. The studied resource-constrained project scheduling problem (RCPSP) is a classical well-known problem which involves resource, precedence, and temporal constraints and has been applied to many applications. However, the RCPSP is confirmed to be an NP-hard combinatorial problem. Restated, it is hard to be solved in a reasonable time. Therefore, there are many metaheuristics-based schemes for finding near optima of RCPSP were proposed. The particle swarm optimization (PSO) is one of the metaheuristics, and has been verified being an efficient nature-inspired algorithm for many optimization problems. For enhancing the PSO efficiency in solving RCPSP, an effective scheme is suggested. The justification technique is combined with PSO as the proposed justification particle swarm optimization (JPSO), which includes other designed mechanisms. The justification technique adjusts the start time of each activity of the yielded schedule to further shorten the makespan. Moreover, schedules are generated by both forward scheduling particle swarm and backward scheduling particle swarm in this work. Additionally, a mapping scheme and a modified communication mechanism among particles with a designed gbest ratio (GR) are also proposed to further improve the efficiency of the proposed JPSO. Simulation results demonstrate that the proposed JPSO provides an effective and efficient approach for solving RCPSP.