A mathematical formulation and an NSGA-II algorithm for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling

Marcelo F Rego; Júlio Cesar E M Pinto; Luciano P Cota; Marcone J F Souza

doi:10.7717/peerj-cs.844

A mathematical formulation and an NSGA-II algorithm for minimizing the makespan and energy cost under time-of-use electricity price in an unrelated parallel machine scheduling

PeerJ Comput Sci. 2022 Feb 3:8:e844. doi: 10.7717/peerj-cs.844. eCollection 2022.

Authors

Marcelo F Rego^{1

2}, Júlio Cesar E M Pinto², Luciano P Cota³, Marcone J F Souza²

Affiliations

¹ Department of Computing, Universidade Federal dos Vales dos Jequitinhonha e Mucuri, Diamantina, Minas Gerais, Brazil.
² Department of Computing, Universidade Federal de Ouro Preto, Ouro Preto, Minas Gerais, Brazil.
³ Instituto Tecnológico Vale, Ouro Preto, Minas Gerais, Brazil.

Abstract

In many countries, there is an energy pricing policy that varies according to the time-of-use. In this context, it is financially advantageous for the industries to plan their production considering this policy. This article 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. We propose a mixed-integer linear programming formulation based on the weighted sum method to obtain the Pareto front. We also developed an NSGA-II method to address large instances of the problem since the formulation cannot solve it in an acceptable computational time for decision-making. The results showed that the proposed NSGA-II is able to find a good approximation for the Pareto front when compared with the weighted sum method in small instances. Besides, in large instances, NSGA-II outperforms, with 95% confidence level, the MOGA and NSGA-I multi-objective techniques concerning the hypervolume and hierarchical cluster counting metrics. Thus, the proposed algorithm finds non-dominated solutions with good convergence, diversity, uniformity, and amplitude.

Keywords: Makespan; Mixed-integer linear programming; Multi-objective optimization; NSGA-II; Total energy cost; Unrelated parallel machine.

Grants and funding

This work was supported by the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior-Brazil (CAPES)-Finance Code 001, Fundação de Amparo à Pesquisa do Estado de Minas Gerais (FAPEMIG, grant 676-17), and Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq, grant 303266/2019-8). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.