A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching

Daniel Kowalczyk and Roel Leus

No 559444, Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven

Abstract: We study the parallel machine scheduling problem to minimize the sum of the weighted completion times of the jobs to be scheduled (problem P m||P wjCj in the standard three-field notation). We use the set covering formulation that was introduced by van den Akker et al. (1999) 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.

Keywords: Parallel machine scheduling; Weighted completion times; Branch and price; ZDD; Stabilization (search for similar items in EconPapers)
Date: 2016-12
New Economics Papers: this item is included in nep-cmp
References: Add references at CitEc
Citations:

Published in FEB Research Report KBI_1631

Downloads: (external link)
https://lirias.kuleuven.be/retrieve/416717 A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching (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:ete:kbiper:559444

Access Statistics for this paper

More papers in Working Papers of Department of Decision Sciences and Information Management, Leuven from KU Leuven, Faculty of Economics and Business (FEB), Department of Decision Sciences and Information Management, Leuven
Bibliographic data for series maintained by library EBIB ().