Report

Managing Cancellations and No-shows of Reservations with Overbooking to Increase Resource Revenue Anthony Sulistio1, Kyong Hoon Kim2, and Rajkumar Buyya1 1Dept. of Computer Science and Software Eng. The University of Melbourne, Australia 2Dept. of Information Science Gyeongsang National University, Korea Proceedings of the 2008 Eighth IEEE International Symposium on Cluster Computing and the Grid (CCGRID) Presented by: minglung Outline Introduction Overview of Revenue Management Overbooking Policies Capacity Allocation with Overbooking Reservation, Penalty, Denied Cost Performance Evaluation Conclusion and Future Work Introduction (1/2) In Grid, advance reservation (AR) is proposed to ensure the specified resources are available for application’s consumption when needed Problem In reality, users may cancel their reservations before starting time or by not submitting at all (no-show) This causes income loss and lower system utilization Overbooking offers a solution Allowing the resource provider to accept more reservations than the capacity Introduction (2/2) This paper consider two challenging issues Determining the appropriate number of excess reservations Minimizing total compensation cost The contribution of this paper is Introducing three overbooking models to find an ideal overbooking limit that exceeds the maximum capacity Introducing three strategies for selecting which bookings to deny Investigating the impact of the models and strategies on the net resource revenue Overview of Revenue Management (1/2) Why use Revenue Management (RM) ? RM has been widely adopted in various industries with limited and perishable capacity, such as airlines, hotels, and car rentals Grid computing is also suitable since computing powers or nodes are considered to be perishable Market segmentation in Grids (Table 1) VO means Virtual Organizations Price of class i: pi, and p1 > p2 > p3 Overview of Revenue Management (2/2) We assume that class 3 users reserve before class 2 users before class 1 users (Figure 1) yi: protection level Protect reservations of class 1, 2 bi: booking limit maxCN: maximum capacity to be reserved The data structure used to administering reservations is a time-slotted data structure Overbooking Policies(1/10) Overbooking can protect a resource provider against cancellation and no-shows (Figure 2) Cancellation: a reservation that is terminated by a user before the service or starting time ts No-show: a reservation that fails to arrive and run on the resource on ts Overbooking Policies(2/10) ob: the overbooking limit Needs to be updated and evaluated frequently as ts approaches The ideal overbooking limit is calculated using… A probability-based policy A risk-based policy A service-level policy And some assumptions should be made Cancellations and no-shows are independent of the number of total bookings The probability of a cancellation only depends on the current time No-shows are treated as cancellations on ts Hence, we can define q(t) as a show rate that reservations show up from the time remaining until ts Overbooking Policies(3/10) A probability-based policy ob is determined statistically based on the probability of shows A risk-based policy Aims to balance the expected cost of denied service with the revenue by accepting more bookings The cost of denied service refers to the compensation money given to users who got rejected at the service time Overbooking Policies(4/10) The cost of denied service is denoted as costds and is usually higher than the resource price p A(x): the probability that the demand of users is less than or equal to x, the number of bookings Fx(y): the probability that the number of bookings that will show up at the time of service is less than or equal to y Assuming the current booking limit and the capacity are b and C, the expected revenue change by increasing the booking limit from b to b+1 can be derived: Only if demand > b causes revenue change The case that the number of shows ≦ C The case that the number of shows > C Overbooking Policies(5/10) Algorithm 1 calculates the booking limit using risk-based policy The booking limit increases while the expected revenue change is positive Overbooking Policies(6/10) In multiple fare classes, the increased revenue from having an additional booking can not be easily calculated A suitable approach is to determine a weighted average price based on the mean demands μ in each user class Assuming that each customer’s showing probabilities are independent, the show distribution Fx(y) at time t is as follows: Overbooking Policies(7/10) A service-level policy Consider the negative impact from the users who got rejected Define a service-level threshold and try not to exceed the threshold B(x): the number of shows for a given x bookings s(x): the service level of x bookings, defined by EQ5 ( B( x) C) max(0, B( x) C) If we use a binomial distribution for show demands… 1/ E[B(x)] E[(B(x) – C)+] Overbooking Policies(8/10) Algorithm 2 calculates the booking limit using service-level policy The booking limit increases while the service-level not exceeds the threshold Overbooking Policies(9/10) Overbooking limit calculation Price, p = 100 Capacity, C = 50 Denied cost, costds: 125 ~ 175 Show-rate, q: 0.60 ~ 0.95 Expected net revenue (ENR) is calculated by EQ7 Overbooking Policies(10/10) The service-level policy produces a lower deniedservice rate compared to the probability- and riskbased policy Capacity Allocation with Overbooking (1/3) The capacity allocation problem in RM is to decide the booking limit for each class user, in order to maximize the overall expected total revenue Expected marginal seat revenue (EMSR) heuristic is used to determine the booking limits of the three user class (algorithm 3) Capacity Allocation with Overbooking (2/3) Fi(x) denotes the probability that the demand of a class i user is less than or equal to x BookingLimit finds the booking limit of a lower class user Capacity Allocation with Overbooking (3/3) BookingLimit algorithm Expected revenue increase from bl-1 to bl Reservation, Penalty, Denied Cost (1/5) Initial Cost of A Reservation For non-AR jobs dur: duration numCN: the number of CNs used bcost: the base cost of running a job at one time unit For AR jobs numSlot: the total number of reserved slots bcostAR: the cost of running the AR job at one time slot τ: a constant factor (τ>1) to differentiate the pricing δ: the length of a slot Reservation, Penalty, Denied Cost (2/5) Penalty Cost Penalty rate: αp Penalty cost: αp * (the price for each reservation) 0 ≦ αp ≦ 1 αp = 0: reservation is fully refundable αp = 1: not refundable In multiple fare classes, αp1 < αp2 < αp3 Reservation, Penalty, Denied Cost (3/5) Denied cost We use EQ9 to determine costds τds depends on the agreement or policy set by the resource provider to a particular user class, τds > τ Denied-booking strategies Lottery (algorithm 4) Reservation, Penalty, Denied Cost (4/5) Denied Cost First (DCF) (algorithm 5) Reservation, Penalty, Denied Cost (5/5) Lower Class DCF (algorithm 6) Performance Evaluation (1/7) Simulation by GridSim toolkit Simulation setups MIPS Exponential Poisson Performance Evaluation (2/7) Exponential Objective: examine the impact of the overbooking policies and the denied-booking strategies on the net revenue of a resource, where cancellations and no-shows are allowed Performance Evaluation (3/7) Experimental result Negative effect of unanticipated cancellations and no-shows Performance Evaluation (4/7) 6-9% increase in net profits using overbooking strategies On average, DCF gives the highest total amount of income, followed by LC-DCF and then Lottery Performance Evaluation (5/7) The SL policy is the most conservative of all Performance Evaluation (6/7) Lottery strategy works best in reducing total denied bookings From the compensation cost’s point of view, Lottery is the least desirable DCF seems to be a better choice than LC-DCF Performance Evaluation (7/7) LC-DCF has the lowest number of denied Premium users To minimize the negative effects from high-paying users who have been denied access, the combination of SL and LC-DCF policies is a better solution in the long run Conclusion and Future Work Conclusion DCF is best since it has the lowest costds and the highest net revenue associated with the SL policy Future work Cancellations and no-shows are dependent of the number of total booking Handling a group cancellation for batch reservations