Scheduling on Identical Parallel Machines with Time-of-Use Costs

In the latest years, energy-efficient scheduling has become an increasingly compelling and relevant matter due to both the rising global pollution levels and the growing interest of the industry towards sustainable manufacturing [1]. Specifically, many efforts have been devoted towards scheduling with the Time-of-Use (TOU) energy consumption model [2]. A scheduling horizon subject to a TOU policy is partitioned into different time slots, each one characterized by a different cost. The typical goal is to assign jobs to available machines in order to minimize the total energy consumption together with other possible objectives, such as the makespan or the total weighted tardiness. In this work, we consider the problem of scheduling a set of independent jobs on a set of identical, parallel machines with the objective of simultaneously minimizing the makespan and the total energy consumption. In more detail, we build upon [3] and provide an enhanced heuristic as well as a novel mixed-integer programming formulation. Finally, we show the effectiveness of the proposed solution approaches by reporting results from experimental tests performed on large size instances. [1 ] K. Gao, Y. Huang, Ali Sadollah, and L. Wang. A review of energy-efficient scheduling in intelligent production systems. Complex Intell. Syst., 6:237-249, 2020. [2 ] K. Train and G. Mehrez. Optional time-of-use prices for electricity: Econometric analysis of surplus and pareto impacts. RAND J. Econ., 25:263-283, 1994. [3 ] D. Anghinolfi, M. Paolucci, and R. Ronco. A bi-objective heuristic approach for green identical parallel machine scheduling. Eur. J. Oper. Res., 289(2):416-434, 2021.