Efficient repairs of infeasible job shop problems by evolutionary algorithms

We address the task of repairing infeasibility in the context of infeasible job shop scheduling problems with a hard constraint on the maximum makespan allowed. For this purpose, we adopt a job-based view of repairs, that allows for dropping some of the jobs and so gives rise to the problem of computing the largest subset of jobs that can be scheduled under the makespan constraint. Recent work proposed a genetic algorithm for solving this problem, which integrates an efficient solution builder for defining the search space. In this paper, we build on this earlier work and make several contributions. We provide a formal analysis of both the search space and the solution builder. Then, we propose two important enhancements to the genetic algorithm: first, we develop a new solution builder aimed at reducing the number of feasibility tests, making the search process more efficient. In addition, we propose a more effective procedure for testing the feasibility of different subsets of jobs under the given makespan constraint based on the use of a light-weight genetic algorithm. Experimental results show that the proposed methods are effective at solving the problem, and that the enhancements bring significant improvements.

Automated summary

We address the task of repairing infeasibility in job shop scheduling problems with a hard constraint on the maximum makespan. By adopting a job-based view of repairs and proposing enhancements to a genetic algorithm, we aim to improve efficiency and effectiveness in solving the problem. The proposed methods show significant improvements in experimental results.