Integrating iterative crossover capability in orthogonal neighborhoods for scheduling resource-constrained projects

Area of Science:

• Optimization Algorithms
• Computational Intelligence
• Operations Research

Background:

• Evolutionary algorithms and local search are common optimization techniques.
• Integrating these methods can potentially enhance performance.
• The resource-constrained project scheduling problem (RCPSP) is a complex optimization challenge.

Purpose of the Study:

• To develop and evaluate an effective hybrid evolutionary search method.
• To integrate genetic algorithms (GA) with local search (LS) for robust optimization.
• To apply the hybrid method to the resource-constrained project scheduling problem (RCPSP).

Main Methods:

• A hybrid evolutionary search method integrating a genetic algorithm with a local search.
• The local search component uses two neighborhood schemes for diversification.
• Crossover operators enhance locally optimal solutions from both neighborhood schemes.
• The local search provides new solutions to the genetic algorithm pool when needed.

Main Results:

• The hybrid method demonstrates robustness and effectiveness.
• The local search component diversifies the search by examining unvisited regions.
• The genetic algorithm component intensifies the search by recombining high-quality solutions.
• Computational experiments on 2,040 benchmark instances showed the procedure to be very effective.

Conclusions:

• The hybrid evolutionary search method effectively balances diversification and intensification.
• This balance allows for exploitation of search space structure to produce superb solutions.
• The implemented procedure is highly effective for the resource-constrained project scheduling problem.