Iterated-greedy-based algorithms with beam search initialization for the permutation flowshop to minimise total tardiness

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

Authors

Fernandez Viagas, V (Author) Other; Jorge M S Valente (Author) FEP; Framinan, JM (Author) Other

Journal

Title: Expert Systems with Applications

Vol. 94

Pages: 58-69

ISSN: 0957-4174

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 46 Citations

Scopus - 54 Citations

Other information

Authenticus ID: P-00N-5TW

DOI: 10.1016/j.eswa.2017.10.050

Abstract (EN): The permutation flow shop scheduling problem is one of the most studied operations research related problems. Literally, hundreds of exact and approximate algorithms have been proposed to optimise several objective functions. In this paper we address the total tardiness criterion, which is aimed towards the satisfaction of customers in a make-to-order scenario. Although several approximate algorithms have been proposed for this problem in the literature, recent contributions for related problems suggest that there is room for improving the current available algorithms. Thus, our contribution is twofold: First, we propose a fast beam-search-based constructive heuristic that estimates the quality of partial sequences without a complete evaluation of their objective function. Second, using this constructive heuristic as initial solution, eight variations of an iterated-greedy-based algorithm are proposed. A comprehensive computational evaluation is performed to establish the efficiency of our proposals against the existing heuristics and metaheuristics for the problem.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 12