Memetic algorithm for multi-mode resource-constrained project scheduling problems

Shixin Liu, Di Chen, Yifan WangJournal of Systems Engineering and Electronics 2014 · DOI

TL;DR

This paper introduces a novel Memetic Algorithm (MA) designed to tackle the complex Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP). By employing a unique "strategic oscillation" fitness function and two innovative local search procedures, the MA effectively navigates the search space to find high-quality project schedules, demonstrating competitive performance against existing state-of-the-art algorithms.

What Problem Does This Paper Address?

Project scheduling is a critical task in management, but real-world projects often involve activities that can be performed in multiple ways (modes), each with different durations and resource requirements. Furthermore, projects are constrained by limited resources (e.g., personnel, equipment) that are available only up to a certain capacity. This is known as the Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP). The goal is to determine the optimal mode for each activity and its start time to minimize the overall project completion time (makespan) while satisfying all precedence relationships between activities and resource availability constraints. The MRCPSP is notoriously difficult, being strongly NP-hard, meaning that finding the absolute best solution becomes computationally infeasible for larger problems. Existing exact methods struggle with problem size, and while heuristics and meta-heuristics have been developed, there's a continuous need for more effective approaches that can find near-optimal solutions efficiently.

Methods

The core of this paper is the development of a Memetic Algorithm (MA) tailored for the MRCPSP. MAs combine population-based meta-heuristics (like Genetic Algorithms) with local search methods to refine solutions. The authors introduce several key innovations:

  • Novel Fitness Function: They propose a fitness function that incorporates a "strategic oscillation" mechanism. This function penalizes infeasible solutions but does so in a way that encourages the search to explore solutions near the "feasible boundary." This means it's willing to temporarily explore infeasible solutions if they show promise for leading to better overall outcomes, rather than strictly favoring only feasible solutions.
  • Two Novel Local Search Procedures:
    • LS1: This procedure focuses on improving the lower bound of the project makespan. It's activated when the current lower bound of an individual is higher than the best makespan found so far. LS1 attempts to find better mode assignments that can potentially reduce this lower bound, aiming to bring it closer to the known upper bound.
  • LS2: This procedure is designed to improve solutions by reducing the value of the new fitness function. It starts from either a feasible or infeasible individual and iteratively tries to change activity modes to decrease the fitness value. This procedure is particularly effective in finding better local optima, even when starting from promising infeasible solutions.
  • Justification Technique: The MA also employs a "justification" technique, which is used to improve feasible solutions by shifting activity start times as much as possible to the right (right justification) or left (left justification) without violating constraints. This helps to tighten schedules.
  • Standard MA Components: The MA also includes standard components like an initial population generator (using a "frequency-based memory" for mode selection), a one-point crossover operator, and a mutation operator that primarily targets mode lists.

Datasets

The authors evaluated their proposed MA using instances from the PSPLIB (Project Scheduling Problem Library). Specifically, they used instance sets with varying numbers of non-dummy activities: J10, J12, J14, J16, J18, J20, and J30. The J30 set is highlighted as particularly challenging because not all optimal solutions are known.

Key Insights and Ideas

  • Strategic Oscillation for Feasibility: The idea that a search algorithm can benefit from exploring infeasible regions near the feasible boundary is a key insight. This approach allows the MA to potentially escape local optima that might trap purely feasible-seeking algorithms.
  • Dual Local Search Strategy: The combination of LS1 (focused on lower bounds) and LS2 (focused on the new fitness function) provides a robust local search mechanism that addresses different aspects of solution quality.
  • Effectiveness of Novel Components: The paper strongly suggests that the novel fitness function and local search procedures are the primary drivers of the MA's improved performance.
  • Importance of Parameter Tuning: The authors conducted extensive experiments to find optimal parameter settings (population size, crossover probability, mutation probability), highlighting that these settings significantly impact performance.

Key Results

  • The proposed MA demonstrated competitive performance against state-of-the-art algorithms on various MRCPSP instances from PSPLIB.
  • For instance sets J10 and J12, the MA was capable of providing optimal solutions within a limited number of generated schedules.
  • For other instance sets (J14, J16, J18, J20), the MA provided high-quality solutions with low average deviations from the optimum.
  • The MA achieved an improved solution for one specific instance in the J30 set (J3013_10.mm), reducing the makespan from 43 to 42.
  • A comparison of fitness functions showed that the newly proposed fitness function outperformed existing ones across all tested instance sets.

Limitations and Future Work

  • Comparison with Scatter Search: While the MA is highly competitive, the paper notes that the scatter search algorithm proposed in [18] achieved better results on some instances. This is attributed to [18]'s incorporation of resource scarceness parameters and tailored improvement methods.
  • Computational Effort: The performance of the MA is shown to be dependent on the computational effort (number of generated schedules). While it performs well, achieving optimal solutions for all instances might require significant computational resources.
  • Future Work: The paper doesn't explicitly detail future work, but the success of the proposed MA suggests potential avenues for further research could include:
  • Investigating the integration of resource scarceness characteristics into the MA.
  • Exploring more advanced crossover and mutation operators.
  • Applying the MA to larger and more complex MRCPSP instances.
  • Further refining the "strategic oscillation" mechanism or exploring other meta-heuristic frameworks.

Summary updated

Abstract

A memetic algorithm (MA) for a multi-mode resource-constrained project scheduling problem (MRCPSP) is proposed. We use a new fitness function and two very effective local search procedures in the proposed MA. The fitness function makes use of a mechanism called “strategic oscillation” to make the search process have a higher probability to visit solutions around a �sible boundary”. One of the local search procedures aims at improving the lower bound of project makespan to be less than a known upper bound, and another aims at improving a solution of an MRCPSP instance accepting infeasible solutions based on the new fitness function in the search process. A detailed computational experiment is set up using instances from the problem instance library PSPLIB. Computational results show that the proposed MA is very competitive with the state-of-the-art algorithms. The MA obtains improved solutions for one instance of set J30.
BibTeX
@article{liu2014memetic,
  author = {Shixin Liu and Di Chen and Yifan Wang},
  title = {{Memetic algorithm for multi-mode resource-constrained project scheduling problems}},
  journal = {Journal of Systems Engineering and Electronics},
  year = {2014},
  doi = {10.1109/jsee.2014.00071},
}
Figure