Split-merge: using exponential neighborhood search for scheduling a batching machine

We address the problem of scheduling a single batching machine to minimize
the maximum lateness with restricted batch size. A solution for this NP-hard
problem is dened by a selection of jobs for each batch and an ordering of
those batches. Instead we choose to represent solutions as a sequence of jobs.
This is a reasonable approach since we have developed a dynamic programming
formulation to nd a schedule which minimizes the maximum lateness
while preserving the underlying job order. Given this solution representation
we are able to dene and evaluate various job-insert and job-swap neighborhood
searches. Furthermore we introduce a new neighborhood, we named
split-merge, that allows multiple job inserts in a single move. The split-merge
neighborhood is of exponential size, but can be searched in polynomial time
by dynamic programming. Computational results with an iterated descent
algorithm that employs the split-merge neighborhood show that it compares
favorably with corresponding iterated descent algorithms based on the jobinsert
and job-swap neighborhoods.