Non zero-sum stochastic games in admission,service and routing control in queueing systems

The purpose of this paper is to investigate situations of non-cooperative dynamic control of queueing systems by two agents, having different objectives. The main part of the paper is devoted to analyzing a problem of an admission and a service (vacation) control. The admission controller has to decide whether to allow arrivals to occur. Once the queue empties, the server goes on vacation, and controls the vacations duration (according to the state and past history of the queue). The immediate costs for each controller are increasing in the number of customers, but no convexity assumptions are made. The controllers are shown to have a stationary equilibrium policy pair, for which each controller uses a stationary threshold type policy with randomization in at most one state. We then investigate a problem of a non-zero sum stochastic game between a router into several queues, and a second controller that allocates some extra service capacity to one of the queues. We establish the equilibrium of a policy pair for which the router uses the intuitive Join the shortest queue policy.     

Analysis of quota assignment and time block duration in multi-block appointment systems

The objective of this study is to propose performance evaluatorsand optimizers for the quota appointment system in many hospitalsand clinics used to smooth the patient flow. This type of queueingsystem with finite population and controlled arrivals is studiedon a single server with exponential service time. Given a targetwaiting time set by the hospital, the quota assignment givingthe minimum chance of underachievement in each time block isderived using a dynamic programming approach. This enables exactcalculations of performance measures of expected waiting time,server overtime and congestion measured in headcount. The optimaltime block duration, in addition to the quota assignment, isexamined using an extended dynamic programming formulation.Special cases of absentees, late arrivals and re-entry patientsare then incorporated into the basic model. Performance measuresare evaluated through two approaches, according to the prioritiesof treatment for the special cases.     

Structure-reversibility and departure functions of queueing networks with batch movements and state dependent routing

We consider characterizations of departure functions in Markovian queueing networks with batch movements and state-dependent routing in discrete-time and in continuous-time. For this purpose, the notion of structure-reversibility is introduced, which means that the time-reversed dynamics of a queueing network corresponds with the same type of queueing network. The notion is useful to derive a traffic equation. We also introduce a multi-source model, which means that there are different types of outside sources, to capture a wider range of applications. Characterizations of the departure functions are obtained for any routing mechanism of customers satisfying a recurrent condition. These results give a unified view to queueing network models with linear traffic equations. Furthermore, they enable us to consider new examples as well as show limited usages of this kind of queueing networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

Allocations of cold standbys to series and parallel systems with dependent components

In the context of industrial engineering, cold‐standby redundancies allocation strategy is usually adopted to improve the reliability of coherent systems. This paper investigates optimal allocation strategies of cold standbys for series and parallel systems comprised of dependent components with left/right tail weakly stochastic arrangement increasing lifetimes. For the case of heterogeneous and independent matched cold standbys, it is proved that better redundancies should be put in the nodes having weaker [better] components for series [parallel] systems. For the case of homogeneous and independent cold standbys, it is shown that more redundancies should be put in standby with weaker [better] components to enhance the reliability of series [parallel] systems. The results developed here generalize and extend those corresponding ones in the literature to the case of series and parallel systems with dependent components. Numerical examples are also presented to provide guidance for the practical use of our theoretical findings.     

Modeling a class of state-dependent routing in flexible manufacturing systems

We develop a closed queueing network model for flexible manufacturing systems (FMSs), where parts routing follows a probabilistic shortest-queue (PSQ) scheme, i.e. parts are routed to the shortest queue (or the most empty station) with the highest probability. We allow limited local buffer at each work station. We prove that with the PSQ routing, the Markovian queue-length process satisfies time reversibility and has a product-form equilibrium distribution. An algorithm is developed to compute the solutions to the model. The model can be used as a performance evaluation tool to study FMSs.     

不确定环境下多自主体系统的分布式估计与控制

多自主体系统是当前系统控制界研究的热点问题. 在实际中, 自主体系统通常并不是在理想的环境下执行任务, 而是面临多源头、多层次和多变化的各类不确定性因素的影响. 它们通过在微观层面上影响各自主体决策的正确性, 从而在宏观上对自主体系统的整体行为产生显著影响. 不确定性因素和多自主体系统分布式信息架构交互耦合, 给系统的设计与分析带来本质性困难. 本文围绕分布式估计与分布式控制问题, 研究在随机通信噪声、数据丢失、量化和系统未知结构参数等不确定因素影响下, 如何为各自主体设计更加鲁棒、更加有效的分布式估计算法及分布式控制律, 以实现全局估计与控制目标, 并对闭环系统性能进行系统分析.     

On the perturbation analysis of discrete-event dynamic systems

The paper describes a new approach to the analysis and optimization of discrete-event dynamic systems, such as queueing networks.Dedicated to G. LeitmannThe work reported in this paper was supported in part by ONR Contracts Nos. N00014-75-C-0648 and N00014-79-C-0776 and in part by NSF Grant No. NSF-ECS-82-13680.     

Markovian network processes: Congestion-dependent routing and processing

A Markovian network process describes the movement of discrete units among a set of nodes that process the units. There is considerable knowledge of such networks, often called queueing networks, in which the nodes operate independently and the routes of the units are independent. The focus of this study, in contrast, is on networks with dependent nodes and routings. Examples of dependencies are parallel processing across several nodes, blocking of transitions because of capacity constraints on nodes, alternate routing of units to avoid congestion, and accelerating or decelerating the processing rate at a node depending on downstream congestion. We introduce a general network process representing the numbers of units at the nodes and derive its equilibrium distribution. This distribution takes the form of a product of functions of vectors in which the arguments of the functions satisfy an interchangeability property. This new type of distribution may apply to other multi-variate processes as well. A basic idea in our approach is a linking of certain micro-level balance properties of the network routing to the processing rates at the nodes. The link is via routing-balance partitions of nodes that are inherent in any network. A byproduct of this approach is a general characterization of blocking of transitions without the restriction that the process is reversible, which had been a standard assumption. We also give necessary and sufficient conditions under which a unit moving in the network sees a time average for the unmoved units (called the MUSTA property). Finally, we discuss when certain flows between nodes in an open network are Poisson processes.This research was sponsored in part by Air Force Office of Scientific Research contract 84-0367.     

Cybernetic optimization by simulated annealing: Accelerating convergence by parallel processing and probabilistic feedback control

The convergence of the simulated annealing algorithm is accelerated by a probabilistic feedback control scheme. This scheme uses two or more parallel processors to solve the same or related combinatorial optimization problems and are coupled by a probabilistic measure of quality (PMQ). The PMQ is used to generate an error signal for use in feedback control. Control over the search process is achieved by using the error signal to modulate the temperature parameter. Other aspects of control theory, such as the system gain and its effects on system performance, are described. Theoretical and experimental results show that such a scheme increases the steadystate probability of the globally optimal solutions.     

Convexity and characterization of optimal policies in a dynamic routing problem

An infinite horizon, expected average cost, dynamic routing problem is formulated for a simple failure-prone queueing system, modelled as a continuous time, continuous state controlled stochastic process. We prove that the optimal average cost is independent of the initial state and that the cost-to-go functions of dynamic programming are convex. These results, together with a set of optimality conditions, lead to the conclusion that optimal policies are switching policies, characterized by a set of switching curves (or regions), each curve corresponding to a particular state of the nodes (servers).     

Structural results for the control of queueing systems using event-based dynamic programming

In this paper we study monotonicity results for optimal policies of various queueing and resource sharing models. The standard approach is to propagate, for each specific model, certain properties of the dynamic programming value function. We propose a unified treatment of these models by concentrating on the events and the form of the value function instead of on the value function itself. This is illustrated with the systematic treatment of one and two-dimensional models. This revised version was published online in June 2006 with corrections to the Cover Date.     

An efficient parallel processing optimal control scheme for a class of nonlinear composite systems

This article presents an efficient parallel processing approach for solving the optimal control problem of nonlinear composite systems. In this approach, the original high-order coupled nonlinear two-point boundary value problem (TPBVP) derived from the Pontryagin's maximum principle is first transformed into a sequence of lower-order decoupled linear time-invariant TPBVPs. Then, an optimal control law which consists of both feedback and forward terms is achieved by using the modal series method for the derived sequence. The feedback term specified by local states of each subsystem is determined by solving a matrix Riccati differential equation. The forward term for each subsystem derived from its local information is an infinite sum of adjoint vectors. The convergence analysis and parallel processing capability of the proposed approach are also provided. To achieve an accurate feedforward-feedback suboptimal control, we apply a fast iterative algorithm with low computational effort. Finally, some comparative results are included to illustrate the effectiveness of the proposed approach.     

Unrelated parallel machines scheduling with deteriorating jobs and resource dependent processing times

We consider unrelated parallel machines scheduling problems involving resource dependent (controllable) processing times and deteriorating jobs simultaneously, i.e., the actual processing time of a job is a function of its starting time and its resource allocation. Two generally resource consumption functions, the linear and convex resource, were investigated. The objective is to find the optimal sequence of jobs and the optimal resource allocation separately. This paper focus on the objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. If the number of unrelated parallel machines is a given constant, we show that the problems remain polynomially solvable under the proposed model.     

Stochastic petri net analysis of finite-population vacation queueing systems

We consider queueing systems in which the server occasionally takes a vacation of random duration. The vacation can be used to do additional work; it can also be a rest period. Several models of this problem have been analyzed in the past assuming that the population of the system is infinite. Similarly, it is generally assumed that the capacity of the system is infinite. In this paper we show how the finite-population system can be modeled by the stochastic Petri net. We also extend the model to the finite-capacity system. This research was sponsored by the SDIO Innovative Science and Technology Office and was managed by the Office of Naval Research under grant N3014-88-K-0623.     

Local and global optimization by parallel algorithms for MIMD systems

This paper describes an implementation on the Neptune system at Loughborough University of Sutti's parallel (MIMD) algorithm [1–3] and an analysis of its performance. Parallel asynchronous versions of Powell's method [6] and Price's algorithm [7] are proposed, designed for efficient implementation on MIMD systems.This work has been developed during the author's stay at the Numerical Optimization Centre, Hatfield Polytechnic, England.     

Optimal dynamic routing in Flexible Manufacturing Systems with limited buffers

An optimal routing policy is obtained for Flexible Manufacturing Systems (FMSs) with limited buffers at the work stations. This policy is used to effectively drive a robotic material handling system. The routing decisions are made by a supervising computer on a real-time basis in order to avoid any work station running out of inputs and to control the blocking of the material handling system. Using our model, general material handling times can be assumed. The optimal policy and several key performance measures are computed, following the problem formulation as a continuous-time, semi-Markovian decision process. Fast convergence and computational stability are ensured by the ergodic solution algorithm augmented to solve the functional equations of the renewal process. The solution algorithm was implemented, tested on an extensive range of problems regarding the structure and the performance of the optimal policy. Complex environments involving diverse processing times, as well as very limited buffer storage, were examined. The interaction between the allocation of buffer spaces to work stations, the structural properties of the optimal monotone (threshold-type) policy and the system performance are also investigated.     

Pooling through lateral transshipments in service parts systems

We study the inventory management problem of a service center operating in a decentralized service parts network. The service centers collaborate through inventory and service pooling, and through sharing information on the inventory status. Upon demand arrival, a service center may request a part from the other center, in which case a payment is made. Under this competitive and collaborative environment, we first characterize the optimal operating policy of an individual service center. Through computational analysis we identify the conditions under which pooling is most beneficial to the service center, and make an assessment of different pooling strategies which are commonly adopted in practice and in the literature. Finally, we analyze the effect of interaction between the centers on the benefit of pooling.     

Maximizing throughput in finite-source parallel queue systems

Motivated by the dispatching of trucks to shovels in surface mines, we study optimal routing in a Markovian finite-source, multi-server queueing system with heterogeneous servers, each with a separate queue. We formulate the problem of routing customers to servers to maximize the system throughput as a Markov Decision Process. When the servers are homogeneous, we demonstrate that the Shortest Queue policy is optimal, and when the servers are heterogeneous, we partially characterize the optimal policy and present a near-optimal and simple-to-implement policy. We use the model to illustrate the substantial benefits of pooling, by comparing it to the permanent assignment of customers to servers.     

Comparisons of series and parallel systems with components sharing the same copula

The paper is devoted to study stochastic comparisons of series and parallel systems with vectors of component lifetimes sharing the same copula. We show that, under some conditions on the common copula, the series system with heterogeneous components is worse than the series system with homogeneous components having a common reliability function, which is equal to the average of the reliability functions of the heterogeneous components. However, we show that this property is not necessarily true for arbitrary copulas. We obtain similar properties for parallel systems and for general coherent systems. For these purposes, we introduce in our analysis the notion of the mean function of a copula. Copyright © 2009 John Wiley & Sons, Ltd.     

Probabilistic diversification and intensification in local search for vehicle routing

This article presents a probabilistic technique to diversify, intensify, and parallelize a local search adapted for solving vehicle routing problems. This technique may be applied to a very wide variety of vehicle routing problems and local searches. It is shown that efficient first-level tabu searches for vehicle routing problems may be significantly improved with this technique. Moreover, the solutions produced by this technique may often be improved by a postoptimization technique presented in this article, too. The solutions of nearly forty problem instances of the literature have been improved.