The Knapsack-Lightening problem and its application to scheduling HRT tasks

• Autorzy: Nawrocki J.R. , Complak W. , Błażewicz J. , Kopczyńska S. , Maćkowiak M.
• Języki publikacji: EN

Abstrakty

EN

In hard real-time systems timeliness is as important as functional correctness. Such systems contain so called hard real-time tasks (HRT tasks) which must be finished by a given deadline. One of the methods of scheduling of HRT tasks is periodic loading introduced by Schweitzer, Dror, and Trudeau. The paper presents an extension to that method which allows for deterministic utilization of cache memory in hard real-time systems. It is based on a new version of the Knapsack problem named Knapsack-Lightening. In the paper the Knapsack-Lightening problem is defined, its complexity is analyzed, and an exact algorithm along with two heuristics are presented. More-over the application of the Knapsack-Lightening problem to scheduling HRT tasks is described.

Słowa kluczowe

EN

algorithms; computational complexity; knapsack problem; greedy algorithms; branch and bound scheduling; real-time systems; cache memory; periodic loading

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2009
• Tom: Vol. 57, nr 1
• Strony: 71--77
• Opis fizyczny: Bibliogr. 8 poz., rys., tab.

Twórcy

autor

Nawrocki J.R.

autor

Complak W.

autor

Błażewicz J.

autor

Kopczyńska S.

autor

Maćkowiak M.

• Institute of Computing Sci., Poznan University of Technology, 60-965 Poznan, Poland,

Bibliografia

• [1] J. Błażewicz, P. Formanowicz, W. Kubiak, M. Przysucha, and G. Schmidt, "Parallel branch and bound algorithms for the two machine flow shop problem with limited machine availability", Bull. Pol. Ac.: Tech. 48 (1), 105-115 (2000).
• [2] W. Complak, "Deterministic approach to the notebook memory management in systems strongly conditioned by time", Doctoral Dissertation, Poznan University of Technology, Poznan, 2001, (in Polish).
• [3] H. Kellerer, U. Pferschy, and D. Pi singer, Knapsack Problems, Springer Verlag, Berlin, 2004.
• [4] J.R. Nawrocki and A. Urbański, "Optimization of region-based storage allocation", Bull. Pol. Ac.: Tech. 42 (4), 605-617 (1994).
• [5] J.R. Nawrocki and A. Czajka, "Task c1assyfying in systems strongly conditioned by time with the use of the method of cyclic loading", Silesian University of Technology Periodicals: Automatics 1389, 169-179 (1998), (in Polish).
• [6] P.J. Schweitzer, M. Dror, and P. Trudeau, "The periodic loading problem: formulation and heuristics", INFOR 26 (1), 40-62 (1988).
• [7] G. Yu, "On the max-min 0-1 Knapsack problem with robust optimization applications", Operations Research 44 (2), 407--415 (1996).
• [8] D.D. Zeng, M. Dror, and H. Chen, "Efficient scheduling of periodic information monitoring requests", EJOR 173 (2), 583-599 (2006).