A neighbourhood scheme with a compressed solution space for the early/tardy scheduling problem

The single machine, distinct due date, early/tardy machine scheduling problem closely models the situation faced by Just-In-Time manufacturers. This paper develops a new method of finding good quality solutions to this scheduling problem by using the concept of a ‘compressed solution space’, based on a binary representation of the early/tardy scheduling problem, and tabu search. A heuristic which simultaneously sequences and schedules the jobs is developed to perform the conversion between the compressed and physical solution spaces. Results show that the compressed solution space performs well with small problems, and is superior to standard tabu search solution spaces for large-scale, realistically sized problems.