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

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® 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.