Tese
Modelling batch processing machines problems with symmetry breaking and arc flow formulation
Modelagem de problemas de máquinas de processamento em lote utilizando formulações com quebra de simetrias e fluxo em arco
Autor
Trindade, Renan Spencer
Institución
Resumen
Problems of minimizing makespan in scheduling batch processing machines are widely exploited by academic literature, mainly motivated by burn-in tests in the semiconductor industry. The problems addressed in this work consist of grouping jobs in batches and scheduling this in parallel machines. The jobs have non-identical size and processing times. The total size of the batch cannot exceed the capacity of the machine. The processing time of each batch will be equal to the higher processing time of all the jobs assigned to it. Jobs can also consider non-identical release times; in this case, the batch can only be processed after the job with the longest release time is available. This thesis discusses four different batch scheduling problems, which consider different characteristics: single processing machine 1|sj , B|Cmax, parallel processing machines Pm|sj , B|Cmax, single processing machine and non-identical release times 1|rj , sj , B|Cmax, parallel processing machines and non-identical release times Pm|rj , sj , B|Cmax. New mathematical formulations are proposed exploiting the treatment of symmetry for these problems. In addition, an arc-flow-based model is presented for problems 1|sj , B|Cmax and Pm|sj , B|Cmax. The mathematical models are solved using CPLEX, and computational results show that the proposed models have a better performance than other models in the literature. 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.