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.

Abstract

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.