A timed Petri net framework to find optimal IRIS schedules

• Autorzy: Werner M.
• Języki publikacji: EN

Abstrakty

EN

IRIS (increasing reward with increasing service) realtime scheduling appears frequently in real-time control applications such as heuristic control. IRIS requires not only meeting deadlines, but also finding the schedule with the best result (highest reward). In this paper, a framework is presented that uses Timed Petri nets (TPN) to transform an IRIS problem into a dynamic programming (DP) problem, allowing the application of known TPN and DP techniques. In the presented approach, an IRIS problem with tasks having discrete-time optimal parts is transformed into a (possibly unbounded) TPN. Then, the critical path problem of the TPN state graph can be tackled with DP. This approach allows for the IRIS problem multiple constraints and negative rewards.

Słowa kluczowe

EN

IRIS; increasing reward with increasing service; scheduling; timed Petri nets; critical path; real time

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2006
• Tom: Vol. 35, no 3
• Strony: 703--719
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Werner M.

• TU Berlin, Communication and Operating Systems Group, Einsteinufer 17, 10587 Berlin, Germany,

Bibliografia

• BELLMAN, R. (1958) On a routing problem. Quarterly of Applied Mathematics 16 (1), 87-90.
• CORMEN, T.H., LEISERSON, C.E. and RIVEST, R.L. (1990) Introduction to Algorithms. MIT Press/McGraw-Hill, Cambridge, MA.
• DEY, J.K. KUROSE, J.F. TOWSLEY, D.F. KRISHNA, C.M. and GIRKAR, M. (1993) Efficient on-line processor scheduling for a class of IRIS (increasing reward with increasing service) real-time tasks. In: Measurement and Modeling of Computer Systems, 217-228.
• FORD, L.R. and FULKERSON, D.R. (1962) Flows in Networks. Princeton University Press, Princeton, New Jersey.
• KRISHNA, C.M. and SHIN. K.G. (1997) Real-Time Systems. McGraw Hill, New York, NY.
• LIU, J.W.S., SHIH, W.-K., LIN, K.-W., BETTATI. R. and CHUNG, J.-Y. (1994) Imprecise computations. Proc. of the IEEE, January, 82 (1), 83-94 .
• LIU, J.W.S., LIN, K.-J., Yu, A.C.-S., CHUNG, J.-Y. and ZHAO, W. (1991) Algorithms for scheduling imprecise computations. IEEE Computer 24 (5).
• MERLIN, P. (1974) A Study of the Recoverability of Communikation Protocols. PhD thesis, Irvine.
• PETRI, C.A. (1962) Kommunikation mit Automaten. Schriften des IIM 2, Institut für Instrumentelle Mathematik, Bonn.
• POPOVA-ZEUGMANN, L. and WERNER, M. (2005) Extreme runtimes of schedules modelled by time petrinets. Fundamenta Informaticae 67 (1 3), 163-174.
• POPOVA-ZEUGMANN, L., WERNER, M. and RICHLING, J. (2003) Using state-equation to prove non-reachability in timed petrinets. Fundamenta Informaticae 55 (3), 187-202.
• PRESS, W.H. TEUKOLSKY, S.A. VETTERLING, W.T. and FLANNERY, B.P. (1992) Numerical Recipies in FORTRAN. Cambridge University Press, Cambridge.
• RAMCHANDANI, C. (1974) Analysis of asynchronous concurrent systems by Timed Petri Nets. Project MAC, Technical Report 120, MIT.
• RICHLING, J., POPOVA-ZEUGMANN, L. and WERNER, M. (2002) Verification of non-functional properties of a composable architecture with petrinets. Fundamenta Informaticae 51 (2), 185-200.
• RÖLKE, H. and HEITMANN, F. Petri Nets World. Web site. http://www.informatik.uni-hamburg.de/TGI/PetriNets /bibliographies.
• SHIH, W.-K. and Liu, J.W.S. (1995) Algorithms for scheduling imprecise computations with timing constraints to minimize maximum error. IEEE Trans, on Computers, 44 (3), 466-471.
• YEE, S.T. and VENTURA, J.A. 1999 A dynamic programming algorithm to determine optimal assembly sequences using petri nets. International Journal of Industrial Engineering - Theory, Applications and Practice 6 (1), 27-37.