Minimising total weighted earliness and tardiness penalties on identical parallel machines using a fast ruin-and-recreate algorithm

This paper studies the scheduling problem of minimising total weighted earliness and tardiness penalties on identical parallel machines against a restrictive common due date. This problem is NP-hard in the strong sense and arises in many just-in-time production environments. A fast ruin-and-recreate (FR&R) algorithm is proposed to obtain high-quality solutions to this complex problem. The proposed FR&R algorithm is tested on a well-known set of benchmark test problems that are taken from the literature. Computational results provide evidence of the efficiency of FR&R, which consistently outperform existing algorithms when applied to benchmark instances. This work provides a viable alternative approach for efficiently solving this practical but complex scheduling problem.