Minimizing total flow time in permutation flowshop environment

The permutation flowshop scheduling problem with the objective of minimizing total flow time is known as a NP-hard problem, even for the two-machine cases. Because of the computational complexity of this problem, a multi-start simulated annealing (MSA) heuristic, which adopts a multi-start hill climbing strategy in the simulated annealing (SA) heuristic, is proposed to obtain close-to-optimal solutions. To examine the performance of the MSA algorithm, a set of computational experiments was conducted, on a well-known benchmark-problem set from the literature. The experiment results show that the performance of the traditional single-start SA can be significantly improved by incorporating the multi-start hill climbing strategy. In addition, the proposed MSA algorithm is highly effective and efficient as compared with the other state-of-the-art metaheuristics on the same benchmark-problem instances. In terms of both solution quality and computational expense, the proposed algorithm contributes significantly to this extremely challenging scheduling problem.