Loading…

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 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 represe...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2015-11, Vol.63, p.125-135
Main Authors: Cabo, Marta, Possani, Edgar, Potts, Chris N., Song, Xiang
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. •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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2015.04.017