A filter-and-fan approach to the job shop scheduling problem |
| |
Authors: | César Rego Renato Duarte |
| |
Institution: | 1. School of Business Administration, University of Mississippi, University, MS 38677, USA;2. Escola Superior de Ciências Empresariais, Instituto Politécnico de Setúbal, Estefanilha, 2910-503 Setúbal, Portugal |
| |
Abstract: | The job shop scheduling problem (JSSP) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a new heuristic algorithm for the JSSP that effectively combines the classical shifting bottleneck procedure (SBP) with a dynamic and adaptive neighborhood search procedure. Our new search method, based on a filter-and-fan (F&F) procedure, uses the SBP as a subroutine to generate a starting solution and to enhance the best schedules produced. The F&F approach is a local search procedure that generates compound moves by a strategically abbreviated form of tree search. Computational results carried out on a standard set of 43 benchmark problems show that our F&F algorithm performs more robustly and effectively than a number of leading metaheuristic algorithms and rivals the best of these algorithms. |
| |
Keywords: | Heuristics Local search Job shop problem |
本文献已被 ScienceDirect 等数据库收录! |
|