Repairing infeasibility in scheduling via genetic algorithms

Resumen

Scheduling problems arise in an ever increasing number ofapplication domains. Although efficient algorithms exist for a variety of such problems, sometimes it is necessary to satisfy hard constraints that make the problem unfeasible. In this situation, identifying possible ways of repairing infeasibility represents a task of utmost interest. We consider this scenario in the context of job shop scheduling with a hard makespan constraint and address the problem of finding the largest possible subset of the jobs that can be scheduled within such constraint. To this aim, we develop a genetic algorithm that looks for solutions in the searchspace defined by an efficient solution builder, also proposed in the paper. Experimental results show the suitability of our approach.