Heuristics to optimize total completion time subject to makespan in no-wait flow shops with sequence-dependent setup times

Fernando Siqueira de Almeida and Marcelo Seido Nagano

Journal of the Operational Research Society, 2023, vol. 74, issue 1, 362-373

Abstract: We propose four algorithms for the no-wait flow shop scheduling problem. The objective is minimizing total completion time such that makespan is not greater than a maximum value. We address the problem with sequence-dependent setup times, an important production constraint that has never been considered for this problem before. The proposed algorithms start from an initial solution and then iterate through a process that destroys and repairs the incumbent solution in order to improve it. The methods are build combining distinct destruction and construction mechanisms, where the search intensification-diversification is explored at different levels. After an initial assessment, the best proposed algorithm (IG4) is chosen to be compared with three literature methods (PAL, TOB, ISA-2) developed for similar problems. Computational experiments revealed that the overall average relative percentage deviation of PAL, TOB, ISA-2, and IG4 are 10.97%, 4.44%, 2.07%, and 0.36%, respectively. The statistical analysis confirms that IG4 significantly outperforms the existing methods.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2022.2039569 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjorxx:v:74:y:2023:i:1:p:362-373

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2022.2039569

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().