MILP-based local search procedures for minimizing total tardiness in the No-idle Permutation Flowshop Problem
研究了无空闲排列流水车间调度问题，以最小化总延误为目标，提出了两种混合整数线性规划模型和六种局部搜索方法，其中两种方法显著优于现有元启发式算法，更新了63%的已知最优解。
We consider the No-idle Permutation Flowshop Scheduling Problem (NPFSP) with a total tardiness criterion. We present two Mixed Integer Linear Programming (MILP) formulations based on positional and precedence variables, respectively. We study six local search procedures that explore two different neighborhoods by exploiting the MILP formulations. Our computational experiments show that two of the proposed procedures strongly outperform the state-of-the-art metaheuristic. We update 63% of the best known solutions of the instances in Taillards’ benchmark, and 77% if we exclude those instances for which we proved that the previous best known solutions are optimal.