Lower bounds and simulated annealing for job shop scheduling problems with blocking constrains
Résumé
In this paper, we consider the job shop scheduling problem with a particular blocking constraint. The objective is the minimization of the makespan. In this model, a conflict is due to the non-compliance of the precedence and blocking constraints. A necessary and sufficient condition to obtain this conflict is presented. A lower bound to solve this problem is given and a metaheuristic method based on simulated annealing is presented to obtain a solution. Its performances are compared with the optimal solutions.