Heuristics for a flowshop scheduling problem with stepwise job objective function

Luciana S. Pessoa and Carlos E. Andrade

European Journal of Operational Research, 2018, vol. 266, issue 3, 950-962

Abstract: In this work, we introduce the Flowshop Scheduling Problem with Delivery Dates and Cumulative Payoffs. This problem is a variation of the flowshop scheduling problem with job release dates that maximizes the total payoff with a stepwise job objective function. This paper contributes towards proposing a mathematical formulation for this new problem and an original constructive heuristic. Additionally, we develop a new benchmark of 300 hard instances which are available in a public repository. Besides, we provide primal and dual bounds for them. Extensive computational experiments were carried out taking into account classical constructive heuristics and hybrid local searches. Results show the merit of the FF heuristic when compared to other classical heuristics for flowshop scheduling problems. Additionally, we compare an Iterated Local Search (ILS), an Iterated Greedy Search (IGS), and a Biased Random-Key Genetic Algorithm (BRKGA), both customized for the studied problem, and a commercial mixed integer programming solver. The comparison between these methods showed that the BRKGA starting with a solution from FF heuristic is able to find the best solutions in a very short period of time. Iterated local Search and the commercial solver presented significantly worse results than the aforementioned methods.

Keywords: Flowshop scheduling; Heuristics; Metaheuristics (search for similar items in EconPapers)
Date: 2018
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/S037722171730958X
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:266:y:2018:i:3:p:950-962

DOI: 10.1016/j.ejor.2017.10.045

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