Generalised accelerations for insertion-based heuristics in permutation flowshop scheduling

Victor Fernandez-Viagas, Jose M. Molina-Pariente and Jose M. Framinan

European Journal of Operational Research, 2020, vol. 282, issue 3, 858-872

Abstract: The scheduling literature is abundant on approximate methods for permutation flowshop scheduling, as this problem is NP-hard for the majority of objectives usually considered. Among these methods, some of the most efficient ones use an insertion-type of neighbourhood to construct high-quality solutions. It is not then surprising that using accelerations to speed up the computation of the objective function can greatly reduce the running time of these methods, since a good part of their computational effort is spent in the evaluation of the objective function. Undoubtedly, the best-known of these accelerations has been employed for makespan minimisation (commonly denoted as Taillard’s accelerations). These accelerations have been extended to other related problems, but they cannot be employed for the classical permutation flowshop problem if the objective is other than the makespan. In these cases, other types of accelerations have been proposed, but they are not able to achieve a substantial reduction of the computational effort.

Keywords: Scheduling; Flow shop; Speed-up; Critical path (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719308525
Full text for ScienceDirect subscribers only

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:eee:ejores:v:282:y:2020:i:3:p:858-872

DOI: 10.1016/j.ejor.2019.10.017

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().