New approximation algorithms for two-machine flow shop total completion time problem

摘要

This paper considers the two-machine flow shop scheduling problem to minimize the sum of completion times. We design two heuristic algorithms, Triangle Shortest Processing Time first (TSPT) and Dynamic Triangle Shortest Processing Time first (DTSPT), for problems F2∥ΣCj and F2|rj|ΣCj respecttively. Moreover, to further evaluate the heuristics numerically, two new lower bounds with performance guarantee are provided for problems F2∥ΣCj and F2|rj|ΣCj, respectively. At the end of the paper, a series of simulation experiments are conducted to show the effectiveness of the new heuristics.