Multi-Machine Scheduling Lower Bounds Using Decision Diagrams

Master thesis (2018)

Authors

P. van den Bogaerdt Electrical Engineering, Mathematics and Computer Science

Contributors

M.M. de Weerdt (supervisor 1)
C. Witteveen (supervisor 2)
L.J.J. van Iersel (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2018 Pim van den Bogaerdt
More Info
expand_more

Published Date

30-05-2018

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

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].

Files

Mmdd_final.pdf
(.pdf | 0.508 Mb)