Access the full text.
Sign up today, get DeepDyve free for 14 days.
References for this paper are not available at this time. We will be adding them shortly, thank you for your patience.
MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 2019, VOL. 25, NO. 5, 463–481 https://doi.org/10.1080/13873954.2019.1660378 ARTICLE Performance analysis and optimization of a retrial queue with working vacations and starting failures a b Dong-Yuh Yang and Chia-Huang Wu Institute of Information and Decision Sciences, National Taipei University of Business, Taipei, Taiwan; Department of Industrial Engineering and Management, National Chiao Tung University, Hsinchu, Taiwan ABSTRACT ARTICLE HISTORY Received 9 April 2019 This paper presents a steady-state analysis of an M/M/1 retrial Accepted 22 August 2019 queue with working vacations, in which the server is subject to starting failures. The proposed queueing model is described in KEYWORDS terms of the quasi-birth-death (QBD) process. We ﬁrst derive the Matrix-geometric method; system stability condition. We then use the matrix-geometric starting failure; working method to compute the stationary probability distribution of the vacation orbit size. Some performance measures for the system are devel- oped. We construct a cost model, and our objective is to deter- mine the optimal service rates during normal and vacation periods that minimize the expected cost per unit time. The canonical particle swarm optimization (CPSO) algorithm is employed to deal with the cost optimization problem. Numerical results are provided to illustrate the eﬀects of system parameters on the performance measures and the optimal service rates. These results depict the system behaviour and show how the CPSO algorithm can be used to ﬁnd numerical solutions for optimal service rates. 1. Introduction In retrial queues with a single server, customers who ﬁnd the server occupied upon arrival join the retrial group (orbit) to retry obtaining service after a random period of time. If the server is free when a customer arrives, then the customer is served immediately. Over the last two decades, intensive research has been conducted on retrial queues due to their wide applicability in telecommunication networks, commu- nication systems, cellular mobile network, telephone switching systems, and computer networks. For a comprehensive survey on retrial queues, we refer the reader to two survey papers by Yang and Templeton [1] and Shekhar et al.[2]; three bibliographies of Artalejo [3–5]; and two books by Falin and Templeton [6] and Artalejo and Gomez- Corral [7]. In most of the literature on queueing systems, the server is assumed to be reliable (i.e., never fails). However, in the real world, servers are subject to breakdowns and/or repairs. When a breakdown occurs, service is interrupted until the failed server has been repaired. Retrial queues with server breakdowns have been addressed by many authors, CONTACT Dong-Yuh Yang yangdy@ntub.edu.tw Institute of Information and Decision Sciences, National Taipei University of Business, Taipei, Taiwan © 2019 Informa UK Limited, trading as Taylor & Francis Group 464 D.-Y. YANG AND C.-H. WU including Sherman and Kharoufeh [8], Falin [9], Choudhury and Ke [10], and Chang et al.[11]. One important feature of retrial queues with server breakdowns is the issue of starting failure. Yang and Li [12] described retrial queues with starting failures as follows: ‘If the server is idle, an arriving customer turns on the server in a negligible time. If the server is started successfully (with a certain probability), the customer gets service immediately. Otherwise, the server is sent to repair immediately, and the customer leaves the service area and repeats the request at a later time.’ They derived analytical results for the queue length distribution of M/G/1 retrial queues with starting failures, where it was assumed that retrial times are exponentially distributed. Kumar et al.[13] subse- quently investigated the M/G/1 retrial queue with starting failures and feedback, where it was assumed that retrial times are generally distributed. Wang and Zhao [14] extended the work of Yang and Li [12] to a discrete-time Geo/G/1 retrial queue with second optional service. Atencia et al.[15] used the generating function technique to analyse a discrete-time Geo/G/1 retrial queue with general retrial times and Bernoulli feedback, in which the server is subject to starting failures. Wang and Zhou [16] derived [X] the steady-state probabilities for the M /G/1 retrial queue with starting failures and Bernoulli feedback, where Bernoulli admission control was used for each individual customer. Multi-server retrial systems with starting failures were presented by Yang et al.[17] and Ke et al.[18]. In many real-world systems, the server becomes unavailable for a random amount of time (referred to as vacation time) immediately upon the departure of the last customer from the system. Vacation times can be used to perform tasks such as maintenance work or cleaning operations. The queueing systems with server vacations introduced by Levy and Yechiali [19] are widely used in manufacturing systems, production systems, service systems, inventory systems, and other stochastic systems. The literature on vacation queueing models is extensive. Excellent surveys on this topic can be found in [20–23]. During such vacation periods, the server stops working completely; how- ever, in many practical cases, the server continues working during vacation periods. This type of vacation policy (referred to as a working vacation) was introduced by Servi and Finn [24] for the analysis of wavelength-division multiplexing optical access net- work using multiple wavelengths. Servi and Finn [24] considered an M/M/1 queue with working vacations, wherein vacation times are exponentially distributed. Most of the earlier work on queueing models with working vacations can be found in the survey papers of Tian et al.[25] and Chandrasekaran et al.[26]. The M/M/1 retrial queue with working vacations was ﬁrst studied by Do [27], who derived closed-form solutions for the steady-state probabilities pertaining to the number of customers in the orbit. Li et al.[28] and Liu and Song [29] extended this work to discrete-time Geo/Geo/1 queues. Tao et al.[30] generalized the model of Do [27] to include vacation interrup- tions and collisions. Li et al.[31] employed the probability generating function method to obtain the stationary probability distribution of M/M/1 retrial queues with working vacations and vacation interruption. Arivudainambi et al.[32] used the method of supplementary variables to analyse the M/G/1 retrial queue with general retrial times and a single working vacation. Gao et al.[33] used the same method to study the M/G/1 retrial queue with working vacations and vacation interruptions. Li et al.[34] extended the model of Gao et al.[33] to M/G/1 retrial queues with working vacations and vacation interruptions under Bernoulli scheduling, wherein arriving customers may MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 465 balk (with a certain probability) upon ﬁnding that the server is busy. Recently, Do et al. [35] investigated the equilibrium and socially optimal balking strategies of customers in M/M/1 retrial queues with working vacations. In light of the practical applications of working vacations and service interrup- tions, this study focuses on retrial queues with working vacations and starting failures. Such a queueing model has potential applications in a health-care scenario. Rapid economic development and improving living standards have raised awareness of health-related matters and the demand for medical services. Some hospitals or clinics provide online consultation services to resolve the problem of long on-site queues. This allows patients to consult with a doctor without having to wait in line. Following this initial consultation, the patients may visit the hospital for further examination if necessary. Such consultation service also helps patients save time and money. We consider an online medical consultation service system, which operates via an APP running on a mobile device. A doctor is responsible for providing medical consultation services. Unfortunately, server disconnections or software bugs lead to inconsistencies in the provision of service (i.e., starting failure in queueing terminology). When no patients are waiting for online consultation service, the doctor is free to leave the system in order to perform other tasks, such as taking care of patients. While the doctor is absent from the system, a chatbot provides consultation services. After a period of time, the doctor returns to the online service to take over from the chatbot. Therefore, the proposed queueing model would be suitable for studying the above scenario. The remainder of this paper is organized as follows. In Section 2, we present a description of the proposed model and the underlying assumptions. In Section 3, the stationary analysis of the M/M/1 retrial queue with working vacations and starting failures is presented in terms of the quasi-birth-death (QBD) process. We obtain the closed-form expression of the stability condition and use the matrix-geometric method to compute the steady-steady probability distribution. In Section 4, we develop the performance measures for the system. In Section 5, we deal with a cost optimization problem and provide numerical examples to illustrate the eﬀects of parameters on optimal service rates. A special case and numerical comparisons are also presented. Conclusions are drawn in Section 6. 2. The model description and assumptions In this paper, we consider an M/M/1 retrial queue with working vacations and starting failures, where arrivals follow a Poisson process with rate λ. We assume that new arrivals who ﬁnd the server unavailable enter an orbit from which connection attempts are repeated until the requested service is completed. The intervals between successive connection attempts (retrials) are exponentially distributed with rate nγ when there are n customers in orbit. To make the analysis tractable, customers in orbit are permitted to conduct retrials up to Nð 1Þ retrials. In other words, the retrial rate is minfn; Ngγ if the number of customers in orbit is n. The server leaves for a vacation at the instant the system becomes empty. Vacation times follow an exponential distribution with para- meter ν. During a vacation period, the server continues working at a lower level, rather 466 D.-Y. YANG AND C.-H. WU Figure 1. Basic model for an M/M/1/WV retrial queue with starting failures. than halting service entirely. If the system remains empty when a vacation ends, then the server takes another vacation. Service times during normal busy and vacation periods are exponentially distributed with parameters μ and μ ( < μ ), respectively. b v b In cases where the server is on vacation when an arrival occurs, the arrival triggers the server to switch on with probability δ. When the server is operating normally during busy periods, the probability that service will be commenced for a new or returning customer is θ. If the server is successfully started, then the customer is served immediately. Otherwise, the server is sent for repairs, and the repair time follows an exponential distribution with parameter β. In the event that a server fails, the customer is moved into an orbit form which retrial requests are forwarded. The inter-arrival times, vacation times, service times during normal busy and vacation periods, and repair times are mutually independent. Henceforth, we refer to the above model as the M/M/1/WV retrial queue with starting failures. The general structure of the queueing model is illustrated in Figure 1. 3. Stability condition and stationary distribution Let LðtÞ be the number of customers in the orbit at time t, and ςðtÞ be the state of the server at time t, where 0; if the server is down during aworking vacation period at time t; 1; if the server is idle during aworking vacation period at time t; 2; if the server is busy during aworking vacation period at time t; ςðtÞ¼ 3; if the server is down during anormal busy period at time t; > 4; if the server is idle during anormal busy period at time t; 5; if the server is busy during anormal busy period at time t: MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 467 The M/M/1/WV retrial queue with starting failures can be modelled using a two- dimensional continuous-time Markov process fðςðtÞ; LðtÞÞ; t 0g with state space Ω ¼fð1; 0Þ; ð2; 0Þ; ð5; 0Þg [ fði; nÞ : 0 i 5; n 1g. A Markov process is a QBD process when its one-step transitions from each state are restricted to states in the same level or in the two adjacent levels (see Van Leeuwaarden et al.[36]). Thus, the stochastic process fðςðtÞ; LðtÞÞ; t 0g is a QBD process. The state transition diagram is depicted in Figure 2. Using the lexicographical sequence for the states, the inﬁnitesimal generator Q of the process has the block structure as follows:, 2 3 A B 0 0 6 7 C A B 1 1 6 7 6 7 C A B 2 2 6 7 . . . 6 7 . . . 6 7 . . . 6 7 . . . 6 7 . . . Q ¼ . . . ; 6 7 6 7 6 C A B 7 N1 N1 6 7 C A B 6 7 N N 6 7 . . . 6 7 . . . 4 . . .5 . . . . . . where Figure 2. The state transition diagram for an M/M/1/WV retrial queue with starting failures. 468 D.-Y. YANG AND C.-H. WU 2 3 λλδ 0 6 7 μ λ þ μ 0 A ¼ 4 5; v v μ 0 λ þ μ b b 2 3 λδ 000 00 6 7 B ¼ ; 400 λ 00 05 0 000 0 λ 2 3 00 0 6 7 0 γδ 0 6 7 6 7 00 0 6 7 C ¼ : 6 7 00 0 6 7 4 5 00 γθ 00 0 A , B, and C are square matrices of order 6, given by i i 2 3 λ 0 000 0 6 7 λδ 0 000 0 6 7 wv 6 7 A V 00 λ 00 0 6 7 A ¼ ; i 1; B ¼ ; i nb 6 7 O A 00 0 λ 00 i 6 7 4 5 00 0 λθ 00 00 000 λ 2 3 0 0 00 00 6 7 00 iγδ 00 0 6 7 6 7 0 0 00 00 6 7 C ¼ ; i 2; 6 7 0 0 00 00 6 7 4 5 00 0 0 0 iγθ 0 0 00 00 where 2 3 ðÞ λ þ β þ v β 0 wv 4 5 iγδ ðÞ λ þ iγ þ v λδ A ¼ ; 0 μ λ þ μ þ v v v 2 3 ðÞ λ þ β β 0 nb 4 5 A ¼ iγθ ðÞ λ þ iγ λθ ; 0 μ λ þ μ b b O is a zero matrix of size 3 3, and V is a 3 3 diagonal matrix with diagonal elements equal v. 3.1. Stability condition We ﬁrst study the stability condition of the system. To this end, let us deﬁne the invariant probability vector x ¼½ x ; x ; x ; x ; x ; x that satisﬁes xBðÞ þ A þ C¼ 0 1 2 3 4 5 N N MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 469 0 and xe ¼ 1, where 0 is a zero row vector of length 6, and e denotes the identity 6 6 6 6 column vector of order 6. Based on Theorem 3.1.1 in Neuts [37], it follows that xC e > xBe . Then, the necessary and suﬃcient condition for the system to be N 6 6 stable is λθ λ λ þ þ < 1 (1) θβ μ ðÞ λ þ Nγ θ Remark:If N ¼ 1 and θ ¼ 1, the stability condition becomes γ > , which coin- μ λ cides with Do [27]. 3.2. Stationary distribution If the stability condition is fulﬁled, let ðς; LÞ be the stationary limit of the QBD process fðςðtÞ; LðtÞÞg.We deﬁne the steady-state probability vectors as p ¼½p ; p ; p ; p ¼½p ; p ; p ; p ; p ; p ; p ; i 1; 1;0 2;0 5;0 0;i 1;i 2;i 3;i 4;i 5;i 6;i 0 i p ¼ Pðς ¼ i; L ¼ nÞ¼ lim PðςðtÞ¼ i; LðtÞ¼ nÞ; ði; nÞ2 Ω: i;n t!1 We denote the steady-state probability vector using P ¼½ p ; p ; p ; ::: ,which satisﬁes 0 1 2 the steady-state equations PQ ¼ 0 and the normalization condition Pe ¼ 1, where 0 is a zero row vector and e is acolumnvectorwithones. BasedonNeuts [37], the steady-state probability vector p ; p ; p ; ::: takes the following geometric N Nþ1 Nþ2 form: iN p ¼ p R ; i N; (2) i N where R is the minimal nonnegative solution to the matrix-quadratic equation B þ RA þ R C ¼ O ; (3) N N 6 and O is a zero matrix of size 6 6. The spectral radius of the matrix R is less than one if the stability condition is satisﬁed. We numerically compute matrix R using the iterative method. Starting with the initial value R ¼ O , the following iteration is 0 6 executed until the sum of the absolute value of all elements of the matrix is smaller 5 T 2 5 than 10 , i.e., ejj B þ RA þ R C e < 10 . N N 6 2 1 R ¼ðB þ R C ÞA ; i ¼ 0; 1; 2; ::: (4) iþ1 N i N The steady-state equations PQ ¼ 0 can be written as p A þ p C ¼ 0 ; (5) 0 1 3 0 1 p B þ p A þ p C ¼ 0 ; (6) 0 1 2 6 0 1 2 p B þ p A þ p C ¼ 0 ; 2 i N 1; (7) i iþ1 6 i1 i iþ1 470 D.-Y. YANG AND C.-H. WU p B þ p A þ p RC ¼ 0 ; (8) N N 6 N1 N N i1N 2 p R B þ RA þ R C ¼ 0 ; i N þ 1; (9) N N 6 where 0 represents a row vector of length 3, in which all elements are zero. Since the determinant of the matrix A is λðλ þ μ Þðλ þ δμ Þ0, the matrix A is 0 0 b v non-singular and its inverse exists. After some manipulations, Equations (5)–(7) become p ¼ p ðC A Þ¼ p ψ ; (10) 0 1 0 1 1 p ¼ p C ðψ B þ A Þ ¼ p ψ ; (11) 2 0 1 1 2 1 2 2 p ¼ p C ðψ B þ A Þ ¼ p ψ ; 3 i N; (12) i i1 i1 i i1 i i 1 1 where ψ ¼ðC A Þ, ψ ¼C ðψ B þ A Þ , and ψ ¼C ðψ B þ A Þ for 1 2 0 1 i i1 1 0 2 1 i i1 3 i N. Substituting Equations (10)–(12) into Equation (8) gives p ψ B þ A þ RC ¼ 0 : (13) N N 6 N N The vector p is determined by Equation (13) and the normalization condition "# 1 1 N i X Y XY p e þ p e ¼ p ψ e þ ψ e þðÞ I R e ¼ 1: (14) 3 6 3 6 6 0 i N j j i¼1 j¼N i¼2 j¼N Then, the vectors p (0 i N 1, i N þ 1) can be obtained using Equations (2) and (10)–(12). 4. Performance measures Once the steady-state probability vector has been obtained, we are able to develop the following performance measures for the system. The expected number of customers in the system 1 N i Y XY T T L ¼ p ψ ½0; 1; 1 þ ψ ie ½1; 1; 0; 1; 1; 0 s 6 N j j j¼N i¼2 j¼N (15) 1 T 2 þðÞ I R Ne þ½0; 0; 1; 0; 0; 1 þRIðÞ R e : 6 6 ● The expected number of customers in the orbit "# N i XY 1 2 L ¼ p ðÞ i 1 ψ þ NðÞ I R þRIðÞ R e : (16) o 6 N j i¼2 j¼N The probability that the server is on vacation MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 471 () "# 1 N i Y XY T 1 T P ¼ p ψ ½1; 1; 0 þ ψ þðÞ I R ½1; 1; 1; 0; 0; 0 : (17) N j j j¼N i¼2 j¼N The probability that the server undergoes repair "# N i XY 1 T P ¼ p ψ þðÞ I R ½1; 0; 0; 1; 0; 0 : (18) N j i¼2 j¼N ● The probability that the server is idle and waits for newly arriving or retrial customers () "# 1 N i Y XY T 1 T P ¼ p ψ ½1; 0; 0 þ ψ þðÞ I R ½0; 1; 0; 0; 1; 0 : (19) N j j j¼N i¼2 j¼N The probability that the server is busy () "# 1 N i Y XY T 1 T P ¼ p ψ ½0; 1; 1 þ ψ þðÞ I R ½0; 0; 1; 0; 0; 1 : (20) N j j j¼N i¼2 j¼N In the following, we present numerical results illustrating the inﬂuence of various system parameters on some performance measures. The numerical results are com- puted using a PC with an Intel Core i5-7500 CPU and 16 GB RAM running R software (version 3.5.0). We ﬁx N ¼ 30 and consider the following eight cases: Case 1: μ ¼ 1:0, μ ¼ 2:5, β ¼ 1:0, v ¼ 0:2, γ ¼ 2:0, δ ¼ 0:9 and θ ¼ 0:8 for various v b values of λ. Case 2: λ ¼ 1:0, μ ¼ 2:5, β ¼ 1:0, v ¼ 0:2, γ ¼ 2:0, δ ¼ 0:9 and θ ¼ 0:8 for various values of μ . Case 3: λ ¼ 1:0, μ ¼ 1:0, β ¼ 1:0, v ¼ 0:2, γ ¼ 2:0, δ ¼ 0:9 and θ ¼ 0:8 for various values of μ . Case 4: λ ¼ 1:0, μ ¼ 1:0, μ ¼ 2:5, v ¼ 0:2, γ ¼ 2:0, δ ¼ 0:9 and θ ¼ 0:8 for various v b values of β. Case 5: λ ¼ 1:0, μ ¼ 1:0, μ ¼ 2:5, β ¼ 1:0, γ ¼ 2:0, δ ¼ 0:9 and θ ¼ 0:8 for various v b values of v. Case 6: λ ¼ 1:0, μ ¼ 1:0, μ ¼ 2:5, β ¼ 1:0, v ¼ 0:2, δ ¼ 0:9 and θ ¼ 0:8 for various v b values of γ. Case 7: λ ¼ 1:0, μ ¼ 1:0, μ ¼ 2:5, β ¼ 1:0, v ¼ 0:2, γ ¼ 2:0 and θ ¼ 0:8 for various v b values of δ. Case 8: λ ¼ 1:0, μ ¼ 1:0, μ ¼ 2:5, β ¼ 1:0, v ¼ 0:2, γ ¼ 2:0 and δ ¼ 0:9 for various v b values of θ. In each case, the selection of all system parameters fulﬁls the condition for stability. The behaviours of the performance measures for cases 1–8 are visualized in Figure 3–10, 472 D.-Y. YANG AND C.-H. WU Figure 3. Eﬀect of λ on L , P , P , P , and P (case 1). S V D I B respectively. Figure 3 shows that L increases with an increase in λ. This may be due to the fact that any increase in the arrival rate would promote an increase in the number of customers who ﬁnd the server unavailable (busy or failed) and are subsequently moved into the retrial orbit. Conversely, Figures 4 and 5 show that L decreases as μ or μ v b increases. In Figures 3–5, we can see that the mean arrival rate (λ)and themeanservice rates (μ and μ ) have counter eﬀects on probabilities P , P , P ,and P . We can see in V D I B v b Figure 6 that an increase in β leads to (i) L and P decrease, and (ii) P , P and P s D V B I increase. This can be attributed to the fact that any increase in the repair rate would increase the probability of keeping the server available or operational. In Figure 7,it is obvious that L , P and P decrease with an increase in the value of ν. We can also see s B V that P increases as ν increases. Figure 8 shows that the larger is γ, the smaller are L and I s Figure 4. Eﬀect of μ on L , P , P , P , and P (case 2). S V D I B Figure 5. Eﬀect of μ on L , P , P , P , and P (case 3). S V D I B b MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 473 Figure 6. Eﬀect of β on L , P , P , P , and P (case 4). S V D I B Figure 7. Eﬀect of ν on L , P , P , P , and P (case 5). S V D I B Figure 8. Eﬀect of γ on L , P , P , P , and P (case 6). S V D I B P . Furthermore, any increase in γ would lead to increases in P and P . Thus, it is I B V reasonable that an increase in γ would lead to an increase in the frequency with which customers make repeated attempts to access service. Moreover, Figures 7 and 8 show that P is insensitive to change in ν or γ. Figures 9 and 10 clearly show that (i) L and P D s D decrease with an increase in δ or θ,and (ii) P , P and P increase as δ or θ increases. I V B Based on the ﬁgures described above, we can conclude that the behaviour of the performance measures is generally in line with our expectations. 474 D.-Y. YANG AND C.-H. WU Figure 9. Eﬀect of δ on L , P , P , P , and P (case 7). S V D I B Figure 10. Eﬀect of θ on L , P , P , P , and P (case 8). S V D I B 5. The cost model and optimization We construct an expected cost function per unit time, in which the service rates μ and μ are decision variables. We deﬁne the cost elements as follows: C ; holding cost per unit time per customer in the system; C ; cost per unit time when the server is on vacation; C ; cost per unit time when the server is busy; C ; cost per customer served under mean service rate μ ; C ; cost per customer served under mean service rate μ . Based on the above deﬁnitions of the cost elements and the corresponding perfor- mance measures of the system, the expected cost function per unit time can be derived as follows: Fðμ ; μ Þ¼ C L þ C P þ C P þ C μ þ C μ ; (21) h s v V b B 1 2 v b v b where L , P and P are obtained using Equations (15), (17) and (20), respectively. In s V B Equation (21), the ﬁrst term refers to the cost incurred by customers in the system, and the last four terms denote the costs incurred by the server. Our purpose is to determine the optimal service rates ðμ ; μ Þ by minimizing the expected cost function shown in v b Equation (21), where Fðμ ; μ Þ represents the corresponding minimum value of the v b expected cost function; i.e. Fðμ ; μ Þ¼ min Fðμ ; μ Þ. The expected cost function is v b v b μ ;μ v b MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 475 complex and rigorous, making it diﬃcult to derive explicit expressions for the optimal service rates. We, therefore, calculate numerical solutions. 5.1. Canonical particle swarm optimization algorithm The particle swarm optimization (PSO) algorithm introduced by Kennedy and Eberhart [38]isaneﬃcient stochastic approach to optimizing continuous nonlinear functions. For more information on the PSO algorithm, readers are referred to [39–41]. In this study, we utilize the canonical particle swarm optimization (CPSO) algorithm presented by Carlisle and Dozier [42] to obtain numerical results for ðμ ; μ Þ. The CPSO algo- v b rithm has been widely used by several researchers to solve optimization problems in a variety of queueing systems ([43–47]). To approximate an optimal solution for ðμ ; μ Þ, we implement the following procedure based on the CPSO algorithm. v b Step 1: Set t ¼ 0, the population size M, the upper bound of the position value X , max and the lower bound of the position value X . min Step 2: The initial positions and velocities of particles are randomly generated as ðtÞ ðtÞ ðtÞ ðtÞ ðtÞ ðtÞ follows: X ¼ðx ; x Þ and V ¼ðv ; v Þ, where i ¼ 1; 2; :::; M. i 1;i 2;i i 1;i 2;i Step 3: Assess the ﬁtness values of each particle using the expected cost function in ðtÞ ðtÞ ðtÞ Equation (21); i.e., FðX Þ¼ Fðx ; x Þ. i 1;i 2;i Step 4: The initial position of the particle i is set to the initial personal best position ð0Þ of the particle i (pbest ), and the initial global best position of all particles is ð0Þ set to gbest ¼ arg fmin FðX Þg. 1iN Step 5: Update the velocity of each particle using the following equation: ðtÞ ðtÞ ðtÞ ðtÞ ðtÞ ðtÞ ðtþ1Þ Υ v þ c r ðpbest x Þþ c r ðgbest x Þ ; X < x < X ; 1 1 2 2 min max d;i d;i d;i d;i v ¼ d;i 0; otherwise; where d ¼ 1; 2 and i ¼ 1; 2; :::; M. We generate random values for r and r 1 2 pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ in [0, 1]. Note that Υ ¼ 2=j2 φ φ 4φj is the constriction coeﬃcient, and φ is the sum of acceleration constants c and c ; i.e. φ ¼ c þ c . 1 2 1 2 Moreover, c and c are set to 2.8 and 1.3, respectively. 1 2 Step 6: Update the position of each particle using the following equation: ðtÞ ðtþ1Þ ðtÞ ðtþ1Þ x þ v ; X < x þ v < X ; min max < d;i d;i d;i d;i ðtþ1Þ ðtÞ ðtþ1Þ x ¼ X ; x þ v > X ; max max d;i d;i d;i ðtÞ ðtþ1Þ X ; x þ v < X : min min d;i d;i ðtÞ Step 7: Update the personal best position of particle i (pbest ) and the global best position of all particles gbest. Step 8: Update the iteration counter t ¼ t þ 1. ðtÞ ðtÞ Step 9: Stopping criterion: If max FðX Þ min FðX Þ is less than tolerance ε, i j 1i M 1j M then the algorithm terminates; else return to Step 5. Step 10: Output ðμ ; μ Þ¼ gbest and Fðμ ; μ Þ. v b v b 476 D.-Y. YANG AND C.-H. WU Figure 11. Expected cost Fðμ ; μ Þ for various values of μ and μ . v b v b 5.2. Numerical results In the following, we present a numerical experiment to check the convexity of Fðμ ; μ Þ. v b The graphical representation of Fðμ ; μ Þ is plotted in Figure 11 with the following v b parameter setting: N ¼ 30, λ ¼ 1:0, γ ¼ 2:0, β ¼ 1:0, v ¼ 0:2, δ ¼ 0:9, θ ¼ 0:8, C ¼ 45, C ¼ 60, C ¼ 90; C ¼ 30, and C ¼ 15. Figure 11 shows that Fðμ ; μ Þ is h v b 1 2 v b convex with respect to service rates μ and μ ; i.e. there exists a (local) minimum in the b v surface of the expected cost. We ﬁnd the minimum expected cost using the CPSO algorithm to approximate the optimal values for μ and μ . We then explore the b v sensitivity of the approximate optimal service rates ðμ ; μ Þ with respect to various system v b parameters. In implementing the CPSO algorithm, we ﬁx the upper and lower bounds of μ and μ at 0 and 10λ, respectively. The population size is set to 500 (M ¼ 500), and the b v tolerance is set to 0.01 (ε ¼ 10 ). The results are given in Tables 1–6,whereinCPU time represents the running time (in seconds) of the algorithm. From Table 1, we can see that μ and μ increase with an increase in λ. This can be attributed to the fact that an increase in the arrival rate would increase the probability of congestion. An increase in the service rate would decrease the congestion of the Table 1. Optimal service rates ðμ ; μ Þ and the corresponding expected cost Fðμ ; μ Þ for diﬀerent v b v b values of λ. λ 0.5 1.0 1.5 2.0 2.5 3.0 μ 1.4932 2.1842 2.8395 3.4717 4.0449 4.3651 μ 1.5810 3.6002 6.7294 11.8441 21.2200 30.0000 Fðμ ; μ Þ 189.796 290.395 432.258 661.191 1083.050 2301.318 v b Iterations 47 64 47 62 59 54 CPU time 43.091 100.785 95.806 161.140 203.165 341.029 MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 477 Table 2. Optimal service rates ðμ ; μ Þ and the corresponding expected cost Fðμ ; μ Þ for diﬀerent v b v b values of β. β 0.5 0.7 0.9 1.1 1.3 1.5 μ 2.2472 2.1887 2.1820 2.1879 2.1966 2.2055 μ 6.8209 4.6189 3.8268 3.4315 3.1986 3.0465 Fðμ ; μ Þ 448.016 335.273 299.848 283.586 274.546 268.895 v b Iterations 56 85 115 173 61 48 CPU time 124.829 138.64 195.984 232.822 68.648 2953.08 Table 3. Optimal service rates ðμ ; μ Þ and the corresponding expected cost Fðμ ; μ Þ for diﬀerent v b v b values of v. v 0.5 0.7 0.9 1.1 1.3 1.5 μ 1.2032 0.7135 0.2945 0 0 0 μ 3.9246 4.0103 4.0577 4.0846 4.1082 4.1260 Fðμ ; μ Þ 274.079 265.080 257.431 250.880 245.968 242.385 v b Iterations 45 62 47 46 51 58 CPU time 65.869 82.761 68.052 65.692 71.943 80.614 Table 4. Optimal service rates ðμ ; μ Þ and the corresponding expected cost Fðμ ; μ Þ for diﬀerent v b v b values of γ. γ 0.5 1.0 1.5 2.0 2.5 3.0 μ 1.2349 1.8555 2.0781 2.1843 2.2437 2.2809 μ 5.1534 4.2113 3.8171 3.6002 3.4634 3.3695 Fðμ ; μ Þ 340.251 309.048 297.049 290.395 286.118 283.128 Iterations 95 40 101 43 52 89 CPU time 135.811 50.677 136.717 59.182 70.484 118.308 system. From Table 2, it reveals that μ decreases with an increase in the value of β. Table 3 shows that μ decreases and μ increases as v increases. It is noted that μ v b v remains at 0 even when v is varied between 1.1 and 1.5. As shown in Table 4, μ increases and μ decreases with an increase in γ.In Table 5, one can see that an increase in δ causes μ to increase and μ to decrease. We can see in Table 6 that μ decreases v b v when θ is varied from 0.55 to 0.9. Furthermore, increasing θ leads to a decrease in μ . As shown in Table 1–6, Fðμ ; μ Þ increases with an increase in the value of λ and v b decreases with an increase in any one of the parameters β, v, γ, δ,or θ. The results listed above demonstrate that system managers could optimize system costs by adjusting various system parameters. This observation provides a useful reference for decision- making. Table 5. Optimal service rates ðμ ; μ Þ and the corresponding expected cost Fðμ ; μ Þ for diﬀerent v b v b values of δ. δ 0.3 0.4 0.5 0.6 0.7 0.8 μ 0.5793 0.8332 1.1059 1.3884 1.6637 1.9222 μ 3.8856 3.8804 3.8731 3.8562 3.8191 3.7439 Fðμ ; μ Þ 370.612 361.847 351.046 338.241 323.665 307.700 v b Iterations 45 42 55 50 86 52 CPU time 86.399 73.611 94.646 78.236 125.566 74.321 478 D.-Y. YANG AND C.-H. WU Table 6. Optimal service rates ðμ ; μ Þ and the corresponding expected cost Fðμ ; μ Þ for diﬀerent v b v b values of θ. θ 0.55 0.6 0.7 0.8 0.9 1.0 μ 3.4578 2.8021 2.3038 2.1842 2.1680 2.1843 μ 10.0000 10.0000 5.2442 3.6002 2.8435 2.4279 Fðμ ; μ Þ 1772.060 574.944 346.610 290.395 268.831 258.717 v b Iterations 44 97 65 72 59 135 CPU time 268.664 238.092 108.138 99.508 71.901 147.042 5.3. A special case and numerical comparison The model of Do [27] is a special case of our model when δ ¼ θ ¼ 1 (the server always starts successfully) and N ¼ 1 (constant retrial policy). We set τ ¼ δ ¼ θ and choose the system parameters as N ¼ 1, λ ¼ 1:0, γ ¼ 3:0, β ¼ 3:0, and v ¼ 0:2. The cost elements are identical to those used in Section 5.2. We select diﬀerent values of τ to compare the numerical results with Do [27]’s model. Given the mean service rates μ 3:5 and μ ¼ 6:5, Figure 12 shows that the eﬀects of τ on some performance measures. It reveals that L and P decrease as τ increases. This is because that when τ increases, s D the server is less prone to breakdowns, which leads to the smaller value of L and P .It S D is also found that P , P and P increase with an increase in τ. Table 7 shows the V I B optimal service rates ðμ ; μ Þ and the corresponding expected cost Fðμ ; μ Þ for diﬀerent v b v b values of τ. From Table 7, we observe that μ increases and μ decreases as τ increases. v b Moreover, it is found that Fðμ ; μ Þ decreases with increasing values of τ. Therefore, we v b conclude that the probability τ has an impact on the performance measures, the optimal service rates, and the minimum expected cost per unit time. Table 7. Optimal service rates ðμ ; μ Þ and the corresponding expected cost Fðμ ; μ Þ for diﬀerent v b v b values of τ. τ 0.5 0.6 0.7 0.8 0.9 1.0 μ 1.9544 2.1495 2.3090 2.4291 2.5209 2.5341 μ 15.3794 6.4964 4.3709 3.4129 2.8591 2.5341 Fðμ ; μ Þ 733.521 391.981 316.170 282.770 263.354 250.272 v b Iterations 63 129 80 75 81 146 CPU time 189.996 202.83 81.788 64.783 57.212 53.376 Figure 12. Eﬀect of τ on L , P , P , P , and P . S V D I B MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 479 6. Conclusions In this paper, we analysed the M/M/1/WV retrial queue with starting failures. The proposed queueing model was described by a QBD process. We ﬁrst derived the stability conditions of the model. We then used the matrix-geometric method to obtain the stationary probability distribution and developed a number of performance mea- sures. We formulated a cost optimization problem to determine the optimal service rates ðμ ; μ Þ at the minimum expected cost per unit time. The CPSO algorithm was employed to obtain numerical solutions for ðμ ; μ Þ. We also examined the eﬀects of v b various system parameters on performance measures and ðμ ; μ Þ through numerical v b experiments. In future works, the arrival process could be extended to the Markovian arrival process. Another direction would be to study the proposed queueing model within scenarios involving multiple servers. Acknowledgments The authors thank two anonymous referees for their valuable comments on this manuscript. This work was partially supported by the Ministry of Science and Technology, Taiwan, under Grant No. MOST 107-2218-E-009-058-MY2. Disclosure statement No potential conﬂict of interest was reported by the authors. Funding This work was partially supported by the Ministry of Science and Technology, Taiwan [MOST 107-2218-E-009-058-MY2]. References [1] T. Yang and J.G.C. Templeton, A survey on retrial queues, Queueing Syst. 2 (1987), pp. 201–233. doi:10.1007/BF01158899 [2] C. Shekhar, A.A. Raina, and A. Kumar, A brief review on retrial queue: Progress in 2010–2015,Int. J.Appl. Sci. Eng. Res. 5(2016), pp. 324–336. doi:10.6088/ijaser.05032 [3] J.R. Artalejo, A classiﬁed bibliography of research on retrial queues: Progress in 1990–1999, Top. 7 (1999), pp. 187–211. doi:10.1007/BF02564721 [4] J.R. Artalejo, Accessible bibliography on retrial queues, Math. Comput. Model. 30 (1999), pp. 1–6. doi:10.1016/j.mcm.2009.12.011 [5] J.R. Artalejo, Accessible bibliography on retrial queues: Progress in 2000–2009, Math. Comput. Model. 51 (2010), pp. 1071–1081. doi:10.1016/j.mcm.2009.12.011 [6] G.I. Falin and J.G.C. Templeton, Retrial Queues, Chapman and Hall, London, 1997. [7] J.R. Artalejo and A. Gomez-Corral, Retrial Queueing Systems: A Computational Approach, Springer-Verlag, Berlin, Heidelberg, 2008. [8] N.P. Sherman and J.P. Kharoufeh, An M/M/1 retrial queue with unreliable server, Oper. Res. Lett. 34 (2006), pp. 697–705. doi:10.1016/j.orl.2005.11.003 [9] G. Falin, An M/G/1 retrial queue with an unreliable server and general repair times, Perform. Eval. 67 (2010), pp. 569–582. doi:10.1016/j.peva.2010.01.007 480 D.-Y. YANG AND C.-H. WU [10] G. Choudhury and J.-C. Ke, An unreliable retrial queue with delaying repair and general retrial times under Bernoulli vacation schedule, Appl. Math. Comput. 230 (2014), pp. 436–450. doi:10.1016/j.amc.2013.12.108 [11] F.-M. Chang, T.-H. Liu, and J.-C. Ke, On an unreliable-server retrial queue with customer feedback and impatience, Appl. Math. Model. 55 (2018), pp. 171–182. doi:10.1016/j. apm.2017.10.025 [12] T. Yang and H. Li, The M/G/1 retrial queue with the server subject to starting failures, Queueing Syst. 16 (1994), pp. 83–96. doi:10.1007/BF01158950 [13] B.K. Kumar, S.P. Madheswari, and A. Vijayakumar, The M/G/1 retrial queue with feedback and starting failures, Appl. Math. Model. 26 (2002), pp. 1057–1075. doi:10.1016/S0307- 904X(02)00061-6 [14] J. Wang and Q. Zhao, A discrete-time Geo/G/1 retrial queue with starting failures and second optional service, Comput. Math. Appl. 53 (2007), pp. 115–127. doi:10.1016/j. camwa.2006.10.024 [15] I. Atencia, I. Fortes, and S. Sánchez, A discrete-time retrial queueing system with starting failures, Bernoulli feedback and general retrial times, Comput. Ind. Eng. 57 (2009), pp. 1291–1299. doi:10.1016/j.cie.2009.06.011 [16] J. Wang and P.-F. Zhou, A batch arrival retrial queue with starting failures, feedback and admission control,J. Syst. Sci. Syst.Eng.19(2010), pp. 306–320. doi:10.1007/s11518-010-5140-z [17] D.-Y. Yang, J.-C. Ke, and C.-H. Wu, The multi-server retrial system with Bernoulli feedback and starting failures, Int. J. Comput. Math. 92 (2015), pp. 954–969. doi:10.1080/ 00207160.2014.932908 [18] J.-C. Ke, T.-H. Liu, and D.-Y. Yang, Retrial queues with starting failure and service interruption, IET Commun. 12 (2018), pp. 1431–1437. doi:10.1049/iet-com.2017.0820 [19] Y. Levy and U. Yechiali, Utilization of idle time in an M/G/1 queueing system, Manage. Sci. 22 (1975), pp. 202–211. doi:10.1287/mnsc.22.2.202 [20] B.T. Doshi, Queueing systems with vacations—a survey, Queueing Syst. 1 (1986), pp. 29–66. doi:10.1007/BF01149327 [21] H. Takagi, Queueing Analysis: A Foundation of Performance Evaluation, Vol. 1, North- Holland, Amsterdam, 1991. [22] N.-S. Tian and Z.G. Zhang, Vacation Queueing Models: Theory and Applications, Springer- Verlag, New York, 2006. [23] J.-C. Ke, C.-H. Wu, and Z.-G. Zhang, Recent developments in vacation queueing models: a short survey, Int. J. Oper. Res. 7 (2010), pp. 3–8. [24] L.D. Servi and S.G. Finn, M/M/1 queues with working vacations (M/M/1/WV), Perform. Eval. 50 (2002), pp. 41–52. doi:10.1016/S0166-5316(02)00057-3 [25] N.-S. Tian, J.-H. Li, and Z.G. Zhang, Matrix analytic method and working vacation queues —a survey, Int. J. Inf. Manage. Sci. 20 (2009), pp. 603–633. [26] V.M. Chandrasekaran, K. Indhira, M.C. Saravanarajan, and P. Rajadurai, A survey on working vacation queueing models, Int. J. Pure Appl. Math. 106 (2016), pp. 33–41. doi:10.12732/ijpam.v106i6.5 [27] T.V. Do, M/M/1 retrial queue with working vacations, Acta Inform. 47 (2010), pp. 67–75. doi:10.1007/s00236-009-0110-y [28] T. Li, Z. Wang, and Z. Liu, Geo/Geo/1 retrial queue with working vacations and vacation interruption,J. Appl. Math.Computing. 39(2012), pp. 131–143. doi:10.1007/s12190-011-0516-x [29] Z. Liu and Y. Song, Geo/Geo/1 retrial queue with non-persistent customers and working vacations, J. Appl. Math. Computing. 42 (2013), pp. 103–115. doi:10.1007/s12190-012-0623-3 [30] L. Tao, Z. Liu, and Z. Wang, M/M/1 retrial queue with collisions and working vacation interrup- tion under N-policy,Rairo-Oper.Res.46 (2012), pp. 355–371. doi:10.1051/ro/2012022 [31] T. Li, L. Zhang, and S. Gao, Performance of an M/M/1 retrial queue with working vacation interruption and classical retrial policy, Adv. Oper. Res. (2016), Article ID 4538031, PP. 9. doi:10.1155/2016/4538031. MATHEMATICAL AND COMPUTER MODELLING OF DYNAMICAL SYSTEMS 481 [32] D. Arivudainambi, P. Godhandaraman, and P. Rajadurai, Performance analysis of a single server retrial queue with working vacation, Opsearch. 51 (2014), pp. 434–462. doi:10.1007/ s12597-013-0154-1. [33] S. Gao, J. Wang, and W.W. Li, An M/G/1 retrial queue with general retrial times, working vacations and vacation interruption, Asia Pac. J. Oper. Res. 31 (2014), pp. 25. doi:10.1142/ S0217595914400065. [34] T. Li, L. Zhang, and S. Gao, An M/G/1 retrial queue with balking customers and Bernoulli working vacation interruption, Qual. Technol. Quant. Manag. 16 (2019), pp. 511–530. doi:10.1080/16843703.2018.1480264 [35] N.H. Do, T.V. Do, and A. Melikov, Equilibrium customer behavior in the M/M/1 retrial queue with working vacations and a constant retrial rate, Oper. Res. Int. J. (2018). doi:10.1007/s12351-017-0369-7. [36] J.S.H. Van Leeuwaarden, M.S. Squillante, and E.M.M. Winands, Quasi-birth-and-death processes, lattice path counting, and hypergeometric functions, J. Appl. Probab. 46 (2009), pp. 507–520. doi:10.1239/jap/1245676103 [37] M. Neuts, Matrix-Geometric Solutions in Stochastic Models, Johns Hopkins University Press, Baltimore, 1981. [38] J. Kennedy and R. Eberhart, PSO optimization. In Proceedings of the IEEE international conference on Neural Networks, IEEE service center, Piscataway, NJ, pp. 1942–1948, 1995. [39] Y. Shi and R. Eberhart, A modiﬁed particle swarm optimizer, In Proceedings of the IEEE International Conference on Evolutionary Computation, Anchorage, AK, USA, 1998, pp.69–73. [40] J. Robinson and Y. Rahmat-Samii, Particle swarm optimization in electromagnetics, IEEE Trans. Antennas Propag. 52 (2004), pp. 397–407. doi:10.1109/TAP.2004.823969 [41] R. Poli, J. Kennedy, and T. Blackwell, Particle swarm optimization, Swarm Intell. 1 (2007), pp. 33–57. doi:10.1007/s11721-007-0002-0 [42] A. Carlisle and G. Dozier, An oﬀ-the-shelf PSO, In Proceeding of the workshop on particle swarm optimization, Purdue School of Engineering and Technology, Indianapolis, 2001. [43] X. Zhang, J. Wang, and T.V. Do, Threshold properties of the M/M/1 queue under T-policy with applications, Appl. Math. Comput. 261 (2015), pp. 284–301. doi:10.1016/j. amc.2015.03.109 [44] X. Zhang, J. Wang, and Q. Ma, Optimal design for a retrial queueing system with state-dependent service rate, J. Syst. Sci. Complex. 30 (2017), pp. 883–900. doi:10.1007/ s11424-017-5097-9 [45] Y. Zhang and J. Wang, Equilibrium pricing in an M/G/1 retrial queue with reserved idle time and setup time, Appl. Math. Model. 49 (2017), pp. 514–530. doi:10.1016/j. apm.2017.05.017 [46] J. Wang, X. Zhang, and P. Huang, Strategic behavior and social optimization in a constant retrial queue with the N-policy, Eur. J. Oper. Res. 256 (2017), pp. 841–849. doi:10.1016/j. ejor.2016.06.034 [47] K.-H. Wang, J. Wang, C.-D. Liou, and X. Zhang, Particle swarm optimization to the retrial machine repair problem with working breakdowns under the N policy, Queueing Mod, Serv. Manage 2 (2019), pp. 61–81.
Mathematical and Computer Modelling of Dynamical Systems – Taylor & Francis
Published: Sep 3, 2019
Keywords: Matrix-geometric method; starting failure; working vacation
You can share this free article with as many people as you like with the url below! We hope you enjoy this feature!
Read and print from thousands of top scholarly journals.
Already have an account? Log in
Bookmark this article. You can see your Bookmarks on your DeepDyve Library.
To save an article, log in first, or sign up for a DeepDyve account if you don’t already have one.
Copy and paste the desired citation format or use the link below to download a file formatted for EndNote
Access the full text.
Sign up today, get DeepDyve free for 14 days.
All DeepDyve websites use cookies to improve your online experience. They were placed on your computer when you launched this website. You can change your cookie settings through your browser.