A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching
Daniel Kowalczyk () and
Roel Leus ()
Additional contact information
Daniel Kowalczyk: ORSTAT, Faculty of Economics and Business, KU Leuven, 3000 Leuven, Belgium
Roel Leus: ORSTAT, Faculty of Economics and Business, KU Leuven, 3000 Leuven, Belgium
INFORMS Journal on Computing, 2018, vol. 30, issue 4, 768-782
Abstract:
We study the parallel machine scheduling problem to minimize the sum of the weighted completion times of the jobs to be scheduled (problem Pm ∥∑ w j C j in the standard three-field notation). We use the set covering formulation that was introduced by van den Akker et al. [van den Akker J, Hoogeveen J, van de Velde S (1999) Parallel machine scheduling by column generation. Oper. Res. 47(6):862–872.] for this problem, and we improve the computational performance of their branch-and-price (B&P) algorithm by a number of techniques, including a different generic branching scheme, zero-suppressed binary decision diagrams (ZDDs) to solve the pricing problem, dual-price smoothing as a stabilization method, and Farkas pricing to handle infeasibilities. We report computational results that show the effectiveness of the algorithmic enhancements, which depends on the characteristics of the instances. To the best of our knowledge, we are also the first to use ZDDs to solve the pricing problem in a B&P algorithm for a scheduling problem. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0809 .
Keywords: parallel machine scheduling; weighted completion times; branch-and-price • ZDD; stabilization (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)
Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0809 (application/pdf)
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:inm:orijoc:v:30:y:2018:i:4:p:768-782
Access Statistics for this article
More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().