Fragmental optimization on the 2-machine bicriteria flowshop scheduling problem

The 2-machine bicriteria flowshop scheduling problem F2||(ΣC_i/C_max) is studied in this paper, which minimizes the total flow time subject to the makespan of the schedule being minimum. This problem is known to be strongly NP-hard, and several heuristic algorithms have been proposed to solve it. In this paper, we present a new approach, which we named fragmental optimization (FO), that combines the dynamic programming and local search strategies. Extensive experimentation shows that our FO algorithm outperforms existing heuristics and provides solutions that are very close to the optimal.