Moments of Real-Time Systems with Shortage of Maintenance Teams
Edward Ianovsky*,** and Joseph Kreimer*
*Department of Industrial Engineering and Management, Ben-Gurion University of
the Negev, P.O.Box 653, Beer-Sheva 84105, Israel.
E.mail: ; Fax: 972-8-6472958.
**Rothman School of Business Administration, University of Toronto
Summary
We consider a real-time monitoring system with a large number of homogeneous servers (such as unmanned air vehicles, machine controllers, overhearing devices, etc.), several heterogeneous channels (such as surveillance regions, assembly line, , communications lines, etc.) and shortage of maintenance teams working under maximum load regime. The distinguishing feature of real-time systems is their attempt to achieve both logical and temporal correctness of operations. We show how to compute the moment generating function of these systems in a steady state, their moments and discuss the rate of convergence.
Keywords: moments, moment generating function, rate of convergence, real-time system.
1. INTRODUCTION
Real-time systems(RTS) are responsible for operations management of very sensitive structures, particularly those in which failures to satisfy timing constraints can lead to extremely serious consequences.
An operation is temporally correct if it finishes within a specified time frame. In these systems, tasks have timing constraints that must be satisfied for correct operation. Real-time applications, such as homeland security, military intelligence, avionics, and industrial process control, impose strict timing requirements.
Various RTS have been treated by different scientific communities.
Liu and Layland [22] performed combinatorial analysis for multiprogram scheduling on a single processor in a hard real-time environment. Interesting modification for dynamic priority algorithm proposed by Litoiu and Tadei [21] deals with RTS allowing fuzzy due dates.
Dhall and Liu [2] solved the problem of specifying an optimal order in which the requests of periodic real-time jobs are to be executed by a multiprocessor computing system, with the purpose to minimize the number of processors.
A number of authors dealt with real-time Flexible Manufacturing Systems (FMS): Chakravarty and Balakrishnan [1], Tawegoum et al [25], etc.
Efficient metaheuristic methods, such as Greedy Randomized Adaptive Search Procedure (Feo and Resende [3] and Feo et al. [4]), Simulated Annealing (Kirkpatrick et al. [11]) and Tabu Search (Glover and Laguna [5]), were proposed during the last three decades. A comprehensive survey on real-time decision problems in OR perspective is given in (Seguin et al. [23]).
We study RTS with a zero deadline for the beginning of job processing. In these systems, jobs are processed immediately upon arrival, conditional on system availability. That part of the job which is not executed immediately is lost and cannot be stored for the later executing. Thus, there are no queues of jobs in such a RTS.
The following works treated RTS with a zero deadline for the beginning of job processing. Kreimer and Mehrez ([18] and [19]) have proved the optimality of the non-mix policy for a multiserver single-channel RTS involving preventive maintenance and working in general regime. Kreimer and Mehrez [20] and Kreimer [13] presented muliserver and multichannel (homogeneous servers and channels) RTS (with unlimited and limited number of maintenance facilities respectively), working under maximum load regime as finite source queues (Gross and Harris, [8]). Kreimer [12] and [14] applied the two-dimensional birth-and-death processes in worst case analysis of a multiserver RTS (with ample and restricted maintenance facilities respectively) with two different channels. Ianovsky and Kreimer [9] obtained optimal routing probabilities maximizing availability of RTS with redundant maintenance facilities studied in [12], for large number of servers. Kreimer [16] generalized the results of [12] for arbitrary number of heterogeneous channels operating under a maximum load regime. Kreimer [15] and Ianovsky and Kreimer [10] studied multiserver and multichannel RTS working in general regime. Shimshi and Kreimer [24] and Kreimer [17] investigated RTS performing different kinds of activities under non-preemptive priorities policy. Basan and Kreimer [??] considered RTS with preemptive priorities policy.
The work presented here extends the results concerning RTS with ample maintenance facilities obtained by Ianovsky and Kreimer [??] to RTS with limited maintenance facilities. It focuses on a RTS, with large number of homogeneous servers, several heterogeneous channels and limited maintenance teams working under maximum load regime. We obtain the moment generating function (MGF) and factorial moments of this RTS in a steady state, when both service and maintenance times are exponentially distributed, and investigate their rate of convergence as the number of servers increases to infinity. We also provide some numerical results.
The paper is organized as follows: Section 2 contains the description of the model is Section 3 presents our main results: MGF, moments and their limiting values. Section 4 provides some numerical results. Finally, in Section 5 some ideas for further research are discussed.
2. THE MODEL
The most typical characteristics of RTS with a zero deadline for the beginning of job processing are presented in Kreimer [15]. We study the following generalization of a real-world problem presented in (Kreimer [14]).
We consider a RTS consisting of N homogeneousl servers providing service to r heterogeneous channels with requests of real-time jobs working under maximal load regime (e.g. a military intelligence unit, equipped with N homogeneous unmanned aerial vehicles (UAV), which is responsible for r non-overlapping differentregions required to be under nonstop surveillance). We assume that there is exactly one request of real-time job in each channel at any moment (there are no additional job arrivals to the busy channel), and therefore one server/UAV at most is used (with others being on stand-by or in maintenance, or waiting for maintenance, or providing the service to another channel) to serve/observe the channel/region at any moment. Thus, the total number of operating servers is at most r (as the number of channels).
Each channel/region has its own specifications (e.g. weather conditions, defense systems, military command, etc.), and therefore different kinds of equipment and inventory are needed to serve/observe different channels/regions.
A server providing service to i-th channel is operative for a period of time before requiring hours of maintenance. and areindependent exponentially distributed random values with parameters (i=1,...,r) and respectively.
It is assumed that there are K () identical maintenance teams available to repair (with repair times being i.i.d.r.v.) the servers. Thus, a shortage of maintenance facilities is possible, when there are more than K servers out of order.
Thus, each server/UAV coming back from a mission and finding available maintenance team enters maintenance facilities without delay, otherwise it is waiting for maintenance. This server is assigned/routed to the i-th channel with probability (i=1,...,r).Itreceives the appropriate kind of maintenance (equipment, programming, etc.), and therefore cannot be sent to another channel. Assignment probabilities maydepend upon inventory conditions. They also can be used as control parameters. The duration of repair is exponentially distributed with parameter, and does not depend on the region. After maintenance, the server will either be on stand-by or serving the assigned channel.
This RTS works under a maximum load regime (worst case) of nonstop jobs arrival, which is equivalent to the case of a unique job of infinite duration in each one of r channels. This kind of operation is typical in high performance data acquisition, processing and control systems, such as satellites, space stations, self-guided missiles, etc.
If, during some period of time of length T , there is no available server to execute job in one of the channels, it means that the part of the job of length T is lost forever.
Denote the state of the system, where (i=1,...,r) is a number of fixed servers assigned to the i-th channel (obviously ), and the corresponding steady state probability. There are states in total.
Then steady state probabilities are given by the following formulas [14]:
(1),
(2).
where and.
Our purpose is to obtain the MGF and factorial moments of this RTS in a steady state and to investigate the rate of convergence, when the number of servers N tends to infinity.
3. MOMENT GENERATING FUNCTION AND MOMENTS
According to Gihman and Skorohod [6] a MGF of the set of random variables distributed (1)-(2) is given by the following formula:
(3).
Corresponding factorial moments defined similarly to Gross & Harris [8] and Gihman and Skorohod [7] are given by the following formulae:
= (4),
where and (). These moments can be obtained from MGF (3) by differentiation:
(5).
We are interested in limiting values of MGF and factorial moments, when .
Theorem1:
A RTS with N homogeneous servers, K () maintenance crews, r () different channels and exponentially distributed operating and maintenance times (with parameters () and respectively), operating under a maximum load regime, has following limiting values (as ) of factorial moments
,
if or and for any for which , where , and ().
Otherwise, if and for some such that , then increases to infinity as .
The proof follows directly from the sequence of Lemmas and Corollaries given in Appendix.
The following Theorem provides the rate of convergence as .
Theorem 2:
The rate of convergence of factorial moments as , if or and for any for which , is
, where , , and m is a number of accepting a maximal value ().
Othervise, if and for some such that , then increases to infinity as O(1/N).
The proof follows directly from the sequence of Lemmas and Corollaries given in Appendix.
Note 1: Limiting values (as ) of any ordinary moment can be obtained from existing limiting values of factorial moments by recursive procedure.
Note 2: The value of in can be chosen as for each vector under consideration and such that . Thus, the exponential convergence rate is faster, if the value is smaller. Similarly, the exponential convergence rate is faster, if the value of is smaller.
4. NUMERICAL RESULTS
In this Section we present some numerical results supporting the Theorems 1 and 2 of previous Section.
Table 1
Values of moments , where , , ,
, , , , , , , .
N
10 1.337562 13.781935 46.279606
20 2.134306 114.210118 846.942511
30 2.187316 232.230846 4124.847968
40 2.190298 294.319499 12310.060076
50 2.190466 315.513878 28363.881146
60 2.190476 321.109115 55596.817536
70 2.190476 322.361271 97511.886337
80 2.190476 322.611283 157697.671606
90 2.190476 322.65721 239768.92281
100 2.190476 322.665128 347340.392529
2.190476 322.666666
It can be easily seen that in given examples the limiting values of the moments are approached already for moderate values of N (few dozens).
5. FUTURE RESEARCH
In this Section, we present some ideas for further research. The limiting values of the moments can be obtained in a similar way also for the following models
RTS with different kinds of activities;
RTS with more than one job in each channel;
RTS in which each server needs more than one kind of maintenance.
ACKNOWLEDGEMENT
This research was partially supported by the Paul Ivanier Center for Robotics Research and Production Management at Ben-Gurion University.
REFERENCES
[1] A. K. Chakravarty and N. Balakrishnan, “Reacting in real-time to production contingencies in a capacitated flexible cell,” European Journal of Operational Research, vol. 110, no. 1, pp. 1-19, 1998.
[2] S. K. Dhal and C. L. Liu, “On a real-time scheduling problem,” Operations Research, vol. 26, no. 1, pp. 127-140,1978.
[3] T.A. Feo and M.G.C. Resende, “A probabilistic heuristic for a computationally difficult set covering problem,” Operations Research Letters, vol. 8,67-71, (1984).
[4] T.A. Feo, K.Venkatraman and J.F. Bard, A GRASP for a difficult single scheduling problem, Computers and Operations Research, vol. 18,635-643, (1991).
[5] F.W. Glover and M. Laguna, Tabu Search, Kluwer Academic Publishers, Dordrecht, (1997).
[6] I.I. Gihman and A.V. Skorohod, The Theory of Stochastic Processes I, Springer Verlag, Berlin, (1974).
[7] I.I. Gihman and A.V. Skorohod, The Theory of Stochastic Processes II, Springer Verlag, Berlin, (1975).
[8]D. Gross and C. M. Harris, Fundamentals of queueing theory,John Wiley, New York, 1998.
[9]E. Ianovsky and J. Kreimer, “Optimization of real-time multiserver system with two different channels,” Communications in Dependability and Quality Management,vol. 4, no. 1, pp. 16-23, 2001.
[10] E. Ianovsky and J. Kreimer, “Performance of Real-Time Multiserver and Multichannel System with Joint Source”, Communications in Dependability and Quality Management, vol. 5, no 2, pp. 75-88, 2002.
[11] S. Kirkpatrick, C.D. Gelatt Jr. and M.P. Vecchi, “Optimization by Simulated Annealing”, Science, vol. 220,671-680, 1983.
[12] J. Kreimer, “Performance of real-time multiserver system with two different channels in equilibrium,” Communications in Dependability and Quality Management,vol. 2, no. 1, pp. 16-23, 1999.
[13] J.Kreimer, “Real-time multiserver and multichannel systems with shortage of maintenance crews,” Mathematical and Computer Modelling,vol. 30, no. 11-12, pp. 169-176, 1999.
[14] J. Kreimer, “Real-Time Multiserver System with Two Non-identical Channels and Limited Maintenance Facilities,” Mathematics and Computers in Simulation, vol. 53, no. 1-2, pp. 85-94, 2000.
[15] J. Kreimer, “Effectiveness analysis of real-time data acquisition and processing multichannel systems,” IEEE J. on Reliability, vol 51, no 1, 91-99, 2002.
[16] J. Kreimer, “Real-time system with homogeneous servers and nonidentical channels in steady state,” Computers Operations Research,vol. 29, no 11, 1465-1473, 2002.
[17] J. Kreimer, “Multiserver Single-channel Real-Time Systems with Different Kinds of Activities,” Communications in Dependability and Quality Management,vol. 6, no. 1, pp. 91-100, 2003.
[18] J. Kreimer and A. Mehrez, “An optimal operation policy for real-time n-server stand-by system involving preventive maintenance,” European Journal of Operational Research, vol. 69, 50-54, 1993.
[19] J. Kreimer and A. Mehrez, “Optimal Real-Time Data Acquisition and Processing by a Multiserver Stand-By System,” Operations Research,vol. 42, no. 1, 24-30, 1994.
[20] J. Kreimer and A. Mehrez, “Computation of Availability of a Real-Time System Using Queueing Theory Methodology,” Journal of the Operational Research Society,vol. 49, pp.1095-1100, 1998.
[21] M. Litoiu and R. Tadei, “Real time task scheduling allowing fuzzy due dates,” European Journal of Operational Research,vol. 100, pp. 475- 481, 1997.
[22] C. L. Liu and J.W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,” J.ACM,vol. 20, no. 1, pp. 46-61, January 1973.
[23] R. Seguin, J.Y. Potvin, M. Gendreau, T. G. Crainic, P. Marcotte, “Real-time decision problems: An operational research perspective,” Journal of the Operational Research Society, vol. 48,162-174, (1997).
[24] Y. Shimshi and J. Kreimer, “Real-Time Multiserver System with Different kinds of Activities, ” Proceedings of the 11th Conference on Industrial Engineering and Management IE&M'2000, (Ladany S.P., Ed.), 17-21, Beer-Sheva, Israel, 2000.
[25] R. Tawegoum, E. Castelain, and J. C. Gentina, “Real-time piloting of flexible manufacturing systems,” European Journal of Operational Research, vol. 78, no. 2, pp. 252-261, 1994.
APPENDIX
We will use further the following notations:
the probability that the k-th channel is not served, and .
Now we will formulate the sequence of Lemmas and Corollaries.
Lemmas 1-4,6 and Corollary 1, are literally the same as in Ianovsky and Kreimer [??].
Let (), and (, ), ().
Lemma 5: For it is true
Lemma 7:
,
where , .
Lemma 8:
, .
Corollary 2: Let (), and (, ), and . Then, for ,
Lemma 9:, for and .
, for and .
Corollary 3: Lemma 9, when , results in
, , .
Corollary 4: Let (, ), (), (), and .
Then, for and , we have
.
Lemma 10: Let and , then
, for ,
and
, for .
Corollary 5:,
when , , , , and .
Lemma 11: Let (, , ), , and (), then
,
where , .
Lemma 12:
, .
Lemma 13:
, , , , ().
1