Souza, Marcone Jamilson FreitasCota, Luciano PerdigãoRego, Marcelo Ferreira2022-05-302022-05-302022REGO, 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.http://www.repositorio.ufop.br/jspui/handle/123456789/14909Programa 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.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.pt-BRabertoUnrelated parallel machineTotal energy costMakespanMixed-Integer Linear ProgrammingMultiobjective optimizationTeseAutorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 16/05/2022 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho, desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação.