Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 1 von 2
Zurück zur Trefferliste

Fastest, Average and Quantile Schedule

  • We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.
Metadaten
Verfasserangaben:Torsten Klug, Konstanty Junosza-Szaniawski, Slawomir Kwasiborski, Armin Fügenschuh, Thomas Schlechte
Dokumentart:Konferenzbeitrag
Titel des übergeordneten Werkes (Englisch):SOFSEM 2015: Theory and Practice of Computer Science
Erste Seite:201
Letzte Seite:216
Verlag:Springer Berlin Heidelberg
Freies Schlagwort / Tag:eulerian multigraphs; scheduling
MSC-Klassifikation:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Axx Enumerative combinatorics For enumeration in graph theory, see 05C30
CCS-Klassifikation:G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.1 Combinatorics (F.2.2) / Permutations and combinations
Jahr der Erstveröffentlichung:2015
Preprint:urn:nbn:de:0297-zib-53592
DOI:https://doi.org/10.1007/978-3-662-46078-8_17
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.