Use este identificador para citar ou linkar para este item: http://www.repositorio.ufop.br/jspui/handle/123456789/14909
Título: 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.
Autor(es): Rego, Marcelo Ferreira
Orientador(es): Souza, Marcone Jamilson Freitas
Cota, Luciano Perdigão
Palavras-chave: Unrelated parallel machine
Total energy cost
Makespan
Mixed-Integer Linear Programming
Multiobjective optimization
Data do documento: 2022
Membros da banca: Souza, Marcone Jamilson Freitas
Cota, Luciano Perdigão
Penna, Puca Huachi Vaz
Coelho, Igor Machado
Arroyo, José Elias Claudio
Batista, Lucas de Souza
Referência: 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.
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.
Resumo em outra língua: In many countries, energy pricing varies according to the time-of-use policy. As a general rule, it is financially advantageous for the industries to plan their production considering this policy. This thesis introduces a new bi-objective unrelated parallel machine scheduling problem with sequence-dependent setup times, in which the objectives are to minimize the makespan and the total energy cost under machines with different operating modes and the time-of-use electricity price policy. We introduced a mixed-integer linear programming formulation and applied the weighted sum method to obtain the Pareto front. We also developed multi-objective methods, based on the Multi-objective Variable Neighborhood Search with intensification procedure (named MOVNS2) and Non-dominated Sorting Genetic Algorithm II (NSGA-II), to address large instances with at least 50 jobs since the formulation cannot solve it in acceptable computational time for decision-making. We compared the performance of the NSGA-II and MOVNS2 algorithms with two multi-objective algorithms of the literature, MOVNS1, and NSGAI, concerning the hypervolume and hierarchical cluster counting (HCC) metrics. The results showed that the proposed methods are able to find a good approximation for the Pareto front compared with the presented results by the weighted sum method in small instances with up to 10 jobs. Considering only large instances, MOVNS2 is superior to MOVNS1, NSGA-I, and NSGA-II in the hypervolume metric. In addition, NSGA-II outperforms the NSGA-I, MOVNS1, and MOVNS2 multi-objective techniques concerning the HCC metric. Both results are with a 95% confidence level. Thus, the proposed MOVNS2 finds non-dominated solutions with good convergence and NSGA-II with good diversity.
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.
URI: http://www.repositorio.ufop.br/jspui/handle/123456789/14909
Licença: Autorizaçã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.
Aparece nas coleções:PPGCC - Doutorado (Teses)

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
TESE_MathemathicalFormulationHeuristic.pdf869,05 kBAdobe PDFVisualizar/Abrir


Este item está licenciado sob uma Licença Creative Commons Creative Commons