Algorithms 2018, 11,18
Nevertheless, electricity is hard to store effectively, and thus, must be produced and delivered to its
customers at once [
7
]. In addition, the electricity demand is always uneven, which leads to an increase
in generating cost owing to the utilization of backup power facilities during peak hours [
8
]. In order
to maintain balance between electricity supply and demand, electricity providers usually implement
demand-side management programs [
9
], which are an essential component of realizing the goals of a
smart grid and rationalizing the allocation of power resources [10].
One of the demand-side management programs is time-of-use (TOU) electricity tariffs, which
have been widely used around the world. Usually, a common TOU tariff scheme can be divided
into three types of periods: off-peak, mid-peak, and on-peak periods. The basic nature of the TOU
scheme is that the retail prices set by electricity providers vary hourly throughout the day according to
the amount of electricity demands; when there is an increase in demand, the electricity cost goes up
correspondingly, and vice versa [
11
]. The practice of TOU electricity tariffs not only provides significant
opportunities for the industrial sector to enhance energy efficiency, but also avoids power rationing
during on-peak periods, and improves the stability of the power grid [7].
Using low-energy equipment and improving the efficiency of production management are two
important methods to save energy [
12
]. As a widely used production management method, scheduling
can effectively control energy consumption [
13
], which brings a lower cost of operation. However,
the studies about energy-saving scheduling are still limited [
14
]. Over recent years, energy-efficient
scheduling problems have gradually aroused the attention of scholars. To achieve the goal of energy
saving during the production process, some researchers have investigated the problems with various
energy-efficient mechanisms to reduce electricity costs by minimizing overall energy consumption,
such as speed-scaling [
15
–
18
] and power-down [
19
–
21
], while others have studied the problems from
the perspective of TOU electricity tariffs, which has become a frontier issue in this field.
As for researching scheduling problems under TOU electricity tariffs, there has been a growing
interest recently. Considering both production and energy efficiency, Luo et al. [
22
] proposed an
ant colony optimization meta-heuristic algorithm for hybrid flow shop scheduling problems under
TOU electricity tariffs. Zhang et al. [
12
] studied a flow shop scheduling problem with production
throughput constraints to minimize electricity cost and the carbon footprint simultaneously. Sharma
et al. [
23
] presented a so called “econological scheduling” model for a speed-scaling multi-machine
scheduling problem aimed to minimize the electricity cost and environmental impact. Moon et al. [
24
]
examined the unrelated parallel machine scheduling problem under TOU electricity tariffs to optimize
the weighted sum of makespan and electricity cost. Ding et al. [
7
] and Che et al. [
25
] addressed a similar
parallel machine scheduling problem under TOU electricity tariffs to minimize the total electricity cost.
The former developed a time-interval-based mixed-integer linear programming (MILP) model and a
column generation heuristic algorithm. The latter improved the former model by providing a linear
programming relaxation and a two-stage heuristic algorithm.
Single machine scheduling problems are of great significance both in theory and practice.
On one hand, there are many single machine scheduling problems in the real industrial environment.
For example, a Computer Numerical Control (CNC for short) planer horizontal milling and boring
machine can be regarded as a single machine. On the other hand, the research results and methods of
single machine scheduling problems can provide reference for other scheduling problems, such as flow
shop, job shop, and parallel machine scheduling problems. For single machine scheduling problems
under TOU electricity tariffs, Wang et al. [
26
] investigated a single-machine batch scheduling problem
to minimize the makespan and the total energy costs simultaneously. Considering the TOU electricity
tariffs and the power-down mechanism, Shrouf et al. [
27
] proposed a model that enables the operations
manager to determine the “turning on” time, “turning off” time, and idle time at machine level, leading
to a significant reduction in electricity cost by avoiding on-peak periods. Gong et al. [
28
] developed a
mixed integer linear programming model and a genetic algorithm for the same problem, reducing
electricity cost and greenhouse gas emissions effectively during peak time periods. Without considering
a power-down mechanism, Fang et al. [
29
] studied the single machine scheduling problem under TOU
2