Efficient constructive and composite heuristics for the Permutation Flowshop to minimise total earliness and tardiness

摘要

In this paper we address the problem of scheduling jobs in a permutation fiowshop with a just-in-time objective, i.e. the minimisation of the sum of total tardiness and total earliness. Since the problem is NP-hard, there are several approximate procedures available for the problem, although their performance largely depends on the due dates of the specific instance to be solved. After an in-depth analysis of the problem, different cases or sub-problems are identified and, by incorporating this knowledge, four heuristics are proposed: a fast constructive heuristic, and three different local search procedures that use the proposed constructive heuristic as initial solution.