Scheduling with release times and deadlines

Master thesis (2014)

Authors

Contributors

M.M. De Weerdt (mentor)
C. Witteveen (mentor)
K.I. Aardal (mentor)
Programme
Algorithmics (EEMCS) (TU Delft)
Copyright: © 2014 Elffers, J.A.
Scheduling Exact algorithms Forbidden regions
More Info
expand_more

Published Date

28-08-2014

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.

Programme

Algorithmics

Abstract

We study the single machine version of the task scheduling problem with release times and deadlines. This problem is too simple to be of practical importance in itself, but it is also used as a relaxation in algorithms for the Job Shop scheduling problem, which is a more practical task scheduling problem. We study exact algorithms for solving the single machine problem. We propose a new lower bound for the single machine problem and analyze its practical performance when used in a branch and bound algorithm. We also study the theoretical hardness of the single machine problem with a fixed set of task lengths.

Files

Thesis.pdf
(pdf | 0.726 Mb)