Lower Bounds for Uniform Machine Scheduling Using Decision Diagrams

Pim van den Bogaerdt, Mathijs de Weerdt

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

2 Citations (Scopus)
115 Downloads (Pure)

Abstract

We propose a relaxed decision diagram (DD) formulation for obtaining lower bounds on uniform machine scheduling instances, based on separators to separate jobs on different machines. Experiments on the total tardiness for instances with tight due times show that for obtaining nontrivial bounds, it is important to partition the DD nodes on a layer based on their machine finishing time. When the number of jobs is small, DDs provide stronger bounds in less time than a time-indexed LP relaxation.
Original languageEnglish
Title of host publicationIntegration of Constraint Programming, Artificial Intelligence, and Operations Research
EditorsLouis-Martin Rousseau, Kostas Stergiou
PublisherSpringer
Pages565-580
ISBN (Electronic)978-3-030-19212-9
ISBN (Print)978-3-030-19211-2
DOIs
Publication statusPublished - 2019
EventCPAIOR 2019: 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research - Thessaloniki, Greece
Duration: 4 Jun 20197 Jun 2019
Conference number: 16

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11494

Conference

ConferenceCPAIOR 2019: 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research
Abbreviated titleCPAIOR 2019
Country/TerritoryGreece
CityThessaloniki
Period4/06/197/06/19

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

  • Multi-machine scheduling
  • Uniform machines
  • Lower bounds
  • Decision diagrams

Fingerprint

Dive into the research topics of 'Lower Bounds for Uniform Machine Scheduling Using Decision Diagrams'. Together they form a unique fingerprint.

Cite this