This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Developing a Scheduler with Difference-Bound Matrices and the Floyd-Warshall Algorithm
January/February 2012 (vol. 29 no. 1)
pp. 76-83
Lorenzo Ridi, Universita di Firenze
Jacopo Torrini, Universita di Firenze
Enrico Vicario, Universita di Firenze
A study of difference-bound matrices and the Floyd-Warshall algorithm in the development of an online scheduler provides the backdrop for a comparison of software practice and algorithmic theory.

1. R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.
2. D.L. Dill, "Timing Assumptions and Verification of Finite-State Concurrent Systems," Automatic Verification Methods for Finite State Systems, LNCS 407, Springer, 1990, pp. 197–212.
3. E. Vicario, "Static Analysis and Dynamic Steering of Time-Dependent Systems," IEEE Trans. Software Eng., vol. 27, no. 8, 2001, pp. 728–748.
4. J. Bengtsson et al., "Uppaal—A Tool Suite for Automatic Verification of Real-Time Systems," Hybrid Systems III, LNCS 1066, Springer, 1996, pp. 232–243.
5. C. Kloukinas and S. Yovine, "Synthesis of Safe, QoS Extendible, Application Specific Schedulers for Heterogeneous Real-Time Systems," Proc. 15th Euromicro Conf. Real-Time Systems (ECRTS 03), IEEE CS Press, 2003, pp. 287–294.
6. G. Gardey et al., "Romeo: A Tool for Analyzing Time Petri Nets," Computer Aided Verification, LNCS 3576, Springer, 2005, pp. 261–272.
7. B. Berthomieu, P.-O. Ribet, and F. Vernadat, "The Tool TINA—Construction of Abstract State Spaces for Petri Nets and Time Petri Nets," Int'l J. Production Research, vol. 42, no. 14, 2004, pp. 2741–2756.
8. G. Bucci et al., "Oris: A Tool for Modeling, Verification and Evaluation of Real-Time Systems," Int'l J. Software Tools for Technology Transfer, vol. 12, no. 5, 2010, pp. 391–403.
9. A. Fehnker, "Scheduling a Steel Plant with Timed Automata," Proc. 6th Int'l Conf. Real-Time Computing Systems and Applications (RTCSA 99), IEEE CS Press, 1999, pp. 280–286.
10. K. Larsen, "Resource-Efficient Scheduling for Real Time Systems," Embedded Software, LNCS 2855, Springer, 2003, pp. 16–19.
11. I. Al Attili et al., "Adaptive Scheduling of Data Paths Using Uppaal Tiga," Proc. 1st Workshop Quantitative Formal Methods: Theory and Applications (QFM 09), Electronic Proceedings in Theoretical Computer Science, 2009, pp. 1–11.
12. I. Calvino, Invisible Cities, Harcourt Brace Jovanovich, 1978.

Index Terms:
sequencing and scheduling, graph algorithms, Floyd-Warshall algorithm, difference-bound matrix, model checking, software engineering
Citation:
Lorenzo Ridi, Jacopo Torrini, Enrico Vicario, "Developing a Scheduler with Difference-Bound Matrices and the Floyd-Warshall Algorithm," IEEE Software, vol. 29, no. 1, pp. 76-83, Jan.-Feb. 2012, doi:10.1109/MS.2011.128
Usage of this product signifies your acceptance of the Terms of Use.