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

Marta Cabo, Edgar Possani, Chris N. Potts, Xiang Song

Research output: Contribution to journalArticlepeer-review

168 Downloads (Pure)

Abstract

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.
Original languageEnglish
Pages (from-to)125-135
JournalComputers & Operations Research
Volume63
Early online date14 May 2015
DOIs
Publication statusPublished - Nov 2015

Keywords

  • maximum lateness
  • batching machine
  • dynamic programming
  • exponential neighborhoods
  • local search
  • WNU

Fingerprint

Dive into the research topics of 'Split-merge: using exponential neighborhood search for scheduling a batching machine'. Together they form a unique fingerprint.

Cite this