Structural properties of the optimal resource allocation policy for single-queue systems

This paper studies structural properties of the optimal resource allocation policy for single-queue systems. Jobs arrive at a service facility and are sent one by one to a pool of computing resources for parallel processing. The facility poses a constraint on the maximum expected sojourn time of a job. A central decision maker allocates the servers dynamically to the facility. We consider two models: a limited resource allocation model, where the allocation of resources can only be changed at the start of a new service, and a fully flexible allocation model, where the allocation of resources can also change during a service period. In these two models, the objective is to minimize the average utilization costs whilst satisfying the time constraint. To this end, we cast these optimization problems as Markov decision problems and derive structural properties of the relative value function. We show via dynamic programming that (1) the optimal allocation policy has a work-conservation property, and (2) the optimal number of servers follows a step function with as extreme policy the bang-bang control policy. Moreover, (3) we provide conditions under which the bang-bang control policy takes place. These properties give a full characterization of the optimal policy, which are illustrated by numerical experiments.     

Service outsourcing under co-opetition and information asymmetry

Co-opetition refers to the phenomenon that firms simultaneously cooperate and compete in order to maximize their profits. This paper studies the contracting for an outsourcing supply chain (a user company vs. a service provider) in the presence of co-opetition and information asymmetry. The user company outsources part of his service capacity at a discount price to the service provider for sale. The service provider charges a commission for doing outsourcing work and competes with the user company for the service capacity to satisfy their respective demands. We solve for the service provider’s optimal commission decision and the user company’s optimal outsourcing decisions (outsourcing volume and price discount) when the user company has private information about his service capacity. Specifically, we highlight the following observations. For the service provider, a menu of two-part tariffs that consist of a fixed commission and a per-volume commission can reveal the true type of the user company’s capacity; the user company’s optimal outsourcing proportion is quasi-convex and the optimal price discount is non-decreasing in his capacity volume, which is counterintuitive.     

Capacity allocation for demand of different customer-product-combinations with cancellations, no-shows, and overbooking when there is a sequential delivery of service

We consider a problem where different classes of customers can book different types of services in advance and the service company has to respond immediately to the booking request confirming or rejecting it. Due to the possibility of cancellations before the day of service, or no-shows at the day of service, overbooking the given capacity is a viable decision. The objective of the service company is to maximize profit made of class-type specific revenues, refunds for cancellations or no-shows as well as the cost of overtime. For the calculation of the latter, information of the underlying appointment schedule is required. Throughout the paper we will relate the problem to capacity allocation in radiology services. Drawing upon ideas from revenue management, overbooking, and appointment scheduling we model the problem as a Markov decision process in discrete time which due to proper aggregation can be optimally solved with an iterative stochastic dynamic programming approach. In an experimental study we successfully apply the approach to a real world problem with data from the radiology department of a hospital. Furthermore, we compare the optimal policy to four heuristic policies, of whom one is currently in use. We can show that the optimal policy significantly improves the currently used policy and that a nested booking limit type policy closely approximates the optimal policy and is thus recommended for use in practice.     

Option contracts: a solution for overloading problems in the delivery service supply chain

Owing to the limited service capacity of express delivery providers, most online retailers have to reject many orders during hot selling seasons. In this paper, we consider an express delivery service supply chain consisting of an express delivery provider and an online retailer whereby the selling season includes both regular periods and online sales periods. Utilizing a modified newsvendor model, we derive the express delivery provider’s optimal capacity decision and find that the overloading problem cannot be avoided because delivery service cannot be inventoried. To solve such a problem, we introduce an option contract to coordinate the supply chain. By allowing the online retailer to book the capacity, the express delivery provider can rent capacity from a third party in advance. Results show this approach can mitigate the problem significantly. We also extend our model to a supply chain consisting of a delivery provider and two retailers.     

基于博弈论的节能量保证型EPC合同决策分析

合同能源管理(EPC)是一种以未来节约的能源费用支付节能项目成本的节能管理机制。节能量保证型EPC模式中,耗能企业负责为项目融资,节能服务公司提供项目的全程服务并向客户企业保证一定的节能效益。若达不到承诺值,节能服务公司向客户进行补偿,若超出承诺值,客户给予节能服务公司一定的奖励。合同决策问题是该模式应用中的重要问题。本文以节能量保证型EPC合同中初始项目投资、合同期限和超额节能效益奖励的决策问题为研究对象,建立了客户和节能服务公司之间的决策博弈模型,分析二者的最优合同决策。数值试验结果表明,该方法不仅能让客户企业和节能服务公司均受益,还可以有效提高项目的投资报酬率,并且较高的节能服务公司技术水平和客户初始耗能水平能产生更高的节能效率。     

Optimal control of a dual service rate M/M/1 production-inventory model

We analyse a dual-source, production-inventory model in which the processing times at a primary manufacturing resource and a second, contingent resource are exponentially distributed. We interpret the contingent source to be a subcontractor, although it could also be overtime production. We treat the inventory and contingent sourcing policies as decision variables in an analytical study and, additionally, allow the primary manufacturing capacity to be a decision variable in a subsequent numerical study. Our goal is to gain insight into the use of subcontracting as a contingent source of goods and whether it can fulfill real-world managers' expectations for improved performance. We prove that a stationary, non-randomised inventory and subcontracting policy is optimal for our M/M/1 dual-source model and, moreover, that a dual base-stock policy is optimal. We then derive an exact closed-form expression for one of the optimal base stocks, which to our knowledge is the first closed-form solution for a dual-source model. We use that closed-form result to advantage in a numerical study from which we gain insight into how optimal capacity, subcontracting, and inventory policies are set, and how effectively a contingent source can reduce total cost, capacity cost, and inventory cost. We find that (i) the contingent source can reduce total cost effectively even when contingent sourcing is expensive and (ii) contingent sourcing reduces capacity cost more effectively than it does inventory cost.     

Optimal multi-period service capacity allocation and pricing allowing for uncertain competitive entry

A nonlinear programming model is formulated in this paper to determine the optimal scheme of capacity allocation and prices over a multi-period planning horizon for a service provider in the absence and presence of uncertain competitive entry. The model is solved for constant, decreasing, and increasing price sensitivities employing a combination of analytical and numerical methods. The study highlights the importance of advance selling of service prior to its eventual consumption in the spot period and investigates the impact of uncertain competitive entry on the optimal capacity allocation policy and its related profit if the entry is more or less likely or if the rival is more or less influential. The findings of the study reveal that the conclusions drawn from a two-period model are not necessarily generalizable to a model of a multi-period planning horizon.     

Characterizing optimal empty container reposition policy in periodic-review shuttle service systems

This paper considers a periodic-review shuttle service system with random customer demands and finite reposition capacity. The objective is to find the optimal stationary policy of empty container reposition by minimizing the sum of container leasing cost, inventory cost and reposition cost. Using Markov decision process approach, the structures of the optimal stationary policies for both expected discounted cost and long-run average cost are completely characterized. Monotonic and asymptotic behaviours of the optimal policy are established. By taking advantage of special structure of the optimal policy, the stationary distribution of the system states is obtained, which is then used to compute interesting steady-state performance measures and implement the optimal policy. Numerical examples are given to demonstrate the results.     

Software rejuvenation and resource reservation policies for optimizing server resource availability using cyclic nonhomogeneous Markov chains

Software rejuvenation is modeled in a client–server system, which provides resources to priority classes of users. To assure availability, resource reservation policies are adopted for the higher priority classes. In addition software rejuvenation is proposed to optimize resource availability. The system is modeled by a cyclic nonhomogeneous Markov chain to capture the variation of the arrival and service rates during a day period. An optimization problem is solved based on a similar previous work and given the optimal resource reservation policy obtained by its solution, rejuvenation is performed and the optimal rejuvenation policy is determined. As a measure of resource availability the blocking probability of each priority class is used. Performability indicators expressing the total cost are also derived, with respect to the optimal resource reservation and optimal rejuvenation policies, to examine whether rejuvenation benefits the system in terms of cost. To derive the blocking probabilities, the limiting probability distribution is computed using explicit generalized approximate inverse preconditioning for solving efficiently sparse linear systems of algebraic equations. Copyright © 2012 John Wiley & Sons, Ltd.     

基于时间窗延迟的资源约束项目调度双层优化研究

本研究从业主—承包商交互的视角构建了一种RCPSP(resource-constrained project scheduling problem)双层优化模型,即在可更新资源约束条件下,项目双方如何进行交互决策达到双方NPV(Net present value)最大化的目标。首先对研究问题进行界定,构建资源约束下的max-NPV项目调度双层优化模型;然后利用延迟优先规则设计了一种基于时间窗延迟的嵌套式自适应遗传算法来求解该模型,以达到双方NPV最大化;最后用一个算例验证算法的有效性,同时通过PSPLIB数值实验说明算法的稳定性,并分析关键参数对项目双方收益的影响。研究结果为项目进程的安排以及奖励机制的设计提供依据,以提高双方利益。     

Simulation and Queueing Theory Applied to a Single-Server Queue with Advertising and Balking

We use a single-server queueing model, with limited waiting room capacity, to model a situation where the manager of a facility tries to maximize the profit generated by the facility. He advertises to attract customers. The effectiveness of advertising may depend on the reputation of the facility, which is measured by the fraction of customers who balk. We assume Poisson arrivals and allow Erlang service times to study how the variance of service times affects the optimal policy, both when the efficiency of advertising is exogenous, and when it is a function of the balking rate. We conclude that the optimal policies are similar for deterministic service times, but diverge as the variance of the service time increases.     

Optimal inventory replenishment policy for a queueing system with finite waiting room capacity

We treat an inventory control problem in a facility that provides a single type of service for customers. Items used in service are supplied by an outside supplier. To incorporate lost sales due to service delay into the inventory control, we model a queueing system with finite waiting room and non-instantaneous replenishment process and examine the impact of finite buffer on replenishment policies. Employing a Markov decision process theory, we characterize the optimal replenishment policy as a monotonic threshold function of reorder point under the discounted cost criterion. We present a simple procedure that jointly finds optimal buffer size and order quantity.     

基于网络顾客行为意向的物流服务供应链定价策略

就一个运营网络购物的供应链,分析物流服务需求方和服务提供方的定价和服务水平决策等问题。在成本共担优化模型中考虑基于顾客购买行为意向的产品需求函数,进而分别给出非合作、准合作和完全合作模式下供应链企业决策间的关系,以及网购顾客重购概率对最优定价策略的影响。结论有:证明三种合作模式下双方最优策略的存在性及存在条件;给出最优产品定价策略和服务定价策略间的数量关系,并证明其与网购顾客行为意向有关。数值分析表明,最优定价策略随服务水平和网购顾客重购概率的变化趋势受成本共担系数的影响;较小的成本分摊系数使最优产品定价随着服务水平和网购顾客重购概率的变化幅度增大。     

基于离散事件仿真的妇产科孕妇建卡接收规则优化

孕妇在怀孕九周后会选择一家医院申请建立孕妇档案卡(简称建大卡),管理者需决定是否接收。一旦该医院做出接收决策,孕妇将在该院接受妊娠期内的产检并在该医院分娩。孕妇在妊娠期内所需的医疗资源的多样化、尤其是对关键资源即病床需求时间及服务时间不确定性,增加了决策的难度,从而导致妇产科资源利用率分布不均衡,影响医疗服务质量。为了解决该问题,本文首先建立动态规划模型来最小化病床的空闲、加床和转院的惩罚成本。由于动态规划模型非常复杂,难以用解析方法来获取最优控制策略,因此本文建立离散事件仿真系统,以病床的空闲、加床和转院的惩罚成本最小化为目标,采用广域搜索对多种阈值控制策略进行参数优化。数值实验表明,本文提出的阈值策略比医院目前采用的阈值策略有显著改进,进一步进行了敏感度分析,发现随着到达率逐渐增大,期望成本首先逐渐降低然后在某一水平上波动,加床成本的上升对于期望成本的影响更大。     

On the optimality of a full-service policy for a queueing system with discounted costs

We provide weak sufficient conditions for a full-service policy to be optimal in a queueing control problem in which the service rate is a dynamic decision variable. In our model there are service costs and holding costs and the objective is to minimize the expected total discounted cost over an infinite horizon. We begin with a semi-Markov decision model for a single-server queue with exponentially distributed inter-arrival and service times. Then we present a general model with weak probabilistic assumptions and demonstrate that the full-service policy minimizes both finite-horizon and infinite-horizon total discounted cost on each sample path.     

Optimal pricing for tandem queues with finite buffers

We consider optimal pricing for a two-station tandem queueing system with finite buffers, communication blocking, and price-sensitive customers whose arrivals form a homogeneous Poisson process. The service provider quotes prices to incoming customers using either a static or dynamic pricing scheme. There may also be a holding cost for each customer in the system. The objective is to maximize either the discounted profit over an infinite planning horizon or the long-run average profit of the provider. We show that there exists an optimal dynamic policy that exhibits a monotone structure, in which the quoted price is non-decreasing in the queue length at either station and is non-increasing if a customer moves from station 1 to 2, for both the discounted and long-run average problems under certain conditions on the holding costs. We then focus on the long-run average problem and show that the optimal static policy performs as well as the optimal dynamic policy when the buffer size at station 1 becomes large, there are no holding costs, and the arrival rate is either small or large. We learn from numerical results that for systems with small arrival rates and no holding cost, the optimal static policy produces a gain quite close to the optimal gain even when the buffer at station 1 is small. On the other hand, for systems with arrival rates that are not small, there are cases where the optimal dynamic policy performs much better than the optimal static policy.

     

Timing order fulfillment of capital goods under a constrained capacity

This paper studies the order-fulfillment process of a supplier producing multiple customized capital goods. The times when orders are confirmed by customers are random. The supplier can only work on one product at any time due to capacity constraints. The supplier must determine the optimal time to start the process for each order so that the total expected cost of having the goods ready before or after their orders are confirmed is minimized. We formulate this problem as a discrete time Markov decision process. The optimal policy is complex in general. It has a threshold-type structure and can be fully characterized only for some special cases. Based on our formulation, we compute the optimal policy and quantify the value of jointly managing the order fulfillment processes of multiple orders and the value of taking into account demand arrival time uncertainty.     

Optimal resource allocation for multiqueue systems with a shared server pool

We study optimal allocation of servers for a system with multiple service facilities and with a shared pool of servers. Each service facility poses a constraint on the maximum expected sojourn time of a job. A central decision maker can dynamically allocate servers to each facility, where adding more servers results in faster processing speeds but against higher utilization costs. The objective is to dynamically allocate the servers over the different facilities such that the sojourn-time constraints are met at minimal costs. This situation occurs frequently in practice, for example, in Grid systems for real-time image processing (iris scans, fingerprints). We model this problem as a Markov decision process and derive structural properties of the relative value function. These properties, which are hard to derive for multidimensional systems, give a full characterization of the optimal policy. We demonstrate the effectiveness of these policies by extensive numerical experiments.     

Allocation of flexible and indivisible resources with decision postponement and demand learning

We consider a firm that uses two perishable resources to satisfy two demand types. Resources are flexible such that each resource can be used to satisfy either demand type. Resources are also indivisible such that the entire resource must be allocated to the same demand type. This type of resource flexibility can be found in different applications such as movie theater complexes, cruise lines, and airlines. In our model, customers arrive according to independent Poisson processes, but the arrival rates are uncertain. Thus, the manager can learn about customer arrival rates from earlier demand figures and potentially increase the sales by postponing the resource allocation decision. We consider two settings, and derive the optimal resource allocation policy for one setting and develop a heuristic policy for the other. Our analysis provides managerial insights into the effectiveness of different resource allocation mechanisms for flexible and indivisible resources.