Hybrid Flow Shop with Setup Times Scheduling Problem

Mahdi Jemmali; Lotfi Hidri

doi:10.32604/csse.2023.022716

Table of Content

Open Access

ARTICLE

Hybrid Flow Shop with Setup Times Scheduling Problem

Mahdi Jemmali^1,2,3,*, Lotfi Hidri⁴
1 Department of Computer Science and Information, College of Science at Zulfi, Majmaah University, Majmaah, 11952, Saudi Arabia
2 Mars Laboratory, University of Sousse, Sousse, Tunisia
3 Department of Computer Science, Higher Institute of Computer Science and Mathematics of Monastir, Monastir University, Monastir, 5000, Tunisia
4 Industrial Engineering Department, College of Engineering, King Saud University, Riyadh, 11421, Saudi Arabia
* Corresponding Author: Mahdi Jemmali. Email:

Computer Systems Science and Engineering 2023, 44(1), 563-577. https://doi.org/10.32604/csse.2023.022716

Received 16 August 2021; Accepted 17 September 2021; Issue published 01 June 2022

Abstract

The two-stage hybrid flow shop problem under setup times is addressed in this paper. This problem is NP-Hard. on the other hand, the studied problem is modeling different real-life applications especially in manufacturing and high performance-computing. Tackling this kind of problem requires the development of adapted algorithms. In this context, a metaheuristic using the genetic algorithm and three heuristics are proposed in this paper. These approximate solutions are using the optimal solution of the parallel machines under release and delivery times. Indeed, these solutions are iterative procedures focusing each time on a particular stage where a parallel machines problem is called to be solved. The general solution is then a concatenation of all the solutions in each stage. In addition, three lower bounds based on the relaxation method are provided. These lower bounds present a means to evaluate the efficiency of the developed algorithms throughout the measurement of the relative gap. An experimental result is discussed to evaluate the performance of the developed algorithms. In total, 8960 instances are implemented and tested to show the results given by the proposed lower bounds and heuristics. Several indicators are given to compare between algorithms. The results illustrated in this paper show the performance of the developed algorithms in terms of gap and running time.

Keywords

Hybrid flow shop; genetic algorithm; setup times; heuristics; lower bound

Cite This Article

M. Jemmali and L. Hidri, "Hybrid flow shop with setup times scheduling problem," Computer Systems Science and Engineering, vol. 44, no.1, pp. 563–577, 2023.

This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.