Evaluation of Search Heuristics for Embedded System Scheduling Problems

1. T. F. Abdelzaher and K. G. Shin. Period-based load partitioning and assignment for large real-time applications. IEEE Trans. on Computers, 49(1): 81–87, 2000.

   Article  Google Scholar 

2. I. Ahmad and Y.-K. Kwok. Optimal and near-optimal allocation of precedence-constrained tasks to parallel processors: Defying the high complexity using effective search techniques. In Proc. of the Int’l Conf. on Parallel Processing, pp. 424–431, Minneapolis, Minnesota, August 10-14, 1998.

   Google Scholar 

3. J. A. Bannister and K. S. Trivedi. Task allocation in fault-tolerant distributed systems. Acta Informatica, 20: 261–281, 1983.

   Article  MathSciNet  Google Scholar 

4. P. Brucker, M. R. Garey, and D. S. Johnson. Scheduling equal-length tasks under treelike precedence constraints to minimize maximum lateness. Mathematics of Operations Research, 2(3): 275–284, August 1977.

   Article  MathSciNet  Google Scholar 

5. M. Carlsson, G. Ottosson, and B. Carlson. An open-ended finite domain constraint solver. In H. Glaser et al.,editors, Proc. of the Int’l Symposium on Programming Languages: Implementations, Logics, and Programs, volume 1292 of Lecture Notes in Computer Science, pp. 191–206, Southampton, UK, September 3-5, 1997.

   Google Scholar 

6. C. Ekelin and J. Jonsson. A modeling framework for constraints in real-time systems. Tech. Rep. 00-9, Dept. of Computer Engineering, Chalmers University of Technology, S-412 96 Göteborg, Sweden, May 2000.

   MATH  Google Scholar 

7. C. Ekelin and J. Jonsson. Solving embedded system scheduling problems using constraint programming. Tech. Rep. 00-12, Dept. of Computer Engineering, Chalmers University of Technology, S-412 96 Göteborg, Sweden, April 2000.

   MATH  Google Scholar 

8. J. Jonsson and K. G. Shin. A parametrized branch-and-bound strategy for scheduling precedence-constrained tasks on a multiprocessor system. In Proc. of the Int’l Conf. on Parallel Processing, pp. 158–165, Bloomingdale, Illinois, 1997.

   Google Scholar 

9. Intelligent Systems Laboratory. SICStus Prolog User’s Manual. Swedish Institute of Computer Science, 1995. http://www.sics.se/isl/sicstus/

10. C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1): 46–61, January 1973.

    Article  MathSciNet  Google Scholar 

11. K. Ramamritham. Allocation and scheduling of precedence-related periodic tasks. IEEE Trans. on Parallel and Distributed Systems, 6(4): 412–420, April 1995.

    Article  Google Scholar 

12. K. Schild and J. Würtz. Scheduling of time-triggered real-time systems.Constraints, 5(4): 335–357, October 2000.

    Article  MathSciNet  Google Scholar 

13. J. Slaney and S. Thiébaux. On the hardness of decision and optimisation problems. In Proc. of ECAI, pp. 244–248, Brighton, UK, 1998.

    Google Scholar 

14. B. M. Smith and I. P. Gent. Symmetry breaking during search in constraint programming. In Proc. of ECAI, pp. 599–603, Berlin, Germany, 2000.

    Google Scholar 

15. R. Szymanek, F. Gruian, and K. Kuchcinski. Digital systems design using constraint logic programming. In Proc. of the Practical Application of Constraint Technology and Logic Programming, Manchester, England, April 10-12, 2000.

    Google Scholar 

16. K. W. Tindell, A. Burns, and A. J. Wellings. Allocating hard real-time tasks: An NP-hard problem made easy. Real-Time Systems, 4(2): 145–165, June 1992.

    Article  Google Scholar 

17. E. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.

    Google Scholar 

18. J. Xu. Multiprocessor scheduling of processes with release times, deadlines, precedence, and exclusion relations. IEEE Trans. on Software Engineering, 19(2): 139–154, February 1993.

    Article  Google Scholar 

Download references