Efficient procedures for the weighted squared tardiness permutation flowshop scheduling problem

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

Authors

Costa, MRC (Author) Other; Jorge M S Valente (Author) FEP; Schaller, JE (Author) Other

Journal

Title: Flexible Services and Manufacturing Journal

Vol. 32

Pages: 487-522

ISSN: 1936-6582

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 8 Citations

Scopus - 8 Citations

Other information

Authenticus ID: P-00Q-VFJ

DOI: 10.1007/s10696-019-09363-6

Abstract (EN): This paper addresses a permutation flowshop scheduling problem, with the objective of minimizing total weighted squared tardiness. The focus is on providing efficient procedures that can quickly solve medium or even large instances. Within this context, we first present multiple dispatching heuristics. These include general rules suited to various due date-related environments, heuristics developed for the problem with a linear objective function, and procedures that are suitably adapted to take the squared objective into account. Then, we describe several improvement procedures, which use one or more of three techniques. These procedures are used to improve the solution obtained by the best dispatching rule. Computational results show that the quadratic rules greatly outperform the linear counterparts, and that one of the quadratic rules is the overall best performing dispatching heuristic. The computational tests also show that all procedures significantly improve upon the initial solution. The non-dominated procedures, when considering both solution quality and runtime, are identified. The best dispatching rule, and two of the non-dominated improvement procedures, are quite efficient, and can be applied to even very large-sized problems. The remaining non-dominated improvement method can provide somewhat higher quality solutions, but it may need excessive time for extremely large instances.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 36