A memetic algorithm for restoring feasibility in scheduling with limited makespan.

When solving a scheduling problem, users are often interested in finding a schedule optimizing a given objective function. However, in some settings there can be hard constraints that make the problem unfeasible. In this paper we focus on the task of repairing infeasibility in job shop scheduling problems with a hard constraint on the makespan. In this context, earlier work addressed the problem of computing the largest subset of the jobs that can be scheduled within the makespan constraint. Herein, we face a more general weighted version of the problem, consisting in computing a feasible subset of jobs maximizing their weighted sum. To this aim, we propose an efficient memetic algorithm, that combines a genetic algorithm with a local search method, also proposed in the paper. The results from an experimental study show the practical suitability of our approach. [ABSTRACT FROM AUTHOR]