Escalonamento de Tarefas com Níveis Variados de Criticidade
Resumo
Abordamos o problema de escalonamento não preemptivo de tarefas unitárias com diferentes níveis de criticidade em múltiplas máquinas com capacidade definida. Se necessário durante a execução, uma tarefa pode executar por um tempo extra, que depende de sua criticidade, e tarefas menos críticas podem ser canceladas. O objetivo é minimizar o número de máquinas necessárias para escalonar todas as tarefas. Apresentamos um APTAS para o caso em que todas as tarefas são significativamente críticas, ou seja, há um limite mínimo para os valores de criticidade.Referências
Baruah, S., Li, H., and Stougie, L. (2010). Towards the design of certifiable mixedcriticality systems. In 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 13–22.
Burns, A. and Davis, R. I. (2015). Mixed criticality systems - a review.
de la Vega, W. F. and Lueker, G. S. (1981). Bin packing can be solved within 1 + ϵ in linear time. Combinatorica, 1:349–355.
Eisenbrand, F. (2003). Fast integer programming in fixed dimension. In Di Battista, G. and Zwick, U., editors, Algorithms - ESA 2003, pages 196–207, Berlin, Heidelberg. Springer Berlin Heidelberg.
Hanzalek, Z. and Pacha, T. (1998). Use of the fieldbus systems in academic setting. In Proceedings Real-Time Systems Education III, page 15.
Hanzálek, Z., Tunys, T., and ůcha, P. (2016). An analysis of the non-preemptive mixed-criticality match-up scheduling problem. Journal of Scheduling, 19:601 – 607.
Lenstra, H. W. (1983). Integer programming with a fixed number of variables. Math. Oper. Res., 8:538–548.
Socci, D., Poplavko, P., Bensalem, S., and Bozga, M. (2013). Mixed critical earliest deadline first. In 2013 25th Euromicro Conference on Real-Time Systems, pages 93–102.
Vestal, S. (2007). Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the 28th IEEE International Real-Time Systems Symposium, RTSS ’07, page 239–243, USA. IEEE Computer Society.
Burns, A. and Davis, R. I. (2015). Mixed criticality systems - a review.
de la Vega, W. F. and Lueker, G. S. (1981). Bin packing can be solved within 1 + ϵ in linear time. Combinatorica, 1:349–355.
Eisenbrand, F. (2003). Fast integer programming in fixed dimension. In Di Battista, G. and Zwick, U., editors, Algorithms - ESA 2003, pages 196–207, Berlin, Heidelberg. Springer Berlin Heidelberg.
Hanzalek, Z. and Pacha, T. (1998). Use of the fieldbus systems in academic setting. In Proceedings Real-Time Systems Education III, page 15.
Hanzálek, Z., Tunys, T., and ůcha, P. (2016). An analysis of the non-preemptive mixed-criticality match-up scheduling problem. Journal of Scheduling, 19:601 – 607.
Lenstra, H. W. (1983). Integer programming with a fixed number of variables. Math. Oper. Res., 8:538–548.
Socci, D., Poplavko, P., Bensalem, S., and Bozga, M. (2013). Mixed critical earliest deadline first. In 2013 25th Euromicro Conference on Real-Time Systems, pages 93–102.
Vestal, S. (2007). Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In Proceedings of the 28th IEEE International Real-Time Systems Symposium, RTSS ’07, page 239–243, USA. IEEE Computer Society.
Publicado
19/07/2026
Como Citar
DELL’ARRIVA, Elisa; MIYAZAWA, Flávio K..
Escalonamento de Tarefas com Níveis Variados de Criticidade. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 11. , 2026, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 124-128.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2026.23397.
