Department of Economics and Business Economics

Simon Emde

Logic-based benders decomposition for scheduling a batching machine

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-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.

Original languageEnglish
Article number104777
JournalComputers and Operations Research
Number of pages12
Publication statusPublished - 1 Jan 2020
Externally publishedYes

    Research areas

  • Automated storage and retrieval, Benders decomposition, Maximum lateness, Precedence constraints, Single batching machine

See relations at Aarhus University Citationformats

ID: 167799282