An iterated local search variable neighborhood descent hybrid heuristic for the total earliness tardiness permutation flow shop

This paper considers the minimal earliness tardiness m-machine permutation flow shop scheduling problem with distinct due dates and no inserted idle time when a job is waiting. It models the problem as a mixed integer program, and approximately solves it using V, a fast variable neighborhood based hybrid heuristic. V is an iterated local search that applies a variable neighborhood descent as its search engine. The numerical testing provides computational proof of the good performance of V, which matches existing upper bounds of 20.02% benchmark instances and tightens 70.54% ones with an average percent deviation from the best upper bound of 0.07%.