Power of pre-processing: production scheduling with variable energy pricing and power-saving states
- PDF / 896,619 Bytes
- 19 Pages / 439.642 x 666.49 pts Page_size
- 100 Downloads / 219 Views
Power of pre-processing: production scheduling with variable energy pricing and power-saving states Ondˇrej Benedikt1,2
1,2 ´ Modos ´ · Istvan
ˇ Hanzalek ´ 2 · Zdenek
Accepted: 20 October 2020 / Published online: 16 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper addresses a single machine scheduling problem with non-preemptive jobs to minimize the total electricity cost. Two latest trends in the area of the energy-aware scheduling are considered, namely the variable energy pricing and the power-saving states of a machine. Scheduling of the jobs and the machine states are considered jointly to achieve the highest possible savings. Although this problem has been previously addressed in the literature, the reported results of the state-of-the-art method show that the optimal solutions can be found only for instances with up to 35 jobs and 209 intervals within 3 hours of computation. We propose an elegant pre-processing technique called SPACES for computing the optimal switching of the machine states with respect to the energy costs. The optimal switchings are associated with the shortest paths in an interval-state graph that describes all possible transitions between the machine states in time. This idea allows us to implement efficient integer linear programming and constraint programming models of the problem while preserving the optimality. The efficiency of the models lies in the simplification of the optimal switching representation. The results of the experiments show that our approach outperforms the existing state-of-the-art exact method. On a set of benchmark instances with varying sizes and different state transition graphs, the proposed approach finds the optimal solutions even for the large instances with up to 190 jobs and 1277 intervals within an hour of computation. Keywords Single machine production scheduling · Machine states · Variable energy costs · Total energy cost minimization
Ondˇrej Benedikt
[email protected] Istv´an M´odos [email protected] Zdenˇek Hanz´alek [email protected] 1
Faculty of Electrical Engineering, Czech Technical University in Prague, Prague, Czech Republic
2
Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Prague, Czech Republic
Constraints (2020) 25:300–318
301
1 Introduction Energy-efficient scheduling has been attracting a considerable amount of attention lately, as reported by both Gahm et al. [6] and Gao et al. [7]. The trend is most likely to continue in the future since the energy-efficient scheduling helps to achieve sustainability of the production by both decreasing the production cost and minimizing its environmental impact. Gahm et al. [6] identified promising approaches to the energy-aware scheduling, including, among others, (i) the optimization of the energy demand by considering the power-saving states of the machines, and (ii) the participation in demand response programs, which are used by the electric utilities to reward the energ
Data Loading...
