A moving block heuristic to minimise earliness and tardiness costs on parallel machines

Earliness and tardiness problems are commonly encountered in just-in-time manufacturing systems, where the operations are performed neither early nor late. In this paper, a parallel machine moving block heuristic (Pm-MBH) with polynomial-time computational complexity is developed to address an earliness and tardiness scheduling problem. A mixed integer program (MIP) is presented in order to analyse the solution quality of the Pm-MBH solutions. Using a paired t-test, an analysis is performed to analyse the performance of Pm-MBH when compared to time-constrained MIP (MIPH) over the experimental space. Based on the computational results, Pm-MBH obtains good solutions in a short amount of computation time.