Beam search heuristics for quadratic earliness and tardiness scheduling / J. M. S. Valente in Journal of the operational research society (JORS), Vol. 61 N° 4 (Avril 2010)  

Public ISBD [article]  inJournal of the operational research society (JORS) > Vol. 61 N° 4 (Avril 2010) . - pp. 620–631 Titre : Beam search heuristics for quadratic earliness and tardiness scheduling Type de document : texte imprimé Auteurs : J. M. S. Valente, Auteur Année de publication : 2010 Article en page(s) : pp. 620–631 Note générale : Recherche opérationnelle Langues : Anglais (eng) Mots-clés : Scheduling Heuristics Beam search Single machine Quadratic earliness tardiness Index. décimale : 001.424 Résumé : In this paper, we present beam search heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. These heuristics include classic beam search procedures, as well as filtered and recovering algorithms. We consider three dispatching heuristics as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search procedures. The computational results show that using better dispatching heuristics improves the effectiveness of the beam search algorithms. The performance of the several heuristics is similar for instances with low variability. For high variability instances, however, the detailed, filtered and recovering beam search (RBS) procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small- to medium-sized instances. For larger instances, however, this procedure requires excessive computation times, and the RBS algorithm then becomes the heuristic of choice. DEWEY : 001.424 ISSN : 0160-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v61/n4/abs/jors2008191a.html [article] Beam search heuristics for quadratic earliness and tardiness scheduling [texte imprimé] / J. M. S. Valente, Auteur . - 2010 . - pp. 620–631. Recherche opérationnelle Langues : Anglais (eng) in Journal of the operational research society (JORS) > Vol. 61 N° 4 (Avril 2010) . - pp. 620–631 Mots-clés : Scheduling Heuristics Beam search Single machine Quadratic earliness tardiness Index. décimale : 001.424 Résumé : In this paper, we present beam search heuristics for the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. These heuristics include classic beam search procedures, as well as filtered and recovering algorithms. We consider three dispatching heuristics as evaluation functions, in order to analyse the effect of different rules on the performance of the beam search procedures. The computational results show that using better dispatching heuristics improves the effectiveness of the beam search algorithms. The performance of the several heuristics is similar for instances with low variability. For high variability instances, however, the detailed, filtered and recovering beam search (RBS) procedures clearly outperform the best existing heuristic. The detailed beam search algorithm performs quite well, and is recommended for small- to medium-sized instances. For larger instances, however, this procedure requires excessive computation times, and the RBS algorithm then becomes the heuristic of choice. DEWEY : 001.424 ISSN : 0160-5682 En ligne : http://www.palgrave-journals.com/jors/journal/v61/n4/abs/jors2008191a.html

Exemplaires

Code-barres	Cote	Support	Localisation	Section	Disponibilité
aucun exemplaire