License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2018.6
URN: urn:nbn:de:0030-drops-97112
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9711/
Go to the corresponding OASIcs Volume Portal

van Heuven van Staereling, Irving

Tree Decomposition Methods for the Periodic Event Scheduling Problem

pdf-format:
OASIcs-ATMOS-2018-6.pdf (0.5 MB)

Abstract

This paper proposes an algorithm that decomposes the Periodic Event Scheduling Problem (PESP) into trees that can efficiently be solved. By identifying at an early stage which partial solutions can lead to a feasible solution, the decomposed components can be integrated back while maintaining feasibility if possible. If not, the modifications required to regain feasibility can be found efficiently. These techniques integrate dynamic programming into standard search methods.
The performance of these heuristics are very satisfying, as the problem using publicly available benchmarks can be solved within a reasonable amount of time, in an alternative way than the currently accepted leading-edge techniques. Furthermore, these heuristics do not necessarily rely on linearity of the objective function, which facilitates the research of timetabling under nonlinear circumstances.

BibTeX - Entry

@InProceedings{vanheuvenvanstaereling:OASIcs:2018:9711,
  author =	{Irving van Heuven van Staereling},
  title =	{{Tree Decomposition Methods for the Periodic Event Scheduling Problem}},
  booktitle =	{18th Workshop on Algorithmic Approaches for Transportation  Modelling, Optimization, and Systems (ATMOS 2018)},
  pages =	{6:1--6:13},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-096-5},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{65},
  editor =	{Ralf Bornd{\"o}rfer and Sabine Storandt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9711},
  URN =		{urn:nbn:de:0030-drops-97112},
  doi =		{10.4230/OASIcs.ATMOS.2018.6},
  annote =	{Keywords: Dynamic Programming, Trees, Periodic Event Scheduling Problem}
}

Keywords: Dynamic Programming, Trees, Periodic Event Scheduling Problem
Collection: 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)
Issue Date: 2018
Date of publication: 28.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI