Characteristics of available system components on the market
1. Introduction
One of the most important problems in many industrial applications is the redundancy optimization problem. This latter is well known combinatorial optimization problem where the design goal is achieved by discrete choices made from elements available on the market. The natural objective function is to find the minimal cost configuration of a seriesparallel system under availability constraints. The system is considered to have a range of performance levels from perfect working to total failure. In this case the system is called a
A limitation can be undesirable or even unacceptable, where only identical elements are used in parallel (i.e. homogeneous system) for two reasons. First, by allowing different versions of the devices to be allocated in the same system, one can obtain a solution that provides the desired availability or reliability level with a lower cost than in the solution with identical parallel devices. Second, in practice the designer often has to include additional devices in the existing system. It may be necessary, for example, to modernize a production line system according to a new demand levels from customers or according to new reliability requirements.
1.1. Literature review
The vast majority of classical reliability or availability analysis and optimization assume that components and system are in either of
The structure function approach.
The stochastic process (mainly Markov) approach.
The MonteCarlo simulation technique.
The universal moment generating function (UMGF) approach.
In (Ushakov, Levitin and Lisnianski, 2002), a comparison between these four approaches highlights that the UGF approach is fast enough to be used in the optimization problems where the search space is sizeable.
The problem of total investmentcost minimization, subject to reliability or availability constraints, is well known as the redundancy optimization problem (ROP). The ROP is studied in many different forms as summarized in (Tillman, Hwang and Kuo, 1977), and more recently in (Kuo and Prasad, 2000). The ROP for the multistate reliability was introduced in (Ushakov, 1987). In (Lisnianski, Levitin, BenHaim and Elmakis, 1996) and (Levitin, Lisnianski, BenHaim and Elmakis, 1997), genetic algorithms were used to find the optimal or nearly optimal power system structure.
This work uses an
In this paper, we extend the work of other researchers by proposing ant colony system algorithm to solve the ROP characterised in the problem of optimization of the structure of power system where redundant elements are included in order to provide a desired level of reliability through optimal allocation of elements with different parameters (optimal structure with seriesparallel elements) in continuous production system.
The use of this algorithm is within a general framework for the comparative and structural study of metaheuristics. In a first step the application of ant colonies in its primal form is necessary and thereafter in perspective the study will be completed.
1.2. Approach and outlines
The problem formulated in this chapter lead to a complicated combinatorial optimization problem. The total number of different solution to be examined is very large, even for rather small problems. An exhaustive examination of all possible solutions is not feasible given reasonable time limitations. Because of this, the ant colony optimization (or simply ACO) approach is adapted to find optimal or nearly optimal solutions to be obtained in a short time. The newer developed metaheuristic method has the advantage to solve the ROP for MSS
During the optimization process, artificial ants will have to evaluate the availability of a given selected structure of the seriesparallel system (electrical network). To do this, a fast procedure of availability estimation is developed. This procedure is based on a modern mathematical technique: the
2. Formulation of redundancy optimization problem
2.1. Seriesparallel system with different redundant elements
Let consider a seriesparallel system containing
2.2. Availability of reparable multistate systems
The seriesparallel system is composed of a number of failure prone elements, such that the failure of some elements leads only to a degradation of the system performance. This system is considered to have a range of performance levels from perfect working to complete failure. In fact, the system failure can lead to decreased capability to accomplish a given task, but not to complete failure. An important MSS measure is related to the ability of the system to satisfy a given demand.
In electric power systems, reliability is considered as a measure of the ability of the system to meet the load demand (
For reparable MSS, a multistate steadystate availability
If the operation period
We denote by
2.3. Optimal design problem formulation
The multistate system redundancy optimization problem of electrical power system can be formulated as follows: find the minimal cost system configuration
The input of this problem is the specified availability and the outputs are the minimal investmentcost and the corresponding configuration determined. To solve this combinatorial optimization problem, it is important to have an effective and fast procedure to evaluate the availability index for a seriesparallel system of elements. Thus, a method is developed in the next section to estimate the value of
3. Multistate system availability estimation
The procedure used in this chapter is based on the universal
3.1. Definition and properties
The UMGF of a discrete random variable
where the variable
The probabilistic characteristics of the random variable
where
It can be easily shown that equations (7) – (10) meet condition
Consider single elements with total failures and each element
To evaluate the MSS availability of a seriesparallel system, two basic composition operators are introduced. These operators determine the polynomial
3.2. Composition operators
3.2.1. Properties of the operators
The essential property of the UMGF is that it allows the total UMGF for a system of elements connected in parallel or in series to be obtained using simple algebraic operations on the individual UMGF of elements. These operations may be defined according to the physical nature of the elements and their interactions. The only limitation on such an arbitrary operation is that its operator
3.2.2. Parallel elements
Let consider a system component
The
Therefore for a pair of elements connected in parallel:
Parameters
One can see that the
Given the individual UMGF of elements defined in equation (11), we have:
3.2.3. Series elements
When the elements are connected in series, the element with the least performance becomes the bottleneck of the system. This element therefore defines the total system productivity. To calculate the
so that
Applying composition operators
4. The ant colony optimization approach
The problem formulated in this chapter is a complicated combinatorial optimization problem. The total number of different solutions to be examined is very large, even for rather small problems. An exhaustive examination of the enormous number of possible solutions is not feasible given reasonable time limitations. Thus, because of the search space size of the ROP for MSS, a new metaheuristic is developed in this section. This metaheuristic consists in an adaptation of the ant colony optimization method.
4.1. The ACO principle
Recently, (Dorigo, Maniezzo and Colorni, 1996) introduced a new approach to optimization problems derived from the study of any colonies, called “Ant System”. Their system inspired by the work of real ant colonies that exhibit the highly structured behavior. Ants lay down in some quantity an aromatic substance, known as pheromone, in their way to food. An ant chooses a specific path in correlation with the intensity of the pheromone. The pheromone trail evaporates over time if no more pheromone in laid down by others ants, therefore the best paths have more intensive pheromone and higher probability to be chosen. This simple behavior explains why ants are able to adjust to changes in the environment, such as new obstacles interrupting the currently shortest path.
Artificial ants used in ant system are agents with very simple basic capabilities mimic the behavior of real ants to some extent. This approach provides algorithms called ant algorithms. The Ant System approach associates pheromone trails to features of the solutions of a combinatorial problem, which can be seen as a kind of adaptive memory of the previous solutions. Solutions are iteratively constructed in a randomized heuristic fashion biased by the pheromone trails, left by the previous ants. The pheromone trails,
Various extensions to the basic TSP algorithm were proposed, notably by (Dorigo and Gambardella, 1997a). The improvements include three main aspects: the state transition rule provides a direct way to balance between exploration of new edges and exploitation of a priori and accumulated knowledge about the problem, the global updating rule is applied only to edges which belong to the best ant tour and while ants construct solution, a local pheromone updating rule is applied. These extensions have been included in the algorithm proposed in this paper.
4.2. ACObased solution approach
In our reliability optimization problem, we have to select the best combination of parts to minimize the total cost given a reliability constraint. The parts can be chosen in any combination from the available components. Components are characterized by their reliability, capacity and cost. This problem can be represented by a graph (figure 2) in which the set of nodes comprises the set of subsystems and the set of available components (i.e. max (
In figure 2, a seriesparallel system is illustrated where the first and the second subsystem are connected respectively to their 3 and 2 available components. The nodes
and
The heuristic information used is :
The pheromone update consists of two phases: local and global updating. While building a solution of the problem, ants choose components and change the pheromone level on subsystemcomponent edges. This local trail update is introduced to avoid premature convergence and effects a temporary reduction in the quantity of pheromone for a given subsystemcomponent edge so as to discourage the next ant from choosing the same component during the same cycle. The local updating is given by:
where
After all ants have constructed a complete system, the pheromone trail is then updated at the end of a cycle (i.e. global updating), but only for the best solution found. This choice, together with the use of the pseudorandomproportional rule, is intended to make the search more directed: ants search in a neighbourhood of the best solution found up to the current iteration of the algorithm. The pheromone level is updated by applying the following global updating rule:
4.3. The algorithm
An antcycle algorithm is stated as follows. At time zero an initialization phase takes place during wish
The followings are formal description of the algorithm.
1.  Set NC:=0 (NC: cycle counter)  
For every edge (i,j) set an initial value τ_{ij}(0)= τ_{o}  
2.  For k=1 to NbAnt do  
For i=1 to NbSubSystem do  
For j=1 to MaxComponents do  
Choose a component, including blanks, according to (1) and (2).  
Local update of pheromone trail for chosen subsystem component edge (i,j) :  
End For  
End For  
3.  Calculate R_{k} (system reliability for each ant)  
Calculate the total cost for each ant TC_{k}  
Update the best found feasible solution  
4.  Global update of pheromone trail:  
For each edge (i,j)∈ best feasible solution, update the pheromone trail according to:  
End For  
5.  cycle=cycle +1  
6.  if (NC < NC_{max}) and ( not stagnation behavior)  









5. Illustrative example
The power station coal transportation system which supplies the boilers is designed with five basic components as depicted in figure.3.
The process of coal transportation is: The coal is loaded from the bin to the primary conveyor (Conveyor 1) by the primary feeder (Feeder 1). Then the coal is transported through the conveyor 1 to the Stackerreclaimer, when it is left up to the burner level. The secondary feeder (Feeder 2) loads the secondary conveyor (Conveyor 2) which supplies the burner feeding system of the boiler. Each element of the system is considered as unit with total failures.
1  1 2 3 4 5 6 7 
0.980 0.977 0.982 0.978 0.983 0.920 0.984 
0.590 0.535 0.470 0.420 0.400 0.180 0.220 
120 100 85 85 48 31 26 
2  1 2 3 4 5 
0.995 0.996 0.997 0.997 0.998 
0.205 0.189 0.091 0.056 0.042 
100 92 53 28 21 
3  1 2 3 4 
0.971 0.973 0.971 0.976 
7.525 4.720 3.590 2.420 
100 60 40 20 
4  1 2 3 4 5 6 7 8 9 
0.977 0.978 0.978 0.983 0.981 0.971 0.983 0.982 0.977 
0.180 0.160 0.150 0.121 0.102 0.096 0.071 0.049 0.044 
115 100 91 72 72 72 55 25 25 
5  1 2 3 4 
0.984 0.983 0.987 0.981 
0.986 0.825 0.490 0.475 
100 60 40 20 
100  80  50  20  
4203  788  1228  2536  
0.479  0.089  0.140  0.289 
0.975  0.9760 

0.9773  13.4440 
0.980  0.9826 

0.9812  14.9180 
0.990  0.9931 

0.9936 

Optimal availabilities obtained by Ant Algorithm were compared to availabilities given by genetic algorithm (presented by symbol A_{0} in table 3) in the reference (Levitin et al., 1997), and to those obtained by harmony search (presented by symbol A_{01} in table 3) given in (Rami et al., 2009).
For this type of problem, we define the minimal cost system configuration which provides the desired reliability level A ≥ A_{0} (where A_{0} is given in (Levitin et al, 1997) taken as reference).
We will clearly remark the improvement of the reliability of the system at price equal compared to the two other methods.
We gave more importance to the reliability of the system compared to its cost what justifies the increase in the cost compared to the reference.
The compromise of the cost/reliability was treated successfully in this work.
The objective is to select the optimal combination of elements used in seriesparallel structure of power system. This has to correspond to the minimal total cost with regard to the selected level of the system availability. The ACO allows each subsystem to contain elements with different technologies. The ACO algorithm proved very efficient in solving the ROP and better quality results in terms of structure costs and reliability levels have been achieved compared to GA (Levitin et al., 1997).


0.975  0.1  0.23  58.5 
0.980  0.0  0.12  13.3 
0.990  0.2  0.36  39.4 
From figure 4 and the table, one can observe:
ACO achieved better quality results in terms of structure cost and reliability in different reliability levels (figure 4). We remark in all case, GA performed better by achieving a less expensive configuration, however ACO algorithm achieved a near optimal configuration with a slightly higher reliability level (table 4).
We take, for example, for reference reliability level (A_{0} = 0.975, table 4), GA prove an augmentation of 0.1 percent compared to 0.23 percent given by ACO this for a difference in rate Costreliability of 58.3%. It is noticed, according to figure 4, that ACO tends, at equal price, to increase the reliability of the system.
6. Conclusion
A new algorithm for choosing an optimal seriesparallel power structure configuration is proposed which minimizes total investment cost subject to availability constraints. This algorithm seeks and selects devices among a list of available products according to their availability, nominal capacity (performance) and cost. Also defines the number and the kind of parallel machines in each subsystem. The proposed method allows a practical way to solve wide instances of structure optimization problem of multistate power systems without limitation on the diversity of versions of machines put in parallel. A combination is used in this algorithm is based on the universal moment generating function and an ant colony optimization algorithm.
References
 1.
AitKadi and Nourelfath 2001 Availability optimization of faulttolerant systems.International Conference on Industrial Engineering and Production Management (IEPM’2001) , Québec20 23  2.
Bauer Bullnheimer, Hartl and Strauss, (2000 Minimizing Total Tardiness on a Single machine using Ant Colony Optimization. Central European Journal of Operations research,8 2  3.
Bullnheimer Hartl and Strauss, (1997 Applying the Ant System to the vehicle Routing problem.2nd Metaheuristics International Conference (MIC97), SophiaAntipolis, France,21 24  4.
Billinton and Allan 1990 Reliability evaluation of power systems.Pitman .  5.
Chern 1992 On the Computational Complexity of Reliability redundancy Allocation in a Series System. Operations Research Letters,11  6.
Costa and Hertz 1997 Ants Can Colour Graphs. Journal of the Operational Research Society,48  7.
Dallery and Gershwin 1992 Manufacturing Flow Line Systems: A Review of Models and Analytical Results.Queueing Systems theory and Applications , Special Issue on Queueing Models of Manufacturing Systems,12 12 3 94  8.
Den Besto Stützle and Dorigo, (2000 Ant Colony Optimization fort he Total Weighted tardiness Problem. Proceeding of the 6^{th} International Conference on parallel problem Solving from nature (PPSNVI), LNCS 1917, Berlin,611 620  9.
Di Caro and Dorigo 1998 Mobile Agents for Adaptive Routing.Proceedings for the 31st Hawaii International Conference On System Sciences , Big Island of Hawaii,74 83  10.
Dorigo Maniezzo and Colorni, (1996 The Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man and Cybernetics Part B,26 1 1 13  11.
Dorigo and Gambardella 1997a Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem”, IEEE Transactions on Evolutionary computation,1 1 53 66  12.
Dorigo and Gambardella 1997b Dorigo, M. and L. M. Gambardella. Ant Colonies for the Travelling Salesman Problem. Bio Systems,43  13.
Kuo and Prasad 2000 An Annotated Overview of Systemreliability Optimization. IEEE Transactions on Reliability,49 2  14.
Levitin and Lisnianski 2001 A new approach to solving problems of multistate system reliability optimization.Quality and Reliability Engineering International ,47 2 93 104  15.
Levitin Lisnianski, BenHaim and Elmakis, (1997 Structure optimization of power system with different redundant elements.Electric Power Systems Research ,43 1 19 27  16.
(Levitin Lisnianski, BenHaim and Elmakis, (1998 Redundancy optimization for seriesparallel multistate systems.IEEE Transactions on Reliability 47 2 165 172  17.
Liang and Smith 2001 An Ant Colony Approach to Redundancy Allocation. Submitted toIEEE Transactions on Reliability .  18.
Lisnianski Levitin, BenHaim and Elmakis, (1996 Power system structure optimization subject to reliability constraints.Electric Power Systems Research ,39 2 145 152  19.
Maniezzo and Colorni 1999 The Ant System Applied to the Quadratic Assignment Problem. IEEE Transactions on Knowledge and data Engineering,11 5  20.
Murchland 1975 Fundamental concepts and relations for reliability analysis of multistate systems.Reliability and Fault Tree Analysis , ed. R. Barlow, J. Fussell, N. Singpurwalla. SIAM, Philadelphia.  21.
AïtKadi Daoud, Efficiently solving the redundancy allocation problem by using ant colony optimization and the extended great deluge algorithm, International Conference on Probabilistic Safety Assessment and Management (PSAM) and ESREL, New Orleans, USA, May 14_19,Nahas N Nourelfath M 2006  22.
Nourefath AitKadi and Soro, (2002 Optimal design of reconfigurable manufacturing systems.IEEE International Conference on Systems, Man and Cybernetics (SMC’02) , Tunisia.  23.
Rami Zeblah and Massim, (2009 Cost optimization of power system structure subject to reliability constraints using harmony search”, PRZEGLĄD ELEKTROTECHNICZNY (Electrical Review), R. 85 NR 4/2009.  24.
Ross 1993 Introduction to probability models.Academic press .  25.
Schoofs and Naudts 2000 Schoofs, L. and B. Naudts, “Ant Colonies are Good at Solving Contraint Satisfaction Problem,” Proceeding of the 2000 Congress on Evolutionary Computation, San Diego, CA, July2000 1190 1195  26.
Tillman Hwang and Kuo, (1977 Tillman, F. A., C. L. Hwang, and W. Kuo, “Optimization Techniques for System Reliability with Redundancy A review,” IEEE Transactions on Reliability,R26 3  27.
Ushakov Levitin and Lisnianski, (2002 Multistate system reliability:from theory to practice.Proc. of 3 Int. Conf. on mathematical methods in reliability, MMR 2002 , Trondheim, Norway,635 638  28.
Ushakov 1987 optimal standby problems and a universal generating function.Sov. J. Computing System Science ,25 N 4,79 82  29.
Ushakov 1986 Universal generating function.Sov. J. Computing System Science ,24 N 5,118 129  30.
Wagner and Bruckstein 1999 Wagner, I. A. and A. M. Bruckstein. Hamiltonian(t)An Ant inspired heuristic for Recognizing Hamiltonian Graphs. Proceeding of the 1999 Congress on Evolutionary Compuation, Washington, D.C.,1465 1469  31.
J Ringlee (Wood A. J. & R 1970 Frequency and duration methods for power reliability calculations ‘, Part II, ‘ Demand capacity reserve model ‘,IEEE Trans. On PAS,94 375 388