Minimizing total earliness and tardiness on a permutation flow shop using VNS and MIP

This paper addresses the NP hard earliness tardiness m-stage permutation flow shop scheduling problem where idle time can be inserted. It proposes different new formulations for the problem, and provides computational proof of the superiority of the positional model. This latter yields when solved with a mixed integer programming solver the exact solution for small or easy instances. For large and difficult instances, the paper proposes an approximate approach H that hybridizes variable neighborhood search (VNS) with mixed integer programming (MIP). VNS searches for the best sequence of the jobs whereas MIP inserts idle time optimally for each sequence. In addition, H feeds the VNS near global optimum and its value to the solver of the positional model. They constitute a good initial solution and a valid upper bound. Extensive experimental investigation highlights the usefulness of the hybridization and the competitiveness of H. This hybrid approach can be easily extended to more complex scheduling problems.