Heuristics for the two-machine flowshop scheduling problem to minimise makespan with bounded processing times

Abstract

The two-machine flowshop scheduling problem of minimising makespan is addressed where jobs have random processing times that are bounded within certain intervals. The probability distributions of job processing times within intervals are not known. The only known information about job processing times is the lower and upper bounds. The decision concerning the solution to the problem, i.e. finding a sequence, has to be made based on these bounds. Different heuristics using the bounds are proposed, and the proposed heuristics are compared based on randomly generated data. Computational analysis has shown that three of the proposed heuristics perform well with an overall average error of less than one percent. Moreover, for symmetric distributions, it is also shown that one of the heuristics, which applies Johnson's algorithm to the average of the lower and upper bounds, performs best with an overall average percentage error of 0.71. The obtained results are also shown to be consistent with recent results reported in the literature.