Search

• A chat service with actively involved customers and repeating interactions is studied. • The capacity of parallel chats and the server's response effort are derived. • A queueing game for a dual-channel system of chat service and call center is analyzed. • Customer bounded rationality is considered. Many service systems in various type of industry provide services via chat technologies. This type of service system is characterized by an interesting combination of properties. First, the customer is actively involved in service execution, since the service is comprised of responses of the server and the customer to each other, until the customer's request is satisfied. In addition, in such a system, the service can be provided by a single server in a parallel manner to a number of customers. Motivated by these and others interesting properties of the chat service, we formulate and analyze the stochastic queueing system as a two-dimensional quasi-birth-and-death process and derive its steady-state probabilities using matrix geometric methods. By means of economic analysis, we provide a scheme for deriving the optimal capacity of parallel chats and the optimal response effort that should be made by the server, considering that higher effort lengthens the response time but increases the probability of successful service completion. We next investigate a queueing game that considers a multi-channel service system consisting of a chat service and a traditional multi-server call center, and we consider strategic customers under both a centralized and a decentralized scenario. We show that competition between service channels may lead to lower service utilization even though customers enjoy higher expected utility. Finally, customer bounded rationality is considered and it is shown that customers who are less rational may enjoy higher utility. Sensitivity analyses are conducted for all scenarios. [ABSTRACT FROM AUTHOR]

We develop new techniques involving group symmetries and complex analysis to obtain exact solutions for the transition probabilities of the M/M/1/k queueing process. These methods are based on the underlying Markovian structure of these random processes and do not involve any generating functions, Laplace transforms, or advanced special functions. Our techniques exploit the intrinsic group symmetries for both the state spaces and the matrix generators of the Markov processes related to the M/M/1/k queue. These results complement and extend the previous transient solutions given by Takács (Introduction to the theory of queues. University texts in the mathematical sciences, Oxford University Press, New York, 1962). Much of the inspiration for this work comes from viewing this queueing process as a fundamental Markovian model for the dynamics of a bike sharing station. The exact transient analysis for a related stopped version of this process can be used to address fundamental decision-making issues for managing bike-sharing services. [ABSTRACT FROM AUTHOR]

We explore settings where it is necessary (due to physical or operational constraints) or desirable (due to synergies or ease of implementation) to assign resources to tasks in a synchronous manner. We model the system as a queueing network with flexible servers and introduce the notion of a configuration to address the synchronous assignment of servers. This allows for a unified approach to determine the effects of resource synchronization, covering a wide range of problems in the literature. The maximal capacity of the system is given by the solution of a linear programming problem that also provides the optimal fractions of time the servers should spend in different configurations. This is used as a basis for constructing policies that have capacity arbitrarily close to the maximal capacity. We contrast synchronous server assignment with an asynchronous approach (focusing on independently scheduling individual servers rather than configurations) and show that synchronous server assignment is attractive with respect to applicability (it can capture constraints on server assignment and synergies among servers), implementation (it may have significantly fewer combinations of server allocations), and capacity (when both are applicable, asynchronous and synchronous server assignment will yield the same maximal capacity). Finally, we illustrate our modeling framework using several examples. [ABSTRACT FROM AUTHOR]

The present paper analyses a retrial queueing system with Catastrophe. Primary and secondary customers follow Poisson processes. Inter arrival and service times are Exponentially distributed. Catastrophe occurs on a busy server and follows Poisson process. The server is sent for repair after its failure. The repair times are also Exponentially distributed. Steady state and time dependent solutions for number of customers in the system when the server is idle or busy are obtained. The probability of the server being under repair is obtained. Some performance measures are also evaluated. Numerical results are obtained and represented graphically. [ABSTRACT FROM AUTHOR]

We study a quantum switch that distributes tripartite entangled states to sets of users. The entanglement switching process requires two steps: First, each user attempts to generate bipartite entanglement between itself and the switch, and second, the switch performs local operations and a measurement to create multipartite entanglement for a set of three users. In this work, we study a simple variant of this system, wherein the switch has infinite memory and the links that connect the users to the switch are identical. This problem formulation is of interest to several distributed quantum applications, while the technical aspects of this work result in new contributions within queueing theory. The state of the system is modeled as continuous-time Markov chain (CTMC), and performance metrics of interest (probability of an empty system, switch capacity, expectation, and variance of the number of qubit-pairs stored) are computed via the solution of a two-dimensional functional equation obtained by reducing it to a boundary value problem on a closed curve. This work is a follow-up of Nain et al. (Proc ACM Measure Anal Comput Syst(POMACS) 4, 2020) where a switch distributing entangled multipartite states to sets of users was studied, but only the switch capacity and the expected number of stored qubits were derived. [ABSTRACT FROM AUTHOR]

Many infrastructure managers have the goal to increase the capacity of their railway infrastructure due to an increasing demand. While methods for performance calculations of railway line infrastructure are already well established, the determination of railway junction capacity remains a challenge. This work utilizes the concept of queueing theory to develop a method for the capacity calculation of railway junctions, solely depending on their infrastructure layout along with arrival and service rates. The implementation of the introduced approach is based on probabilistic model-checking. It can be used to decide which infrastructure layout to build, i.e. whether an overpass for the analysed railway junction is needed. The developed method addresses the need for fast and reliable timetable-independent railway junction capacity evaluation, catering specifically to the long-term strategic planning of junction infrastructure. • Timetable independent capacity analysis of railway junctions. • Formulation as a queueing system utilizing Continuous-Time Markov Chains. • Application of state-of-the-art probabilistic model-checking to estimate performance indicators. • Decision support for infrastructure managers when planning required infrastructure layouts. • Comparison with classical methods determining the capacity occupation of railway infrastructure. [ABSTRACT FROM AUTHOR]

Queueing systems with batch Markovian arrival process (BMAP) have paramount applications in the domain of wireless communication. The BMAP has been used to model the superposition of video sources and to approximate the super-position of data, voice and video traffic. This article analyzes an infinite-buffer generally distributed batch-service queue with BMAP, general bulk service (a, b) rule and batch-size-dependent service time. In this proposed analysis, we mainly focus on deriving the bivariate vector generating function of queue and server content distribution together at departure epoch using supplementary variable technique. The mathematical procedure for the complete extraction of distribution at departure epoch has been discussed and using those extracted probabilities, we achieve the queue and server content distribution at arbitrary epoch. Finally, numerical illustrations have been carried out in order to make a deep insight to the readers which contains deterministic as well as phase-type service time distributions. [ABSTRACT FROM AUTHOR]

We consider an infinite waiting space G I / M a , b / 1 queueing system in which customers arrive according to a renewal process. The server serves the customers in batches under general bulk-service rule. The successive service times of batches are mutually independent and have a common exponential distribution. To obtain the queue-length distributions at prearrival and random epochs, we have used the displacement operator which assists to solve simultaneous non-homogeneous difference equations. An analytically simple and computationally efficient procedures have developed to compute the waiting-time distribution of an arrival customer. Our formula to determine the waiting-time distribution is also useful even when multiple poles occur in the Laplace-Stieltjes transform of the interarrival time distribution. We have determined closed-form analytical expression for the distribution of size of a service batch of an arrived customer. We also have derived the results of some particular well-known queueing models from our model. Some numerical results are provided in the form of tables for a variety of interarrival-time distributions to demonstrate the variation of performance measures of the system. [ABSTRACT FROM AUTHOR]

Extending the results of Kruk (Queueing theory and network applications. QTNA 2019. Lecture notes in computer science, vol 11688. Springer, Cham, pp 263–275, 2019), we derive heavy traffic limit theorems for a single server, single customer class queue in which the server uses the Shortest Remaining Processing Time (SRPT) policy from heavy traffic limits for the corresponding Earliest Deadline First queueing systems. Our analysis allows for correlated customer inter-arrival and service times and heavy-tailed inter-arrival and service time distributions, as long as the corresponding stochastic primitive processes converge weakly to continuous limits under heavy traffic scaling. Our approach yields simple, concise justifications and new insights for SRPT heavy traffic limit theorems of Gromoll et al. (Stoch Syst 1(1):1–16, 2011). Corresponding results for the longest remaining processing time policy are also provided. [ABSTRACT FROM AUTHOR]

Present paper discusses a two-state retrial queueing model with feedback and balking. If a customer on arrival finds the server free it is served immediately. Else either it joins the retrial orbit as a secondary customer or balks from the system due to impatience. Primary and secondary arrivals both follow Poisson process. If the customer feels unsatisfied after service, it may join the orbit as a feedback customer. Service times follow Exponential distribution. The transient state probabilities for exact number of arrivals and departures when the server is busy or idle are obtained by solving difference-differential equations. Numerical solution is obtained and presented graphically. [ABSTRACT FROM AUTHOR]

This paper investigates a single server queueing system with an infinite waiting space in which customers are arrived according to renewal process and are served in batches of random size under continuous-time batch Markovian service process. We first determine the vector probability generating function of the system-length distribution at pre-arrival epoch. The system-length distribution at pre-arrival epoch is extracted in terms of zeros of the related characteristic polynomial of the vector probability generating function. By the Markov renewal theory argument, we determine the system-length distribution at random epoch. We also derive the system-length distribution at post-departure epoch using the 'rate in = rate out' argument. Finally, some numerical results are exhibited for different inter-arrival time distribution to demonstrate the system performance measures and correctness of analytical results. [ABSTRACT FROM AUTHOR]

Congestion-aware scheduling in case of downlink cellular communication has ignored the distribution of diverse content to different clients with heterogeneous secrecy requirements. Other possible application areas that encounter the preceding issue are secure offloading in mobile-edge computing, and vehicular communication. In this paper, we extend the work in Arvanitaki et al. (SN Comput Sci 1(1):53, 2019) by taking into consideration congestion and random access. Specifically, we study a two-user congestion-aware broadcast channel with heterogeneous traffic and different security requirements. We consider two randomized policies for selecting which packets to transmit, one is congestion-aware by taking into consideration the queue size, whereas the other one is congestion-agnostic. We analyse the throughput and the delay performance under two decoding schemes at the receivers, and provide insights into their relative security performance and into how congestion control at the queue holding confidential information can help decrease the average delay per packet. We show that the congestion-aware policy provides better delay, throughput, and secrecy performance for large arrival packet probabilities at the queue holding the confidential information. The derived results also take account of the self-interference caused at the receiver for whom confidential data is intended due to its full-duplex operation while jamming the communication at the other user. Finally, for two decoding schemes, we formulate our problems in terms of multi-objective optimization, which allows for finding a trade-off between the average packet delay for packets intended for the legitimate user and the throughput for the other user under congestion-aware policy. [ABSTRACT FROM AUTHOR]

Accurate modeling of viral outbreaks in living populations and computer networks is a prominent research field. Many researchers are in search for simple and realistic models to manage preventive resources and implement effective measures against hazardous circumstances. The ongoing Covid-19 pandemic has revealed the fact about deficiencies in health resource planning of some countries having relatively high case count and death toll. A unique epidemic model incorporating stochastic processes and queuing theory is presented, which was evaluated by computer simulation using pre-processed data obtained from an urban clinic providing family health services. Covid-19 data from a local corona-center was used as the initial model parameters (e.g. R 0 , infection rate, local population size, number of contacts with infected individuals, and recovery rate). A long–run trend analysis for 1 year was simulated. The results fit well to the current case data of the sample corona center. Effective preventive and reactive resource planning basically depends on accurately designed models, tools, and techniques needed for the prediction of feature threats, risks, and mitigation costs. In order to sufficiently analyze the transmission and recovery dynamics of epidemics it is important to choose concise mathematical models. Hence, a unique stochastic modeling approach tied to queueing theory and computer simulation has been chosen. The methods used here can also serve as a guidance for accurate modeling and classification of stages (or compartments) of epidemics in general. [ABSTRACT FROM AUTHOR]

This paper treats an M/G/1 queue with retrial customers due to server vacation, which can be used to model a hospital service system. When an arriving customer finds the server on vacation at his arrival epoch, he either enters the retrial group with probability p or leaves the system with probability 1 - p. Otherwise, the new arriving customer begins his service immediately if the server is idle upon his arrival or joins the original queue with infinite capacity under FCFS if the sever is busy at his arrival epoch. First, we develop the steady-state analysis by the supplementary variable method and the generating function approach, and give some important performance measures. Moreover, we obtain the Laplace-Stieltjes transform of the sojourn time in the system of an arbitrary customer and prove that the Little's law still holds in our model. Finally, sensitivity analysis and optimal joining policy are given for illustrative purpose. [ABSTRACT FROM AUTHOR]

The common queueing problem has always focused on domestic and industrialized activities. Various improved models of queueing theory are widely used to solve problems. The aim of this paper is to deduce the exact solution of Bogoyavlenskii equation via direct extended modified algebraic method. In addition, we apply it to determine the upper and lower bounds through the semidefinite optimization packages software (SeDuMi). The suggested model indicated strong bounds in reasonable times, we obtain a definite value of u 0 = 1 1. 8 7 6 of the function u (x) over [ 0 , 1 ] where N = 2 0 in a time duration less than 60 s and a maximum value of u 0 = 2 4. 9 8 7 where N = 5 0 in a time frame of approximately 7 min. This study enriches the theoretical optimization queueing network and provides an analysis and decision making method for perfecting the theory. [ABSTRACT FROM AUTHOR]

In this paper, we present an analytical framework for the performance evaluation of a pre-emptive priority scheduler in multi-resource networks, like those using Orthogonal Frequency Division Multiple Access (OFDMA). We focus on Quality of Service (QoS)-guaranteed traffic for which QoS is guaranteed to individual users by restricting the number of admitted users. For this, the QoS-constrained capacity, in terms of the number of supported users, needs to be ascertained a priori. The QoS-constrained capacity is a function of users' QoS requirements, channel conditions, and radio resource allocation algorithms, which in this work is the pre-emptive priority scheduler. It is, thus, a variable quantity and mostly obtained using time-consuming offline computer simulations. Mathematical models, on the other hand, are timely and accurate, allowing the capacity to be derived in real-time as a function of the current network configuration. Existing works on mathematical modelling of pre-emptive priority schedulers have mostly focussed on single servers or multiple servers where a single server is assigned to each user. In contrast, OFDMA networks have multiple radio resources, i.e., multiple servers and each user may need more than one radio resource for a single packet transmission, i.e. it is a multi-resource system, which has been accounted for in this paper. We classify the users based on their resource requirements and model the pre-emptive priority scheduler as a multi-class, multi-server, multi-resource, non-work conserving queueing system. We derive its QoS metrics like average delay, packet drop probability, throughput, etc., from its continuous-time Markov Chain. We then use the derived QoS metrics to obtain the QoS-constrained capacity and design a threshold based predictive call admission control unit. We have validated the results using extensive discrete event simulations. [ABSTRACT FROM AUTHOR]

A retrial queuing system with a single server is investigated in this paper. The server is subject to random breakdowns. The number of customers is finite and collision may take place. A collision occurs when a customer arrives to the busy server. In case of a collision both customers involved in the collision are sent back to the orbit. From the orbit the customers retry their requests after a random waiting time. The server can be down due to a failure. During the failed period the arriving customers are sent to the orbit, as well. The novelty of this analysis is the impatient behaviour of the customers. A customer waiting in the orbit may leave it after a random waiting time. The requests of these customers will not be served. All the random variables included in the model construction are assumed to be exponentially distributed and independent from each other. The impatient property makes the model more complex, so the derivation of a direct algorithmic solution (which was provided for the non-impatient case) is difficult. For numerical calculations the MOSEL-2 tool can be used. This tool solves the Kolmogorov system equations, and from the resulting steady-state probabilities various system characteristics and performance measures can be calculated, i.e. mean response time, mean waiting time in the orbit, utilization of the server, probability of the unserved impatient requests. Principally the effect of the impatient property is investigated in these results, which are presented graphically, as well. [ABSTRACT FROM AUTHOR]

Stochastic kriging is a popular metamodeling technique to approximate computationally expensive simulation models. However, it typically treats the simulation model as a black box in practice and often fails to capture the highly nonlinear response surfaces that arise from queueing simulations.We propose a simple, effective approach to improve the performance of stochastic kriging by incorporating stylized queueing models that contain useful information about the shape of the response surface. We provide several statistical tools to measure the usefulness of the incorporated stylized models. We show that even a relatively crude stylized model can substantially improve the prediction accuracy of stochastic kriging. [ABSTRACT FROM AUTHOR]

This paper considers an M/G/1 queue with the following vacation discipline. The server takes a vacation as soon as it has served a certain amount of work since the end of the previous vacation. If the system becomes empty before the server has completed this amount of work, then it stays idle until the next customer arrival and then becomes active again. Such a vacation discipline arises, for example, in the maintenance of production systems, where machines or equipment mainly degrade while being operational. We derive an explicit expression for the distribution of the time it takes until the prespecified amount of work has been served. For the case the total amount of work till vacation is exponentially distributed, we derive the transforms of the steady-state workload at various epochs, busy period, waiting time, sojourn time, and queue length distributions. [ABSTRACT FROM AUTHOR]

We introduce a stochastic orienteering problem on a network of queues in which the traveler must arrive and enter service at locations within the respective time windows to collect rewards, but the traveler may experience stochastic wait time at each location before service can begin. To maximize the expected rewards collected, the traveler must determine which locations to visit and how long to wait in queues at each location. We formally model the problem as a Markov decision process with the objective of maximizing the expected collected rewards. We investigate the existence of optimal control limits and examine conditions under which certain actions cannot be optimal. To solve the problem, we propose an approximate dynamic programming approach based on rollout algorithms. The method introduces a two-stage heuristic estimation that we refer to as compound rollout. In the first stage, the algorithm decides whether to stay at the current location or go to another location. If departing the current location, it chooses the next location in the second stage. We demonstrate the value of our modeling and solution approaches by comparing the dynamic policies to a-priori-route solutions with recourse actions. [ABSTRACT FROM AUTHOR]

This paper considers a single-server queueing model in which the customers are served in batches of varying size depending on predetermined thresholds as well as available inventory. There is a finite buffer for the inventory and the service of every customer requires an inventory item. An ( s, S) -type inventory system is used for the models considered in this paper. Initially, the model is studied in detail using the matrix-analytic method by assuming all the underlying random variables to be exponentially distributed. Thereafter, an outline of the model in a more general set up is also presented. Due to complexity of the model when more general assumptions are made on the underlying random variables, simulation is opted after a satisfactory validation with the analytic counterpart of the exponential model. Finally, some illustrative numerical examples are also presented to accomplish our analysis. [ABSTRACT FROM AUTHOR]

In this paper, we consider the integrated planning of resources in a service maintenance logistics system in which spare parts supply and service engineers deployment are considered simultaneously. The objective is to determine close-to-optimal stock levels as well as the number of service engineers that minimize the total average costs under a maximum total average waiting time constraint. When a failure occurs, a spare part and a service engineer are requested for the repair call. In case of a stock-out at spare parts inventory, the repair call will be satisfied entirely via an emergency channel with a fast replenishment time but at a high cost. However, if the requested spare part is in stock, the backlogging policy is followed for engineers. We model the problem as a queueing network. An exact method and two approximations for the evaluation of a given policy are presented. We exploit evaluation methods in a greedy heuristic procedure to optimize this integrated planning. In a numerical study, we show that for problems with more than five types of spare parts it is preferable to use approximate evaluations as they become significantly faster than exact evaluation. Moreover, approximation errors decrease as problems get larger. Furthermore, we test how the greedy optimization heuristic performs compared to other discrete search algorithms in terms of total costs and computation times. Finally, in a rather large case study, we show that we may incur up to 27% cost savings when using the integrated planning as compared to a separated optimization. [ABSTRACT FROM AUTHOR]

A queueing model with catastrophes and delayed action is studied in this paper. This delayed action could be in the form of protecting or removing all the customers that are in the system based on the outcome of two random clocks which are simultaneously activated upon the occurrence of a catastrophic event. Assuming the customers to arrive according to a versatile Markovian point process to a single server system, the service times to be of phase type, and all other underlying random variables to be exponentially distributed, we use matrix-analytic methods to study the delayed catastrophic model in steady-state. Needed expressions for the number in the system as well as the waiting time distributions are derived along with a discussion on some special cases of this model. Detailed illustrative examples are presented. [ABSTRACT FROM AUTHOR]

In this paper, we present a comparative study on the total revenue generated with pre-emptive and non pre-emptive priority scheduler for a fairly generic problem of pricing the server’s surplus capacity in a single server Markovian queue. The specific problem is to optimally price the server’s surplus capacity by introducing a new class of customers (secondary class) without affecting the pre-specified service level of its current customers (primary class) when pre-emption is allowed. Pre-emptive scheduling is used in various applications. First, a finite step algorithm is proposed to obtain global optimal operating and pricing parameters for this problem. These optimal operating and pricing parameters constitute a unique Nash equilibrium in a certain two player non cooperative game. We then describe the range of service level where pre-emptive scheduling gives feasible solution and generates some revenue while non pre-emptive scheduling has infeasible solution. Further, some complementary conditions are identified to compare revenue analytically for certain range of service level where strict priority to secondary class is optimal. Our computational examples show that the complementary conditions adjust in such a way that pre-emptive scheduling always generates more revenue. Theoretical analysis is found to be intractable for the range of service level when pure dynamic policy is optimal. Hence, extensive numerical examples are presented to describe different instances. It is noted in numerical examples that pre-emptive scheduling generates at least as much revenue as non pre-emptive scheduling. A certain range of service level is identified where improvement in revenue is quite significant. [ABSTRACT FROM AUTHOR]

The goal of this paper is to provide a model that is an extension of classic scheduling problems for a tandem queueing system by including customer impatience. In such scenarios, the server(s) must balance abandonments from each phase of service with the need to prioritize higher reward customers. This presents an interesting challenge since the trade-off between the cost of abandonments and revenue maximization is not at all clear. As a result of customer abandonments, traditional solution techniques are not available. In particular, uniformization is not possible since the transition rates are unbounded. We do our analysis in continuous time, using the continuous-time Markov decision process framework to discern simple relationships of the value functions depending on the starting state. We then use sample path arguments to analyze the structure of the optimal policy. We provide conditions under which an optimal policy is nonidling and never splits servers (except to avoid idling). We then consider the single-server model as a proxy for the decision problem when there are more customers at each station than there are servers. In this case, we provide conditions under which it is optimal to prioritize each station. [ABSTRACT FROM AUTHOR]

We investigate the staffing problem at Peace Arch, one of the major U.S.–Canada border crossings, with the goal of reducing time delay without compromising the effectiveness of security screening. Our data analytics show how the arrival rates of vehicles vary by time of day and day of week, and that the service rate per booth varies considerably by the time of day and the number of active booths. We propose a time-varying queueing model to capture these dynamics and use empirical data to estimate the model parameters using a multiple linear regression. We then formulate the staffing task as an integer programming problem and derive a near-optimal workforce schedule. Simulations reveal that our proposed workforce policy improves on the existing schedule by about 18% in terms of average delay without increasing the total work hours of the border staff. [ABSTRACT FROM AUTHOR]

We consider multiclass queueing systems where the per class service rates depend on the network state, fairness criterion, and is constrained to be in a symmetric polymatroid capacity region. We develop new comparison results leading to explicit bounds on the mean service time under various fairness criteria and possibly heterogeneous loads. We then study large-scale systems with a growing number of service classes n (for example, files), $$m = \left\lceil {bn} \right\rceil $$ heterogenous servers with total service rate $$\xi m$$ , and polymatroid capacity resulting from a random bipartite graph $${\mathcal {G}}^{(n)}$$ modeling service availability (for example, placement of files across servers). This models, for example, content delivery systems supporting pooling of server resources, i.e., parallel servicing of a download request from multiple servers. For an appropriate asymptotic regime, we show that the system's capacity region is uniformly close to a symmetric polymatroid-heterogeneity in servers' capacity and file placement disappears. Combining our comparison results and the asymptotic 'symmetry' in large systems, we show that large randomly configured systems with a logarithmic number of file copies are robust to substantial load and server heterogeneities for a class of fairness criteria. If each class can be served by $$c_n=\omega (\log n)$$ servers, the load per class does not exceed $$\theta _n=o\left( \min (\frac{n}{\log n}, c_n)\right) $$ , mean service requirement of a job is $$\nu $$ , and average server utilization is bounded by $$\gamma <1$$ , then for each constant $$\delta >1$$ , the conditional expectation of delay of a typical job with respect to the $$\sigma $$ -algebra generated by $${\mathcal {G}}^{(n)}$$ satisfies the following: [ABSTRACT FROM AUTHOR]

In this article, we analyze the transient behavior of the workload process in a Lévy-driven queue. We are interested in the value of the workload process at a random epoch; this epoch is distributed as the sum of independent exponential random variables. We consider both cases of spectrally one-sided Lévy input processes, for which we succeed in deriving explicit results. As an application, we approximate the mean and the Laplace transform of the workload process after a deterministic time. [ABSTRACT FROM PUBLISHER]

In this paper, we present a basic discrete-time queueing model whereby the service process is decomposed in two (variable) components: the demand of each customer, expressed in a number of work units needed to provide full service of the customer, and the capacity of the server, i.e., the number of work units that the service facility is able to perform per time unit. The model is closely related to multi-server queueing models with server interruptions, in the sense that the service facility is able to deliver more than one unit of work per time unit, and that the number of work units that can be executed per time unit is not constant over time. Although multi-server queueing models with server interruptions-to some extent-allow us to study the concept of variable capacity, these models have a major disadvantage. The models are notoriously hard to analyze and even when explicit expressions are obtained, these contain various unknown probabilities that have to be calculated numerically, which makes the expressions difficult to interpret. For the model in this paper, on the other hand, we are able to obtain explicit closed-form expressions for the main performance measures of interest. Possible applications of this type of queueing model are numerous: the variable service capacity could model variable available bandwidths in communication networks, a varying production capacity in factories, a variable number of workers in an HR-environment, varying capacity in road traffic, etc. [ABSTRACT FROM AUTHOR]

TheM/G/1 model is the fundamental basis of the queueing system in many network systems. Usually, the study of theM/G/1 is limited by the assumption of single queue and infinite capacity. In practice, however, these postulations may not be valid, particularly when dealing with many real-world problems. In this paper, a two-stage state-space approach is devoted to solving the state probabilities for the multi-queue finite-capacityM/G/1 model, i.e.q-M/G/1/KiwithKibuffers in theith queue. The state probabilities at departure instants are determined by solving a set of state transition equations. Afterward, an embedded Markov chain analysis is applied to derive the state probabilities with another set of state balance equations at arbitrary time instants. The closed forms of the state probabilities are also presented with theorems for reference. Applications of Little's theorem further present the corresponding results for queue lengths and average waiting times. Simulation experiments have demonstrated the correctness of the proposed approaches. [ABSTRACT FROM PUBLISHER]

Let τ ( x ) be the epoch of first entry into the interval ( x , ∞ ) , x > 0 , of the reflected process Y of a Lévy process X , and define the overshoot Z ( x ) = Y ( τ ( x ) ) − x and undershoot z ( x ) = x − Y ( τ ( x ) − ) of Y at the first-passage time over the level x . In this paper we establish, separately under the Cramér and positive drift assumptions, the existence of the weak limit of ( z ( x ) , Z ( x ) ) as x tends to infinity and provide explicit formulas for their joint CDFs in terms of the Lévy measure of X and the renewal measure of the dual of X . Furthermore we identify explicit stochastic representations for the limit laws. We apply our results to analyse the behaviour of the classical M/G/1 queueing system at buffer-overflow, both in a stable and unstable case. [ABSTRACT FROM AUTHOR]

All financial practitioners are working in incomplete markets full of unhedgeable risk factors. Making the situation worse, they are only equipped with imperfect information on the relevant processes. In addition to the market risk, fund and insurance managers have to be prepared for sudden and possibly contagious changes in the investment flows from their clients so that they can avoid the over- as well as under-hedging. In this work, the prices of securities, the occurrences of insured events and (possibly a network of) investment flows are used to infer their drifts and intensities by a stochastic filtering technique. We utilize the inferred information to provide the optimal hedging strategy based on the mean-variance (or quadratic) risk criterion. A BSDE approach allows a systematic derivation of the optimal strategy, which is shown to be implementable by a set of simple ODEs and standard Monte Carlo simulation. The presented framework may also be useful for manufacturers and energy firms to install an efficient overlay of dynamic hedging by financial derivatives to minimize the costs. [ABSTRACT FROM AUTHOR]

An investigation is carried out on the nature of QoS measures for queues with correlated traffic in both discrete and continuous time domains. The study focuses on the single server GI G /M [ X ] /1/ N and GI G /Geo [ X ] /1/ N queues with finite capacity, N , a general batch renewal arrival process (BRAP), GI G and either batch Poisson, M [ X ] or batch geometric, Geo [ X ] service times with general batch sizes, X . Closed form expressions for QoS measures, such as queue length and waiting time distributions and blocking probabilities are stochastically derived and showed to be, essentially, time domain invariant. Moreover, the sGGeo sGGeo /Geo/1/ N queue with a shifted generalised geometric (sGGeo) distribution is employed to assess the adverse impact of varying degrees of traffic correlations upon basic QoS measures and consequently, illustrative numerical results are presented. Finally, the global balance queue length distribution of the M Geo /M Geo /1/ N queue is devised and reinterpreted in terms of information theoretic principle of entropy maximisation. [ABSTRACT FROM AUTHOR]

Queues with Markovian arrival and service processes, i.e., MAP/MAP/1 queues, have been useful in the analysis of computer and communication systems and different representations for their stationary sojourn time and queue length distribution have been derived. More specifically, the class of MAP/MAP/1 queues lies at the intersection of the class of QBD queues and the class of semi-Markovian queues. While QBD queues have a matrix exponential representation for their queue length and sojourn time distribution of orderNand N2, respectively, whereNis the size of the background continuous time Markov chain, the reverse is true for a semi-Markovian queue. As the class of MAP/MAP/1 queues lies at the intersection, both the queue length and sojourn time distribution of a MAP/MAP/1 queue has an orderNmatrix exponential representation. The aim of this article is to understand why the order N2distributions of the sojourn time of a QBD queue and the queue length of a semi-Markovian queue can be reduced to an orderNdistribution in the specific case of a MAP/MAP/1 queue. We show that the key observation exists in establishing the commutativity of some fundamental matrices involved in the analysis of the MAP/MAP/1 queue. [ABSTRACT FROM AUTHOR]

This paper presents an unobservable single-server queueing system with three types of uncertainty, where the service rate, or waiting cost or service quality is random variable that may obtainn(n> 2) values. The information about the realised values of parameters is only known to the server. We are concerned about the server’s behaviour: revealing or concealing the information to customers. Then-value assumption and the server’s behaviour enable us to consider various pricing strategies. In this paper, we analyse the effect of information and uncertainty on profits and make comparisons between the profits under different pricing strategies. Moreover, as for parameter variability reflected by the number of each parameter’s possible choicesn, we observe the effect of variablenon all types of profits and find that revealing the parameter information can much more benefit the server with the increase ofn. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study a queueing model in which the customers arrive according to a Markovian arrival process (MAP). There is a single server who offers services on a first-come-first-served basis. With a certain probability a customer may require an optional secondary service. The secondary service is provided by the same server either immediately (if no one is waiting to receive service in the first stage) or waits until the number waiting for such services hits a pre-determined threshold. The model is studied as a QBD-process using matrix-analytic methods and some illustrative examples are discussed. [Copyright &y& Elsevier]

This paper considers time-dependent Pht=Mt=s=c queueing nodes and small tandem networks of such nodes. We examine characteristics of the departure processes from a multiserver queueing node; in particular, we focus on solving for the first two time-dependent moments of the departure-count process. A finite set of partial moment differential equations is developed to numerically solve for the departure-count moments over specified intervals of time [ti,1 + τi]. We also present a distribution fitting algorithm to match these key characteristics with a ∼Pht process serving as the approximate departure process. A distribution fitting algorithm is presented for time-dependent point processes where a two-level balanced mixture of Erlang distribution is used to serve as the approximating process. We then use the ∼Pht approximating departure process as the approximate composite arrival process to downstream node(s) in a network of tandem queues. [ABSTRACT FROM AUTHOR]

Let F be a new better than used in expectation (NBUE) distribution function with mean μ. In a previous paper (Brown in Probab. Eng. Inf. Sci. 20:195-230, ), the author derived the following bound. For any t≥ μ, The main result of this paper is to show that this bound is sharp. Other sharp bounds for NBUE distributions are also derived. [ABSTRACT FROM AUTHOR]

We consider a Markovian clearing queueing system, where the customers are accumulated according to a Poisson arrival process and the server removes all present customers at the completion epochs of exponential service cycles. This system may represent the visits of a transportation facility with unlimited capacity at a certain station. The system evolves in an alternating environment that influences the arrival and the service rates. We assume that the arriving customers decide whether to join the system or balk, based on a natural linear reward-cost structure. We study the balking behavior of the customers and derive the corresponding Nash equilibrium strategies under various levels of information. [ABSTRACT FROM AUTHOR]

Single server retrial queueing models in which customers arrive according to a batch Poisson process are considered here. An arriving batch, finding the server busy, enters an orbit. Otherwise, one customer from the arriving batch enters for service immediately while the rest join the orbit. The customers from the orbit (the orbital customers) try to reach the server subsequently with the inter-retrial times exponentially distributed. Additionally, at each service completion epoch, two different search mechanisms, that is, type I and type II search, to bring the orbital customers by the system to service, are switched on. Thus, when the server is idle, a competition takes place among primary customers, customers who come by retrial and by two types of searches. The type I search selects a single customer whereas the type II search considers a batch of customers from the orbit. Depending on the maximum size of the batch being considered for service by a type II search, two cases are addressed here. In the first case, no restriction on batch size is assumed, whereas in the second case, maximum size of the batch is restricted to a pre-assigned value. We call the resulting models as model 1 and model 2 respectively. In all service modes other than type II search, only a single customer is qualified for service. Service times of the four types of customers, namely, primary, repeated, and those who come by two types of searches are arbitrarily distributed (with different distributions which are independent of each other). Steady state analysis is performed and stability conditions are established. A control problem for model 2 is considered and numerical illustrations are provided. [ABSTRACT FROM PUBLISHER]

In this paper, two continuous-review inventory control models are developed using steady-state diffusion approximation method. Accuracy evaluations of the approximate optimal solutions for the inventory control models are reported for selected "Markovian-like" queues to approximate the steady-state queue size behavior of single-server queues with bulkarrival and batch-service. The diffusion approximation method gives a remarkably good performance in approximating the base stock level one-to-one ordering policy inventory model. The approximation for the order-up to inventory model with replenishment lot size greater than one is also exceptionally good at selected values of heavy traffic intensity and when the service time replenishment process distributional characteristic does not differ greatly from the exponential inter-arrival time of the demands. [ABSTRACT FROM AUTHOR]

This paper considers a fork-join system (or: parallel queue), which is a two-queue network in which any arrival generates jobs at both queues and the jobs synchronize before they leave the system. The focus is on methods to quantify the mean value of the 'system's sojourn time' S: with S denoting a job's sojourn time in queue i, S is defined as max{ S, S}. Earlier work has revealed that this class of models is notoriously hard to analyze. In this paper, we focus on the homogeneous case, in which the jobs generated at both queues stem from the same distribution. We first evaluate various bounds developed in the literature, and observe that under fairly broad circumstances these can be rather inaccurate. We then present a number of approximations, that are extensively tested by simulation and turn out to perform remarkably well. [ABSTRACT FROM AUTHOR]

We consider a class of controlled queue length processes, in which the control allocates each server's effort among the several classes of customers requiring its service. Served customers are routed through the network according to (prescribed) routing probabilities. In the fluid rescaling, $X^{n}(t)=\frac{1}{n} X(nt)$, we consider the optimal control problem of minimizing the integral of an undiscounted positive running cost until the first time that X=0. Our main result uses weak convergence ideas to show that the optimal value functions V of the stochastic control problems for X( t) converge (as n→∞) to the optimal value V of a control problem for the limiting fluid process. This requires certain equicontinuity and boundedness hypotheses on { V}. We observe that these are essentially the same hypotheses that would be needed for the Barles-Perthame approach in terms of semicontinuous viscosity solutions. Sufficient conditions for these equicontinuity and boundedness properties are briefly discussed. [ABSTRACT FROM AUTHOR]

We use semi-regenerative, fluctuations methods, and sequential games to examine a queueing system with server performing a secondary maintenance work. When the buffer becomes empty, the server leaves the system to service packets of jobs at a maintenance facility where his time there is restricted by T (a random time). He returns to the system when his sojourn time expires and if the last packet is fully processed. If the buffer contents is below N, the server departs from the system again to continue with maintenance; this time rendering just one packet at a time until the buffer is replenished. We obtain compact and explicit functionals for the queueing process in equilibrium for both discrete and continuous time parameter processes. [ABSTRACT FROM AUTHOR]

Abstract: Several recent papers have investigated the customer reneging behavior in queueing systems with vacations, where the customers become impatient during the absence of the server(s). These studies have treated the cases of independent and synchronized abandonments. In the case of independent abandonments, the customers have their own independent patience times and abandon the system when such times expire. In the case of synchronized abandonments, the abandonment opportunities occur according to a certain point process and then all present customers decide simultaneously but independently whether they will abandon the system or not. In the present paper, we complement these studies by considering the case of geometric abandonments. This case arises when the abandonment opportunities occur according to a certain point process and the customers decide sequentially whether they will leave the system or not. We derive explicit expressions and computational schemes for various performance descriptors, including the number of customers in system, the sojourn time of a customer, the duration and the maximum number of customers in a busy period. [Copyright &y& Elsevier]

To predict cycle time distributions of integrated processing workstations, detailed simulation models are almost exclusively used; these models require considerable development and maintenance effort. As an alternative, we propose an aggregate model that is a lumped-parameter representation of the workstation. The aggregate model is a single server with a work-in-process dependent aggregate process time distribution and overtaking distribution. The lumped parameters are determined directly from arrival and departure events measured at the workstation. An extensive simulation study and an industry case demonstrate that the aggregate model can accurately predict the cycle time distribution of integrated processing workstations in semiconductor manufacturing. [ABSTRACT FROM AUTHOR]

Abstract: We consider the busy period in the GI/M/1 queue with multiple phase-type vacations. We derive the transform of the joint distribution of the length of a busy period, the number of customers served during the busy period, and the residual interarrival time at the instant the busy period ends. [Copyright &y& Elsevier]

Queueing networks have been used to model material handling in flexible manufacturing systems. We explore the use of a closed queueing network model to approximate an intrabay automated material handling system (AMHS) in semiconductor manufacturing. A simulation-based approach is proposed to obtain estimates of system performance measures. Current simulation models in the industry are very complex, require significant development time, and take a long time to run. The proposed simulation-based queueing network approximation can be used as an easy and fast alternative or as a precursor to a full-fledged modeling exercise depending on the type of decision being made and the level of granularity required in the output. Using a simple intrabay configuration, we compare estimates from the approximation approach and a more detailed modeling approach to characterize the performance of the approximation. In addition, a simulation information model is used to compare AMHS models based on the amount and types of information needed to model the system, and to obtain desired output. This classification aids modelers in determining the level of detail to incorporate in a model based on the objectives of the simulation study. [ABSTRACT FROM AUTHOR]

In this article, we consider a single-server, finite-capacity queue with random bulk service rule where customers arrive according to a discrete-time Markovian arrival process (D-MAP). The model is denoted by D-MAP/GY/1/M where server capacity (bulk size for service) is determined by a random variable Y at the starting point of services. A simple analysis of this model is given using the embedded Markov chain technique and the concept of the mean sojourn time of the phase of underlying Markov chain of D-MAP. A complete solution to the distribution of the number of customers in the D-MAP/GY/1/M queue, some computational results, and performance measures such as the average number of customers in the queue and the loss probability are presented. [ABSTRACT FROM AUTHOR]

In cooperative systems, users achieve spatial diversity and multihop gains by transmitting packets over multiple independent fading paths provided by their partners. Most previous works on cooperative communications focus on the physical layer aspects such as coding, modulation, and transceiver signal processing techniques. In this work, we study the advantages of user cooperation from a MAC layer perspective and devise queueing strategies to exploit cooperative gains in random access networks. Based on the conventional slotted ALOHA protocol, we propose a simple cooperative transmission mechanism for a two-user cooperative pair. We derive the two-user stability region of the proposed system and show the improvements compared to noncooperative systems. The benefits can be attributed to both physical layer cooperation, where users with good channels may relay for those with bad channels, and MAC layer cooperation, where system parameters can be chosen to enhance cooperation and reduce competition. Then, we extend the proposed strategy to a finite-user system that consists of multiple cooperative pairs. By treating each pair as a single transmission entity, we derive inner bounds for the finite-user stability region and propose a ranking system to characterize the transmission entities' relative tendency of being stable (or unstable). [ABSTRACT FROM AUTHOR]