کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475826 | 699381 | 2012 | 8 صفحه PDF | دانلود رایگان |

In this paper we consider the well-known single machine scheduling problem with release dates and minimization of the total job completion time. For solving this problem, denoted by 1|rj|∑Cj1|rj|∑Cj, we provide a new metaheuristic which is an extension of the so-called filtered beam search proposed by Ow and Morton [30]. This metaheuristic, referred to as a Genetic Recovering Beam Search (GRBS), takes advantages of a Genetic Local Search (GLS) algorithm and a Recovering Beam Search (RBS) in order to efficiently explore the solution space. In this paper we present the GRBS framework and its application to the 1|rj|∑Cj1|rj|∑Cj problem. Computational results show that it consistently yields optimal or near-optimal solutions and that it provides interesting results by comparison to GLS and RBS algorithms. Moreover, these results highlight that the proposed algorithm outperforms the state-of-the-art heuristics.
Journal: Computers & Operations Research - Volume 39, Issue 6, June 2012, Pages 1257–1264