Modelling Batch Processing Machines Problems with Symmetry Breaking and Arc Flow Formulation

Problemas de minimização do makespan no escalonamento de bateladas em máquinas de processamento são extensamente explorados pela literatura acadêmica, motivados principalmente por testes burn-in na indústria de semicondutores. Os problemas considerados neste trabalho consistem em agrupar tarefas em bateladas e escalonar o processamento em uma ou mais máquinas em paralelo. As tarefas possuem tempos de processamento e tamanhos não idênticos e o tamanho total da batelada não pode exceder a capacidade da máquina. Para cada batelada é definido um tempo de processamento que será igual ao maior tempo de processamento das tarefas que foram alocadas a ela. O problema pode considerar também tempos de liberação das tarefas não idênticos e, neste caso, as bateladas só poderão ser processadas depois que a tarefa com o maior tempo de liberação for disponibilizada. Este trabalho aborda quatro diferentes problemas de escalonamento de bateladas, que consideram diferentes características: máquina de processamento única 1 sj, B Cmax, máquinas de processamento paralelas idênticas Pm sj, B Cmax, máquina de processamento única e tarefas com tempos de liberação não idênticos 1 rj,sj, B Cmax, máquinas de processamento paralelas idênticas e tarefas com tempos de liberação não idênticos Pm rj, sj, B Cmax. São propostos novos modelos matemáticos com formulações que exploram o tratamento de simetria para estes problemas. Além disso, é apresentado um modelo baseado em fluxo em arco para os problemas 1 sj, B Cmax e Pm sj, B Cmax. Os modelos matemáticos são resolvidos utilizando CPLEX e os resultados computacionais comprovam que os modelos propostos possuem um desempenho melhor do que outros modelos da literatura.