Minimizing total tardiness in two-machines flowshop with setup, processing and removal time separated

In this paper, we discuss the total tardiness in two-machines flowshop problem with setup and removal time separated, where setup step and removal step of the same job overlap on two machines, but the processing step cannot, and there is not idleness on the machine M1. We give the conditions satisfied by sequence in solution of total tardiness flowshop problem. From these conditions we construct some approximation algorithms. In order to get the branch and bound method, we also give the lower bound. The computational results indicate that the above approximation algorithm is efficient.