Logic-based benders decomposition for scheduling a batching machine. (January 2020)

• Record Type: Journal Article
• Authors: Emde, Simon; Polten, Lukas; Gendreau, Michel
• Is Part Of: Computers & operations research. Volume 113(2020)
• Publication Date: 2020-01
• Subjects: Benders decomposition -- Single batching machine -- Automated storage and retrieval -- Precedence constraints -- Maximum lateness; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2019.104777
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A generalization of single batching machine scheduling with lateness objective. A novel logic-based Benders decomposition algorithm. The algorithm finds new best upper bounds in short time on literature instances. The algorithm finds high-quality solutions on new instances from the AS/RS context. Abstract: 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.