An hybrid metaheuristic, an hybrid lower bound and a Tabu search for the two-machine flowshop total tardiness problem

The classical F2∥ΣT_j problem is considered. A Tabu search and a matheuristic algorithm are proposed as upper bounds and a lower bound based on a partial relaxation of the MILP model is proposed. All these methods have been extensively tested on randomly generated instances. The results show the performances of the Tabu search algorithm. They also show the good performances of the matheuristic and of the lower bound, preferably for small instances (up to 100 jobs).