Parallel machine scheduling with a total energy consumption limitation for minimizing total completion time

Abstract

This article investigates an energy-efficient, identical parallel machine scheduling problem. The objective is to minimize the total completion time while total energy costs do not exceed a given limitation. First, a reasonable range of total energy cost limits and the NP-hardness of this problem are analysed. Then, a mixed-integer programming model is presented. Afterwards, an improved simulated annealing (ISA) algorithm is devised. The ISA algorithm incorporates four effective neighbourhood operators, a method for adaptive selection of operators, and an initial feasible solution generation method. Comparison with genetic algorithms (GAs) and simplified swarm optimization (SSO) algorithms verifies the effectiveness and efficiency of the ISA algorithm. Results demonstrate that the ISA algorithm can provide near-optimal or better solutions than CPLEX${}^{\circledR }$ in small- and medium-scale instances. Experimental results on large-scale instances show that ISA significantly outperforms GAs and SSOs. ISA, in particular, can find the best values for all instances of 500 jobs except one.

Keywords:

• Identical parallel machine scheduling
• total completion time
• total energy cost limit
• metaheuristic algorithm

Disclosure statement

The authors report there are no competing interests to declare.

The authors' contributions

Kai Li: conceptualization, methodology, writing (reviewing and editing), funding acquisition. Fulong Xie: methodology, software, writing (original draft preparation and revision). Xin Zhao: methodology, writing (original draft and preparation). Jianfu Chen: writing (reviewing and editing). Tao Zhou: writing (reviewing and editing).

Data availability

Data for this article can be accessed at https://github.com/YL-123-max/Paper_data/tree/IPMTC/Instances-and-experimental_results.

Additional information

Funding

This work was supported by the National Natural Science Foundation of China [Nos 72271070, 71871076]; the Natural Science Foundation of Anhui Province [No. 2208085J07].