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

• The earliness tardiness permutation flow shop with forced idle time is NP hard.
• The new proposed mixed integer program is better than the adaptation of existing models.
• A variable neighborhood search obtains good solutions in reduced runtime.
• The hybridization of VNS and MIP provides better results than either approach.

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 HH 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, HH 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 HH. This hybrid approach can be easily extended to more complex scheduling problems.