Algorithms for three-machine flowshop scheduling problem to minimize makespan with uncertain processing times

Allahverdi A., Allahverdi M.

RAIRO-OPERATIONS RESEARCH, vol.57, no.4, pp.1733-1743, 2023 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 57 Issue: 4
  • Publication Date: 2023
  • Doi Number: 10.1051/ro/2023091
  • Journal Name: RAIRO-OPERATIONS RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, ABI/INFORM, Aerospace Database, Business Source Elite, Business Source Premier, Communication Abstracts, Metadex, zbMATH, Civil Engineering Abstracts
  • Page Numbers: pp.1733-1743
  • Keywords: Algorithm, Flowshop, Makespan, Scheduling, Uncertain processing times
  • Gazi University Affiliated: Yes

Abstract

We address the three-machine flowshop scheduling problem to minimize makespan where processing times are uncertain within some lower and upper bounds. We propose sixteen algorithms based on Johnson's algorithm, which is known to yield the optimal solution for the three-machine flowshop problem under certain cases. The proposed algorithms are computationally evaluated based on randomly generated data. Computational experiments indicate that one of the proposed algorithms, algorithm AL-7, significantly performs better than the rest. Tests of hypotheses were performed to statistically confirm the results. In algorithm AL-7, more weight is given to the processing times of jobs on the first and the third machines compared to those of the second machine. Moreover, both the lower and upper bounds of job processing times on all three machines are utilized. Furthermore, algorithm AL-7 is shown to perform the best regardless of the extreme distributions considered. Hence, it is recommended as the best algorithm.