Problemas de Agendamento

Contribuições Pedagógicas para o Aprendizado no Escopo da Teoria da Computação

Autores

DOI:

https://doi.org/10.20873/uft.2675-3588.2026.v7n2.p51-60

Palavras-chave:

NP-Completude, Agendamento, Redução Polinomial, 3-SAT, Complexidade computacional

Resumo

Os problemas de agendamento constituem uma classe essencial de desafios em otimização e computação, especialmente em sistemas operacionais, processamento paralelo e aplicações em tempo real. Apesar de sua ampla utilização prática, diversas variantes permanecem computacionalmente intratáveis, mesmo sob fortes restrições estruturais. Este artigo investiga a NP-completude de duas versões específicas do problema de escalonamento: o agendamento com tempo de execução unitário e o agendamento com dois processadores em tarefas de duração igual a uma ou duas unidades. A fundamentação teórica baseia-se em reduções polinomiais clássicas, em particular a partir do problema 3-SAT, que permite codificar atribuições lógicas diretamente nas restrições de precedência e capacidade dos processadores. Além disso, transformações adicionais entre versões restritas do problema são utilizadas para preservar a equivalência estrutural das soluções. As contribuições incluem uma reconstrução didática das provas originais, a análise dos mecanismos que geram dureza computacional e uma discussão sobre as implicações práticas desses resultados em sistemas reais de escalonamento. Os resultados apresentados na literatura reforçam que mesmo cenários aparentemente simples apresentam comportamento NP-completo.

Biografia do Autor

Tanilson Dias dos Santos

Professor do Curso de Ciência da Computação - UFT. Doutor em Engenharia de Sistemas e Computação pelo PESC/COPPE-UFRJ. Possui Mestrado em Sistemas e Computação pelo Instituto Militar de Engenharia (IME,2014). É também pesquisador da área de Teoria dos Grafos e Teoria da Computação. Possuo graduação em Ciência da Computação e tem interesse de estudo nas áreas de Inteligência Artificial, Grafos, Otimização e Autômatos. Participou, anteriormente, do projeto de futebol de robôs na liga de simulação 2D. Possuo Certificação Internacional em Teste de Qualidade de Software, em exame realizado pela BSTQB, no nível CTFL (Foudation Level).

Downloads

Publicado

2026-02-10

Como Citar

[1]
Rolins Ribeiro, H. et al. 2026. Problemas de Agendamento: Contribuições Pedagógicas para o Aprendizado no Escopo da Teoria da Computação. Academic Journal on Computing, Engineering and Applied Mathematics. 7, 2 (fev. 2026), 51–60. DOI:https://doi.org/10.20873/uft.2675-3588.2026.v7n2.p51-60.

Edição

v. 7 n. 2 (2026)

Seção

Edição Especial

Categorias

Licença

Copyright (c) 2026 Heloisa Rolins Ribeiro, Neci Oneides da Silva Fialho Neta, Daniel Martins da Silva, Tanilson Dias dos Santos

Creative Commons License

Este trabalho está licenciado sob uma licença Creative Commons Attribution-NonCommercial 4.0 International License.

Autores que publicam neste periódico concordam com os seguintes termos:

  1. Autores mantém os direitos autorais e concedem ao periódico o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Creative Commons Attribution License (CC BY-NC 4.0), permitindo o compartilhamento do trabalho com reconhecimento da autoria do trabalho e publicação inicial neste periódico;
  2. Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial neste periódico;
  3. Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto posterior ao processo editorial;
  4. Além disso, o AUTOR é informado e consente com o periódico que, portanto, seu artigo pode ser incorporado pela Academic Journal on Computing, Engineering and Applied Mathematics em bases e sistemas de informação científica existentes (indexadores e bancos de dados atuais) ou a existir no futuro (indexadores e bancos de dados futuros), nas condições definidas por este último em todos os momentos, que envolverá, pelo menos, a possibilidade de que os titulares desses bancos de dados possam executar as seguintes ações sobre o artigo:
    1. Reproduzir, transmitir e distribuir o artigo, no todo ou em parte sob qualquer forma ou meio de transmissão eletrônica existente ou desenvolvida no futuro, incluindo a transmissão eletrônica para fins de pesquisa, visualização e impressão;
    2. Reproduzir e distribuir, no todo ou em parte, o artigo na impressão;
    3. Traduzir certas partes do artigo;
    4. Extrair figuras, tabelas, ilustrações e outros objetos gráficos e capturar metadados, legendas e artigo relacionado para fins de pesquisa, visualização e impressão;
    5. Transmissão, distribuição e reprodução por agentes ou autorizada pelos proprietários de distribuidoras de bases de dados;
    6. A preparação de citações bibliográficas, sumários e índices e referências de captura relacionados de partes selecionadas do artigo;
    7. Digitalizar e / ou armazenar imagens e texto de artigo eletrônico.

Artigos mais lidos pelo mesmo(s) autor(es)