Metaheuristic solutions to the “Job shop scheduling problem with sequence-dependent setup times”

Article type: Other

Authors: González, Miguel A.

Affiliations: Computing Technologies Group, Department of Computing, Artificial Intelligence Center, University of Oviedo, Campus of Viesques, 33271 Gijón, Spain. E-mail: [email protected]

Abstract: In this dissertation, we propose solving methods for the job shop scheduling problem with sequence-dependent setup times, considering four different objective functions. The formal properties of the problem are studied. Two new neighborhood structures are proposed, with their respective feasibility and non-improving conditions, as well as an algorithm for fast neighbors' cost estimation. These structures are embedded in local search procedures, and their hybridization with a genetic algorithm is also studied. The experimental results show that the proposed methods obtain excellent results, improving in many cases the state of the art.

Keywords: Job shop scheduling, setup times, genetic algorithm, local search

DOI: 10.3233/AIC-130571

Journal: AI Communications, vol. 26, no. 4, pp. 419-421, 2013