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

70 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 -
Duration: 4 Jun 20197 Jun 2019

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11494

Conference

ConferenceCPAIOR 2019
Period4/06/197/06/19

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

    van den Bogaerdt, P., & de Weerdt, M. (2019). Lower Bounds for Uniform Machine Scheduling Using Decision Diagrams. In L-M. Rousseau, & K. Stergiou (Eds.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research (pp. 565-580). (Lecture Notes in Computer Science; Vol. 11494). Springer. https://doi.org/10.1007/978-3-030-19212-9_38