Paper received: 04.04.2007 Paper accepted: 16.09.2009
Reward Level Evaluation of Parallel Systems
Vasov Ljubisa1* - Stojiljkovic Branimir1 - Mitrovic Caslav2 1 University of Belgrade, Faculty of Transport and Traffic Engineering, Serbia 2 University of Belgrade, Faculty of Mechanical Engineering, Serbia
In the presented model of the utilization process ofparallel systems, the inherent characteristics of system reliability and maintainability as well as repair shop capacity are included. For the system required to perform a desired function and produce certain yield an achieved reward level is proposed as a measure of the utilization process quality by introducing a referent reward concept. System modeling is accomplished by applying Markov Techniques, and several elements are incorporated: failure and repair rates as well as repair shop capacity. By getting closed-form mathematical expressions for system state probabilities and the achieved reward level, an investigation of reliability, maintainability and repair shop capacity on the achieved reward level and system availability is done. © 2009 Journal of Mechanical Engineering. All rights reserved. Keywords: reward level, parallel system, availability, Markov model
0 INTRODUCTION
In production, power supply, manufacturing and processing there are plenty of operations that involve the use of systems composed of components or subsystems which are mutually independent in accomplishing the same function. Each of these components participates in the overall output result with their own characteristics and in case several components fail, the entire system continues to function. These systems can be treated as parallel systems and are usually considered as 1-out-of-n:G systems, i.e. the entire system continues to function as long as at least one of its n components (units) is working.
However, in this case failures of components reduce a system capability and the application of classical parallel reliability models for overall output result evaluation is limited. Considering a stochastic nature of system state change process, modeling and evaluation of such a system can be more appropriately achieved by the application of Markov Techniques [1]. Besides, an extension of continuous time Markov chains with reward model results in very useful tools for system performance analysis [2].
In this paper, an application of reward model for overall system output result evaluation is shown. By introducing a referent reward concept, measures of instantaneous and achieved reward level are proposed. For a system in continuous operation process, an analysis of the influence of reliability and maintainability as well
as repair shop capacity on reward level and availability is done.
1 REWARD MODEL
All technical systems can fulfill their purpose only when engaged in an utilization process, which involves several different processes like operation process and maintenance process. During the operation process, a system performs a desired function and produces certain yield and gain, and during the maintenance process system functionability is maintained/restored [3]. According to its specific purpose the result of the system operation process can be expressed by various physical measures and many other operational characteristics.
Most often, these measures express system performances, which depend on system state. In other words, each system state has a certain performance level expressed by an appropriate reward rate. It can be interpreted as the rate at which reward is accumulated during the sojourn time of the system in the given state. The set of rewards associated with the individual system states compose the reward structure. There are a few different ways of assigning rewards in the reward structure. Rewards can be applied for the analysis of dependability in which case rewards are 0 or 1 depending on the availability of the overall system. Moreover, the rewards can enable a mixed evaluation of performance and dependability, and generally speaking the reward
*Corr. Author's Address: University of Belgrade, Faculty of Transport and Traffic Engineering, Vojvode Stepe 305, 11000 Belgrade, Serbia, lj.vasov@sf.bg.ac.rs
function is intended to be a measure of performance per unit time [2].
By accepting a concept of referent reward as the criteria of system utilization process quality in the following achieved reward level f(t) is interpreted as the ratio between the accumulated reward &(t) and referent reward &0(t) after operating time interval (0,t) in the utilization process:
f (t) = (1)
Similarly, the instantaneous reward level cp(t) is regarded as the ratio between the instantaneous reward rate <j)(t) and the referent reward rate <0(t) in the given time instant:
<(t)
cp(t) =
&(t)
(2)
According to the interpretation of the reward rate as the rate of reward accumulation in the given time instant accumulated and referent rewards can be expressed by:
t t 0(t) = <)dt, and 0o(t) = \<(t)dt. (3)
0 0
In other words, the achieved reward level (1) can be presented as the ratio between areas of regions under the curves of <(t) and <0(t) in the given operating time interval, and treated as overall measure of goodness of the system utilization process in relation to the accepted referent reward.
The introduction of the referent reward concept is directly associated with the selection of criteria of system utilization process quality. One of plausible criteria is the assumption perfect system, and the acceptance of the perfect system as a criterion is present in some theoretical considerations of the system effectiveness [4] to [6]. The assumption of the perfect system implies a system with perfect components in terms of absolute reliability and fault free operation.
1.1 Systems with a Discrete State Space
In general, the system state depends on its component states and the system structure. By assuming that system components in relation to their ability to perform the required function with specified performances can only have one of two
possible states, then the state of i-th component can be defined by binary variable xi as: i - th component is able to performs its function (Up state) i - th component is not able to	(4)
performs its function (Down state).
1,
0,
Similarly, the state of system with n components is described by the so called structural function Z:
Z =
1,
0,
system is able to
performs its function (Up state)
system is not able to
performs its function (Down state).
(5)
As the system state is thoroughly defined by components states in the system structure, then:
2 = ^ (x) ,	(6)
where x = [x1,x2,...,xn] is the vector of the
system state, with 2n possible values. In a theoretical consideration of perfect system, binary variable for i-th component has constant value xt = 1 for (i = 1,2,...,«) and the structural function of the system state is always Z (x) = 1.
The structural function of the system state depends on the system structure, links between components and components reliability. For a parallel system it can be written:
Z (x ) = 1 -n (! - x )•
(7)
Parallel systems are usually considered as a 1-out-of-n: G systems, i.e. overall system continues to function as long as at least one of its n components is in Up state. However, component failures lead to a deterioration of system capability and reduction of the output result, and for system performances an analysis is necessary to include reward level evaluation.
As the system is composed of n mutually independent components and as i-th component participates in the overall result by its component reward rate ri(t) and its state by variable x, the instantaneous reward rate <(t) and the referent reward rate <0(t) of the entire system are:
n	n
<(t) = Xr (t) x , and <o(t) = Er (t). (8)
i=i
i=i
i=1
As the system is composed of n identical components (homogeneous system) and components reward rates are time independent and equal: r^(t) = r2(t) =... = rn(t) = r, then:
n
<(t) = ^r (t) xt = r ■ k , and
'=' n	(9)
<o(t) = Er(t) = r ■ n ,
i= 1
where k is number of components in Up state in the given time instant.
Based on given relations (2) and (9) the instantaneous reward level of the system is: cp(t) = k/n. In other words, for previous assumptions it can be concluded that, in simple case, the instantaneous reward level of the entire system depends mainly on the number of components in Up state. However, for an achieved reward level f(t) it is necessary to evaluate an accumulated reward during the operating time with certain value of instantaneous reward level.
Thus, below the next assumption is introduced: Up time of i-th component; when the given component is able to perform the desired function, it is also its operating time. In other words, the entire system is in a continuous operation process, and there is plenty of systems with a similar demand in manufacturing, power supply, processing and transportation.
1.2 Systems in a Continuous Operation Process
As previously shown, the accumulated reward for a system in continuous operation depends on the number of components in Up state k, which can be presented by a discrete stochastic process. Thus, the components reward rates ri(t) and the instantaneous reward rate <(t) of system can also be presented as a discrete stochastic process (Figure 1). For further analysis, different fixed rewards are associated with each system state, and they are assigned at the moments of the system state transition's occurrence.
Thereby, the number of components in Up state determines the system state. The system state space is limited by the system capacity in reference to the number of components n and during the utilization process the system can reach one of the (n+1) possible states. In other words, j-th state of system for (j = 0, 1, 2,..., n) is determined by the number of components in Up state kj or more exactly: kj = j.
ri(t)U I—I_I—I I—I ,
t
r2(t)^ n j-1 ^
t
I I_1=1_I U
t
r/t)*_,	,_„
I-1_I	" .
t
t
Fig. 1. Sample paths of reward functions for a system of n = 4 components
In this case, for homogeneous systems component reward rates are r1(t) = r2(t) = . = rn(t) = r and the instantaneous reward level of the system in the given time instant for j-th state p is:
Pj = j/n .	(10)
It is evident that instantaneous reward level can reach the value Pj = 1, in the time instant when all the components are in Up state, i.e. the system in continuous operation process is in n-th state, but with restrictions of previously accepted assumptions.
According to the described discrete process and the path of reward functions, the accumulated reward &(t) and the referent reward &o(t) in operating time interval (0,t), can be expressed by relations:
0(t) = ^kjtj ■ tj , and
j=0 j=0
j	n j	(11)
®0(t) = xn ■ tj = n ■ t,
j=0
where tj is sojourn time of system in the j-th state in the given operating time interval (0,t).
Thus, the achieved reward level f(t) in the given interval (0,t) according to (1) and (11), is:
f (t ) =
S j • tj
j=0
1
n • t
The limiting value of the achieved reward level for the steady state condition for the described utilization process by (10) and (12) can be expressed by the weighted sum of state probabilities p.
f = lim f (t) = J Vj • pj .
j=0
It should be noted that the obtained expression for the limiting value of the achieved reward level (13) corresponds to relation (14) of effectiveness E for some class of technical system [7].
E = S ^ • ps
where es is the conditional indicator of effectiveness for s-th system state, ps is probability of s-th system state and S is state space.
For homogeneous systems, the instantaneous reward level (10) can be treated as the relative number of components in Up state that is determined by a transition process of system states as a discrete stochastic process with continuous time. Despite the introduced simplifications, this number involves many factors of the utilization process, and some of the most important are failure rate A and repair rate ^ as parameters of system reliability and maintainability.
Certainly, a major problem in reward level calculation by using the previous equation is determination of the system state probabilities, based on reliability and maintainability parameters. In such cases, the system modeling
and reward level evaluation can be achieved by
(12)	applying Markov Techniques.
2 MARKOV MODEL DEVELOPMENT
By defining the system state space and knowing the characteristics of transitions between system states, a model of system utilization process with state transition diagram can be
(13)	formed. Below, a homogeneous system with n components in a continuous operation is considered and for the purpose of model development, some assumptions are introduced.
Assumptions:
1)	Failure rates 2 and repair rates / of system components are mutually equal: 2 = 22 = ... = 2n = 2 and / = /2 = ■■ = / = /
2)	Repair shop capacity, i.e. number of service channels m is: 1 < m < n .
3)	After component failure, if m<n and there is free service channels, repair of component starts immediately. Else, if all of m service channels are busy, component waits for repair.
4)	After repair, component starts operation immediately.
Based on the previous assumptions, state transition diagram is formed (Figure 2).
According to the state transition diagram, linear equations that represent system steady state condition (i.e. balance equations) for t^<x, 2 = const and / = const, can be written as:
A) (j+1)2 pj+1 - [(n - j)/+jx\ ■ pj + (n - j +1)/Pj-1 = 0 for n > j > n - m , and
(14)
B) ( j +1)1 • Pj+i - (mp + j!) • pj + mju • pj-1 = 0 for n - m > j > 0.
n1
u
(n-1)1	(n-2)1 (j+1)!
n-1
2p
3p
j! (n-m+1)! (n-m)X
(n-j)u (n-j+1)u mp
mp
(j+1)1
mp
j1
1
mp
mp
Fig. 2. System state transition diagram
S
A) Closed-form analytic expression of system state probability pj for n -1 > j > n - m +1:
Let Xj = (j + 1)2 ■ pj+i - (n - j)/ ■ Pj. As Xj = x-i
and xn-1 = 0 then xj = 0 . Thus:
j +1 2 j +1 2 j + 2 2 Pj =A—~: Pj+1	Pj+2 =
" - J M
=••• = a n
n - J M " - J -1 M
k 2
k=j+i n - (k -1) m 2
Let p = — . After some algebraic manipulations:
M
Pi = PnP
(15)
B) Closed-form analytic expression of system state probability Pj for n - m > j > 0:
Let yj = (j +1)2 ■ p +1 - m/■ p , that satisfies interval n - m > j > 0 . Similarly to the previous, as ys = ytx and y0 = 0 then y = 0 . Thus:
j +1 2 j +1 2 j + 2 2
Pj = ----Pj+1 = --------Pj+2 =
m /	m / m /
= = n1 k 2	.
= K = pn-m+1 II .
k=jj+1 m /
After some algebraic manipulations: n-, 1 n!
Pi = PnP
m
m! J!
By using ^ p = 1, according to (15) and
j =0
(16) probability pn is expressed (Table 1).
According to (16) closed-form analytical relations of system states probabilities are expressed for m = 1, as the first special case of repair shop capacity (Table 1). Also, relation (15) satisfies m = n, as a second special case of repair shop capacity (Table 1).
Thereby, based on relation (13) and according to expressions of system state probabilities (Table 1), relations of the achieved reward level for a steady state condition are shown (Table 2).
It should also be noted that the acquired equation of the achieved reward level f for the case of m = n (Table 2), is the same as the well known equation of limiting or steady state availability. However, it is important to emphasize that this equation for the proposed model does not present availability but a reward level for a particular case of continuous operation of a system with previous assumptions.
Table 1. Closed-form analytic expressions for system states probabilities
		m = 1	1 < m < n	m = n
Pj	n-1 > J > n-m+1	■ n! J !	PP" - - (n)	P'P"- J (" J
	n-m > J > 0		■ 1 n! P P-- F"y m"-m-J m!J!	
		1	1	1
	Pn	■ n! 1 + gp" - J =0 J !	V n- J 1 n! n- J f n) + ' ' P "-m- J i • i + ' ' P \ • \ J=0 m J m! j ! j^ j J	■+1 j f n)
Table 2. Closed-form analytical expressions for achieved reward level f
f		
m = 1	1 < m < n	m = n
1 + Xpn-J (n - 1)! £ (J -1)!	1 + g: 1 1 (n-1)! + g fn -1) m"-m - Jm !(J -1)! j=IJ -1)	1+rjC-:) .
1 + g P n- J% J=0 J !	1+gpPrJ "1m-J 1! n! + g p"jfn) P, m J m! j! j=tm+x \ J J	•+§! 1+P
Moreover, this signifies the importance of availability as a measure, which quantitatively summarizes reliability as well as maintainability and indicates the relation that exists between availability and the achieved reward level.
3 A NUMERICAL EXAMPLE
According to previous relations, the paths of reward level f function and system availability A function in dependence of the ratio p between failure rate 2 and repair rate / (i.e. p = A//), as well as repair shop capacity m, are established. Considering availability as the probability that a system is operational (Up and running) at any random time t, for a considered 1-out-of-n:G system and system state space, steady state availability is given by:
A = 1 - p..	(17)
where p0 is the probability of outage state, i.e. all of n system components are in Down state.
Based on the expressions for states probabilities (Table 1), the achieved reward level (Table 2) and the relation (17), a numerical example is given for a system with n = 21 components and repair shop capacity 1 < m < 21, for different values of parameter p (Figure 3).
In general, it can be noted that the reward level as well as system availability rise with a decrease of ratio p, i.e. with the decrease of failure rate and/or increase of repair rate. Besides, the reward level and availability also rise with an increase of repair shop capacity, as result of repair time reducing and increasing of the number of operating system components.
The upper limit of the reward level can be achieved for the case of m = n, i.e. the repair shop capacity is equal to the number of system components, and in this case the reward level depends only on parameter p.
However, for a system of a certain size with given reliability and maintainability characteristics, expanding repair shop capacity is reasonable only if the reward level is achieved below enough its upper limit. In other words, for a given number of system components n and ratio p, with the increase of repair shop capacity m, the growth of the achieved reward level depends on the slope of reward level function. Thus, after some value of m, the reward level reaches a nearly constant value close to its upper limit, and further expanding or repair shop capacity is not reasonable.
Furthermore, availability is always higher than the reward level as according to (17) it excludes only the probability of outage state which may result in a false conclusion about system effectiveness. Regarded by state space diagram (Figure 2), by transition to lower states (n-1),(n-2),...,2,1 system retains its ability to perform the desired function, but with a gradual reduction of achieved yield and gain. This problem can be partially resolved by increasing the size of the system, i.e. increasing the number of system components, whereby the required bulk of yield is provided. Nevertheless, this approach leads to a significant reduction of the achieved reward level and surely upgrading of system reliability, maintainability and utilization process quality is preferable.
i
f
0.8 0.6 0.4 0.2
p = 0.1
p = 0.3 p = 0.5 p = 0.7 p= 1.0
f,A 0.8
0.6
0.4
0.2
0 3 6 9 12 15 18 21
0 0.01
	\ " ''^„^m = 21
	' ^ m = 7
m = 1 \/	
m = 3 \	V \ \
f - \	\ \ % \ ■
A ........... ^	
0.1
10
P 100
Fig. 3. Paths of reward level f and system availability A
4 CONCLUSIONS
5 REFERENCES
The benefit that can be obtained from this model is the ability to research effects of different parameters and demands on system output characteristics. The introduction of the referent reward concept is directly associated with the selection of criteria of system utilization process quality, and the proposed model brings a possibility of applying different criteria of reward level estimation and various policy in the system utilization process.
In this paper, the reward level of systems in continuous operation process is considered. However, it is evident that in many cases an achieved reward is proportional to time during which the given system performs a stream of operational tasks, and usually these tasks arrive according to some random processes. Thus, in this case, when considering the utilization process and the achieved reward level, it is necessary to include the interaction between system reliability and maintainability as well as the input and output flow of operational tasks.
Certainly a more complete model should include additional parameters as operational task arrival rate, duration of operational tasks, time depended reward rate, different types of tasks, more complex system behaviors, etc. However, an inclusion of a large number of parameters might cause difficulty in getting closed-form mathematical expressions as well as high computational complexity, but a simulation technique can be used to obtain a solution. Thereby, further research will be related to development of a more generalized and complete simulation model of the described utilization process.
[1]	Sharma, T., Bazovsky, I. (1993) Reliability analysis of large system by Markov techniques, Proceedings Annual Reliability and Maintainability Symposium, IEEE 1993, p. 260-267, Chicago, May, 3-6, 1993, ISBN 0-7803-1281-3.
[2]	Donatiello, L., Balakrishna, I. (1987) Analysis of a composite performance reliability measure for fault-tolerant systems, Journal of the Association for Computing Machinery, vol. 34, no. I, p. 179-199.
[3]	Kneževic, J. (1998) System effectiveness, Communications in DQM, vol. 1, no. 1, p. 30-36.
[4]	Kang W.L. (2000) Stochastic Models for Random-Request Availability, IEEE Transactions on Reliability, vol. 49, no. 1, p. 80-84.
[5]	Chervony, A.A, Chobanyan, V.A., Shvarts, V.A., Terekhov, Kh.E., Frolov, A.I., (1976) Methods for determination and control of the reliability of large systems, Energiya, Moscow, (in Russian).
[6]	Nechiporenko, V.I., (1977) Structural analysis of systems (effectiveness and reliability), Sovetskoe radio, Moscow, (in Russian).
[7]	Kozlov, B.A., Ushakov, I.A., (1975) Handbook for calculating the reliability of radio-electronic and automation devices, Sovetskoe radio, Moscow, (in Russian).
[8]	Veber B., Nagode M., Fajdiga M. (2007) Prediction of the cumulative number of failures for a repairable system based on past performance, Strojniški vestnik - Journal of Mechanical Engineering, vol. 53, no. 10, p. 621-634.