Search Results

Documents authored by Ziemke, Theresa

Document
DOI: 10.4230/LIPIcs.ESA.2024.62
Optimizing Throughput and Makespan of Queuing Systems by Information Design

Authors: Svenja M. Griesbach, Max Klimm, Philipp Warode, and Theresa Ziemke

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We study the optimal provision of information for two natural performance measures of queuing systems: throughput and makespan. A set of parallel links (queues) is equipped with deterministic capacities and stochastic offsets where the latter depend on a realized state, and the number of states is assumed to be constant. A continuum of flow particles (agents) arrives at the system at a constant rate. A system operator knows the realization of the state and may (partially) reveal this information via a public signaling scheme to the flow particles. Upon arrival, the flow particles observe the signal issued by the system operator, form an updated belief about the realized state, and decide on which link they use. Inflow into a link exceeding the link’s capacity builds up in a queue that increases the cost (total travel time) on the link. Dynamic inflow rates are in a Bayesian dynamic equilibrium when the expected cost along all links with positive inflow is equal at every point in time and not larger than the expected cost of any unused link. For a given time horizon T, the throughput induced by a signaling scheme is the total volume of flow that leaves the links in the interval [0,T]. The public signaling scheme maximizing the throughput may involve irrational numbers. We provide an additive polynomial time approximation scheme (PTAS) that approximates the optimal throughput by an arbitrary additive constant ε > 0. The algorithm solves a Lagrangian dual of the signaling problem with the Ellipsoid method whose separation oracle is implemented by a cell decomposition technique. We also provide a multiplicative fully polynomial time approximation scheme (FPTAS) that does not rely on strong duality and, thus, allows to compute the optimal signals. It uses a different cell decomposition technique together with a piecewise convex under-estimator of the optimal value function. Finally, we consider the makespan of a Bayesian dynamic equilibrium which is defined as the last point in time when a total given value of flow leaves the system. Using a variational inequality argument, we show that full information revelation is a public signaling scheme that minimizes the makespan.
Cite as

Svenja M. Griesbach, Max Klimm, Philipp Warode, and Theresa Ziemke. Optimizing Throughput and Makespan of Queuing Systems by Information Design. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 62:1-62:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{griesbach_et_al:LIPIcs.ESA.2024.62,
  author =	{Griesbach, Svenja M. and Klimm, Max and Warode, Philipp and Ziemke, Theresa},
  title =	{{Optimizing Throughput and Makespan of Queuing Systems by Information Design}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{62:1--62:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.62},
  URN =		{urn:nbn:de:0030-drops-211336},
  doi =		{10.4230/LIPIcs.ESA.2024.62},
  annote =	{Keywords: Information Design, Dynamic Flows, Public Signals, Convex Envelope}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2023.11
Spillback Changes the Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks

Authors: Theresa Ziemke, Leon Sering, and Kai Nagel

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
We study the long-term behavior of dynamic traffic equilibria and find that it heavily depends on whether spillback is captured in the traffic model or not. We give an example where no steady state is reached. Although the example consists of a single-commodity instance with constant inflow rate, the Nash flow over time consists of infinitely many phases. This is in contrast to what has been proven for Nash flows over time without spillback [Cominetti et al., 2021; N. Olver et al., 2021]. Additionally, we show that similar phase oscillations as in the Nash flow over time with spillback can be observed in the co-evolutionary transport simulation MATSim. This reaffirms the robustness of the findings as the simulation does (in contrast to Nash flows over time) not lead to exact user equilibra and, moreover, models discrete time steps and vehicles.
Cite as

Theresa Ziemke, Leon Sering, and Kai Nagel. Spillback Changes the Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ziemke_et_al:OASIcs.ATMOS.2023.11,
  author =	{Ziemke, Theresa and Sering, Leon and Nagel, Kai},
  title =	{{Spillback Changes the Long-Term Behavior of Dynamic Equilibria in Fluid Queuing Networks}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{11:1--11:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.11},
  URN =		{urn:nbn:de:0030-drops-187722},
  doi =		{10.4230/OASIcs.ATMOS.2023.11},
  annote =	{Keywords: flows over time, transport simulation, Nash flow, dynamic equilibrium, long-term behavior, steady state, oscillation, spillback, MATSim}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact