A mathematical formulation and heuristic algorithms for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling problem.
Nenhuma Miniatura disponível
Data
2022
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
Em muitos países, o preço da energia varia de acordo com a política time-of-use. Como regra geral, é vantajoso financeiramente para as indústrias planejarem sua
produção considerando essa política. Esta tese apresenta um novo problema de sequenciamento de máquinas paralelas não-relacionadas bi-objetivo com tempos de preparação
dependentes da sequência, no qual os objetivos são minimizar o makespan e o custo total
de energia considerando máquinas com diferentes modos de operação e que o preço da
eletricidade segue a política time-of-use. Introduzimos uma formulação de programação
linear inteira mista e aplicamos o método da soma ponderada para obter uma fronteira Pareto. Também desenvolvemos métodos de otimização multiobjetivo, baseados
no Multi-objective Variable Neighborhood Search com procedimento de intensificação
(chamado MOVNS2) e o Non-dominated Sorting Genetic Algorithm II (NSGA-II), para
tratar instâncias grandes, com pelo menos 50 tarefas, uma vez que a formulação não
pode resolvê-las em um tempo computacional aceitável para a tomada de decisão. Comparamos o desempenho dos algoritmos NSGA-II e MOVNS2 com dois algoritmos de
otimização multiobjetivo da literatura, o MOVNS1 e o NSGA-I, em relação às métricas
de hipervolume e hierarchical cluster counting (HCC). Os resultados mostraram que
os métodos propostos são capazes de encontrar uma boa aproximação para a fronteira
Pareto comparado com os resultados do método de soma ponderada em instâncias pequenas, de até 10 tarefas. Quando consideramos apenas as instâncias grandes, o MOVNS2
é superior ao MOVNS1, o NSGA-I e o NSGA-II em relação à métrica de hipervolume. Além disso, o NSGA-II supera os métodos de otimização multiobjetivo NSGA-I,
MOVNS1 e MOVNS2 em relaçãoo à métrica HCC. Ambos os resultados apresentam um
nível de confiança de 95%. Assim, o MOVNS2 proposto é capaz de encontrar soluções
não-dominadas com boa convergência e o NSGA-II com boa diversidade.
Descrição
Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
Palavras-chave
Unrelated parallel machine, Total energy cost, Makespan, Mixed-Integer Linear Programming, Multiobjective optimization
Citação
REGO, Marcelo Ferreira. A mathematical formulation and heuristic algorithms for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling problem. 2022. 72 f. Tese (Doutorado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2022.