How to Measure the Robustness of Shunting Plans

Authors Roel van den Broek, Han Hoogeveen, Marjan van den Akker



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2018.3.pdf
  • Filesize: 0.83 MB
  • 13 pages

Document Identifiers

Author Details

Roel van den Broek
  • Department of Computer Science, Utrecht University, Utrecht, The Netherlands
Han Hoogeveen
  • Department of Computer Science, Utrecht University, Utrecht, The Netherlands
Marjan van den Akker
  • Department of Computer Science, Utrecht University, Utrecht, The Netherlands

Cite AsGet BibTex

Roel van den Broek, Han Hoogeveen, and Marjan van den Akker. How to Measure the Robustness of Shunting Plans. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.ATMOS.2018.3

Abstract

The general problem of scheduling activities subject to temporal and resource constraints as well as a deadline emerges naturally in numerous application domains such as project management, production planning, and public transport. The schedules often have to be implemented in an uncertain environment, where disturbances cause deviations in the duration, release date or deadline of activities. Since these disruptions are not known in the planning phase, we must have schedules that are robust, i.e., capable of absorbing the disturbances without large deteriorations of the solution quality. Due to the complexity of computing the robustness of a schedule directly, many surrogate robustness measures have been proposed in literature. In this paper, we propose new robustness measures, and compare these and several existing measures with the results of a simulation study to determine which measures can be applied in practice to obtain good approximations of the true robustness of a schedule with deadlines. The experiments are performed on schedules generated for real-world scheduling problems at the shunting yards of the Dutch Railways (NS).

Subject Classification

ACM Subject Classification
  • Computing methodologies → Planning under uncertainty
Keywords
  • robustness
  • resource-constrained project scheduling
  • partial order schedule
  • uncertainty
  • Monte Carlo simulation
  • train shunting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Mohammad A. Al-Fawzan and Mohamed Haouari. A bi-objective model for robust resource-constrained project scheduling. International Journal of production economics, 96(2):175-187, 2005. Google Scholar
  2. Louis-Claude Canon and Emmanuel Jeannot. Evaluation and optimization of the robustness of dag schedules in heterogeneous environments. IEEE Transactions on Parallel and Distributed Systems, 21(4):532-546, 2010. Google Scholar
  3. Hédi Chtourou and Mohamed Haouari. A two-stage-priority-rule-based algorithm for robust resource-constrained project scheduling. Computers &industrial engineering, 55(1):183-194, 2008. Google Scholar
  4. Rina Dechter, Itay Meiri, and Judea Pearl. Temporal constraint networks. Artificial intelligence, 49(1-3):61-95, 1991. Google Scholar
  5. Öncü Hazır, Mohamed Haouari, and Erdal Erel. Robust scheduling and robustness measures for the discrete time/cost trade-off problem. European Journal of Operational Research, 207(2):633-643, 2010. Google Scholar
  6. V. Jorge Leon, S. David Wu, and Robert H. Storer. Robustness measures and robust scheduling for job shops. IIE transactions, 26(5):32-43, 1994. Google Scholar
  7. Mohamed Ali Khemakhem and Hédi Chtourou. Efficient robustness measures for the resource-constrained project scheduling problem. International Journal of Industrial and Systems Engineering, 14(2):245-267, 2013. Google Scholar
  8. Przemysław Kobylański and Dorota Kuchta. A note on the paper by Ma Al-Fawzan and M. Haouari about a bi-objective problem for robust resource-constrained project scheduling. International Journal of Production Economics, 107(2):496-501, 2007. Google Scholar
  9. Arfst Ludwig, Rolf H. Möhring, and Frederik Stork. A computational study on bounding the makespan distribution in stochastic project networks. Annals of Operations Research, 102(1-4):49-64, 2001. Google Scholar
  10. Simon Mountakis, Tomas Klos, and Cees Witteveen. Temporal flexibility revisited: Maximizing flexibility by computing bipartite matchings. In ICAPS, pages 174-178, 2015. Google Scholar
  11. Saralees Nadarajah and Samuel Kotz. Exact distribution of the max/min of two gaussian random variables. IEEE Transactions on very large scale integration (VLSI) systems, 16(2):210-212, 2008. Google Scholar
  12. Guido Passage, Han Hoogeveen, and Marjan van den Akker. Combining local search and heuristics for solving robust parallel machine scheduling. Master’s thesis, Utrecht University, 2016. https://dspace.library.uu.nl/bitstream/handle 334269/thesis.pdf. Google Scholar
  13. Roel van den Broek, Han Hoogeveen, Marjan van den Akker, and Bob Huisman. A local search algorithm for train unit shunting with service scheduling, 2018. Manuscript submitted for publication. Google Scholar
  14. Michel Wilson. Robust scheduling in an uncertain environment. PhD thesis, TU Delft, 2016. Google Scholar
  15. Michel Wilson, Tomas Klos, Cees Witteveen, and Bob Huisman. Flexibility and decoupling in simple temporal networks. Artificial Intelligence, 214:26-44, 2014. Google Scholar
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