Revenue maximization in two-station tandem queueing systems

We study optimal pricing for tandem queueing systems with finite buffers. The service provider dynamically quotes prices to incoming price sensitive customers to maximize the long-run average revenue. We present a Markov decision process model for the optimization problem. For systems with two stations, general-sized buffers, and two or more prices, we describe the structure of the optimal dynamic pricing policy and develop tailored policy iteration algorithms to find an optimal pricing policy. For systems with two stations but no intermediate buffer, we characterize conditions under which quoting either a high or a low price to all customers is optimal and provide an easy-to-implement algorithm to solve the problem. Numerical experiments are conducted to compare the developed algorithms with the regular policy iteration algorithm. The work also discusses possible extensions of the obtained results to both three-station systems and two-station systems with price and congestion sensitive customers using numerical analysis.     

A robust queueing network analyzer based on indices of dispersion

We develop a robust queueing network analyzer algorithm to approximate the steady-state performance of a single-class open queueing network of single-server queues with Markovian routing. The algorithm allows nonrenewal external arrival processes, general service-time distributions and customer feedback. The algorithm is based on a decomposition approximation, where each flow is partially characterized by its rate and a continuous function that measures the stochastic variability over time. This function is a scaled version of the variance-time curve, called the index of dispersion for counts (IDC). The required IDC functions for the external arrival processes can be calculated from the model primitives or estimated from data. Approximations for the IDC functions of the internal flows are calculated by solving a set of linear equations. The theoretical basis is provided by heavy-traffic limits for the flows established in our previous papers. A robust queueing technique is used to generate approximations of the mean steady-state performance at each queue from the IDC of the total arrival flow and the service specification at that queue. The algorithm's effectiveness is supported by extensive simulation studies.     

Dynamic service rate control for a single‐server queue with Markov‐modulated arrivals

We consider the problem of service rate control of a single‐server queueing system with a finite‐state Markov‐modulated Poisson arrival process. We show that the optimal service rate is nondecreasing in the number of customers in the system; higher congestion levels warrant higher service rates. On the contrary, however, we show that the optimal service rate is not necessarily monotone in the current arrival rate. If the modulating process satisfies a stochastic monotonicity property, the monotonicity is recovered. We examine several heuristics and show where heuristics are reasonable substitutes for the optimal control. None of the heuristics perform well in all the regimes and the fluctuation rate of the modulating process plays an important role in deciding the right heuristic. Second, we discuss when the Markov‐modulated Poisson process with service rate control can act as a heuristic itself to approximate the control of a system with a periodic nonhomogeneous Poisson arrival process. Not only is the current model of interest in the control of Internet or mobile networks with bursty traffic, but it is also useful in providing a tractable alternative for the control of service centers with nonstationary arrival rates. © 2013 Wiley Periodicals, Inc. Naval Research Logistics 60: 661–677, 2013     

Priority queue with customer upgrades

This article is concerned with a general multi‐class multi‐server priority queueing system with customer priority upgrades. The queueing system has various applications in inventory control, call centers operations, and health care management. Through a novel design of Lyapunov functions, and using matrix‐analytic methods, sufficient conditions for the queueing system to be stable or instable are obtained. Bounds on the queue length process are obtained by a sample path method, with the help of an auxiliary queueing system. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

Optimal control of an M/G/1 queue with impatient priority customers

An optimal operating policy is characterized for the infinite‐horizon average‐cost case of a single server queueing control problem. The server may be turned on at arrival epochs or off at departure epochs. Two classes of customers, each of them arriving according to an independent Poisson processes, are considered. An arriving 1‐customer enters the system if the server is turned on upon his arrival, or if the server is on and idle. In the former case, the 1‐customer is selected for service ahead of those customers waiting in the system; otherwise he leaves the system immediately. 2‐Customers remain in the system until they complete their service requirements. Under a linear cost structure, this paper shows that a stationary optimal policy exists such that either (1) leaves the server on at all times, or (2) turns the server off when the system is empty. In the latter case, we show that the stationary optimal policy is a threshold strategy, this feature being commonplace in most of priority queueing systems and inventory models. However, the optimal policy in our model is determined by two thresholds instead of one. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 201–209, 2001     

A specially structured nonlinear integer resource allocation problem

We present an algorithm for solving a specially structured nonlinear integer resource allocation problem. This problem was motivated by a capacity planning study done at a large Health Maintenance Organization in Texas. Specifically, we focus on a class of nonlinear resource allocation problems that involve the minimization of a convex function over one general convex constraint, a set of block diagonal convex constraints, and bounds on the integer variables. The continuous variable problem is also considered. The continuous problem is solved by taking advantage of the structure of the Karush‐Kuhn‐Tucker (KKT) conditions. This method for solving the continuous problem is then incorporated in a branch and bound algorithm to solve the integer problem. Various reoptimization results, multiplier bounding results, and heuristics are used to improve the efficiency of the algorithms. We show how the algorithms can be extended to obtain a globally optimal solution to the nonconvex version of the problem. We further show that the methods can be applied to problems in production planning and financial optimization. Extensive computational testing of the algorithms is reported for a variety of applications on continuous problems with up to 1,000,000 variables and integer problems with up to 1000 variables. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 770–792, 2003.     

Bicriteria product design optimization: An efficient solution procedure using AND/OR trees

Competitive imperatives are causing manufacturing firms to consider multiple criteria when designing products. However, current methods to deal with multiple criteria in product design are ad hoc in nature. In this paper we present a systematic procedure to efficiently solve bicriteria product design optimization problems. We first present a modeling framework, the AND/OR tree, which permits a simplified representation of product design optimization problems. We then show how product design optimization problems on AND/OR trees can be framed as network design problems on a special graph—a directed series‐parallel graph. We develop an enumerative solution algorithm for the bicriteria problem that requires as a subroutine the solution of the parametric shortest path problem. Although this parametric problem is hard on general graphs, we show that it is polynomially solvable on the series‐parallel graph. As a result we develop an efficient solution algorithm for the product design optimization problem that does not require the use of complex and expensive linear/integer programming solvers. As a byproduct of the solution algorithm, sensitivity analysis for product design optimization is also efficiently performed under this framework. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 574–592, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10031     

动态服务质量的多信道媒体接入控制传输机制

针对航空自组网在高负载下的服务质量及时延问题,提出一种动态服务质量的多信道媒体接入控制传输机制。以多信道检测统计为平台,结合优先级机制,通过在高负载网络中适当遏制低优先级业务,并且进行网络流量优化,保证高优先级业务的低时延发送;同时利用流量预测模型估计网络流量,通过粒子群优化算法进行优化,寻找合适的优先级门限值,确保高优先级业务接入率。通过计算机仿真可知,所设计的动态服务质量的多信道媒体接入控制传输机制,可在大负载网络中动态控制信道的接入,保持良好的网络吞吐量,其高优先级业务接入率达到99%以上,能有效解决航空数据链网络高业务量导致的服务质量及时延问题。     

A note on optimal pricing for finite capacity queueing systems with multiple customer classes

This article investigates optimal static prices for a finite capacity queueing system serving customers from different classes. We first show that the original multi‐class formulation in which the price for each class is a decision variable can be reformulated as a single dimensional problem with the total load as the decision variable. Using this alternative formulation, we prove an upper bound for the optimal arrival rates for a fairly large class of queueing systems and provide sufficient conditions that ensure the existence of a unique optimal arrival rate vector. We show that these conditions hold for M/M/1/m and M/G/s/s systems and prove structural results on the relationships between the optimal arrival rates and system capacity. © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

A note on a computational model for a data/voice communication queueing system

Certain types of communication nodes can be viewed as multichannel queueing systems with two types of arrival streams. Data arrivals are characterized by high arrival and service rates and have the ability to queue if all service channels are busy. Voice arrivals have small arrival and service rates and do not have the ability to wait when the channels are full. Computational procedures are presented for obtaining the invariant probabilities associated with the queueing model.     

Approximation for the departure process of a queue in a network

A simple renewal process is identified to approximate the complex departure process of a queue often found in queueing network models. The arrival process to the queue is the superposition or merging of several independent component-renewal processes that are approximations of departure processes from other queues and external arrival processes; there is a single server with exponential service times, and the waiting space is infinite. The departure process of this queue is of interest because it is the arrival process to other queues in the network. The approximation proposed is a hybrid; the mean and variance of the approximating departure intervals is a weighted average of those determined by basic methods in Whitt [41] with the weighting function empirically determined using simulation. Tandem queueing systems with superposition arrival processes and exponential service times are used to evaluate the approximation. The departure process of the first queue in the tandem is approximated by a renewal process, the tandem system is replaced by two independent queues, and the second queue is solved analytically. When compared to simulation estimates, the average absolute error in hybrid approximations of the expected number in the second queue is 6%, a significant improvement over 22–41% in the basic methods.     

基于粒子群算法的H_∞混合灵敏度控制研究

针对步进电机存在负载摄动和失步超步问题,提出了一种基于粒子群优化算法的混合灵敏度设计方法。在H∞混合灵敏度约束下,采用粒子群算法寻找能够反映系统特性的适应度函数最优值,在搜索到合适的加权阵基础上,利用Matlab得到了H∞最优控制器,并利用优化控制器对步进电机进行控制仿真实验。实验结果表明：该系统具有响应快速平稳、抗负载扰动强等特点。     

采用弹道修正技术的红外干扰弹性能优化

针对弹道修正弹的高维非线性特性导致的性能优化难题,改变概念设计阶段传统的串行设计方式,提出了一种基于实验设计(Design Of Experiments,DOE)和响应面(Response Surface Methodology,RSM)的智能优化算法,定义基本的弹丸结构模型以及相关的设计参数.在DOE的基础上,将设计...     

A constrained optimization problem for a processor sharing queue

In this article we discuss a processor sharing queueing model for a stored program controlled telephone exchange. The model incorporates the effects of both call requests and operator tasks on the load of the processor. Newly arriving call requests and operator tasks can either be admitted or rejected and for this decision the state of the queue at the moment of arrival is available as information. To guarantee a high level of service, we formulate a constrained optimization problem. Two types of access control, viz., partitioning policies and sharing policies, are considered. The optimization problem is solved for partitioning policies and the performance of both types of policies is compared. © 1993 John Wiley & Sons, Inc.     

Some properties of optimal control policies for entry to an M/M/1 queue

Customers served by an M/M/1 queueing system each receive a reward R but pay a holding cost of C per unit time (including service time) spent in the system. The decision of whether or not a customer joins the queue can be made on an individual basis or a social basis. The effect of increasing the arrival rate on the optimal policy parameters is examined. Some limiting results are also derived.     

求解不确定型车辆路径问题的弱鲁棒优化方法

为降低鲁棒优化模型最优解的保守性,以最小化违约车辆数和总惩罚成本为目标,建立针对旅行时间不确定的开放式车辆路径问题的弱鲁棒优化模型。对于不确定数据集的每个取值,该模型的最优解可以使其目标函数值始终不超过某数值,进而改善最优解的保守性。为提高启发式算法发现最优解的概率,提出一种自设计遗传算法对模型进行求解,其主要思想是利用粒子群算法搜索出可使遗传算法预期产生最好解的算法要素,并将其进行组合,从而产生新的遗传算法。采用新产生的遗传算法对模型继续求解,输出最好解。计算结果表明:与以往的鲁棒优化方法相比,弱鲁棒优化方法的最优解的保守性显著降低。     

Service design at diagnostic service centers

We study a service design problem in diagnostic service centers, call centers that provide medical advice to patients over the phone about what the appropriate course of action is, based on the caller's symptoms. Due to the tension between increased diagnostic accuracy and the increase in waiting times more in‐depth service requires, managers face a difficult decision in determining the optimal service depth to guide the diagnostic process. The specific problem we consider models the situation when the capacity (staffing level) at the center is fixed, and when the callers have both congestion‐ and noncongestion‐related costs relating to their call. We develop a queueing model incorporating these features and find that the optimal service depth can take one of two different structures, depending on factors such as the nurses' skill level and the maximum potential demand. Sensitivity analyses of the two optimal structures show that they are quite different. In some situations, it may (or may not) be optimal for the manager to try to expand the demand at the center, and increasing skill level may (or may not) increase congestion. © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

On competitive analysis for polling systems

Polling systems have been widely studied, however most of these studies focus on polling systems with renewal processes for arrivals and random variables for service times. There is a need driven by practical applications to study polling systems with arbitrary arrivals (not restricted to time-varying or in batches) and revealed service time upon a job's arrival. To address that need, our work considers a polling system with generic setting and for the first time provides the worst-case analysis for online scheduling policies in this system. We provide conditions for the existence of constant competitive ratios, and competitive lower bounds for general scheduling policies in polling systems. Our work also bridges the queueing and scheduling communities by proving the competitive ratios for several well-studied policies in the queueing literature, such as cyclic policies with exhaustive, gated or l-limited service disciplines for polling systems.     

混合遗传算法及其在运载火箭最优上升轨道设计中的应用

运载火箭最优上升轨道设计问题是一类终端时刻未定、终端约束苛刻的最优控制问题,经典算法求解这类问题时收敛性差、局部收敛等问题表现得比较突出。针对上述问题,将具有良好全局收敛性的遗传算法应用到运载火箭最优上升段设计问题求解中,为了提高遗传算法的收敛速度和克服早熟问题,结合遗传算法和单纯型算法的优点,设计了两种混合遗传算法。计算结果表明,所设计的混合遗传算法是求解复杂问题的有效全局优化方法,可以成功地解决一类终端时刻可变飞行器最优控制问题。     

基于改进人工蜂群算法的漏磁缺陷轮廓重构

漏磁缺陷重构是指由检测到的漏磁信号重构缺陷轮廓及参数,是实现漏磁反演的关键。将局部最优解和全局最优解引入到人工蜂群算法(Artificial Bee Colony Algorithm,ABC)中,提出了一种基于改进人工蜂群算法的缺陷重构模型。在该模型中,径向基函数神经网络作为前向模型求解漏磁信号,改进人工蜂群算法用于求解反演问题中的优化问题。将改进人工蜂群算法和基本人工蜂群算法作为反演算法进行了比较,实验结果表明,改进人工蜂群反演算法精度较高,速度较快,同时对实测信号具有鲁棒性,是一种有效可行的漏磁反演新方法。