Efficient procedures for the weighted squared tardiness permutation flowshop scheduling problem

Maria Raquel C. Costa (), Jorge M. S. Valente () and Jeffrey E. Schaller ()
Additional contact information
Maria Raquel C. Costa: NORS
Jorge M. S. Valente: Faculdade de Economia da Universidade do Porto
Jeffrey E. Schaller: Eastern Connecticut State University

Flexible Services and Manufacturing Journal, 2020, vol. 32, issue 3, No 1, 487-522

Abstract: Abstract 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.

Keywords: Scheduling; Permutation flowshop; Weighted squared tardiness; Dispatching rules; Improvement procedures (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10696-019-09363-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:flsman:v:32:y:2020:i:3:d:10.1007_s10696-019-09363-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10696

DOI: 10.1007/s10696-019-09363-6

Access Statistics for this article

Flexible Services and Manufacturing Journal is currently edited by Hans Günther

More articles in Flexible Services and Manufacturing Journal from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().