Multi-Machine Scheduling Lower Bounds Using Decision Diagrams

Title

Multi-Machine Scheduling Lower Bounds Using Decision Diagrams

 Author

van den Bogaerdt, Pim (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Algorithmics)

Contributor

de Weerdt, M.M. (mentor) ORCID 0000-0002-0470-6241
Witteveen, C. (graduation committee) ORCID 0000-0002-7717-1209
van Iersel, L.J.J. (graduation committee) ORCID 0000-0001-7142-4706

 Degree granting institution

Delft University of Technology

 Programme

Computer Science | Software Technology

 Date

2018-05-30

 Abstract

We investigate the use of relaxed decision diagrams for obtaining lower bounds on multi-machine scheduling problems. The type of scheduling problem we consider models a railway service site where maintenance jobs are performed, but is sufficiently general to potentially have wider applicability.
We find that our decision diagram formulation is able to give decent lower bounds in short time. Our implementation is competitive with lower bounds given by existing solvers, and is superior when due times are small and have small variance. Further, we find that our model greatly improves upon a naive extension of the state of the art for single-machine scheduling [23].

 Subject

scheduling
decision diagrams
lower bounds
relaxation

 To reference this document use:

http://resolver.tudelft.nl/uuid:c234fa84-6916-400c-8eb4-c8a1146423ea

 Part of collection

Student theses

 Document type

master thesis

 Rights

© 2018 Pim van den Bogaerdt
Files
PDF mmdd_final.pdf 520.56 KB
Close viewer