Name
Title | ||
|---|---|---|
An advanced scatter search algorithm for solving job shops with sequence dependent and non-anticipatory setups. |
Abstract | ||
|---|---|---|
In this paper we tackle the makespan minimization in the job shop scheduling problem with sequence-dependent non-anticipatory setup times. To this end, we design a scatter search algorithm which incorporates path relinking and tabu search in its core. The good performance of this algorithm relies on a new neighborhood structure proposed in this paper based on a graph model that incorporates the non-anticipatory characteristic of setup times. To define this structure, we consider all single moves, i.e., reversals of single arcs in the solution graph, and we give some conditions that establish the feasibility and the chance of improvement for the neighbors. We present the results of an experimental study across usual benchmarks to analyze our algorithm and to compare it with the state-of-the-art. In particular, our approach establishes new best solutions for all the instances. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.3233/AIC-140631 | AI Commun. |
Keywords | Field | DocType |
Job shop scheduling,neighborhood structures,scatter search,path relinking,tabu search,non-anticipatory setup times | Graph,Mathematical optimization,Job shop scheduling,Search algorithm,Job shop scheduling problem,Computer science,Minification,Artificial intelligence,Tabu search,Machine learning,Graph model | Journal |
Volume | Issue | ISSN |
28 | 2 | 0921-7126 |
Citations | PageRank | References |
4 | 0.40 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Miguel A. González | 1 | 153 | 12.44 |
| Camino R. Vela | 2 | 346 | 31.00 |
| Ramiro Varela | 3 | 301 | 29.96 |
| Inés González-Rodríguez | 4 | 115 | 10.73 |