Exact and heuristic solution approaches for energy-efficient identical parallel machine scheduling with time-of-use costs

Nowadays, energy-efficient scheduling has assumed a key role in ensuring the sustainability of manufacturing processes. In this context, we focus on the bi-objective problem of scheduling a set of jobs on identical parallel machines to simultaneously minimize the maximum completion time and the total energy consumption over a time horizon partitioned into a set of discrete slots. The energy costs are determined by a time-of-use pricing scheme, which plays a crucial role in regulating energy demand and flattening its peaks. First, we uncover a symmetry-breaking property that characterizes the structure of the solution space of the problem. As a consequence, we provide a novel, compact mixed-integer linear programming formulation at the core of an efficient exact solution algorithm. A thorough experimental campaign shows that the use of the novel mathematical programming formulation enables the solution of larger-scale instances and entails a reduction in the computational times as compared to the formulation already available in the literature. Furthermore, we propose a new heuristic that improves the state-of-the-art in terms of required computational effort and quality of solutions. Such a heuristic outperforms the existing heuristics for the problem and is also capable of speeding up the exact solution algorithm when used for its initialization. Finally, we introduce a novel dynamic programming algorithm that is able to compute the optimal timing of the jobs scheduled on each machine to further improve the performance of the new heuristic.