Modeling Group Scheduling Problems in Space and Time by Timed Petri Nets

• Autorzy: Graff, D. , Richling, J. , Werner, M.
• Języki publikacji: EN

Abstrakty

EN

Dealing with cyber-physical systems (CPS) puts a strong emphasis on the interaction between computing and non-computing elements. Since the physical world is characterized by being strongly distributed and concurrent, this is also reflected in the computational world making the design of such systems a challenging task. If a number of tasks shall be executed on a CPS which are bound to time and space, may have dependencies to other tasks and requires a specific amount of computing devices, a solution requires a four-dimensional space-time schedule which includes positioning of the devices resulting in an NP-hard problem. In this paper, we address the problem of spatial-temporal group scheduling using Timed Petri nets. We use Timed Petri nets in order to model the spatial, temporal, ordered and concurrent character of our mobile, distributed system. Our model is based on a discrete topology in which devices can change their location by moving from cell to cell. Using the time property of Petri nets, we model movement in a heterogeneous terrain as well as task execution or access to other resources of the devices. Given the modeling, we show how to find an optimal schedule by translating the problem into a shortest path problem, which is solvable with the known method of dynamic programming.

Słowa kluczowe

EN

spatial-temporal group scheduling problems; scheduling; Timed Petri nets; cyber-physical systems

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 122, nr 4
• Strony: 297--313
• Opis fizyczny: Bibliogr. 26 poz., rys., wykr.

Twórcy

autor

Graff, D.

• Communication and Operating Systems Group Berlin Institute of Technology, Germany,

autor

Richling, J.

• Communication and Operating Systems Group Berlin Institute of Technology, Germany,

autor

Werner, M.

• Operating Systems Group Chemnitz University of Technology, Germany,

Bibliografia

• [1] van der Aalst, W. M. P.: Petri net based scheduling, OR Spectrum, 18, 1996, 219–229, ISSN 0171-6468.
• [2] Al-Muhtadi, J., Chetan, S., Ranganathan, A., Campbell, R.: Super Spaces: A Middleware for Large-Scale Pervasive Computing Environments, Pervasive Computing and Communications Workshops., 2004, 198–202.
• [3] Bail, J. L., David, R., Alla, H.: Hybrid Petri nets, European Control Conference, Grenoble, 1991.
• [4] Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C.: Introduction to Algorithms, 2nd edition, MIT Press, 2001.
• [5] David, R., Alla, H.: Continuous Petri nets, 8th European Workshop on Application and Theory of Petri Nets, Zaragoza, 1987.
• [6] David, R., Alla, H.: On Hybrid Petri Nets, Discrete Event Dynamic Systems, 11(1-2), January 2001, 9–40, ISSN 0924-6703.
• [7] Dijkstra, E. W.: A note on two problems in connexion with graphs, Numerische Mathematik, 1, 1959, 269–271.
• [8] George, H. N., Coulouris, G.: Location Information Management, Proceedings of Ubicomp 2001, ACM, 2001.
• [9] Graff, D., Richling, J., Stupp, T. M., Werner, M.: Context-Aware Annotations for Distributed Mobile Applications, ARCS’11 Workshop Proceedings: Second Workshop on Context-Systems Design, Evaluation and Optimisation (CoSDEO 2011) (D. S. Wolfgang Karl, Ed.), VDE, February 2011, ISBN 978-3-8007-3333-0.
• [10] Graff, D., Richling, J., Stupp, T. M., Werner, M.: Distributed Active Objects – A Systemic Approach to Distributed Mobile Applications, 8th IEEE International Conference and Workshops on Engineering of Autonomic and Autonomous Systems (R. Sterrit, Ed.), IEEE Computer Society, April 2011, ISBN 978-0-7695-4380-2.
• [11] Graff, D., Werner, M., Parzyjegla, H., Richling, J., Mühl, G.: An Object-Oriented and Context-Aware Approach for Distributed Mobile Applications, Workshop on Context-Systems Design, Evaluation and Optimisation (CoSDEO 2010) at ARCS 2010 - Architecture of Computing Systems, 2010.
• [12] Lee, E. A.: Cyber-Physical Systems – Are Computing Foundations Adequate?, Position Paper for NSF Workshop On Cyber-Physical Systems: Research Motivation, Techniques and Roadmap, October 2006.
• [13] Lee, E. A.: The Problem with Threads, Computer, 39, 2006, 33–42, ISSN 0018-9162.
• [14] McLurkin, J., Yamins, D.: Dynamic Task Assignment in Robot Swarms, Robotics: Science and Systems Conference, Cambridge, MA, USA, 2005.
• [15] Merlin, P.: A Study of the Recoverability of Communikation Protocols, Ph.D. Thesis, University of California, Irvine, CA, USA, 1974.
• [16] Peter. H. Starke, Humboldt-Universität zu Berlin, Institut fA˘ L’r Informatik, Lehrstuhl für Automaten- und Systemtheorie: Integrated Net Analyzer INA, http://www2.informatik.hu-berlin.de/~starke/ina.html.
• [17] Petri, C. A.: Kommunikation mit Automaten., Ph.D. Thesis, Universität Bonn, Institut für Instrumentelle Mathematik, Bonn, 1962.
• [18] Popova-Zeugmann, L., Werner, M.: Extreme Runtimes of Schedules Modelled by Time Petri Nets, Fundamenta Informaticae, 67, 2005, 163–174.
• [19] Popova-Zeugmann, L., Werner, M., Richling, J.: Using State Equation to Prove Non-Reachability in Timed Petrinets, Fundamenta Informaticae, 55, 2002, 187–202, ISSN 0169-2968.
• [20] Ramchandani, C.: Analysis of Asynchronous Concurrent Systems by Timed Petri Nets, Project MAC-TR 120, MIT, Massachusetts Institute of Technology, Cambridge, MA, USA, February 1974.
• [21] Richling, J., Popova-Zeugmann, L., Werner, M.: Verification of Non-functional Properties of a Composable Architecture with Petrinets, Fundamenta Informaticae, 51, 2002, 185–200.
• [22] Roman, M., Hess, C. K., Ranganathan, A., Madhavarapu, P., Borthakur, B., Viswanathan, P., Cerqueira, R., Campbell, R. H., Mickunas, M. D.: GaiaOS: An Infrastructure for Active Spaces, Technical report, University of Illinois at Urbana-Champaign, Champaign, IL, USA, 2001.
• [23] University of Hamburg, Faculty of Mathematics, Informatics und Natural Sciences Department of Informatics, TGI Group: Petri Nets World, http://www.informatik.uni-hamburg.de/TGI/PetriNets.
• [24] Werner, M.: A Framework to Find Optimal IRIS Schedules, Journal of Control and Cybernetics, 35(3), 2006, 703–719.
• [25] Xiao, Z., Ming, Z.: A method of workflow scheduling based on colored Petri nets, Data Knowl. Eng., 70, February 2011, 230–247, ISSN 0169-023X.
• [26] Yee, S. T., Ventura, J. A.: A dynamic programming algorithm to determine optimal assembly sequences using Petri nets., International Journal of Industrial Engineering - Theory, Applications and Practice, 6(1), 1999, 27–37.