Competitive strategies for an online generalized assignment problem with a service consecution constraint

This work studies a variant of the online generalized assignment problem, where there are m ? 2 heterogeneous servers to process n requests which arrive one by one over time. Each request must either be assigned to one of the servers or be rejected upon its arrival, before knowing any information of future requests. There is a corresponding weight (or revenue) for assigning each request to a server, and the objective is to maximize the total weights obtained from all the requests. We study the above problem with a service consecution constraint, such that at any time each server is only allowed to process up to d consecutive requests.     

A Markov model for single-leg air cargo revenue management under a bid-price policy

In this paper, we consider the capacity allocation problem in single-leg air cargo revenue management. We assume that each cargo booking request is endowed with a random weight, volume and profit rate and propose a Markovian model for the booking request/acceptance/rejection process. The decision on whether to accept the booking request or to reserve the capacity for future bookings follows a bid-price control policy. In particular, a cargo will be accepted only when the revenue from accepting it exceeds the opportunity cost, which is calculated based on bid prices. Optimal solutions are derived by maximizing a reward function of a Markov chain. Numerical comparisons between the proposed approach and two existing static single-leg air cargo capacity allocation policies are presented.     

Optimal access control for broadband services: Stochastic knapsack with advance information

Suppose that call reservation requests of K different types arrive randomly at a single capacitated link where each in turn must be accepted or rejected. Each request requires an amount of bandwidth and a random duration, both depending on its type. An accepted call generates an immediate fixed revenue followed by a variable revenue per unit time. We assume that each call's requested duration is known when it arrives and that the state of the link is constantly monitored. The problem is to find a call acceptance policy that maximizes the long-run average revenue per unit time generated by the accepted calls. We propose and investigate threshold-type control policies that use the known duration of arriving calls as well as the current link status. Two main contributions result. First are interpretable analytical results for the case of K = 1 that can also be applied to the case of K > 1 using complete partitioning scheme. Second, we illustrate how to apply stochastic optimization techniques to compute optimal thresholds in the general case. We also include the results of initial simulation experiments.     

Integrated revenue management approaches for capacity control with planned upgrades

In many service industries, firms offer a portfolio of similar products based on different types of resources. Mismatches between demand and capacity can therefore often be managed by using product upgrades. Clearly, it is desirable to consider this possibility in the revenue management systems that are used to decide on the acceptance of requests. To incorporate upgrades, we build upon different dynamic programming formulations from the literature and gain several new structural insights that facilitate the control process under certain conditions. We then propose two dynamic programming decomposition approaches that extend the traditional decomposition for capacity control by simultaneously considering upgrades as well as capacity control decisions. While the first approach is specifically suited for the multi-day capacity control problem faced, for example, by hotels and car rental companies, the second one is more general and can be applied in arbitrary network revenue management settings that allow upgrading. Both approaches are formally derived and analytically related to each other. It is shown that they give tighter upper bounds on the optimal solution of the original dynamic program than the well-known deterministic linear program. Using data from a major car rental company, we perform computational experiments that show that the proposed approaches are tractable for real-world problem sizes and outperform those disaggregated, successive planning approaches that are used in revenue management practice today.     

Revenue Models and Policies for the Car Rental Industry

In this paper, we consider the application of revenue management techniques in the context of the car rental industry. In particular, the paper presents a dynamic programming formulation for the problem of assigning cars of several categories to different segments of customers, with rental requests arising dynamically and randomly with time. Customers make a rental request for a given type of car, for a given number of days at a given pickup time. The rental firm can satisfy the demand for a given product with either the product requested or with a car of at most one category superior to that initially required, in this case an “upgrade” can take place. The one-way rental scenario, which allows the possibility of the rental starting and ending at different locations, is also addressed. In the framework considered, the logistic operator has to decide whether to accept or reject a rental request. Since the proposed dynamic programming formulations are impractical due to the curse of dimensionality, linear programming approximations are used to derive revenue management decision policies for the operator. Indeed, primal and dual acceptance policies are developed (i.e. booking limits, bid prices) and their effectiveness is assessed on the basis of an extensive computational phase.     

Filtering Policies in Loss Queuing Network Location Problems

In this paper we deal with two stationary loss queuing network location models. We analyze the influence of filtering policies on the locational aspect of the problems. We assume that requests for service are placed at nodes of a transportation network and they arrive in time as independent homogeneous Poisson processes with different input rates. The considered policies only cover a given proportion of requests even if there are idle service units. This proportion is stationary and fixed in advance and only depends on the node where the request is originated. The objective is to find the location of the facilities together with the filtering policy to be applied that minimize the expected total cost per unit time with respect to a given cost structure. Properties and computational results are presented enabling the resolution of these problems efficiently and showing the good performance of filtering policies in terms of both the overall operating costs, and the demand that is served.     

A dynamic vehicle routing problem with multiple delivery routes

This paper considers a vehicle routing problem where each vehicle performs delivery operations over multiple routes during its workday and where new customer requests occur dynamically. The proposed methodology for addressing the problem is based on an adaptive large neighborhood search heuristic, previously developed for the static version of the problem. In the dynamic case, multiple possible scenarios for the occurrence of future requests are considered to decide about the opportunity to include a new request into the current solution. It is worth noting that the real-time decision is about the acceptance of the new request, not about its service which can only take place in some future routes (a delivery route being closed as soon as a vehicle departs from the depot). In the computational results, a comparison is provided with a myopic approach which does not consider scenarios of future requests.     

Cost thresholds for dynamic resource location

The traditional dynamic resource location problem attempts to minimize the cost of servicing a number of sequential requests, given foreknowledge of a limited number of requests. One artificial constraint of this problem is the presumption that resource relocation and remote servicing of requests have identical costs. Parameterizing the ratio of relocation cost to service cost leads to two extreme behaviors in terms of dynamic optimizability. The threshold at which a specific graph transitions between these behaviors reveals certain characteristics of the graph's decomposability into cycles.     

Strategic and operational decisions in restaurant revenue management

The paper addresses restaurant revenue management from both a strategic and an operational point of view. Strategic decisions in restaurants are mainly related to defining the most profitable combination of tables that will constitute the restaurant. We propose new formulations of the so-called “Tables Mix Problem” by taking into account several features of the real setting. We compare the proposed models in a computational study showing that restaurants, with the capacity of managing tables as renewable resources and of combining different-sized tables, can improve expected revenue performances. Operational decisions are mainly concerned with the more profitable assignment of tables to customers. Indeed, the “Parties Mix Problem” consists of deciding on accepting or denying a booking request from different groups of customers, with the aim of maximizing the total expected revenue. A dynamic formulation of the “Parties Mix Problem” is presented together with a linear programming approximation, whose solutions can be used to define capacity control policies based on booking limits and bid prices. Computational results compare the proposed policies and show that they lead to higher revenues than the traditional strategies used to support decision makers.     

Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases

In many large-scale project scheduling problems, multiple projects are either taking place at the same time or scheduled into a tight sequence in order to efficiently share a common resource. One example of this is the computing resource allocation at an Application Service Provider (ASP) which provides data processing services for multiple paying customers. Typical services provided by ASPs are data mining, payroll processing, internet-based storage backup services and Customer Relation Management (CRM) services. The processing mode of an ASP can be either batch or concurrent, depending on the type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one customer request at a time in order to minimize the context switching overhead. While the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to process a service request depends on the computing resource allocated to that request. The related issue of achieving an optimal use of resources at ASPs leads to problem of project scheduling with controllable project duration.In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project duration and hard resource constraints. Two types of problems are considered. In type I, the duration of each project includes a constant and a term that is inversely proportional to the amount of resource allocated. In type II, the duration of each individual project is a continuous decreasing function of the amount of resource allocated.     

Dynamic cruise ship revenue management

Recently, it has been recognized that revenue management of cruise ships is different from that of airlines or hotels. Among the main differences is the presence of multiple capacity constraints in cruise ships, i.e., the number of cabins in different categories and the number of lifeboat seats, versus a single constraint in airlines and hotels (i.e., number of seats or rooms). We develop a discrete-time dynamic capacity control model for a cruise ship characterized by multiple constraints on cabin and lifeboat capacities. Customers (families) arrive sequentially according to a stochastic process and request one cabin of a certain category and one or more lifeboat seats. The cruise ship revenue manager decides which requests to accept based on the remaining cabin and lifeboat capacities at the time of an arrival as well as the type of the arrival. We show that the opportunity cost of accepting a customer is not always monotone in the reservation levels or time. This non-monotone behavior implies that “conventional” booking limits or critical time periods capacity control policies are not optimal. We provide analysis and insights justifying the non-monotone behavior in our cruise ship context. In the absence of monotonicity, and with the optimal solution requiring heavy storage for “large” (industry-size) problems, we develop several heuristics and thoroughly test their performance, via simulation, against the optimal solution, well-crafted upper bounds, and a first-come first-served lower bound. Our heuristics are based on rolling-up the multi-dimensional state space into one or two dimensions and solving the resulting dynamic program (DP). This is a strength of our approach since our DP-based heuristics are easy to understand, solve and analyze. We find that single-dimensional heuristics based on decoupling the cabins and lifeboat problems perform quite well in most cases.     

Comparison of policies in dynamic routing problems

We consider a company that has to satisfy customers' pick-up requests arriving over time every day. The overall objective of the company is to serve as many requests as possible at a minimum operational cost. When organizing its business the company has to fix some features of the service that may affect both service quality and operational costs. Some of these features concern the time a request is taken into account to plan its service, the associated deadline and the way requests are managed when the system is overloaded. In this paper we analyse several policies that can be implemented by the management of a carrier company in a multi-period context. For example, a company might reject all the requests that cannot be feasibly scheduled or accept all the requests and rely on a backup service in order to serve requests that are difficult to handle. Another interesting issue considered in this paper is the impact of collaborative service where two or more carrier companies, with their own customers, decide to share customers in order to optimize the overall costs. We set up a general framework to allow comparison of alternative service policies. Extensive computational results evaluating the number of lost requests and the distance travelled provide interesting insights.     

On Multi-threaded Metrical Task Systems

Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities.In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information.     

The fair allocation of common fixed cost or revenue using DEA concept

The common fixed cost or revenue distribution amongst decision making units (briefly, DMUs) in an equitable way is one of the problems that can be solved by data envelopment analysis (DEA) concept. The motivation of this paper is common fixed cost or revenue allocation based on following three principles: First, allocation must be directly proportional to the elements (inputs and outputs) that are directly proportional to imposed common fixed cost or to obtained common fixed revenue. Second, allocation must be inversely proportional to the elements that are inversely proportional to common fixed cost or revenue. Finally, the elements that have no effect on common fixed cost or revenue must have no effect on allocation as well.     

On the asymptotics of fault probability in least‐recently‐used caching with Zipf‐type request distribution

We consider the least‐recently‐used cache replacement rule with a Zipf‐type page request distribution and investigate an asymptotic property of the fault probability with respect to an increase of cache size. We first derive the asymptotics of the fault probability for the independent‐request model and then extend this derivation to a general dependent‐request model, where our result shows that under some weak assumptions the fault probability is asymptotically invariant with regard to dependence in the page request process. In a previous study, a similar result was derived by applying a Poisson embedding technique, where a continuous‐time proof was given through some assumptions based on a continuous‐time modeling. The Poisson embedding, however, is just a technique used for the proof and the problem is essentially on a discrete‐time basis; thus, it is preferable to make assumptions, if any, directly in the discrete‐time setting. We consider a general dependent‐request model and give a direct discrete‐time proof under different assumptions. A key to the proof is that the numbers of requests for respective pages represent conditionally negatively associated random variables. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Contract and product quality in platform selling

More and more e-tailers (platforms) are allowing manufacturers direct access to customers. Two common contracts are offered by platforms to manufacturers: the revenue sharing contract where a platform appropriates a portion of the manufacturer’s revenue, and the fixed fee contract where a platform charges a fixed rent for each sale. Using an analytical model, this paper studies the interrelationship between a platform’s contract choice and a manufacturer’s product quality decision. We find that if product quality is exogenously given, the platform will always adopt the revenue sharing contract. If the manufacturer endogenously decides the quality, however, the platform’s contract choice may be changed. This is because the revenue sharing contract, compared to fixed fee, leads to a lower selling price of the manufacturer, whereas the fixed fee contract can motivate a higher quality than does revenue sharing. As a result, a large (small) market heterogeneity induces the platform to adopt the revenue sharing (fixed fee) contract. We also extend the model to several directions, finding that longer product line, manufacturer competition, lower marginal production cost, and higher platform cost all tend to induce the platform to put forward a fixed fee contract; while if quality decision is less flexible than contract decision, the platform is more ready to embrace revenue sharing. Besides, when there are two platforms competing for the same market, they should differentiate their contract choices so as to mitigate competition.     

Investment decisions in the rent-to-own industry in the absence of inventory

This study addresses the product investment decision faced by firms in the rent-to-own industry. In this setting, a customer arrives according to a random process and requests one unit of a product to rent (and eventually own should he/she choose to make all the required payments). At the time of request, if the product is available in inventory, the firm enters into a contractual agreement (by accepting the customer's offer) and rents the merchandise. More interesting and the case considered here, if the requested item is not in inventory, the firm must decide whether to purchase the item in order to rent it out or to simply reject the request. The customer's offer specifies the desired maximum contract length and the payment frequency—from which the firm determines the fixed periodic payment charged. The firm makes its investment decision based on the characteristics of the offer as well as those of the product (eg, initial and resale values, useful life and carrying costs) in essence performing a complicated cost benefit analysis. An extension is also considered whereby instead of simply rejecting the request the firm can adjust the required payment amount. Dynamic programming techniques are used to address the problem and to solve for the firm's optimal decision.     

Optimal seat allocation for two-flight problems with a flexible demand segment

In this paper, we study a two-flight model where there are two flights between two cities in a day (e.g., one departs at 9:00 am and another at 11:00 am) and booking requests in each fare class arrive according to a random process. There are three types of booking requests: the first and second types are respectively for the first and the second flight only; whereas the third type is flexible and willing to take either flight. Upon receiving a booking request, the airline has to decide whether to accept it, and in case a third type is accepted, which flight to accommodate it. This paper uncovers the structure of optimal booking policies through four monotone switching curves. We also present an extension of the basic model to multiple-flight case. Finally, a numerical example is used to illustrate the derivation and the dynamics of the optimal booking policies.     

On relocation problems with multiple identical working crews

The relocation problem was formulated from a public housing project. In its basic form, a set of buildings needed to be torn down and erected by a single working crew. Given a fixed budget, the relocation problem seeks to determine a feasible reconstruction sequence of the old buildings. This problem has been shown to be mathematically equivalent to the classical two-machine flowshop of makespan minimization. In this paper, we consider a variant where multiple working crews are available for the redevelopment project. Most of our results center on the situations where all buildings require the same redevelopment time. We first present a strong NP-hardness proof for the case with two working crews. Then, we give a negative result about the approximability of the studied problem. Approximation algorithms and associated performance-ratio analysis are designed for the cases with unbounded as well as bounded numbers of machines.     

Using different response-time requirements to smooth time-varying demand for service

Many service systems have demand that varies significantly by time of day, making it costly to provide sufficient capacity to be able to respond very quickly to each service request. Fortunately, however, different service requests often have very different response-time requirements. Some service requests may need immediate response, while others can tolerate substantial delays. Thus it is often possible to smooth demand by partitioning the service requests into separate priority classes according to their response-time requirements. Classes with more stringent performance requirements are given higher priority for service. Lower capacity may be required if lower-priority-class demand can be met during off-peak periods. We show how the priority classes can be defined and the resulting required fixed capacity can be determined, directly accounting for the time-dependent behavior. For this purpose, we exploit relatively simple analytical models, in particular, M_t/G/∞ and deterministic offered-load models. The analysis also provides an estimate of the capacity savings that can be obtained from partitioning time-varying demand into priority classes.