Development of heuristics for the job scheduling problem on parallel batching machines with deliveries

Este trabalho consiste no estudo do problema de sequenciamento de tarefas com tempos de processamento distintos em máquinas paralelas idênticas que processam mais de uma tarefa simultaneamente, sendo as tarefas sequenciadas nos veículos capacitados que estão disponíveis para realizar as entregas em momentos especí- ficos pós processamento. O objetivo do problema é determinar o sequenciamento das tarefas que maximize o ganho da empresa, sabido que uma tarefa só poderá ser sequenciada se seu prazo de entrega for respeitado. Neste trabalho, propõe se, pri- meiramente, uma formulação de Programação Linear Inteira Mista (PLIM) para o problema. Em seguida, propõe-se uma relaxação do método heurístico citado na literatura para determinar um limite superior (UB) para a solução. Na sequência aplica-se uma heurística construtiva, para gerar uma solução viável baseada na so- lução de UB. Por fim, são propostas diversas heurísticas de melhoria cujo princípio de funcionamento se baseia nas heurísticas Variable Neighborhood Descent(VND) e Simulated Annealing (SA), com o objetivo de determinar soluções de melhor qualidade. Os resultados obtidos mostraram a eficiência dos métodos heurísticos implementados em relação ao limite superior (UB).This work deals with the job scheduling problem on identical parallel-batch machi- nes and where the jobs have different processing times. When the jobs processing time finish, the jobs are sequenced in vehicles with limited capacity that are avai- lable to deliver at specific times. The goal of the problem is to determine the sequencing of tasks that maximizes the company’s profit, knowing that a job can only be sequenced if its delivery deadline is respected. In this work it was first pro- posed a Mixed Integer Linear Programming for the problem. Then it was proposed a relaxation of the heuristic method mentioned in the literature to determine an upper bound (UB) for the solution. A constructive heuristic was then applied to generate a viable solution based on the UB solution. Finally,several heuristics of improvements were proposed, whose operating principle is based on the heuristic VND and on the heuristic Simulated Annealing (SA), aiming to determine bet- ter quality solutions. The obtained results showed the efficiency of the heuristic methods implemented in relation to the upper bound (UB).Coordenação de Aperfeiçoamento de Pessoal de Nível Superio