An efficient iterated greedy algorithm for a multi-objective no-wait flow shop problem with sequence dependent setup times

Fernando Siqueira Almeida () and Marcelo Seido Nagano ()
Additional contact information
Fernando Siqueira Almeida: University of Sao Paulo
Marcelo Seido Nagano: University of Sao Paulo

4OR, 2024, vol. 22, issue 1, No 3, 45 pages

Abstract: Abstract In this article, we address the m-machine no-wait flow shop scheduling problem with sequence dependent setup times. The objective is to minimize total tardiness subject to an upper bound on makespan. Although these constraints and performance measures have all been extensively studied independently, they have never been considered together in this problem before. So, this multi-criteria approach provides more realistic solutions for complex scenarios. To solve the problem, we developed a new heuristic called $$IG_{A}$$ I G A . The proposed method repeatedly performs a process of destruction and construction of an existing solution in order to improve it. The novelty of this method includes a mechanism capable of adapting the destruction intensity according to the instance size and the number of iterations, calibrating the algorithm during the search. Computational experiments indicate that $$IG_{A}$$ I G A outperforms the best literature method for similar applications in overall solution quality by about 35%. Therefore, $$IG_{A}$$ I G A is recommended to solve the problem.

Keywords: Iterated greedy; Flow shop; No-wait; Sequence-dependent setup; Total tardiness; Makespan; 68T20; 90C59 (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10288-023-00535-7 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:aqjoor:v:22:y:2024:i:1:d:10.1007_s10288-023-00535-7

Ordering information: This journal article can be ordered from
https://www.springer ... ch/journal/10288/PSE

DOI: 10.1007/s10288-023-00535-7

Access Statistics for this article

4OR is currently edited by Yves Crama, Michel Grabisch and Silvano Martello

More articles in 4OR from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().