Matheuristic algorithms to minimize total tardiness in flow shop scheduling

In the permutation flow shop scheduling problem, jobs have to be scheduled on a set of machines. The jobs are processed on the machines in the same order. The objective of this study is to minimize the total tardiness. Heuristic algorithms and new matheuristic algorithms are proposed for solving this problem. The matheuristic methods are approximated algorithms that have been proposed initially for solving some combinatorial optimization problems. These methods embed exact resolution into (meta)heuristic approaches. This type of resolution method has received a great interest in the literature because of their very good performances for solving some difficult problems. The author also considers a problem where an m-machine permutation flow shop scheduling problem and a vehicle routing problem are integrated and the objective is to minimize the total tardiness. An introduction of a direct coding for a complete solution and of a Tabu search algorithm are proposed for finding a production sequence and trips. The results show that the Tabu search greatly improves the initial solution given by Earliest Due Date heuristic where each trip serves only one job at a time.