Coupling Genetic Local Search and Recovering Beam Search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates

Abstract : 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.
Type de document :
Article dans une revue
Computers and Operations Research, Elsevier, 2012, 39 (6), pp.1257-1264. 〈10.1016/j.cor.2010.12.007〉
Liste complète des métadonnées

https://hal-univ-tours.archives-ouvertes.fr/hal-01003845
Contributeur : Vincent T'Kindt <>
Soumis le : mardi 10 juin 2014 - 17:34:56
Dernière modification le : mercredi 21 mars 2018 - 10:54:09

Identifiants

Collections

Citation

Mohammed Ali Rakrouki, Talel Ladhari, Vincent T'Kindt. Coupling Genetic Local Search and Recovering Beam Search algorithms for minimizing the total completion time in the single machine scheduling problem subject to release dates. Computers and Operations Research, Elsevier, 2012, 39 (6), pp.1257-1264. 〈10.1016/j.cor.2010.12.007〉. 〈hal-01003845〉

Partager

Métriques

Consultations de la notice

53