Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm

In this study, a bi-objective multi-start simulated-annealing algorithm (BMSA) is presented for permutation flowshop scheduling problems with the objectives of minimizing the makespan and total flowtime of jobs. To evaluate the performance of the BMSA, computational experiments were conducted on the well-known benchmark problem set provided by Taillard. The non-dominated sets obtained from each of the existing benchmark algorithms and the BMSA were compared, and then combined to form a net non-dominated front. The computational results show that more than 64% of the solutions in the net non-dominated front are contributed by the proposed BMSA. It is believed that these solutions can serve as new benchmarks for future research.