Split–merge: Using exponential neighborhood search for scheduling a batching machine

• We study the scheduling of a single batching machine with restricted batch size.
• We develop an exponential neighborhood that can be explored in polynomial time.
• Dynamic programing formulations are developed for optimal batching.
• We evaluate and compare different local search heuristics.

We address the problem of scheduling a single batching machine to minimize the maximum lateness with a constraint restricting the batch size. A solution for this NP-hard problem is defined by a selection of jobs for each batch and an ordering of those batches. As an alternative, we choose to represent a solution as a sequence of jobs. This approach is justified by our development of a dynamic program to find a schedule that minimizes the maximum lateness while preserving the underlying job order. Given this solution representation, we are able to define and evaluate various job-insert and job-swap neighborhood searches. Furthermore we introduce a new neighborhood, 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 job-insert and job-swap neighborhoods.