A cut and column generation for flowshop scheduling problems to minimize the total weighted tardiness

We propose a new formulation for the column generation for solving flowshop scheduling problems to minimize the total weighted tardiness to derive tighter bounds. In the proposed method, each column represents a two-jobs schedule where the operations of two jobs do not overlap with each other. We show that the lower bound for the original problem can be strengthened by the proposed formulation without significantly increasing the total computing time. Computational experiments demonstrate that the proposed method can derive the solutions with a smaller duality gap compared with those of the conventional formulation.