Metaheuristics for the job-shop scheduling problem with machine availability constraints

This paper addresses the job-shop scheduling problem in which the machines are not available during the whole planning horizon and with the objective of minimizing the makespan. The disjunctive graph model is used to represent job sequences and to adapt and extend known structural properties of the classical job-shop scheduling problem to the problem at hand. These results have been included in two metaheuristics (Simulated Annealing and Tabu Search) with specific neighborhood functions and diversification structures. Computational experiments on problem instances of the literature show that our Tabu Search approach outperforms Simulated Annealing and existing approaches.