Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups

• Type: Article in International Scientific Journal
• Date: 2008

Authors

Jorge M S Valente (Author) FEP; Rui A F S Alves (Author) FEP

Journal

Title: Computers and Operations Research

Vol. 35 No. 7

Pages: 2388-2405

ISSN: 0305-0548

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 47 Citations

ISI Web of Science

Scopus - 56 Citations

Scientific classification

FOS: Engineering and technology > Civil engineering

CORDIS: Social sciences > Economics > Management studies

Other information

Authenticus ID: P-003-XYD

DOI: 10.1016/j.cor.2006.11.004

Abstract (EN): In this paper, we consider the single machine weighted tardiness scheduling problem with sequence-dependent setups. We present heuristic algorithms based on the beam search technique. These algorithms include classic beam search procedures, as well as the filtered and recovering variants. Previous beam search implementations use fixed beam and filter widths. We consider the usual fixed width algorithms, and develop new versions that use variable beam and filter widths. The computational results show that the beam search versions with a variable width are marginally superior to their fixed value counterparts, even when a lower average number of beam and filter nodes is used. The best results are given by the recovering beam search algorithms. For large problems, however, these procedures require excessive computation times. The priority beam search algorithms are much faster, and can therefore be used for the largest instances.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 18