Modelos matemáticos para os problemas de dimensionamento e programação de bateladas em máquina única e máquinas paralelas
Resumo
Problemas de minimização do makespan no dimensionamento e programação de bateladas
em máquinas de processamento são extensamente explorados pela literatura acadêmica,
motivados principalmente por testes de confiabilidade na indústria de semicondutores. Estes
problemas consistem em agrupar tarefas em bateladas e programar 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. As tarefas podem considerar também
tarefas com tempos de liberação não idênticos, 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 dimensionamento e programação de bateladas
com tarefas de tamanhos não idênticos, que consideram diferentes características: máquina de
processamento única (1|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
(Pm|sj,B|Cmax) e 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 características de cada problema. 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. Os modelos
propostos para 1|sj,B|Cmax e 1|rj,sj,B|Cmax são comparados com meta-heurísticas previamente
publicadas e os resultados mostram que os novos modelos oferecem soluções melhores com
tempos computacionais competitivos.