The reversibility property in a job-insertion tiebreaker for the permutational flow shop scheduling problem

Alexander J. Benavides and Antony Vera

European Journal of Operational Research, 2022, vol. 297, issue 2, 407-421

Abstract: The best performing approximate methods proposed for the permutational flow shop scheduling problem with makespan minimization are the well known NEH constructive heuristic and the iterated greedy algorithm. Both methods are based on the successive insertion (or reinsertion) of jobs into a partial schedule, evaluating the makespan of the resulting schedule for all insertion positions, and selecting the insertion position that presents the shortest makespan. Frequently, there are many tied insertion positions that produce such shortest makespan. Thus, a tiebreaker must be used to discern a selection among the tied insertion positions. Many tiebreakers have been proposed in the literature for this case. These tiebreakers improve the results produced by approximate methods when embedded into them. In this paper we propose two new tiebreakers that use a weighted and an unweighted approximation of the idle time increment produced by inserting the job into each tied insertion position. They were designed considering the reversibility property of the PFSSP. Our computational experiments show that the proposed tiebreakers outperform tiebreakers from the literature when evaluated within the NEH heuristic and within the iterated greedy algorithm. The iterated greedy algorithms with the proposed tiebreakers embedded are the best approximate methods so far for the permutational flow shop scheduling problem.

Keywords: Scheduling; Flow shop; Makespan; Tiebreaker; Heuristics (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721004288
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:297:y:2022:i:2:p:407-421

DOI: 10.1016/j.ejor.2021.05.014

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 ().