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

作者：M'Hallah R^*

来源：International Journal of Production Research, 2014, 52(13): 3802-3819.

DOI：10.1080/00207543.2014.899719

• earliness and tardiness
• permutation flow shop scheduling
• distinct due dates
• variable neighborhood search
• iterated local search
• variable neighborhood descent

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%.

• 出版日期2014