A repairing technique for the local search of the job-shop problem

The local search technique has become a widely used tool for solving many combinatorial optimization problems. In the case of the job-shop the implementation of such a technique is not straightforward at all due to the existence of the technological constraints among the operations that belong to the same job. Their presence renders a certain set of schedules infeasible. Consequently, special attention is required when defining optimization algorithms to prevent the possibility of reaching an infeasible schedule during execution. Traditionally, the problem is tackled on the neighborhood level by using only a limited set of moves for which feasibility inherently holds. This paper proposes an alternative way to avoid infeasibility by incorporating a repairing technique into the mechanism for applying moves to a schedule. Whenever an infeasible move is being applied, a repairing mechanism rearranges the underlying schedule in such a way that the feasibility of the move is restored. The possibility of reaching infeasible solutions is, therefore, eliminated on the lowest possible conceptual level. Consequently, neighborhood functions need not to be constrained to a limited set of feasible moves any more. (C) 2002 Published by Elsevier B.V.