Heuristics for no-wait flowshops with makespan subject to mean completion time

摘要

This paper addresses the m-machine no-wait flowshop scheduling problem. Two performance measures are considered; makespan and mean completion time. The objective is to find a sequence that minimizes makespan such that mean completion time is not greater than a certain value. In case such a certain value is not known, an algorithm is presented to find an upper bound on the mean completion time. A heuristic, called HA, a simulated annealing (SA) heuristic, a modified simulated annealing (mSA) heuristic, and two more heuristics, called HH1 and HH2, which are combination of HA and mSA, are proposed for the problem. The proposed heuristics are assessed on randomly generated problems with different number of jobs and machines. Computational experiments revealed that the overall average relative errors of SA, HA, mSA, HH1 and HH2, were 2.99, 1.33, 0.78, 0.04, and 0.87, respectively. These results are also statistically verified. Therefore, the heuristic HH1 significantly outperforms the other heuristics.