Escalonamento de Tarefas com Níveis Variados de Criticidade - Dell’Arriva, Elisa; Miyazawa, Flávio K. (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da Computação, 2026)
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.