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

¹ Department of Mathematical Sciences, School of Natural Sciences, Kean University, 1000 Morris Ave, Union, NJ 07083, USA
² Department of Industrial and Management Systems Engineering, Kuwait University, P.O. Box 5969, Safat, Kuwait

^* Corresponding author: muallahv@kean.edu

Received: 18 November 2018
Accepted: 27 January 2020

Abstract

We consider the four-machine flowshop scheduling problem to minimize makespan where processing times are uncertain. The processing times are within some intervals, where the only available information is the lower and upper bounds of job processing times. Some dominance relations are developed, and twelve algorithms are proposed. The proposed algorithms first convert the four-machine problem into two stages, then, use the well-known Johnson’s algorithm, known to yield the optimal solution for the two-stage problem. The algorithms also use the developed dominance relations. The proposed algorithms are extensively evaluated through randomly generated data for different numbers of jobs and different gaps between the lower and upper bounds of processing times. Computational experiments indicate that the proposed algorithms perform well. Moreover, the computational experiments reveal that one of the proposed algorithms, Algorithm A7, performs significantly better than the other eleven algorithms for all possible combinations of the number of jobs and the gaps between the lower and upper bounds. More specifically, error percentages of the other eleven algorithms range from 2.3 to 27.7 times that of Algorithm A7. The results have been confirmed by constructing 99% confidence intervals and tests of hypotheses using a significance level of 0.01.