Modelling batch processing machines problems with symmetry breaking and arc flow formulation

Detalhes bibliográficos
Ano de defesa: 2019
Autor(a) principal: Trindade, Renan Spencer
Orientador(a): Não Informado pela instituição
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: eng
Instituição de defesa: Universidade Federal do Rio de Janeiro
Brasil
Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
Programa de Pós-Graduação em Engenharia de Sistemas e Computação
UFRJ
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: http://hdl.handle.net/11422/13545
Resumo: 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.