کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477330 | 1446153 | 2009 | 13 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A filter-and-fan approach to the job shop scheduling problem A filter-and-fan approach to the job shop scheduling problem](/preview/png/477330.png)
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.
Journal: European Journal of Operational Research - Volume 194, Issue 3, 1 May 2009, Pages 650–662