An efficient approach to simplify the calculation of makespan in permutation flow shop scheduling problem

摘要

This paper discusses an efficient approach to reduce the evaluation time in the local search for solving the permutation flow shop problem with makespan objective. Based on the proved theorems, some different formulae are proposed to calculate makespan, which can use as much repeated information from the former calculations. Furthermore, computational experiments are given and compared with those results yielded by one basic method and one improved method in the literature. These results show that the given method is more effective in solving large size instances, in which the calculation time can be greatly reduced.