A Practical Optimisation Technique for a Queueing System

A scheduling problem in an outpatient clinic is considered. First the system is represented by means of a simple queueing model. The problem of minimising the patients' total queueing time is then formulated as a non-linear program and solved by applying the Kuhn-Tucker conditions. The results obtained enable the person who manages the appointment system to allocate appointment dates to patients who have different priorities.     

Queueing Models for Out-Patient Appointment Systems — a Case Study

Some recent research on queueing models is successfully applied to the problem of designing an appropriate appointment system for the out-patient department at the Royal Lancaster Infirmary. Although it is acknowledged that improving appointment systems is not simply a modelling problem, it is nevertheless argued that the model used here could be an effective tool in local studies.     

Minimum Required Local Storages of an Automated Assembly System

An optimal strategy for selection of the required local storages of the workstations and transporter stations of a finite capacity flexible assembly line system is presented while controlling the bottleneck problem. For this purpose, a mixed non-Markovian queueing network with infinite capacity nodes is presented to model its performance, a stochastic optimization model is provided and a heuristic algorithm is developed for solving it. Finally, an example is presented and the approximation results are compared with those from a simulation study.     

A large closed queueing network with autonomous service and bottleneck

This paper studies the queue-length process in a closed Jackson-type queueing network with the large number N of homogeneous customers by methods of the theory of martingales and by the up- and down-crossing method. The network considered here consists of a central node (hub), being an infinite-server queueing system with exponentially distributed service times, and k single-server satellite stations (nodes) with generally distributed service times with rates depending on the value N. The service mechanism of these k satellite stations is autonomous, i.e., every satellite server j serves the customers only at random instants that form a strictly stationary and ergodic sequence of random variables. Assuming that the first k-1 satellite stations operate in light usage regime the paper considers the cases where the kth satellite station is a bottleneck node. The approach of the paper is based both on development of the method from the paper by Kogan and Liptser [16], where a Markovian version of this model has been studied, and on development of the up- and down-crossing method. This revised version was published online in June 2006 with corrections to the Cover Date.     

Staffing a service system with appointment-based customer arrivals

Appointment systems are widely used to facilitate customers’ access to services in many industries such as healthcare. A number of studies have taken a queueing approach to analyse service systems and facilitate managerial decisions on staffing requirements by assuming independent and stationary customer arrivals. This paper is motivated by the observation that the queueing-based method shows relatively poor performance when customers arrive according to their appointment times. Because customer arrivals are dependent on their appointment times, this study, unlike queueing-based methods, conducts a detailed analysis of appointment-based customer arrivals instead of making steady-state assumptions. We develop a new model that captures the characteristics of appointment-based customer arrivals and computes the probability of transient system states. Through the use of this model, which relaxes stationary and independent assumptions, we propose a heuristic algorithm that determines staffing requirements with aims to minimizing staff-hours while satisfying a target service level. The simulation results show that the proposed method outperforms the queueing-based method.     

Topological network design of general,finite, multi-server queueing networks

The topological network design of general service, finite waiting room, multi-server queueing networks is a complex optimization problem. Series, merge, and split topologies are examined using an approximation method to estimate the performance of these queueing networks and an iterative search methodology to find the optimal buffer allocation within the network. The coefficient of variation is shown to be a significant factor in the buffer allocation for multiple servers in uniform and bottleneck server networks. Extensive computational results are included to illustrate the symmetries and asymmetries in the buffer patterns which emerge from the series, merge, and splitting topologies.     

Block appointment systems for outpatient clinics with multiple doctors

Studies of appointment systems have to some extent led to a wide acceptance of individual or block appointment schemes in private practice and outpatient clinics. Most of the studies assume there is one punctual doctor in a clinic, which is often not the case in reality. Motivated by observations of actual clinic operations, we develop a block appointment system for clinic operations with multiple random arriving doctors. Through extensive simulation studies, we identify properties shared by the best appointment schedules. With these properties we can design a scheme based on simulation search that provides the optimal schedule for a given scheduling environment in an acceptable computation time. A simple (suboptimal) appointment rule is also proposed.     

Queueing models for appointment-driven systems

Many service systems are appointment-driven. In such systems, customers make an appointment and join an external queue (also referred to as the “waiting list”). At the appointed date, the customer arrives at the service facility, joins an internal queue and receives service during a service session. After service, the customer leaves the system. Important measures of interest include the size of the waiting list, the waiting time at the service facility and server overtime. These performance measures may support strategic decision making concerning server capacity (e.g. how often, when and for how long should a server be online). We develop a new model to assess these performance measures. The model is a combination of a vacation queueing system and an appointment system.     

The outpatient appointment system: Design of a simulation study

This paper describes the model-construction of a simulation study. The purpose of this study was to produce a general method for determining a suitable appointment system for the clinics in the outpatient department of a hospital. The original model contained 11 variables. Investigation of the influence of each variable on patient's wainting-time and doctor's idle-time showed that a considerable reduction in the number of variables could be achieved. Only 5 variables were finally left in the stimulation.The use of the results of this study in a real-life clinic situation is discussed elsewhere.     

Some notes on the reduction of network dimensionality in nested open queueing networks

In this paper, we study an open and nested tandem queueing network, where the population constraint within each subnetwork is controlled by a semaphore queue. The total number of customers that may be present in the subnetwork can not exceed a given value. Each node has a constant service time and the arrival process to the queueing network follows an arbitrary distribution.A major characteristic of this queueing network is that the low layer flow is halted by the state of the high layer. We develop a simple and equivalent queueing network that has the same performance characteristics as the original queueing network. Using this model, the waiting time on the queueing network can be easily derived. It is interesting to see how the simplification process can be applied to multi-layered queueing network.     

A simulation tool to evaluate the performance of finite-source queueing models

This paper deals with a software tool to evaluate the main characteristics of a nonhomogeneous finite-source queueing model to describe the performance of a multi-terminal system subject to random breakdowns under FIFO, priority processor sharing, and polling service disciplines. The model studied here is actually a closed queueing network network with three nonindependent service stations (CPU, terminals, and repairman), and a finite number of customers (jobs), which have different service rates at the service stations. The aim of this paper is to introduce the FQM (finite-source queueing model) program package, which was developed at the Institute of Mathematics and Informatics of Lajos Kossuth University in Debrecen, Hungary, and to investigate the performance of the above-mentioned finite-source queueing models. At the end we give a sample result to illustrate the problem in question. Supported by the Hungarian National Foundation for Scientific Research (grant Nos. OTKA T014974/95 and T016933/95). Proceedings of the Seminar on Stability Problems for Stochastic Models, Vologda, Russia, 1998, Part I.     

一类可变服务率的车辆排队特征分析

本文提出一类服务率随排队车辆数变化的单通道车辆排队模型 ;运用排队理论 ,分析了一种经常可以在高速公路收费站、加油站、平面交叉口等场所看到的随机服务现象 ,充分考虑了服务率与车辆排队数之间的相关特性 ,得出了较切合实际的车辆排队模型 ,给出了各参数指标的数学表达式 ,并且具体实例加以比较说明     

Approximating Unreliable Queueing Networks Under the Assumption of Exponentiality

This paper deals with the approximate analysis and application of an unreliable closed queueing network to model the performance of a flexible manufacturing system. The service stations in the network are subject to breakdown and repair when active. An exact equivalent network is represented with two-stage Coxian service stations. We approximate the equivalent network by assuming exponentiality for the service completion time, which has a two-stage Coxian distribution. We validate the approximation for a wide range of model parameters and demonstrate the robustness of queueing network formulae to the assumption of exponentiality.     

A two-server queueing system with periodic and credit-based server availabilities

A discrete-time, two-server queueing system is studied in this paper. The service time of a customer (cell) is fixed and equal to one time unit. Server 1 provides for periodic service of the queue (periodT). Server 2 provides for service only when server 1 is unavailable and provided that the associated service credit is nonzero. The resulting system is shown to model the queueing behavior of a network user which is subject to traffic regulation for congestion avoidance in high speed ATM networks. A general methodology is developed for the study of this queueing system, based on renewal theory. The dimensionality of the developed model is independent ofT;T increases with the network speed. The cell loss probabilities are computed in the case of finite capacity queue.Research supported by the National Science Foundation under grant NCR-9011962.     

网络环境下的医院门诊挂号预约系统改善研究

本文对改善挂号预约系统的模型进行了分析探索。根据病人的自报病情信息及医疗经验信息,通过量化的方法,对挂号预约阶段病人对疾病分类和症状程度划分进行了研究。研究结果有助于改善预约挂号系统。新的方法有助于解决挂号难的问题、有助于医疗服务质量的提高、并且有助于医疗资源的优化利用。     

A logistics problem: a non-markovian queueing network model and algorithm

In this paper, a stochastic version of the classical deterministic balanced single commodity capacitated transportation network problem is presented. In this model, each arc of the network connects a supply node to a demand node and the flow of units forming along each arc of the network forms a stochastic process (i.e.G/M/1 queueing system with generally distributed interarrival time, a Markovian server, a single server, infinite capacity, and the first come first served queueing discipline). In this model, the total transportation cost is minimized such that the total supply rate is equal to the total demand rate, and the resulting probability of finding excessive congestion along each arc (i.e., the resulting probability of finding congestion inside the queueing system formed along each arc in excess of a fixed number) is equal to a desirable value     

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.     

Queueing network modelling of flexible manufacturing system using mean value analysis

In the present investigation, we develop queueing model for the performance prediction of flexible manufacturing systems (FMSs) with a multiple discrete material-handling devices (MHD). An iterative method has been suggested using mean value analysis (MVA) for the state-dependent routing. Two queueing network models are considered to determine the material-handling device interference. In the first one, we model the interference from the MHD by inflating the station service times but neglect queueing at the MHD. In another network, the queueing for the MHD is taken into consideration. The performance of FMS configuration is obtained by iterating between two networks. The suggested algorithms demonstrate better results than the algorithm used by earlier workers for single MHD. Some performance indices viz. throughput, mean service time, mean waiting time, etc. are obtained. Numerical results are provided to highlight the effect of the system parameters on performance indices, which are further evaluated by using neuro-fuzzy controller system to validate the tactability of soft computing approach.     

A characterisation of (max,+)-linear queueing systems

The (max,+)-algebra has been successfully applied to many areas of queueing theory, like stability analysis and ergodic theory. These results are mainly based on two ingredients: (1) a (max,+)-linear model of the time dynamic of the system under consideration, and (2) the time-invariance of the structure of the (max,+)-model. Unfortunately, (max,+)-linearity is a purely algebraic concept and it is by no means immediate if a queueing network admits a (max,+)-linear representation satisfying (1) and (2). In this paper we derive the condition a queueing network must meet if it is to have a (max,+)-linear representation. In particular, we study (max,+)-linear systems with time-invariant transition structures. For this class of systems, we find a surprisingly simple necessary and sufficient condition for (max,+)-linearity, based on the flow of customers through the network. This revised version was published online in June 2006 with corrections to the Cover Date.     

考虑存在取消预约情形的门诊预约能力分配策略

在现实的门诊预约问题中,已经预约的患者在接收医疗服务之前,有可能取消先前的预约,这会对医院的收益造成负面影响,如何在考虑患者存在取消预约的情形下,设计合理有效的能力分配策略来保证医院的收益,是一个值得研究的问题.本文针对具有提前预约和当天预约的门诊预约能力分配问题,在考虑提前预约患者可能存在取消预约行为的情形下,提出了一种提前预约患者和当天预约患者的最优能力分配策略。文中首先以医院的期望收益最大作为决策目标,建立了存在取消预约患者的医疗预约问题的马尔科夫过程模型,并给出了该模型的相关性质;基于所建立模型的特征,证明了对于任意的提前预约时段,存在提前预约患者的最佳数量,进而给出了提前预约患者和当天预约患者的最优能力分配策略以及确定该策略的精确算法;最后,通过数值试验说明了本文所提出的能力分配策略的适用性和有效性。