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 language | English |
---|---|
Title of host publication | Integration of Constraint Programming, Artificial Intelligence, and Operations Research |
Editors | Louis-Martin Rousseau, Kostas Stergiou |
Publisher | Springer |
Pages | 565-580 |
ISBN (Electronic) | 978-3-030-19212-9 |
ISBN (Print) | 978-3-030-19211-2 |
DOIs | |
Publication status | Published - 2019 |
Event | CPAIOR 2019: 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research - Thessaloniki, Greece Duration: 4 Jun 2019 → 7 Jun 2019 Conference number: 16 |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 11494 |
Conference
Conference | CPAIOR 2019: 16th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research |
---|---|
Abbreviated title | CPAIOR 2019 |
Country/Territory | Greece |
City | Thessaloniki |
Period | 4/06/19 → 7/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-careOtherwise 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