《2016 A filter-and-fan approach to the job shop scheduling problem》.pdf

Available online at European Journal of Operational Research 194 (2009) 650–662 /locate/ejor Discrete Optimization A filter-and-fan approach to the job shop scheduling problem ´ a,* b Cesar Rego , Renato Duarte a School of Business Administration, University of Mississippi, University, MS 38677, USA b ˆ ´ ´ ´ Escola Superior de Ciencias Empresariais, Instituto Politecnico de Setubal, Estefanilha, 2910-503 Setubal, Portugal Received 4 February 2007; accepted 28 December 2007 Available online 16 January 2008 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 (FF) procedure, uses the SBP as a subroutine to generate a starting solution and to enhance the best schedules produced. The FF approach is a local search procedure that generates compound moves by a strategically abbreviated form of tree