Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.16 No.2 pp.234-239
DOI : https://doi.org/10.7232/iems.2017.16.2.234

Optimal Pricing Strategies and Equilibrium Behaviors in the Discrete-Time Geo/Geo/1 Queueing System

Doo Ho Lee*
Department of Industrial and Management Engineering, Kangwon National University, Korea
Corresponding Author, enjdhlee@kangwon.ac.kr
October 20, 2016 February 22, 2017 March 13, 2017

ABSTRACT

This study investigates the optimal pricing strategies of the server and the equilibrium behaviors of customer in the discrete-time Geo/Geo/1 queueing system. In this work, we consider two pricing models. The first one is called the ex-ante payment (EAP) scheme where the server charges a flat price for all services. The second one is called the expost payment (EPP) scheme where the server charges a price that is proportional to the time that a customer spends in the system. Based on the reward-cost structure, the server should make the optimal pricing decisions in order to maximize its expected profit per unit time in each payment scheme. This study also investigates customer’s equilibrium joining or balking behaviors under server’s optimal pricing strategies under the corresponding pricing models. Numerical experiments are conducted to help the server best select one between two pricing models. The work results could provide the managers with reference information on the pricing problem in the queueing system.


초록


    1.INTRODUCTION

    Thanks to recent advances in computer and telecommunication technology, the importance of the discrete- time queueing system has been increased. This is because the conventional continuous-time queueing system cannot accurately give the performance measures of computer and telecommunication systems where basic operational units are bits, packets and cells, although they have been used in the past to approximately evaluate some performance measures of these systems. Hence, the discrete-time queueing system is potentially more suitable for application to the digital computer and communication networks. For detailed information on the discretetime queueing system, readers may refer to Meisling (1958), Hunter (1983), Bruneel and Kim (1993), and Takagi (1993).

    Recently, Ma and Liu (2015) studied the discretetime Geo/Geo/1 queue from an economic point of view. Ma and Liu (2015) analyzed the equilibrium strategies under two types of pricing structures. In the first structure, the server charges a fee that is proportional to the sojourn time (waiting time plus service time), called ex-post payment (EPP) scheme. In the second structure, however, the server charges a fixed fee for the service, which means the server implements an ex-ante payment (EAP) scheme. Under these two pricing schemes, Ma and Liu (2015) analyzed customer’s equilibrium joining behaviors and server’s expected profit maximization strategies. By the way, in Section 2 of their work, the expected sojourn time of the discrete-time Geo/Geo/1 queue was presented as 1/ (μpq) , where μ is server’s service rate and pq is customers’ effective arrival rate, but this is not correct. Actually, 1/ (μpq) is the expected sojourn time of the continuous-time M/M/1 queueing system. It is thought that Ma and Liu (2015) analyzed pricing models of not the discrete-time Geo/Geo/1 queue but the continuoustime M/M/1 queue. The purpose of this work is to correct the work of Ma and Liu (2015) and to present the exact pricing strategies in the discrete-time Geo/Geo/1 queue.

    The paper structured as follows. In section 2, we first derive the exact expected sojourn time in the discretetime Geo/Geo1 queue. In section 3 and 4, we analyze customer’s equilibrium joining behaviors and server’s profit maximization strategies under EPP and EAP schemes, respectively. Section 5 deals with numerical experiments where we investigate trends of the optimal prices of EPP and EAP schemes according to various input values.

    2.PRELIMINARIES

    This study considers a queueing system with following features. We adopt a late arrival system-delayed access (LAS-DA) (Takagi, 1993). Let the time axis be marked by t = 0, 1, 2, ⋯. According to the LAS-DA model, a customer arrival occurs during the interval (t, t) and a service completion occurs during the interval (t, t+) , where t and t+ represent lim Δ t 0 ( t | Δ t | ) and lim Δ t 0 ( t + | Δ t | ) respectively. The arrival process of potential customers is the Bernoulli process with a rate of p (0 < p < 1). Whenever each potential customer arrives at the system, they decide whether to join or balk the system depending on the specific joining probability, denoted by q (0 < q ≤ 1). It is well known that the decomposition property holds in the Bernoulli process; therefore, the effective arrival process follows the Bernoulli process with a rate of pq. Service times are independent and identically distributed random variables (RVs) following the geometric distribution with a parameter μ ( 0 < μ < 1). For analytical simplicity, we assume followings: i) All RVs defined above are mutually independent; ii) Services are provided on a first-in-first-out basis; iii) The decision whether to join or balk the system is irrevocable, which means that customers are not allowed to neither abandon services nor retry to join the system; iv) The stable system should satisfy pq < μ.

    The queueing system under our study is represented by a discrete-time Markov chain. Let N(t+ ) be the number of customers in the system at t+ . Then, {N(t+ ), t = 0, 1, ⋯} becomes the discrete-time Markov chain with the state space expressed as Ω = {n : n ≥ 0}. Let πn be the stationary queue length distribution: π n =lim Δ t 0 Pr { N ( t + ) = n } , n 0 . Then, we now have the following the local balance equations of our Markov chain (see Figure 1):

    π n p q ( 1 ( 1 δ n , 0 ) μ ) = π n + 1 ( 1 p q ) μ ,    n 0
    (1)

    where δi, j is the Kronecker delta. From the normalizing condition n = 0 π n = 1 , we can solve (1) and the queue length distribution has the form of(2)

    π 0 = 1 p q μ  and  π n = μ p q μ ( 1 μ ) ( p q ( 1 μ ) μ ( 1 p q ) ) n ,     n 1.
    (2)

    Let L and ω respectively denote the expected queue length and the expected sojourn time. L is then given by L = n = 1 n π n = p q ( 1 p q ) / ( μ p q ) . By Little’s formula, ω = (1− pq) / (μpq) . Due to the fact that μ < 1 , we have ω > 1 .

    After the completion of a service, a customer receives a reward R (R > 0). This may reflect his/her satisfaction or the added value of being served. In addition, there exists a waiting cost C (C > 0) per unit time when the customer stays in the system. To make the model nontrivial, we assume that > C, which ensures that the reward exceeds the cost for an arriving customer finding the empty system.

    3.EPP SCHEME

    We first investigate the EPP scheme, where the sever charges a price that is proportional to customer’s sojourn time. Let Kt (Kt ≥ 0) and Pt denote the price charged by the server and the expected server profit per unit time, respectively. Then, the expected utility Ut has the following relation: Ut = RKtω. If Ut equals zero at customer’s equilibrium, we have R = (Kt + C)(1-pq)/(μpq). Therefore, customer’s joining probability is equal to

    q = R μ K t C p ( R K t C )
    (3)

    Substituting (3) into Pt = pqKtω, we have(4)

    P t = R μ K t C R K t C K t R K t + C
    (4)

    Now we verify the following facts: lim K t ( R C ) P t = and lim K t ( R C ) + P t = . Therefore, Pt is not a continuous function and it is impossible to differentiate Pt when Kt = RC. Unlike Ma and Liu (2015), we establish the following non-linear programming (NLP) problem to maximize Pt with respect to Kt:

    max K t +    P t = R μ K t C R K t C K t R K t + C subject to      0 q 1      p q < μ
    (5)

    In (5), we want to maximize the expected server profit per unit time. The first constraint shows that the joining probability should be bounded between 0 and 1, and the second one guarantees the system to be stable. Actually, pq < μ in (5) can be simplified to ; Kt > −C therefore, we can neglect the second constraint due to the fact that Kt ≥ 0. Using (3), we rewrite (5) as

    max K t +    P t = R μ K t C R K t C K t R K t + C subject to      R ( 1 μ ) R K t C R ( 1 μ ) 1 p
    (6)

    • Lemma 1: The optimization problem in (6) is a convex maximization problem (CMP).

    The proof of Lemma 1 is given in Appendix A. Since the optimization problem in (6) is a CMP, Lagrange multiplier method can be used to find the optimal solution. Observing (6), we can find that all constraints are inequality constraints. Thus, Karush-Kuhn-Tucker (KKT) conditions can be used to generalize the method of Lagrange multiplier. The Lagrange function can be formulated as

    L t ( K t , λ 1 , λ 2 ) = P t + λ 1 ( K t + C R μ ) + λ 2 ( R ( μ p ) 1 p K t C ) ,

    where λ1 and λ2 are Lagrange multipliers. According to KKT conditions, the optimal solution K t * exists the following conditions can be satisfied simultaneously.

    { K t L t ( K t , λ 1 , λ 2 ) = 0 , K t + C R μ 0 , R ( μ p ) 1 p K t C 0 , λ 1 ( K t + C R μ ) = 0 , λ 2 ( R ( μ p ) 1 p K t C ) = 0 , λ 1 , λ 2 0.

    By solving the above equations group, we obtain the optimal price under the EPP scheme as follows:

    K t * = C ( R C ) + R C μ ( 1 μ ) ( R C ) R ( 1 μ ) C
    (7)

    If q > 1 , the preferred joining probability pq cannot be reached since p poses an effective limitation. In this case, the server may increase its price without having impact on pq, up to the point where R = Kf + C(1-p)/(μp)) . Therefore, the optimal price and its maximum profit for the server in this case are K t = R ( μ p ) / ( 1 p ) C and P t = p R ( 1 p ) / ( 1 p ) C ) , respectively. Based on the above analysis, we could give the following theorem.

    • Theorem 1: In the EPP scheme, denoting q t = ( R μ K t * C ) / ( p ( R K t * C ) ) , one has the following:

    • (1) if qt ≤ 1, there exists a unique equilibrium where customers join the queue with probability pqt, and K t * is given in (7) and P t = K t * R ( R μ K t * C ) / ( ( R K t * C ) ( K t * + C ) ) ;

    • (2) if qt > 1, there exists a unique equilibrium where customers join the queue with probability p, and K t * = R ( μ p ) / ( 1 p ) C and P t = p R ( 1 p ) / ( ( 1 p ) C ) .

    4.EAP SCHEME

    Next, we consider the EAP scheme model, where the server charges a flat price for services. Define Kf as the fixed price charged by the server and Pf as the server expected profit per unit time. Since the expected utility for a customer is expressed as Uf = R - Kf - and it equals zero an customers’ equilibrium, we obtain R = Kf + C(1-pq)/(μpq). Hence, customer’s joining probability is equal to

    q = R μ K f μ C p ( R K f C )
    (8)

    Substituting (8) into Pf = pqKf, we have

    P f = K f ( R μ K f μ C ) R K f C
    (9)

    Pf in (9) is neither continuous nor differentiable when Kf = RC due to the fact that lim K f ( R C ) P f = and lim K f ( R C ) + P f = . Similar to the EPP scheme model, we establish the following NLP problem to maximize Pf with respect to Kf:

    max K t +    P f = K f ( R μ K f μ C ) R K t C subject to      0 q 1 ,      p q < μ .
    (10)

    In (10), we also want to maximize the expected server profit per unit time. The first constraint shows that the joining probability should be bounded between 0 and 1, and the second one guarantees the system to be stable. Actually, pq < μ in (10) can be simplified to μ < 1 ; therefore, we neglect the second constraint by the model assumption in Section 2. Using (8), we rewrite (10) as

    max K t +    P f = K f ( R μ K f μ C ) R K t C subject to      ( R K f ) ( 1 μ ) R K f C ( R K f ) ( 1 μ ) 1 p
    (11)

    • Lemma 2: The optimization problem in (11) is a CMP.

    The proof of Lemma 2 is given in Appendix B. Since the optimization problem in (11) is a CMP, Lagrange multiplier method can be used to find the optimal solution. Observing (11), we can find that all constraints are inequality constraints. Thus, KKT conditions can be used to generalize the method of Lagrange multiplier. The Lagrange function can be formulated as

    L f ( K f , γ 1 , γ 2 ) = P f + γ 1 ( C μ ( R K f ) ) + γ 2 ( ( R K f ) ( μ p ) 1 p C ) ,

    where γ1 and γ2 are Lagrange multipliers. According to KKT conditions, the optimal solution K f * exists the following conditions can be satisfied simultaneously.

    { K f L f ( K f , γ 1 , γ 2 ) = 0 , C μ ( R K f ) 0 , ( R K f ) ( μ p ) 1 p C 0 , γ 1 ( C μ ( R K f ) ) = 0 , γ 2 ( ( R K f ) ( μ p ) 1 p C ) = 0 , γ 1 , γ 2 0

    By solving the above equations group, we obtain the optimal price under the EAP scheme as follows:

    K f * = μ ( R C ) C μ ( 1 μ ) ( R C ) μ
    (12)

    If q >1 , the preferred joining probability pq cannot be reached since p poses an effective limitation. In this case, the server may increase its price without having impact on pq , up to the point where R = K f + C ( 1 p ) / ( μ p ) . Therefore, the optimal price and its maximum profit for the server in this case are K f * = R C ( 1 p ) / ( μ p ) and Pf = p(R - C(1-p) / (μ-p) respectively. Based on the above analysis, we could give the following theorem.

    • Theorem 2: In the EAP scheme, denoting q f = ( R μ K f * μ C ) / ( p ( R K f * C ) ) , one has the following:

      • (1) if qf ≤ 1, there exists a unique equilibrium where customers join the queue with probability pqf, and K f * is given in (12) and P f = K f * ( R μ K f * μ C ) / ( R K f * C ) ;

      • (2) if qf > 1, there exists a unique equilibrium where customers join the queue with probability p, and K f * = R C ( 1 p ) / ( μ p ) and P f = p ( R C ( 1 p ) / ( μ p ) ) .

    5.NUMERICAL ANALYSIS

    It is interesting to note that the two different pricing models (EPP and EAP) do not affect customer’s equilibrium joining probability and the server’s maximum profits. Although K t * K f * , after some calculations, we can show that qt = qf and Pt = Pf if qt = qf < 1. In other words, customer’s equilibrium joining strategies and the expected server profits are identical in the two different pricing models in case of not only the continuous-time M/M/1 queue (see Proposition 3 in Ma and Liu, 2015) and but also the discrete-time Geo/Geo/1 queue.

    Based on our results, we present some numerical analyses. Figure 2 records the optimal price, the optimal joining probability, the maximum server profit of the EPP scheme and those of the EAP scheme according to the service rate. From Figure 2(a), we observe that EAP scheme generally sets a higher price than EPP scheme. Since Pt = Pf and EAP charges a flat price for a service, K f * should be relatively higher than K t * . We also observe that K f * ( K t * ) sharply increases when the service rate μ is low (high). This means that, in EAP (EPP) scheme, the server can maximize its profit by a small increase in the service rate when μ is low (high). Finally, as μ goes to C / R or 1, K t * and K f * tend to have the same value. From Figure 2(b), we observe that as μ increases, the optimal joining probability qt(=qf) first increases and then stays stable at the top point of 1. This means that, within a certain range, more customers join the system with a faster service. Accordingly, the maximum server profit Pt(=Pf) increases as the joining probability and the price increases. We also observe that the increasing rate of Pt(=Pf becomes lower after qt(=qf) reaches 1.

    Figure 3 records the optimal price, the optimal joining probability, the maximum server profit of the EPP scheme and those of the EAP scheme according to the reward. Figure 3(a) shows that both K f * and K t * are increasing functions of the reward R. As R increases, customer’s utilities Ut and Uf also increase in both EPP and EAP schemes. Hence, in order to maintain customer’s equilibrium, both K f * and K t * should increase when R increases. We also see that K f * is generally higher than K t * . At customer’s equilibrium, both Ut and Uf are equal to zero; therefore, K f * = K t * ω . In other words, EAP should set a higher price than EPP at the same values of R. From Figure 3(b), we observe that as R increases, qt(=qf) first increases and then stays stable at the top point of 1. This also means that more customers join the system with a higher reward. Accordingly, Pt(=Pf) increases as the joining probability and the price increases.

    6.CONCLUSIONS

    This study investigated customer’s equilibrium joining behaviors and server’s optimal pricing strategies in the Geo/Geo/1 queue. We first introduced the two different pricing models, namely EPP and EAP. Under the EPP scheme, the server charges a price that is proportional to customer’s sojourn time. Meanwhile, under the EAP scheme, the server charges a flat price for services. We established the convex maximization problem and decided the optimal price that maximizes the server’s expected profits for each pricing model. We also found that customer’s equilibrium joining strategies and server’s maximum profits under two different pricing schemes are the same.

    This work could provide queue managers with useful information for making the pricing decisions and instruct customers to take optimal strategies. Future studies include the extension of this work to other queueing systems considering multiple-server system, vacation policy and server failure phenomena.

    ACKNOWLEDGEMENT

    This study was supported by 2016 Research Grant from Kangwon National University.

    Figure

    IEMS-16-234_F1.gif

    Transition diagram of the Geo/Geo/1 queueing system.

    IEMS-16-234_F2.gif

    Optimal price, optimal joining probability, and maximum server profit versus μ for R = 20 , C = 1 and p = 0.6.

    IEMS-16-234_F3.gif

    Optimal price, optimal joining probability, and maximum server profit versus R for μ = 0.8 , C = 1 and p = 0.6.

    Table

    REFERENCES

    1. Bruneel H , Kim B G (1993) Discrete-Time Models for Communication Systems Including ATM, Kluwer Academic Publishers,
    2. Boyd S , Vandenberghe L (2004) Convex Optimization, Cambridge University Press,
    3. Hunter J J (1983) Mathematical Techniques of Applied Probability, Academic Press,
    4. Ma Y , Liu Z (2015) Pricing analysis in Geo/Geo/1 queueing system , Mathematical Problems in Engineering 2005,
    5. Meisling T (1958) Discrete-time queuing theory , Operations Research, Vol.6 (1) ; pp.96-105
    6. Takagi H (1993) Queueing Analysis vol. 3: Discrete-Time Systems,