Lower bounds and simulated annealing for job shop scheduling problems with blocking constrains

Ali Gorine , Nathalie Sauer (1)

1 COSTEAM - Optimal and secure management of manufacturing systems

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.

Domaines: Modélisation et simulation; Performance et fiabilité [cs.PF]; Recherche opérationnelle [math.OC]

Ali Gorine, Nathalie Sauer. Lower bounds and simulated annealing for job shop scheduling problems with blocking constrains. IEEE Conference on Emerging Technologies and Factory Automation - ETFA'2010, Sep 2010, Bilbao, Spain. pp.1-8, ⟨10.1109/ETFA.2010.5641271⟩. ⟨inria-00601373⟩