Problema das Sequências Justas Ponderadas
Sequenciamento; Sequências justas, programaçao inteira mista
Problemas de escalonamento aos quais são impostas restrições relativas às distâncias temporais entre sucessivas execuções de uma mesma tarefa possuem um grande número de aplicações, que variam desde o escalonamento de tarefas em sistemas de tempo real à produção de automóveis em uma linha de montagem. O presente trabalho apresenta um novo problema de otimização, denominado de Problema das Sequências Justas Ponderadas (PSJP), que faz parte dessa classe de problemas. Além do estudo da complexidade computacional do problema, é apresentada uma formulação matemática baseada Programação Linear Inteira Mista e uma série de cortes que aprimoram sua resolução via métodos exatos. Por fim, propõe-se uma solução heurística que utiliza bem menos variáveis que a formulação PJSP. Experimentos computacionais mostram que, para um dado horizonte de tempo, a solução proposta aumentam o número de instâncias resolvidas na prática. Além disso, seus resultados devem ser considerados como ótimos caso uma conjectura apresentada sobre o PJSP seja provada verdadeira no futuro.