A moving block heuristic for minimizing earliness and tardiness on a single machine with unrestrictive common due dates

A moving block heuristic (MBH) is developed for earliness-tardiness scheduling problems, which are observed in just-in-time (JIT) production environments. The MBH is described for the single-machine environment under unrestrictive job due date conditions. The proposed MBH, which has polynomial computational complexity, outperforms previous heuristic solution approaches for 16 reference single-machine problems from the open literature. Experimental design results confirm the efficacy of the MBH over a wide range of single-machine earliness-tardiness problem instances.