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

dc.contributorFampa, Marcia Helena Costa
dc.contributorhttp://lattes.cnpq.br/0523104569378276
dc.contributorhttp://lattes.cnpq.br/5925479498003995
dc.contributorAraújo, Olinto César Bassi de
dc.contributorhttp://lattes.cnpq.br/3250263200794986
dc.contributorSimonetti, Luidi Gelabert
dc.contributorFrota, Yuri Abitbol de Menezes
dc.contributorD’Ambrosio, Claudia
dc.creatorTrindade, Renan Spencer
dc.date2021-01-22T00:07:35Z
dc.date2023-09-27T03:03:09Z
dc.date2019-05
dc.date.accessioned2023-09-27T13:42:22Z
dc.date.available2023-09-27T13:42:22Z
dc.identifierhttp://hdl.handle.net/11422/13545
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/8912179
dc.descriptionProblems 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.
dc.descriptionProblemas 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.
dc.languageeng
dc.publisherUniversidade Federal do Rio de Janeiro
dc.publisherBrasil
dc.publisherInstituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
dc.publisherPrograma de Pós-Graduação em Engenharia de Sistemas e Computação
dc.publisherUFRJ
dc.rightsAcesso Aberto
dc.subjectBatch processing machine
dc.subjectScheduling
dc.subjectMakespan
dc.subjectSymmetry
dc.subjectArc flow
dc.subjectCNPQ::ENGENHARIAS
dc.titleModelling batch processing machines problems with symmetry breaking and arc flow formulation
dc.titleModelagem de problemas de máquinas de processamento em lote utilizando formulações com quebra de simetrias e fluxo em arco
dc.typeTese


Este ítem pertenece a la siguiente institución