NODAL-BASED ANT COLONY OPTIMIZATION FOR PROFIT MAXIMIZATION OF GENCOS IN A DISTRIBUTED CLUSTER MODEL

Abstract

In the deregulated electricity market, each generating company has to maximize its own profit by committing to a suitable generation schedule termed profit-based unit commitment (PBUC). This article proposes a nodal ant colony optimization (NACO) solution to the PBUC problem. This method has better convergence characteristics in obtaining an optimum solution. The proposed approach uses a cluster of computers performing parallel operations in a distributed environment for obtaining the PBUC solution. The time complexity and the solution quality, with respect to the number of processors in the cluster, are thoroughly tested. The method has been applied to systems of up to 120 units, and the results show that the proposed NACO in a distributed cluster consistently outperforms the other methods that are available in the literature.

INTRODUCTION

In the regulated electricity markets, unit commitment (UC) must satisfy load demand at the least operational cost while satisfying prevailing constraints such as minimum up/down time, ramping up/down, and minimum/maximum generating capacity. The UC has the potential to save millions of dollars per year in terms of economic operation (Wood and Wollenberg 1996). The need for practical, cost-effective UC solutions led to the development of various UC algorithms that produce suboptimal but efficient scheduling for real-sized power systems comprising hundreds of generators (Sheblé and Fahd 1994). Traditionally, UC problems have been solved successfully by many conventional and intelligent heuristic methods, such as integer programming (Dillon et al. 1978), dynamic programming (Pang, Sheblé, and Albuyeh 1981; van den Bosch and Honderd 1985; Snyder, Powell, and Rayburn 1987), branch and bound method (Cohen and Yoshimura 1983), combination of Lagrangian relaxation and linear programming (Tong and Shahidehpour 1989), artificial neural networks (Sasaki, Watanabe, and Yokoyama 1992), genetic algorithms (GA) (Kazarlis, Bakirtzis, and Petridis 1996; Maifeld and Sheblé 1996; Damousis, Bakirtzis, and Dokopoulos 2004; Senjyu et al. 2005), and hybrid techniques (Wong and Wong 1995; Aldridge et al. 2001; El Desouky et al. 2001) and an ant colony approach (Simon, Padhy, and Anand 2006).

In a deregulated market, the generation companies (GENCOs) operate and maintain their generating power plants independently. GENCOs solve the UC and economic dispatch (ED) problems not for minimization of total production costs as had been the case, but for maximizing their own profits; it is referred to as profit-based unit commitment (PBUC), which emphasizes the importance of the price signal. The UC used by GENCOs refers to optimizing generation scheduling in order to maximize the GENCO's profit (Shahidehpour, Yamin, and Li 2002). In this new paradigm, scheduling of units into ON/OFF will depend on the pertaining profit. The PBUC problem is a mixed integer and continuous nonlinear optimization problem, which is very complex to solve because of its enormous dimensions, nonlinearity, and large number of constraints.

A PBUC formulation using a mixed integer programming method, providing a better solution than the Lagrangian relaxation (LR) method but with increased computation time (Li and Shahidehpour 2005), is a hybrid method of LR and the evolutionary programming (EP) method that helps a GENCO to make a decision on how much power and reserve it should sell in the markets and how to schedule generators in order to receive the maximum profit (Pathom Attaviriyanupap et al. 2003). Here the authors have considered both power and reserve generation at the same time. GAs are global optimization techniques inspired by the study of genetics (Goldberg 1989; Michalewicz 1996). They can be easily implemented for the solution of hard optimization problems, and they provide great modeling flexibility. GA considers the softer demand constraints and allocates fixed and transitional costs to the scheduled hours (Richter and Sheblé 2000; Georgilakis 2009).

This article proposes a nodal ant colony optimization (NACO) model for the solution of the PBUC problem. This approach is called NACO because of the nodal representation of the search space, however, it uses the same search mechanism as ant colony optimization (ACO; Simon, Padhy, and Anand 2006). The power of the suggested ACO solution relies on the proposed variable fitness function and the problem-specific operators adopted. Additional advantages of the proposed ACO solution are flexibility in modeling the PBUC problem constraints and easy implementation for working on parallel computers.

PBUC PROBLEM FORMULATION

The price-based unit commitment problem can be stated as follows: for a GENCO with N generating units, and given a certain market price profile of energy as well as a certain demand profile (with reserves), it is required to determine the start-up/shut-down times and the power output of all the generating units at each time interval t over a specified scheduling period T, so that the generation company's total profit is maximized, subject to the unit and power balance constraints. In this article, the time interval for the considered electricity market is one hour. The market price for energy can be forecasted using time-series models (Contreras et al. 2003), wavelet transform (Yao and Song 2000), and artificial neural networks (Georgilakis 2007).

or

where PF is the total profit in ($), RV is the total revenue in ($), TC is the total operating cost in ($) for unit i at hour t, and the profit is calculated by subtracting the total production cost and start up cost during that hour from the revenue:

The start-up cost in any given hour t depends on the number of hours a unit has been OFF prior to start up. This cost is modeled by an exponential function of the form

where C _i is the production cost, which is calculated by using the equation , where the power level of i ^th generator unit at t ^th hour (MW) is P _(i,t). The commitment state of i ^th unit at t ^th hour is I _(i,t), ST _t is the startup cost in ($), t is the index for time, T is the dispatch period in hours, i is the index for generator unit, N is the total number of generating units and σ _g (t) is the forecasted market price for energy at time t. The fuel cost coefficients are a, b, and c. The combined crew start-up cost is D(i), and E(i) is the cold start-up cost of unit i. The “off” duration of i ^th generator unit till time t is X ^off (i,t). The cooling time constant of unit i is CT(i).

System Constraints

1.	Demand constraints

Here, D _t is the total system demand at time t. Demand is forecasted demand with reserves for hour t, constraints are different from traditional unit commitment problem (UCP) because the GENCO can now select to produce demand and reserve less than the forecasted level if it creates more profit.

Unit Constraints

	2. Unit power and reserve constraints where P i,min and P i,max are the minimum and maximum power output of i th generator unit (MW).
	3. Minimum Up-and-Down time constraints where X on (i,t) is the “on” duration of i th generator unit until time t, and X off (i,t) is the “off” duration of i th generator unit until time t.
	4. Unit ramp constraints where UR(i) is the ramp-up rate limit of i th generator unit and DR(i) is the ramp-down rate limit of i th generator unit.

ANT COLONY OPTIMIZATION

ACO is a random stochastic population-based heuristic algorithm on agents that simulate the natural behavior of ants developing mechanisms of cooperation and learning, which enables the exploration of the positive feedback between agents as a search mechanism.

An important and interesting behavior of ant colonies is their foraging and, in particular, how ants can find shortest paths between food sources and their nest. While walking from food sources to their nest and vice versa, ants deposit on the ground a chemical substance called a pheromone, forming in this way a pheromone trail. Ants can smell the pheromone and, when choosing their path, they tend to choose, in quasi-random fashion with probability, paths marked by strong pheromone concentrations. The pheromone trail allows the ants to find their way back to the food by their nest mates. Similarly, the construction of a solution is performed in a pseudorandom probabilistic way in ACO. Essentially, an ACO algorithm performs a loop applying two basic procedures:

1.	A procedure specifying how ants construct a solution for the problem in hand;
2.	A procedure for updating the pheromone trail.

The probability of adding a new term to the solution under construction is, in turn, a function of a problem-dependent heuristic and the amount of pheromone previously deposited in this trail. The pheromone updating is based on evaporation rate and quality of the current solution (Dorigo, Maniezzo, and Colomi 1996, Dorigo and Gambardella 1997).

NODAL ANT COLONY OPTIMIZATION

NACO is based on the ant's search on the search space that consists of a combination of binary nodes, as shown in Figure 1. Here, each node in the search space represents a small group of generating units. The status of the generating units in the group is represented as “1” for “ON” and “0” for “OFF.” For example, if one node has the status of “10,” it indicates that the first generator in the node is ON and the second one is OFF. However, in NACO-based implementation, there is no need to keep all the N generating units together in a node for checking the transitional constraints. Here, to get an optimal matrix space for the effective implementation of the ACO technique, the node that keeps all the status of the generating unit can be broken into multiples of (1 or 2 or 3 or 4…n) units. Based on statistical analysis during parameter settings, an optimal number of generating units is grouped in a node, and the matrix space (i.e.,2 ⁿ * (24* (N/n))) will be best suited for good exploration and exploitation capabilities for the ant search. In case (N/n) is not divisible to become an integer, then any of the hourly stage's nodes n can be adjusted to have proper matrix space. For example, if N = 11 and n = 2, then in any one column of the matrix space, n can be fixed as n = 3, and for other columns of the matrix space, n can be fixed as n = 2. Figure 1 represents the matrix search space of a 20-unit system for a schedule of 24 hours. Here, because N = 20 and n = 2, state represents the column matrix of the search space, and each ant visits one node from each state during its tour.

FIGURE 1 Graph structure of search space (N = 20, n = 2).

Whenever the ant selects an eligible node, it checks the nonviolation of transitional constraints from the previously selected node. It should be noted that the selected nodes for the (t + 1) ^th hour should not violate the minimum up/down constraints from t ^th hour. An ant will continuously select nodes until it reaches (24*(N/n)) ^th state and thus completes one successful tour. This process is continued until the ants are able to find the best optimal commitment for a 24-hour schedule. NACO follows the same rules framed as per basic ACO, in which both local updating and global updating are implemented (Dorigo and Gambardella 1997). Because the representation of ants visiting nodes in the search space are represented differently, the ACO model is coined as NACO.

PARALLEL APPROACH ON NACO

The procedure of the parallel approach on the NACO algorithm to solve PBUC is as follows:

	Step 1: Select the optimal number of units for the ant search space (ASS) based on statistical analysis.
	Step 2: Initialize generator and NACO parameter specifications. Specify minimum or maximum generation limits, minimum up/down time constraints and start-up cost of each unit. Specify the parameters of the NACO algorithm such as number of ants, maximum iterations, alpha, beta, initial pheromone, and evaporation factor.
	Step 3: Master node decides the sharing of ants by ants-sharing policy (ASP). Therefore, the number of ants allocated as slave processors or workers is given by where where N ants is the total number of ants and W h is the total number of workers/processors in the cluster. Master node allocates (x + 1) ants to the first hx slaves in the W h cluster(W 1...W hx ....W h ) and x ants to the remaining slaves (W hx + 1 … W h ).
	Step 4: Each worker/processor initializes its own pheromone matrix and has an individual ASS.
	Step 5: Each ant with respect to each slave processor has to start from the starting node of its search space. The transition from one node r to the next node s is carried out by a pseudorandom transition rule and also by satisfying the transitional constraints such as minimum up time and minimum down time of PBUC. The pseudorandom transition probability for the k th ant from one node r to next node s for NACO is given by “allowed k ” is the available or eligible nodes k th ant can choose as a subpath from r th node to s th node; where is the transition probability of k th ant from state r to s. The heuristic function of state (st)r to s is η rs (st). The pheromone trail intensity of state (st)r to s is τ rs (st). Where The profit is calculated based on the forecasted energy pricing given for each of the generating units grouped in each node.
	Step 6: Whenever an ant takes a subpath, pheromone updating is done locally.

Local Pheromone Trail Update

Whenever an ant moves from one node r to the next node s, an amount of pheromone 1/η _rs is deposited in the subpath (r, s) during the tour construction. The local updating is implemented by the following equation:

Step 7: Once all the ants in the cluster complete successful tours, the master compares the best tour path received from its slaves and computes the best global path obtained so far. Then the pheromone updating is done for all ASS pertaining to that individual slave processor.

Global Pheromone Trail Update

In NACO, an amount of pheromone (L _gb )⁻¹ based on the best global tour computed by the master node is deposited on the subpaths of the best global tour path of each ASS. Thus, the global update in NACO enables the ants to search nearer paths of the global best path for getting an optimum solution. The global updating is implemented by the following equation:

where

where ρ is the evaporation factor and Δτ _rs is the change in pheromone deposition.

	Step 8: Whenever a global best path is selected by the master node and if the total profit is found to be more than the maximum total profit paths computed by the master, then the present path is captured, or else the previous maximum total profit path is retained.
	Step 9: Continue Step 5 to Step 8 until the number of desired iterations is completed and the operation of program is stopped. The optimal PBUC schedule is obtained after the successful completion of all iterations.

The flowchart of the proposed method is shown in Figure 2.

FIGURE 2 Flow chart of NACO for PBUC.

DISTRIBUTED CLUSTER FORMATION

Scientific applications are still the driving force behind the development of those parallel computing technologies needed to manipulate large databases, accelerate code execution, and resolve excessive time-consuming problems (Fadlallah, Lavoie, and Dessaint 2008). In clusters, powerful low-cost workstations and/or PCs are linked through fast communication interfaces to achieve high-performance parallel computing. Workstation clusters have become an increasingly popular alternative to traditional parallel supercomputers for many workloads requiring high-performance computing. The use of parallel computing for scientific simulations has increased tremendously in the last ten years, and parallel implementations of scientific simulation codes are now in widespread use (Zhu and Fan 2008). Systems implementing shared memory provide cooperating processes with a shared memory address space that can be accessed by all processors. In shared memory systems, parallel processing occurs through the use of shared data structures, or through emulation of message-passing semantics in software. Distributed memory systems are composed of a number of interconnected computational nodes, which do not share memory but can communicate with each other through a high-performance Ethernet switch (HPES) as shown in Figure 3. Parallelism is achieved on distributed memory systems with multiple copies of the parallel program running on different nodes, sending messages to each other to coordinate computations. The cluster should perform as a parallel computing resource, achieving higher performance than possible when using workstations configured in a more standard way. The nodes in the cluster are always used in groups, not individually as in a general-purpose workstation laboratory.

FIGURE 3 Distributed network of workstations (a cluster with 20 Nodes).

Users run jobs on the cluster through job execution scripts or applications. Users should never need to log in to computer nodes. Batch queuing systems are frequently employed along with the job execution facilities included with a message passing interface (MPI) and parallel virtual machine (PVM). MPI has a much richer set of communication functions and consequently has the advantage of expected higher communication performance (Kumm and Lea 1994). PVM has the advantage of heterogeneity and fault-tolerance features. MPI supports better portability, whereas PVM supports interoperability exclusively. In this article, the authors describe the parallel computation in a clustered environment using MPI with a cluster size of 20 nodes. From this cluster any one node is taken as the master node and it will act as the cluster file server. Here W ₁ is acting as a master node.

Speedup Factor and Efficiency

To evaluate the parallel performance of the NACO algorithm, the speedup factor SW _h and efficiency EW _h of the cluster (Kumm and Lea 1994) is calculated as follows:

where W _t is the execution time of one processor and W _ht is the execution time of a cluster.

RESULTS AND DISCUSSION

The effectiveness of the proposed NACO has been tested for six problem sets comprising 20, 40, 60, 80, 100, and 120-unit systems, respectively. Initially, a base problem set of 20 units was chosen along with a 24-hour price profile for energy as well as a 24-hour profile for the forecasted demand with reserves. For the 40-unit problem, the initial 20 units are duplicated, the forecasted demand (with reserves) is multiplied by two, while the price profile remains identical. A similar approach is followed to produce the unit and demand data for the remaining problem sets. The data for the 20-unit problem set, price profile, and forecasted demand with reserves are taken from Georgilakis (2009).

Good convergence behavior can be obtained by proper setting of parameters. The guidelines for setting the parameters are given in α ≥ 0, β ≥ 0, 0 ≤ ρ < 1, C-Positive value (Dorigo, Maniezzo, and Colomi 1996). The selection of parameters α, β, ρ, number of nodes (n) and constant (C) affects directly or indirectly altering the probablistic transition rule and influences the selection of nodes and the computation. Based on the above guidelines, numerical analysis is carried out to get the best selection of parameter values. By default setting of parameters taken initially, one of the parameters is varied and the other parameters are kept constant. It has been tested for each parameter, taking several values within a boundary limit. Over 10 simulations for each setting are performed in order to achieve some statistical information about the average evolution. The range of interval considered for each parameter and the order of fixing the parameter from the default setting is α{0–5}, β{0–20}, ρ{0.1–0.9}, n{1,2,3,5,.≤N} and C{0.1–500} (Simon, Padhy, and Anand 2006). The intial pheromone trail level τ _rs between nodes is set as 0.01. The total number of ants (N _ants) is kept as 50, and the maximum number of iterations (Max iter) is 20.

The control parameters are selected based on the maximum average profit obtained out of 10 simulations (AvgP) and are shown as the bold figures in Table 1. The final combination of parameters that provided the best results are (α = 0.2, β = 12, ρ = 0.7, n = 2 and C = 100). It should be noted, once the parameters are finalized for this system, the same settings can be used even if there is a change in the forecasted load.

TABLE 1 Ant Parameter Settings for 20-Unit System

α	AvgP *10^5	β	AvgP *10^5	ρ	AvgP *10^5	n	AvgP *10^5	C	AvgP *10^5
0	9.68	0	9.68	0.1	9.70	1	9.69	0.1	9.69
0.1	9.70	1	9.63	0.3	9.71	2	9.72	1	9.71
0.2	9.72	2	9.67	0.5	9.71	4	9.70	100	9.72
0.5	9.67	4	9.65	0.7	9.72	5	9.71	500	9.70
1	9.70	7	9.70	0.9	9.68	–	–	–	–
1.5	9.69	10	9.71	–	–	–	–	–	–
2	9.68	12	9.72	–	–	–	–	–	–
5	9.65	18	9.71	–	–	–	–	–	–
–	–	20	9.68	–	–	–	–	–	–

Table 2 presents the 20-units ON/OFF schedule obtained by the NACO, and Table 3 shows the corresponding generation schedule obtained by the lambda iteration solution to the economic dispatch problem. It is concluded from Table 2 that all 20 units are ON from hour 6 to hour 18, when the market price for energy is a valuable one. Although the profit is zero during hours 1, 2, 23, and 24, because all units are OFF during these hours because of the low quoted market price.

TABLE 2 ON\OFF Status of 20-Unit System

Hour	On\Off status of Units
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	1	0	0	0	0	0	0	0	0	0	1	1	1
4	1	1	1	1	0	0	0	1	1	1	0	0	0	1	0	0	0	1	1	1
5	1	1	1	1	0	0	0	1	1	1	0	0	0	1	1	1	1	1	1	1
6	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
7	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
8	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
9	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
10	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
11	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
12	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
13	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
14	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
15	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
16	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
17	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
18	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
19	1	1	1	1	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1
20	1	1	1	1	0	0	0	1	1	1	0	0	0	1	1	1	1	1	1	1
21	1	1	1	1	0	0	0	1	1	1	0	0	0	1	1	1	1	1	1	1
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	1	1	1
23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
24	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

TABLE 3 Production (MW) Schedule for 20-Unit System

Hour	Unit's Name
	U18a	U18b	U18c	U18d	U30a	U30b	U30c	U114a	U114b	U114c	U150a	U150b	U150c	U230a	U230b	U295a	U295b	U350a	U400a	U400b
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	23	0	0	0	0	0	0	0	0	0	200	250	250
4	6	6	6	6	0	0	0	46	23	23	0	0	0	150	0	0	0	350	400	400
5	12	12	12	12	0	0	0	69	46	46	0	0	0	230	225	290	290	350	400	400
6	18	18	18	18	12	12	12	92	69	69	38	45	45	230	230	295	295	350	400	400
7	18	18	18	18	24	24	24	114	92	92	76	90	90	230	230	295	295	350	400	400
8	18	18	18	18	30	30	30	114	114	114	114	135	135	230	230	295	295	350	400	400
9	18	18	18	18	30	30	30	114	114	114	150	150	150	230	230	295	295	350	400	400
10	18	18	18	18	30	30	30	114	114	114	150	150	150	230	230	295	295	350	400	400
11	18	18	18	18	30	30	30	114	114	114	150	150	150	230	230	295	295	350	400	400
12	18	18	18	18	30	30	30	114	114	114	150	150	150	230	230	295	295	350	400	400
13	18	18	18	18	30	30	30	114	114	114	150	150	150	230	230	295	295	350	400	400
14	18	18	18	18	30	30	30	114	114	114	150	150	150	230	230	295	295	350	400	400
15	18	18	18	18	30	30	30	114	114	114	150	150	150	230	230	295	295	350	400	400
16	18	18	18	18	30	30	30	114	114	114	150	150	150	230	230	295	295	350	400	400
17	18	18	18	18	30	30	30	114	114	114	112	105	105	230	230	295	295	350	400	400
18	18	18	18	18	15	15	15	91	91	91	74	60	60	230	230	295	295	350	400	400
19	13	13	13	13	0	0	0	68	68	68	38	38	38	230	230	295	295	350	400	400
20	8	8	8	8	0	0	0	45	45	45	0	0	0	230	230	295	295	350	400	400
21	3.6	3.6	3.6	3.6	0	0	0	23	23	23	0	0	0	80	80	295	295	350	400	400
22	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	140	150	150
23	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
24	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Table 4 compares the results obtained from the NACO with GA and the Lagrangian relaxation method for the six problem sets (Georgilakis 2009). For the NACO, both the best and the worst solutions produced during the 20 runs are presented together with their difference as a percentage of the best solution. Table 4 shows that the NACO constantly outperforms the LR and GA methods, which are available in the literature, because the profit calculated even by the worst NACO solution is always higher than the profit calculated by the LR method. Moreover, the difference between the worst and the best NACO solution is very small, ranging from 0.09% to 0.38%. These very good results are attributed to the robust optimization capabilities of the NACO.

TABLE 4 Comparison of Results

	Langrangian relaxation	Genetic Algorithm			NACO
	(Georgilakis 2009)
		Total profit ($)			Total profit ($)
Units	Total profit ($)	Best	Worst	Difference (%)	Best	Worst	Difference (%)
20	972214	972214	967450	0.49	972602	968901	0.38
40	1939221	1944914	1938496	0.33	1945509	1939427	0.31
60	2903369	2918443	2912314	0.21	2918831	2914269	0.16
80	3873213	3891430	3884815	0.17	3891775	3886692	0.13
100	4838537	4864331	4857521	0.14	4864719	4859115	0.12
120	5804271	5837545	5831707	0.10	5837663	5831939	0.09

When a single processor is used, it consumes more time for execution, in other words, 1568.34 sec is taken for 120 units and 1232.25 sec for 100 units. The execution times for the 20-node clusters of 1000 and 100 units are around 132.57 sec and 108.28 sec respectively. It clearly shows the execution time decreases as the number of processors increases. Each test system has been tested for 20 trial runs and the best results are presented. Figures 4 and 5 shows the execution time achieved by a single processor and different clusters. Figure 6 shows the speedup achieved by the different clusters for the test systems. The speedup factor increases with the cluster size. The highest speedup factor reaches 11.83 for a 20-node cluster. It can be seen from Figure 7 that the performance of the workstation cluster with varying number of processors will not have much variation in their efficiencies.

FIGURE 4 Execution time chart for single processor.

FIGURE 5 Execution time chart for different clusters.

FIGURE 6 Speedup factors for different cluster.

FIGURE 7 Efficiencies for different cluster.

CONCLUSION

The proposed NACO method has been applied to systems of up to 120 units. The test results show that the proposed method constantly outperforms the Lagrangian relaxation and GA for PBUC methods for the taken systems. Moreover, the difference between the worst and the best NACO solution is very small, not more than 0.38%. The obtained results show that the proposed NACO approach is a very effective method for the solution of the PBUC problem. The proposed MPI-based parallel approach on the NACO model for PBUC is executed in a distributed environment. The approach is simple, efficient, economic, and can be extended for making smarter decisions in a large-scale power system. Simulation results obtained from the cluster demonstrate the accuracy of the proposed algorithm and its capability to greatly reduce the execution time.