  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.
