Logic-based benders decomposition for scheduling a batching machine

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review


  • Simon Emde
  • Lukas Polten, Technische Universität Darmstadt
  • ,
  • Michel Gendreau, Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation

This paper investigates the problem of scheduling a set of jobs on a single batching machine to minimize the maximum lateness, where jobs may be subject to precedence constraints and incompatibilities. Single batching machine scheduling has many applications, but this study is particularly motivated by single crane scheduling in an automated storage and retrieval system (AS/RS): given a set of transport requests, which requests should be processed together in the same dual command cycle, and in what order should the cycles be processed? Since storage and retrieval requests may refer to the same physical item, precedence constraints must be observed. Moreover, the crane may not be capable of handling multiple storage or retrieval requests in the same cycle, hence the need to account for incompatibilities. We present a novel exact algorithm based on branch & Benders cut, which is shown to solve even large instances with more than 100 jobs to optimality in many cases. For the special case without precedence constraints and incompatibilities, it improves on several best-known upper bounds from the literature.

TidsskriftComputers and Operations Research
StatusUdgivet - 1 jan. 2020
Eksternt udgivetJa

Se relationer på Aarhus Universitet Citationsformater

ID: 167799282