A continuous-time seat control model for single-leg flights with no-shows and optimal overbooking upper bound

This article proposes a continuous-time model to combine seat control and overbooking policies for single-leg flights. We assume that demand is time-and-fare dependent and follows a Poisson process. No-show passengers receive refunds which depend on their fares. Overbooking penalty is a uniformly convex function of oversale. To maximize the expected revenue, airline managers seek optimal seat allocation among competing passengers. In the meantime, they need to determine an optimal aggregate overbooking upper bound, which balances the no-show refunds and oversale penalties. Our basic model shows (i) although the nested-fare structure does not hold for the face value of fares, its essence is preserved in the sense of net fares; i.e., the face value less the no-show refund; (ii) the optimal control policy is based on a set of pre-calculated time thresholds, which is easy to implement; and (iii) there exists an optimal overbooking upper bound, below which the value function strictly increases in the upper bound, and above which the value function stays constant. We further extend the basic model to consider fare-dependent no-show rates. Numerical examples are presented.     

Dynamic overbooking scheduling system to improve patient access

Patient no-show has long been a recognized problem in modern outpatient health-care delivery systems. The common impacts are reduced clinic efficiency and provider productivity, wasted medical resources, increased health-care cost and limited patient access to care. The main goal of this research is to develop an effective dynamic overbooking policy into any scheduling system that accounts for the predictive probability of no-shows for any given patient. This policy increases the quality of patient care in terms of wait time and access to care while minimizing the clinic's costs. This proposed model is also illustrated to be more cost-effective than overbooking patients evenly throughout a clinic session. This paper also suggests that overbooking should be performed at better patient flow and higher no-show rate so that the costs are minimized. Consequently, this research improves the outpatient experience for both patients and medical providers.     

Analysis of seat allocation and overbooking decisions with hybrid information

We investigate a single-leg airline revenue management problem where an airline has limited demand information and uncensored no-show information. To use such hybrid information for simultaneous overbooking and booking control decisions, we combine expected overbooking cost with revenue. Then we take a robust optimization approach with a regret-based criterion. While the criterion is defined on a myriad of possible demand scenarios, we show that only a small number of them are necessary to compute the objective. We also prove that nested booking control policies are optimal among all deterministic ones. We further develop an effective computational method to find the optimal policy and compare our policy to others proposed in the literature.     

Outpatient appointment scheduling given individual day-dependent no-show predictions

This paper examines the combined use of predictive analytics, optimization, and overbooking to schedule outpatient appointments in the presence of no-shows. We tackle the problem of optimally overbooking appointments given no-show predictions that depend on the individual appointment characteristics and on the appointment day. The goal is maximizing the number of patients seen while minimizing waiting time and overtime. Our analysis leads to the definition of a near-optimal and simple heuristic which consists of giving same-day appointments to likely shows and future-day appointments to likely no-shows. We validate our findings by performing extensive simulation tests based on an empirical data set of nearly fifty thousand appointments from a real outpatient clinic. The results suggest that our heuristic can lead to a substantial increase in performance and that it should be preferred to open access under most parameter configurations. Our paper will be of great interest to practitioners who want to improve their clinic performance by using individual no-show predictions to guide appointment scheduling.     

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.     

Gossip based asynchronous and randomized distributed task assignment with guaranteed performance on heterogeneous networks

The main contribution of this paper is a novel distributed algorithm based on asynchronous and randomized local interactions, i.e., gossip based, for task assignment on heterogeneous networks. We consider a set of tasks with heterogeneous cost to be assigned to a set of nodes with heterogeneous execution speed and interconnected by a network with unknown topology represented by an undirected graph. Our objective is to minimize the execution time of the set of tasks by the networked system. We propose a local interaction rule which allows the nodes of a network to cooperatively assign tasks among themselves with a guaranteed performance with respect to the optimal assignment exploiting a gossip based randomized interaction scheme. We first characterize the convergence properties of the proposed approach, then we propose an edge selection process and a distributed embedded stop criterion to terminate communications, not only task exchanges, while keeping the performance guarantee. Numerical simulations are finally presented to corroborate the theoretical results.     

Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect

In this study, we introduce a time-dependent learning effect into a single-machine scheduling problem. The time-dependent learning effect of a job is assumed to be a function of total normal processing time of jobs scheduled in front of it. We introduce it into a single-machine scheduling problem and we show that it remains polynomially solvable for the objective, i.e., minimizing the total completion time on a single machine. Moreover, we show that the SPT-sequence is the optimal sequence in this problem.     

Flow shop scheduling with heterogeneous workers

We propose an extension to the flow shop scheduling problem named Heterogeneous Flow Shop Scheduling Problem (Het-FSSP), where two simultaneous issues have to be resolved: finding the best worker assignment to the workstations, and solving the corresponding scheduling problem. This problem is motivated by Sheltered Work centers for Disabled, whose main objective is the labor integration of persons with disabilities, an important aim not only for these centers but for any company desiring to overcome the traditional standardized vision of the workforce. In such a scenario the goal is to maintain high productivity levels by minimizing the maximum completion time, while respecting the diverse capabilities and paces of the heterogeneous workers, which increases the complexity of finding an optimal schedule. We present a mathematical model that extends a flow shop model to admit a heterogeneous worker assignment, and propose a heuristic based on scatter search and path relinking to solve the problem. Computational results show that this approach finds good solutions within a short time, providing the production managers with practical approaches for this combined assignment and scheduling problem.     

A cost-effective urgent care policy to improve patient access in a dynamic scheduled clinic setting

Patient no-show in outpatient clinics has been a long recognized issue, which negatively impacts clinic operational efficiency in terms of costs and patient access to care. One way to reduce these negative impacts is to allow urgent walk-ins during a clinic day. Some clinics allow random walk-ins and some purposely leave open time slots to accommodate them. The objective of this paper is to develop a cost-effective urgent care policy that is added on top of a full schedule and takes into account scheduled patients’ no-show rates to improve patient access to care in a dynamic clinic environment. The findings indicate that the proposed approach outperforms the current random and urgent slot approaches. This paper demonstrates a dynamic approach for accommodating urgent patients into a patient scheduling system, based on the prediction of an individual patient's no-show probability and the maximum number of urgent patients allowed.     

Risk-averse decision making in overbooking problem

Traditional literature studying overbooking problems focuses on risk-neutral decision makers. In this paper, we propose a multi-period overbooking model incorporating risk-aversion and extend well-known structural results (the 3-region policy) under the risk-neutral case to the risk-averse one on the basis of an exponential utility function. We also show that the optimal policy for the risk-neutral decision maker can be obtained by letting the risk-aversion parameter approach to zero under the risk-averse case. Therefore, the extant results under the risk-neutral case can be interpreted as a special case of ours. We also investigate how the optimal policy changes with some cost parameters and the decision maker's degree of risk-aversion. Numerical results suggest that the optimal bounds in the 3-region policy may increase or decrease with the decision maker's degree of risk-aversion.     

基于收益管理理论的门诊预约存量控制研究

门诊预约机制能够帮助医疗服务系统实现合理的资源组织与顺畅的服务流程,目前是医疗系统管理中的热点问题。论文分析了收益管理的适用性条件,提出其在医院门诊预约调度问题中应用的可行性,然后构建了门诊预约存量控制的Littlewood基础模型,并考虑患者爽约的情况,建立了超订策略下的门诊预约存量控制模型,最终用实例验证了所提出方法的实用性和有效性。     

可加号的门诊预约能力分配问题

预约服务可以有效优化医院门诊就诊流程,针对我国患者预约意识不强和预约患者爽约率高的特点,本文研究患者需求量较高时可以增加号源的条件下,考虑加号和拒绝患者成本,以门诊收益期望最大为目标,匹配预约患者和现场挂号患者需求量的能力分配问题。证明了门诊收益期望函数的单峰性,给出了最优解满足的条件。通过大量数值实验分析不同参数对门诊能力分配方案的影响,结果表明两类患者需求量对能力分配方案有较大影响,可加号情况下能力分配方案对患者爽约更敏感。     

Round robin scheduling of heterogeneous parallel servers in heavy traffic

We consider scheduling for heterogeneous server systems, where tasks arrive according to a Poisson process, with their processing requirements following a discrete distribution with finite support. For a system with a dispatcher and several heterogeneous servers, we propose an optimized multi-layered round robin routing policy followed by shortest remaining processing time scheduling at each server. Using a heavy traffic approximation, we show that the proposed policy performs as well as the optimal scheduling policy for a heterogeneous servers system with a single queue (no routing) in heavy traffic. Additional simulation results suggest that such policies will be effective in more general settings.     

随机服务时间下异质患者门诊预约调度优化

考虑随机服务时间与行为特征互不相同的异质患者,建立随机混合整数规划模型对门诊预约调度问题展开研究。首先在给定服务顺序的假设下求解了两个患者的预约调度问题;在此基础上,设计启发式算法对多个患者预约方案和服务顺序同时进行优化。数值结果表明:当患者服务时间为独立同分布的随机变量时,患者预约时间间隔呈现先增加后减少的圆顶形状;当患者服务时间服从不同分布时,通过与样本平均近似方法对比,验证了启发式算法的计算效率和有效性。     

Λ-Shaped Policies to Schedule Deteriorating Jobs

We study a problem of scheduling deteriorating jobs, i.e. jobs whose processing times are an increasing function of their starting times. We consider the case of a single machine and linear job-independent deterioration. The objective is to minimize the sum of weighted completion times, with weights proportional to the basic processing times. The optimal schedule is shown to be Λ-shaped, i.e. the sequence of the basic processing times has a single local maximum. Moreover, we show that the problem is solved in O(N log N) time. In the last section we test heuristics for the case of general weights.     

基于退化效应的两台机器流水作业可拒绝排序

考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法.     

A stochastic appointment scheduling system on multiple resources with dynamic call-in sequence and patient no-shows for an outpatient clinic

This research focuses on the stochastic assignment system motivated by outpatient clinics, especially the physical therapy in rehabilitation service. The aim of this research is to develop a stochastic overbooking model to enhance the service quality as well as to increase the utilization of multiple resources, like therapy equipment in a physical therapy room, with the consideration of patients’ call-in sequence. The schedule for a single-service period includes a fixed number of blocks of equal length. When patients call, they are assigned to an appointment time for that block, and an existing appointment is not allowed to be changed. In each visit, a patient might require more than one resource and a probability of no-show. Two estimation methods were proposed for the expected waiting and overtime cost with multiple resources: Convolution Estimation Method and Joint Cumulative Estimation Method for the upper and lower bound value; respectively. A numerical example based on a physical therapy room was used to show that this stochastic model was able to schedule patients for better profitability compared with traditional appointment systems based on four prioritization rules. The workload in each appointment slot was more balanced albeit more patients were assigned to the first slot to fill up the empty room.     

Production scheduling with supply and delivery considerations to minimize the makespan

In this paper we study a scheduling model that simultaneously considers production scheduling, material supply, and product delivery. One vehicle with limited loading capacity transports unprocessed jobs from the supplier’s warehouse to the factory in a fixed travelling time. Another capacitated vehicle travels between the factory and the customer to deliver finished jobs to the customer. The objective is to minimize the arrival time of the last delivered job to the customer. We show that the problem is NP-hard in the strong sense, and propose an O(n) time heuristic with a tight performance bound of 2. We identify some polynomially solvable cases of the problem, and develop heuristics with better performance bounds for some special cases of the problem. Computational results show that all the heuristics are effective in producing optimal or near-optimal solutions quickly.     

带有运输且加工具有灵活性的无等待流水作业排序问题

研究一类带有运输且加工具有灵活性的两阶段无等待流水作业排序问题, 其中每阶段只有一台机器, 每个工件有两道工序需要依次在两台机器上加工, 工件在两台机器上的加工及两道工序之间不允许等待. 给出两种近似算法, 并分别分析其最坏情况界. 第一种算法是排列排序, 证明了最坏情况界不超过5/2; 第二种算法将工件按照两道工序加工时间之和的递增顺序排序, 证明其最坏情况界不超过2. 最后, 通过数值模拟比较算法的性能. 对问题中各参数取不同值的情况, 分别生成若干个实例, 用算法得到的解与最优解的下界作比值, 通过分析这些比值的最大值、最小值和平均值来比较上述两个算法的性能.     

“酒店+OTA”双渠道供应链超订策略研究

为解决市场需求不确定环境下,酒店和在线旅行网站(Online Travel Agency,OTA)合作时的能力超订量与在线房间预留量的决策问题,建立了基于佣金合作模式的数学模型,给出了实现酒店整体期望收益最大化的在线房间预留量与能力超订量。借助数值分析,进一步研究了佣金率与需求不确定性对最优决策的影响。结果表明,当佣金率与门店需求不确定性较小时,酒店采取双渠道策略并且实施超订;当佣金率与门店需求不确定性很大时,酒店采取门店单渠道策略但不实施超订。另外,在线房间预留量随着佣金率、门店需求不确定性的增大而减小。