The robust machine availability problem - bin packing under uncertainty

Guopeng Song, Daniel Kowalczyk, Roel Leus (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

8 Citations (Scopus)

Abstract

We define and solve the robust machine availability problem in a parallel machine environment, which aims to minimize the number of identical machines required while completing all the jobs before a given deadline. The deterministic version of this problem essentially coincides with the bin packing problem. Our formulation preserves a user-defined robustness level regarding possible deviations in the job durations. For better computational performance, a branch-and-price procedure is proposed based on a set covering reformulation. We use zero-suppressed binary decision diagrams for solving the pricing problem, which enable us to manage the difficulty entailed by the robustness considerations as well as by extra constraints imposed by branching decisions. Computational results are reported that show the effectiveness of a pricing solver with zero-suppressed binary decision diagrams compared with a mixed integer programming solver.
Original languageEnglish
Pages (from-to)997-1012
Number of pages16
JournalIISE Transactions
Volume50
Issue number11
DOIs
Publication statusPublished - 2 Nov 2018
Externally publishedYes

Keywords

  • Parallel machine scheduling; machine availability; bin packing; robust optimization; branch and price; ZDD

Fingerprint

Dive into the research topics of 'The robust machine availability problem - bin packing under uncertainty'. Together they form a unique fingerprint.

Cite this