Escalonamento da produção na SAPEC

O presente estudo tem como objetivo encontrar um sequenciamento de tarefas (scheduling), ou seja, determinar uma afetação ótima das tarefas às máquinas, minimizando o tempo de execução total (makespan). Este tipo de problema é um clássico da literatura e é conhecido como um problema de job-shop scheduling com uma sequência dependente de tempos de setup (JSP-SDST). Um JSP-SDST apresenta, uma complexidade NP-difícil. Sendo um problema de difícil otimização, constituiu, assim, um desfio nas áreas da Investigação Operacional e Ciência da Computação. A abordagem escolhida passou primeiramente por definir o espaço de soluções admissíveis (S.A.) e neste encontrar uma solução ótima (sob determinadas condições), através do algoritmo Branch-and-Bound, recorrendo-se particularmente ao tipo de pesquisa Depth First Search (B&B-DFS) no espaço das soluções admissíveis. Neste estudo são apresentados outros tipos de pesquisa, também baseados em B&B, por forma a avaliá-los. Foi desenvolvida uma interface gráfica centrada no utilizador para que este possa usufruir do presente estudo, sem ter de de lidar com a complexidade envolvida. A interface gráfica implementada é viável e, em articulação com os procedimentos de otimização escolhidos, constitui uma mais-valia para a organização, esperando-se que possa vir a ser instrumento de trabalho futuro.