The robust machine availability problem – bin packing under uncertainty

Guopeng Song, Daniel Kowalczyk and Roel Leus

IISE Transactions, 2018, vol. 50, issue 11, 997-1012

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.

Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2018.1468122 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:uiiexx:v:50:y:2018:i:11:p:997-1012

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/uiie20

DOI: 10.1080/24725854.2018.1468122

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().