Multi-machine scheduling lower bounds using decision diagrams

Pim van den Bogaerdt; Mathijs de Weerdt

doi:10.1016/j.orl.2018.11.003

Multi-machine scheduling lower bounds using decision diagrams

Pim van den Bogaerdt^*, Mathijs de Weerdt

^*Corresponding author for this work

Algorithmics

Research output: Contribution to journal › Article › Scientific › peer-review

5 Citations (Scopus)

52 Downloads (Pure)

Abstract

We consider parallel multi-machine scheduling with due times, where a partition of jobs is given where jobs in the same partition have a common release time, possibly precedence constraints, and cannot overlap. A formulation of decision diagrams for this problem greatly improves upon a more natural extension of the state-of-the-art for single-machine scheduling, and can provide decent lower bounds, outperforming existing solvers given the same short runtime limit, for problem instances with large time scales and tight due times.

Original language	English
Pages (from-to)	616-621
Number of pages	6
Journal	Operations Research Letters
Volume	46
Issue number	6
DOIs	https://doi.org/10.1016/j.orl.2018.11.003
Publication status	Published - 2018

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care

Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Keywords

Decision diagrams
Lower bounds
Multi-machine scheduling

Access to Document

10.1016/j.orl.2018.11.003

1-s2.0-S016763771830227X-mainFinal published version, 555 KB

Cite this

@article{5538437b0c72407db8e0888855fa8bc5,

title = "Multi-machine scheduling lower bounds using decision diagrams",

abstract = "We consider parallel multi-machine scheduling with due times, where a partition of jobs is given where jobs in the same partition have a common release time, possibly precedence constraints, and cannot overlap. A formulation of decision diagrams for this problem greatly improves upon a more natural extension of the state-of-the-art for single-machine scheduling, and can provide decent lower bounds, outperforming existing solvers given the same short runtime limit, for problem instances with large time scales and tight due times.",

keywords = "Decision diagrams, Lower bounds, Multi-machine scheduling",

author = "{van den Bogaerdt}, Pim and {de Weerdt}, Mathijs",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.",

year = "2018",

doi = "10.1016/j.orl.2018.11.003",

language = "English",

volume = "46",

pages = "616--621",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - Multi-machine scheduling lower bounds using decision diagrams

AU - van den Bogaerdt, Pim

AU - de Weerdt, Mathijs

N1 - Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2018

Y1 - 2018

N2 - We consider parallel multi-machine scheduling with due times, where a partition of jobs is given where jobs in the same partition have a common release time, possibly precedence constraints, and cannot overlap. A formulation of decision diagrams for this problem greatly improves upon a more natural extension of the state-of-the-art for single-machine scheduling, and can provide decent lower bounds, outperforming existing solvers given the same short runtime limit, for problem instances with large time scales and tight due times.

AB - We consider parallel multi-machine scheduling with due times, where a partition of jobs is given where jobs in the same partition have a common release time, possibly precedence constraints, and cannot overlap. A formulation of decision diagrams for this problem greatly improves upon a more natural extension of the state-of-the-art for single-machine scheduling, and can provide decent lower bounds, outperforming existing solvers given the same short runtime limit, for problem instances with large time scales and tight due times.

KW - Decision diagrams

KW - Lower bounds

KW - Multi-machine scheduling

UR - http://www.scopus.com/inward/record.url?scp=85056634913&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2018.11.003

DO - 10.1016/j.orl.2018.11.003

M3 - Article

AN - SCOPUS:85056634913

SN - 0167-6377

VL - 46

SP - 616

EP - 621

JO - Operations Research Letters

JF - Operations Research Letters

IS - 6

ER -

Multi-machine scheduling lower bounds using decision diagrams

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this