| Title: |
Scheduling Problems: Pedagogical Contributions to Learning within the Scope of Computation Theory ; Problemas de Agendamento: Contribuições Pedagógicas para o Aprendizado no Escopo da Teoria da Computação |
| Authors: |
Rolins Ribeiro, Heloisa; Oneides da Silva Fialho Neta, Neci; Martins da Silva, Daniel; Dias dos Santos, Tanilson |
| Source: |
Academic Journal on Computing, Engineering and Applied Mathematics; Vol. 7 No. 2 (2026); 51-60 ; Academic Journal on Computing, Engineering and Applied Mathematics; v. 7 n. 2 (2026); 51-60 ; 2675-3588 ; 10.20873/uft.2675-3588.2026.v7n2 |
| Publisher Information: |
Universidade Federal do Tocantins |
| Publication Year: |
2026 |
| Collection: |
Periódicos UFT (Universidade Federal do Tocantins) |
| Subject Terms: |
NP-Completude; Agendamento; Redução Polinomial; 3-SAT; Complexidade computacional; NP-completeness; Scheduling; Polynomial reduction; Computational complexity |
| Description: |
Scheduling problems constitute a fundamental class of challenges in optimization and computing, particularly in operating systems, parallel processing, and real-time applications. Despite their wide practical use, many variants remain computationally intractable, even under strong structural restrictions. This article investigates the NP-completeness of two specific versions of the scheduling problem: scheduling with unit processing time and scheduling on two processors with tasks of duration one or two time units. The theoretical foundation relies on classical polynomial-time reductions, especially from the 3-SAT problem, which allows logical assignments to be encoded directly into precedence constraints and processor-capacity limitations. Furthermore, additional transformations between restricted versions of the problem are employed to preserve the structural equivalence of solutions. The contributions include a didactic reconstruction of the original proofs, an analysis of the mechanisms that give rise to computational hardness, and a discussion of the practical implications of these results in real scheduling systems. The results presented in the literature reinforce that even seemingly simple scenarios exhibit NP-complete behavior. ; 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 ... |
| Document Type: |
article in journal/newspaper |
| File Description: |
application/pdf |
| Language: |
Portuguese |
| Relation: |
https://sistemas.uft.edu.br/periodicos/index.php/AJCEAM/article/view/22514/24039; https://sistemas.uft.edu.br/periodicos/index.php/AJCEAM/article/view/22514 |
| DOI: |
10.20873/uft.2675-3588.2026.v7n2.p51-60 |
| Availability: |
https://sistemas.uft.edu.br/periodicos/index.php/AJCEAM/article/view/22514; https://doi.org/10.20873/uft.2675-3588.2026.v7n2.p51-60 |
| Rights: |
Copyright (c) 2026 Heloisa Rolins Ribeiro, Neci Oneides da Silva Fialho Neta, Daniel Martins da Silva, Tanilson Dias dos Santos ; https://creativecommons.org/licenses/by-nc/4.0 |
| Accession Number: |
edsbas.FD2B0FE9 |
| Database: |
BASE |