Improving column generation methods or sheduling problems using ZDD and stabilization

Roel Leus; Daniel Kowalczyk

doi:10.1109/IEEM.2016.7797844

Improving column generation methods or sheduling problems using ZDD and stabilization

Roel Leus, Daniel Kowalczyk

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

In this work we tackle the parallel machine scheduling problem with identical machines to minimize the sum of weighted completion times. We study the set covering formulation for this problem that was introduced by van den Akker et al. [1], and improve the performance of their branch-and-price algorithm by a number of techniques, including zero-suppressed binary decision diagrams (ZDD) and stabilization. These techniques are sufficiently generic to be promising also for other scheduling problems.

Original language	English
Title of host publication	2016 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM)
Place of Publication	Piscataway
Publisher	Institute of Electrical and Electronics Engineers
Pages	99-103
Number of pages	5
ISBN (Electronic)	978-1-5090-3665-3
DOIs	https://doi.org/10.1109/IEEM.2016.7797844
Publication status	Published - Dec 2016
Externally published	Yes
Event	2016 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2016 - Bali, Indonesia Duration: 4 Dec 2016 → 7 Dec 2016

Conference

Conference	2016 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2016
Abbreviated title	IEEM 2016
Country/Territory	Indonesia
City	Bali
Period	4/12/16 → 7/12/16

Access to Document

10.1109/IEEM.2016.7797844

Cite this

@inproceedings{b3d96ab7f670454498dc8d345982936d,

title = "Improving column generation methods or sheduling problems using ZDD and stabilization",

abstract = "In this work we tackle the parallel machine scheduling problem with identical machines to minimize the sum of weighted completion times. We study the set covering formulation for this problem that was introduced by van den Akker et al. [1], and improve the performance of their branch-and-price algorithm by a number of techniques, including zero-suppressed binary decision diagrams (ZDD) and stabilization. These techniques are sufficiently generic to be promising also for other scheduling problems.",

author = "Roel Leus and Daniel Kowalczyk",

year = "2016",

month = dec,

doi = "10.1109/IEEM.2016.7797844",

language = "English",

pages = "99--103",

booktitle = "2016 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM)",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "2016 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2016, IEEM 2016 ; Conference date: 04-12-2016 Through 07-12-2016",

}

Leus, R & Kowalczyk, D 2016, Improving column generation methods or sheduling problems using ZDD and stabilization. in 2016 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). Institute of Electrical and Electronics Engineers, Piscataway, pp. 99-103, 2016 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2016, Bali, Indonesia, 4/12/16. https://doi.org/10.1109/IEEM.2016.7797844

Improving column generation methods or sheduling problems using ZDD and stabilization. / Leus, Roel; Kowalczyk, Daniel.
2016 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM). Piscataway: Institute of Electrical and Electronics Engineers, 2016. p. 99-103.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Improving column generation methods or sheduling problems using ZDD and stabilization

AU - Leus, Roel

AU - Kowalczyk, Daniel

PY - 2016/12

Y1 - 2016/12

N2 - In this work we tackle the parallel machine scheduling problem with identical machines to minimize the sum of weighted completion times. We study the set covering formulation for this problem that was introduced by van den Akker et al. [1], and improve the performance of their branch-and-price algorithm by a number of techniques, including zero-suppressed binary decision diagrams (ZDD) and stabilization. These techniques are sufficiently generic to be promising also for other scheduling problems.

AB - In this work we tackle the parallel machine scheduling problem with identical machines to minimize the sum of weighted completion times. We study the set covering formulation for this problem that was introduced by van den Akker et al. [1], and improve the performance of their branch-and-price algorithm by a number of techniques, including zero-suppressed binary decision diagrams (ZDD) and stabilization. These techniques are sufficiently generic to be promising also for other scheduling problems.

U2 - 10.1109/IEEM.2016.7797844

DO - 10.1109/IEEM.2016.7797844

M3 - Conference contribution

SP - 99

EP - 103

BT - 2016 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM)

PB - Institute of Electrical and Electronics Engineers

CY - Piscataway

T2 - 2016 IEEE International Conference on Industrial Engineering and Engineering Management, IEEM 2016

Y2 - 4 December 2016 through 7 December 2016

ER -

Improving column generation methods or sheduling problems using ZDD and stabilization

Abstract

Conference

Access to Document

Fingerprint

Cite this