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

Daniel Kowalczyk, Roel Leus

Research output: Contribution to journalArticleAcademicpeer-review

10 Citations (Scopus)

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∥∑wjCj 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.
Original languageEnglish
Pages (from-to)768-782
Number of pages15
JournalINFORMS Journal on Computing
Volume30
Issue number4
DOIs
Publication statusPublished - Sep 2018

Keywords

  • Branch-and-price
  • Parallel machine scheduling
  • Stabilization
  • Weighted completion times
  • ZDD
  • stabilization
  • branch-and-price
  • parallel machine scheduling
  • weighted completion times

Fingerprint

Dive into the research topics of 'A branch-and-price algorithm for parallel machine scheduling using ZDDs and generic branching'. Together they form a unique fingerprint.

Cite this