The 14th International Conference on Intelligent System Applications to Power Systems, ISAP 2007
November 4 - 8, 2007, Kaohsiung, Taiwan650
Relaxed Dynamic Programming for Constrained Economic Direct Loads Control Scheduling Tsair-Fwu Lee, Member, IEEE, Horng-Yuan Wu, Ying-Chang Hsiao, Pei-Ju Chao, Fu-Min Fang, and Ming-Yuan Cho*, Member, IEEE
saving benefits and the second is to minimize the perturbation of load interruption to the customer simultaneously. The proposed model can be built to achieve customer satisfaction and to achieve the electricity saving requirement, the mathematical model of the problem can be formulated as follows [7, 8].
Abstract-- We study the problem of dynamically scheduling a set of period stage control tasks controlling a set of large air conditioner loads (ACLs). To be able to solve the scheduling problem for realistic on-line cases, we utilize the technique of relaxed dynamic programming (RDP) algorithm to generate an optimal or near optimal daily control scheduling for ACLs with relaxing bounds. Field tests of controlling the ACLs located in the campus are tested on-site to demonstrate the effectiveness of the proposed load control strategy. Index Terms—relaxed dynamic programming, optimization, load control scheduling.
I. INTRODUCTION
E
NERGY saving efficiency is an ongoing problem, especially for industries with high power consumption, such as the iron and steel, the petrochemistry, the cement, and the paper-making industries, which need to continually consider electricity saving schemes to increase their competitiveness [1-3]. The conventional control mode for ACL supports three types of control, demand control, cycling control and timer control, to assist customers in saving electricity costs. The proposed optimum loads control scheduling (LCS) scheme supports any combinations of these three control types to optimally save costs during the dispatch period [4, 5] by using RDP algorithm to adopt optimal loads scheduling. To be able to solve the scheduling problem for realistic on-line cases, we utilize the technique of RDP algorithm to generate an optimal or near optimal daily control scheduling for ACLs with relaxed bounds under constraints. To carry out the proposed strategy, the techniques of microprocessor hardware are applied with Visual C++ language. II. PROBLEM FORMULATION There are two objectives to be implemented for the LCS strategy [6]. The first is to maximize the customer electricity T.-F. Lee and F.-M. Fang are with the Department of Radiation Oncology, Chang Gung Memorial Hospital Kaohsiung Medical Center, Kaohsiung, Taiwan. (E-mail:
[email protected],
[email protected]). Y.-C. Hsiao is with the Department of Electrical Engineering, Fortune Institute of Technology, Kaohsiung County, Taiwan, ROC. (E-mail:
[email protected]). P.-J. Chao is with the Department of Radiation Oncology, Kaohsiung Yuan’s General Hospital, Taiwan. (E-mail:
[email protected]). M.-Y. Cho and H.-Y. Wu are with the Department of Electrical Engineering National Kaohsiung University of Applied Sciences. (*Corresponding author, phone: 886-7-3814526*5530; Fax: 886-7-392-3532, E-mail:
[email protected],
[email protected]).
650
A. Objective function For minimizing the uncomfortable situation and disturbance to the customers, the objective function B considered in this problem comprises two terms. The first term is to minimize inconvenient and disturbance to customers during the daily dispatch period, and the second term considers the willingness of customers to be charged an incentive rate for accepting interrupted control schemes, which can be expressed as follows: M N 1 B = Min ∑∑ CLg (i ) × 1 − Sg (i ) × × δ , 0 ≤ δ ≤ 1. g =1 i =1 4
(
)
(1)
Where M: N: CLg(i): Sg(i):
δ: B:
number of ACLs number of control periods (daily) capacity of the gth ACL group in period i (kW) State of the gth ACL growth in period i =1 if the gth ACL group is connected to the system in period i; =0 if the gth ACL group is disconnected from the system in period i saving weighting percentage factor of the gth ACL group; its value is between 0 and 1 objective weighting capacity; it is the shared by demand control and cycling control strategies
We adopt the knapsack technique based on a RDP algorithm to find a global optimal or near optimal solution but less complexity in dimensionality. In the first, assume Sm is the solution set of objective function from 1 to the mth number of the ACL, and then to define benefit function bi and weighting function wi at each period. The objective function solution is to obtain the maximum corresponding B under constraints which will discuss next had to be satisfied. Thus, the objective function and constraint function can be expressed as follows:
Objective : maximize ∑ bi = B,
(2)
i∈T
Constraint :
∑ wi ≤ W .
i∈T
(3)
Namely, the optimal result is decided by the benefit
The 14th International Conference on Intelligent System Applications to Power Systems, ISAP 2007
function B, for which the mathematical equation takes the following form:
November 4 - 8, 2007, Kaohsiung, Taiwan651
Bk +1 ( x ) = min{ Bk ( f (x, u )) + l (x, u ) }.
(9)
u
, if wm > w, B(m − 1, w) (4) B (m,w ) = max[B (m − 1, w ), B (m − 1, w − wm ) + bm ] , otherwise .
Where l(x,u) is a given cost function. In RDP method, we have to find a B(x) with relaxed bounds which fulfills B(0)=0 and
Where
min{ Bk ( f (x, u )) + l ( x, u ) } ≤ Bk ( x )
Sm: set of items numbered 1 to m B(m,w): best solution in Sm with weight exactly equal to w
u
{
}
≤ min Bk ( f (x, u )) + l (x, u ) . u
(10)
B. Load Constraints Apart from fitting the above-mentioned formulation rules, the proposed algorithm must also satisfy the loads constraints. Due to the characteristics of ACLs, the load demand of ACL will be increased due to the energy payback phenomenon. In this paper, the energy payback is expressed as follows [9]:
In particular, there is a lower bound in (10) implies that B is a Lyapunov function for the closed-loop system [9]. Usually l and l are chosen to satisfy l ( x, m ) ≤ l (x, m ) ≤ l (x, m ) , for example
l ( x, m ) = λ l ( x, m ), λ ≥ 1 ,
(11)
PPB (i ) = 0.6 × PLC (i − 1) + 0.3 × PLC (i − 2) + 0.1 × PLC (i − 3) .
l (x, m ) = λ l ( x, m ), λ ≤ 1.
(12)
(5)
Once the load recovery demand increase caused by the energy payback is calculated, the load demand in period i after control must be modified as follows: P(i ) = P' (i ) − PLC (i ) + PPB (i ) .
With this relaxation of Bellman’s equation, we can search for a solution B(x) which is more easily parameterized than optimal B*(x). From this, a simplified Bk (x) which satisfies
B k ( x ) ≤ Bk ( x ) ≤ B k ( x )
(6)
(13)
is calculated. This satisfies
Where P(i): modified load demand in period i P’(i): forecasted load demand in period i PLC (i ) : amount of load reduced by control in period i
k
mink
{u (m )}m= 0
The load demand control can be stated as follows: N
Minimize P (i ) = Min ∑ (P ' (i ) − PLC (i ) + PPB (i )) ,
(7)
i =1
subject to 0 ≤ PLC (i ) ≤ Pmax , for 1 ≤ i ≤ 96.
III. RELAXED DYNAMIC PROGRAMMING The idea of RDP was first proposed by B. Lincoln and A. Rantzer of LTH, Lund University, Sweden in 2003 [10-13]. The principle is shortly described in the following. The optimal value function is characterized by the “Bellman equation” as follows [14]:
k
∑ l (x, u ) ≤ Bk (x ) ≤ {u min ∑ l ( x, u ) , ( m )}k
m =0
m =0
(14)
m =0
The λ ’s (and the l’s) are chosen as a trade off between complexity (time and memory) and accuracy. If λ and λ are close to 1, then the iterative condition (13) becomes close to ordinary value iteration (9), which gives high accuracy and high complexity. On the other hand, if the fraction λ / λ is very big, then the accuracy drops, but (13) can be satisfied with less complex computations. Note that if l is chosen as in (11) and (12), then the relative error in the value function defined by λ and λ is independent of the number of iterations [10-13].
A. RDP solution methodology The LCS period is first divided into a number of intervals, each of which is defined as a stage in the RDP. In each stage, a * * (8) B (x ) = min B ( f (x, u )) + l (x, u ) , B (0 ) = 0. u number of state-sets are given. All the states contained in a state-set are faced with the same load levels, but those in a different state-set have distinct load levels, ranging from the A common method to find the optimal value function is value criteria λ l (upper bound) to λl (lower bound) around the iteration, i.e., to start at some initial B0 ( x) , for example B0 ≡ 0 , predicted load level to suit for the constrained uncertainties and update iteratively and to reduce the dimension curse. Fig.1 displays the search structure of the RDP with lower dimensions than the DP structure. Each state of a state-set in the current stage
{
}
651
The 14th International Conference on Intelligent System Applications to Power Systems, ISAP 2007
represents the on/off combinations of all the ACL groups, originating from the states with the maximum objective function in the state-sets of the previous stage [9, 10]. To avoid the explosion of the dimension needed, a relaxed search strategy RDP is employed. Only the states with larger objective values defined in (15) are saved in each stage, and then branch out the feasible states in the next stage. The recursive strategy of B(x) for each state is expressed as:
min{ B( f (x, u )) + λl ( x, u ) } ≤ B (x ) u
{
}
≤ min B( f (x, u )) + λ l (x, u ) . u
(15)
November 4 - 8, 2007, Kaohsiung, Taiwan652
IV. LCS IMPLEMENTATION As seen from Fig. 2, this algorithm adopts the loop-priority method as rules to execute the whole control scheme. When the load demand exceeds the limit set, the subroutine executes load shedding to reduce the peak demand; on the other hand, load restoring is enabled. Therefore, when the system starts to execute load shedding/restoring, the energy payback phenomenon is considered according to (5) to revise the previous energy demand. A subroutine automatically reviews the status in each time stage to check a suitable time for off/on transition to avoid violating the loads control constraints.
To carry out the proposed strategy, Visual C++ language is According to the optimization policy of RDP, in the last stage used to adopt as the developing tool to carry out the proposed the optimal or near optimal dispatch schedule of the ACLs can LCS [17]. The core of the scheduler is coded by the machine be obtained by backtracking the trajectory of all the states with language for implementation. Fig.3 shows a flowchart of the the maximum B(x) in each stage. (This is called value iteration) main program. The background program is operated on the demand control strategy. On the other hand, this LCS is [10, 15, 16]. regarded as a demand controller when the external control mode is disabled. And then the loops-priority method is adopted as the dispatch approach of ACL groups to restrain the power demand not to exceed in setting target. Otherwise, Bk +1 according to the planning specifications connected the communication between PC and the LCS by a RS232 serial Exact port. The MODBUS protocol format defined packages the computation Bk Bk control commands coming from the control PC. PC communication program utilized the stored results of the load control scheduler to map the ACL on/off scheduling during each stage (15 minutes) automatically. Approximated simplification
Bk
Fig. 1. RDP approximated simplification searching structure [13]
Here, the scalar λ >1 is a slack parameter that can be chosen to determine the distance to optimality. By the introduction of inequalities instead of equalities, it is in principle possible to fit a simpler, approximate cost-to-target function between the upper and lower bounds. If, in each step, the upper Bk and lower B k bounds are set as in (11) and (12) in advance, the obtained solution will satisfy
λ Bk* ( x(t k )) ≤ Bk (x(t k )) ≤ λ Bk* (x(t k )) ,
(16)
which gives a guarantee on how far the approximate solution is from the optimal solution [10]. The slack parameters were chosen as λ = 1.05 and λ = 0.9 separately based on an average on 30 evolutional testing runs in this study, mean that the approximate solution will give at almost 5% higher and 10% lower boundary than the true, optimal solution respectively.
652
Fig. 2. Flowchart of the RDP-LCS program
V. CASE STUDY To demonstrate the effectiveness of the proposed algorithm, data for a campus with 8 interruptible ACL groups are tested. Table I shows the characteristics of the interruptible
The 14th International Conference on Intelligent System Applications to Power Systems, ISAP 2007
ACL groups, and Table II shows the operation properties of the loads scheduling of the interruptible ACL groups. Fig.4 shows the model tested on-site, which demonstrated the effectiveness of the proposed algorithm; data for a campus with 8 interruptible ACL groups were tested practically. The maximum off-time allowed and the minimum start-up required were given different values among the groups. In order to improve the efficiency of program, we set each stage of the RDP structure of the ACL scheduling is 15 min and divided into 96 stages with the same condition of DP. Each stage consists of the combinations of the on-off status of ACL groups and further divided into 17 state-sets. Each state-set consists of 10 states with the same load level. It means that the states in the same state-set have the same objective value of the load error. An objective function was established to finetune the load forecasting errors and energy payback phenomenon. In each stage, the values of the objective functions for the 17 state-sets vary from 1.06 to 0.90 in decrements of 0.01 to simulate the range from upper bound λ l to lower bound λl around the predicted load level to suit for the constraints and to reduce the dimension expense. A state in each stage (170 states per stage in total) stands for the combinations of the on/off status of the interruptible ACL groups. There are 28 status combinations in each stage for the 8 interruptible ACL scheduling problems which were used in the conventional DP processing and there are 96 stages need to calculation iteratively. Simulation-executed at a Petium4(3.0GHz) computer, the programming in Visual C++ were linked with the software for LCS. The average execution time needed was less than 1s. The other testing run for conventional DP was taken 2.5s average. Moreover, we have to mention the energy saving ratio is setting at 30% by customer per day and the demand control target value is set at 480 kW and the electricity saving goal is set at 1643kWH in this case. The details are shown in Table II.
November 4 - 8, 2007, Kaohsiung, Taiwan653
TABLE II OPERATION PROPERTIES OF ON-LINE LOADS STATUS Items
Status of operation
Interruptible on-line loads
5477kWH 30％
Customer’s accepted saving rate setting Demand control target (constraint)
Under 480kW
Electricity saving goal
1643kWH
Start
Initial Setting 1. Data 2. Time 3. Demand Contract 4. Demand Target 5. each loop Priority 6. each loop Capacity 7. PT and CT gain
N Is the communication port OK? Y Degree the requisition and start to send data
Keypad input and the OLC program is enabled
Y Decoding data and writing inot DS 1644 NURAM
Is the data rignt?
N Y
Y Detect exceed 1 min?
According to the timetable to control ACL groups
Current status is over the setting target?
N N Read DS 1644 RTC Time and data, and then display
Load shedding
According to 1. Loop Priority 2. Capacity of Loop 3. the exceeding amount
Writing the current PQ value into DS 1644 NURAM Y
Time is 00,15,30,45 min?
To calculate the average of current demand again
N
Scanning the keypad
N The time interval is enough? Y
N Push button? N
The remaining capacity is enough?
Y
Y
Read the value
Determine the value
Load restoring According to 1. Loop Priority 2. Optimal capacity of Loop
Background Function (Demand Control)
Fig. 3. Flowchart of the proposed algorithm software design
TABLE I ON-LINE INTERRUPTIBLE ACL LOADS PROPERTIES Fist item Total Interrupt of Capacity payback ible load payback (kW) ratio group ratio (%) 1st (%) 40
Second Third Maximum Minimum Start-up time item of item of Off time Off time required payback payback ratio ratio 2nd(%) 3rd(%) (15min/scale)
#1
75
102
34
28
5
2
#2
65
103
45
36
22
4
2
5
#3
60
99
43
33
23
5
3
3
#4
55
100
43
34
23
4
1
3
#5
40
101
40
33
28
3
2
5
#6
30
90
40
30
20
4
2
4
#7
40
95
45
35
15
6
3
2
#8
35
87
37
30
20
4
2
3
4
Fig. 4. On-site testing scheme
653
N
Y
The 14th International Conference on Intelligent System Applications to Power Systems, ISAP 2007
A. Numerical results Table III lists the on-off status of each ACL unit at time points throughout the day by using different colors and symbols. The results show that the optimum control scheme achieves better energy savings than each of the regular control modes under the same operating conditions. Details of the benefits are shown in Table IV, which demonstrate the results indeed achieve the optimal goal of customers’ satisfaction and system security. Fig. 5 and Fig. 6 show the load patterns for DP and RDP control scheduling schemes for comparison. Observing the results reveal that, among the studied case, the performance of the proposed RDP scheduling is achieved almost the same as the optimal solution of DP did but reflecting in a trade-off between the memory and computational time consumption. They are the first concerned items on the on-line issues.
November 4 - 8, 2007, Kaohsiung, Taiwan654
Darily load pattern
DP control scheduling
Energy payback
Demand constraint(480KW)
600
Electricity requirement (kW)
500
400
300
200
100
00 :0 0 01 :0 0 02 :0 0 03 :0 0 04 :0 0 05 :0 0 06 :0 0 07 :0 0 08 :0 0 09 :0 0 10 :0 0 11 :0 0 12 :0 0 13 :0 0 14 :0 0 15 :0 0 16 :0 0 17 :0 0 18 :0 0 19 :0 0 20 :0 0 21 :0 0 22 :0 0 23 :0 0
0
Time
Fig. 5. Load patterns of DP scheduling
Darily load pattern
RDP control scheduling
Energy payback
Demand constraint(480KW)
600
TABLE III 500
#1 #2 #3 #4 #5 #6 #7 #8 Time #1 #2 #3 #4 #5 #6 #7 #8 * 12:00 * * * * * * 12:15 * * * * * 12:30 * * * * 12:45 * * * * 13:00 Δ * * * * * 13:15 Δ * * * * * 13:30 Δ * * * * * * 13:45 Δ * * * * * * 14:00 Δ * * * * * * * * 14:15 Δ Δ * * * * * * * 14:30 Δ * * * * * * * * 14:45 Δ * * * * * * * 15:00 Δ * * * * * * 15:15 * * * * * * * 15:30 ○ * * * * * * 15:45 ○ * * * * * 16:00 ○ * * * * 16:15 ○ * * * * 16:30 ○ * * * * 16:45 * * * * * 17:00 * * * 17:15 * * * 17:30 * * * 17:45 * * * 18:00 * * * 18:15 * * * 18:30 * * * 18:45 * * * * * * 19:00 * * * * * * * 19:15 * * * * * * 19:30 ○ * * * * * * 19:45 ○ * * ○ * * * * 20:00 ○ * * ○ ○ * * * 20:15 ○ * ○ ○ * * * 20:30 * * ○ ○ * * * 20:45 * * * ○ ○ ○ * * * 21:00 * * * * * ○ * * * 21:15 * * * * * ○ * * * 21:30 * * * * * * * * * 21:45 * * * * * * * * * * 22:00 * * * ○ * * * * * * 22:15 * * * ○ ○ * * * * * 22:30 * * * ○ ○ * * * * * 22:45 * * ○ ○ * * * * 23:00 * ○ * * * * 23:15 * * * * * * 23:30 * * * * * * 23:45 *
*：On-status
space：Off-status
∆：Demand control
400
300
200
100
0 00 :0 0 01 :0 0 02 :0 0 03 :0 0 04 :0 0 05 :0 0 06 :0 0 07 :0 0 08 :0 0 09 :0 0 10 :0 0 11 :0 0 12 :0 0 13 :0 0 14 :0 0 15 :0 0 16 :0 0 17 :0 0 18 :0 0 19 :0 0 20 :0 0 21 :0 0 22 :0 0 23 :0 0
Time 00:00 00:15 00:30 00:45 01:00 01:15 01:30 01:45 02:00 02:15 02:30 02:45 03:00 03:15 03:30 03:45 04:00 04:15 04:30 04:45 05:00 05:15 05:30 05:45 06:00 06:15 06:30 06:45 07:00 07:15 07:30 07:45 08:00 08:15 08:30 08:45 09:00 09:15 09:30 09:45 10:00 10:15 10:30 10:45 11:00 11:15 11:30 11:45
Electricity requirement (kW)
RDP ALGORITHM SCHEDULING RESULTS
Time
Fig. 6. Load patterns of RDP scheduling
TABLE IV RESULTS FOR RDP AND DP CASES Daily peak demand
Peak load restriction
Electricity saving capacities
Restriction (%)
(kW)
(kWH)
Demand control
2–6
50–75
952
Timer and cycling control
6–12
30–79
1643
DP load control
6–18
30–138
1643
RDP load control
6–18
30–138
1643
Control mode
VI. CONCLUSIONS An on-line scheduling problem has been formulated into a LCS by the RDP algorithm to obtain the optimal or near optimal control policy. The optimal or near optimal on-line scheduling policy has been tested in a case study involving control of 8 interruptible ACL groups practically. Field tests of controlling the ACL groups located in the campus are tested on-site to demonstrate the effectiveness of the proposed scheduling of RDP algorithm. The results show that the interruptible load scheduling can reduce the system load effectively and the load capacity reduced by the proposed load control scheduling follows very close on the trajectory of the peak load.
：Cycling control
654
The 14th International Conference on Intelligent System Applications to Power Systems, ISAP 2007
VII. References [1] [2] [3]
[4]
[5]
[6]
[7]
[8] [9]
[10] [11] [12]
[13]
[14] [15] [16] [17]
Bureau Energy, Ministry of Economic Affairs of USA, “White book”, Chapter 4, 1998, M.L. Chan, “Load Management Master Plan for Taiwan Power Company”, ML Consulting Group, 1996. Lab of load management, “The Technologic Platform of Energy Management and Service for customers”, Institute of Power Research, TPC, 2002. Y.C. Chang, H.C. Tu, “An Effective Method for Reducing Power Consumption-Optimal Chiller Load Distribution”, IEEE Proceedings, Power Control, vol. 2, pp. 1169–1172, 2002. H. Salehfar, P. J. Noll, B. J. LaMeres, M. H. Nehrir, andV. Gerez, “Fuzzy logic-based direct load control of residential electric water heaters and air conditioners recognizing customer preferences in a deregulated environment”, in IEEE/Power Eng. Soc. Summer Meeting, Edmonton, AL, Canada, pp. 1055–1060, July 1999. K.Y. Huang, “Demand Subscription Services – An Iterative Dynamic Programming for the Substation Suffering from Capacity Shortage”, IEEE Trans on Power Systems, vol.18, no.2, pp. 947–953, 2003. Y.Y. Hsu and C.C. Su, “Fuzzy Dynamic Programming: An Application to unit Commitment”, IEEE Trans. on Power Systems, vol.6, no.3, pp.1231–1237, August, 1991. C. S. Chen and J. T. Leu, “Interruptible load control for Taiwan power company”, IEEE Trans. Power Syst., vol. 5, pp. 460–465, Nov. 1990. H.-T. Yang and K.-Y. Huang, “Direct load control using fuzzy dynamic programming”, IEEE Proc.-Gener. Transm. Distrib., vol. 146, no. 3, pp. 123–130, 1999. Lincoln, B., and Rantzer, A.: “Relaxing dynamic programming”, IEEE Trans. Autom. Contr., 2006, vol. 51, no. 8, pp. 1249–1260, Aug, 2006. Rantzer, A. “A dual to Lyapunov’s stability theorem”, Syst. Contr. Lett., 2001, vol. 42, no. 3, pp. 161–168, 2001. Lincoln, B., and Rantzer, A. “Suboptimal dynamic programming with error bounds”, Proc. 41st Conference on Decision and Control, December, 2003. Anton Cervin and Peter Alriksson, “Optimal On-Line Scheduling of Multiple Control Tasks: A Case Study”, Proceedings of the 18th Euro micro Conference on Real-Time Systems (ECRTS’06) IEEE, 2006. Bellman, R.E, “Dynamic programming”, (Princeton University Press, 1957). D. P. Bertsekas, “Dynamic Programming and Optimal Control”, 2nd ed. Belmonth, MA, Athena Scientific, 2000. Rantzer, A. “A dual to Lyapunov’s stability theorem”, Syst. Contr. Lett., 2001, Vol. 42, No. 3, pp. 161–168, 2001. Robert and Sedgewick, “Algorithms in C++”, Addison-Wesley Publishing Company, Inc, 1990.
655
November 4 - 8, 2007, Kaohsiung, Taiwan655
