Paper Info
Title
Fast Local Search for Fuzzy Job Shop Scheduling
Abstract
In the sequel, we propose a new neighbourhood structure for local search for the fuzzy job shop scheduling problem. This is a variant of the well-known job shop problem, with uncertainty in task durations modelled using fuzzy numbers and where the goal is to minimise the expected makespan of the resulting schedule. The new neighbourhood structure is based in changing the relative order of subsequences of tasks within critical blocks. We study its theoretical properties and provide a makespan estimate which allows to select only feasible neighbours while covering a greater portion of the search space than a previous neighbourhood from the literature. Despite its larger search domain, experimental results show that this new structure notably reduces the computational load of local search with respect to the previous neighbourhood while maintaining or even improving solution quality.
Year
DOI
Venue
2010
10.3233/978-1-60750-606-5-739
ECAI
Keywords
Field
DocType
expected makespan,new neighbourhood structure,fuzzy number,previous neighbourhood,search space,fast local search,larger search domain,fuzzy job shop scheduling,makespan estimate,new structure,local search,job shop scheduling
Mathematical optimization,Job shop scheduling,Computer science,Job shop scheduling problem,Job shop,Flow shop scheduling,Fuzzy logic,Neighbourhood (mathematics),Artificial intelligence,Local search (optimization),Fuzzy number,Machine learning
Conference
Volume
ISSN
Citations 
215
0922-6389
11
PageRank 
References 
Authors
0.49
23
3
Name
Order
Citations
PageRank
Jorge Puente117113.16
Camino R. Vela234631.00
Inés González-Rodríguez311510.73