Orientador: Regiane Máximo de Souza / Banca: Enzo Barberio Mariano / Banca: Reinaldo Morabito Neto / Resumo: Vários Sistemas de Atendimento Emergenciais (SAE's) sofrem com as variações diárias da demanda e da disponibilidade das ambulâncias. Nesses sistemas pode haver flutuação do desempenho ao longo do dia devido, por exemplo, a mudança no número de servidores e nas taxas de chegada, levando à necessidade de considerar explicitamente tais variações em uma extensão ao modelo hipercubo ainda não explorada na literatura. Como ocorre em alguns SAE's, as ambulâncias melhor equipadas são reservadas para o atendimento exclusivo de chamados com risco de vida. Dessa maneira, a política de despacho pode ser diferenciada com a finalidade de reservar totalmente o atendimento de alguns servidores para certas gravidades de ocorrências. Além disso, somam-se à natureza aleatória desses sistemas, como por exemplo, as incertezas da disponibilidade das ambulâncias, a chegada de um novo chamado e sua localização. Nesse contexto, os objetivos do presente estudo são: (i) estender o modelo hipercubo de filas para reserva total de capacidade, dependendo do tipo do chamado; (ii) estender o modelo hipercubo de filas para torná-lo mais eficiente computacionalmente, sem haver perda de precisão durante a modelagem e resolução; e (iii) propor uma abordagem baseada no modelo hipercubo não-estacionário para organização do trabalho das ambulâncias em qualquer momento do dia. Para verificar a viabilidade e a aplicabilidade dessas abordagens, é realizado um estudo de caso no SAMU da cidade de Bauru (SAMU-Bauru) que,... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: Many Emergency Service Systems face daily variations on demand and ambulance availability. These systems may suffer, for example, performance fluctuations throughout the day, changes on the number of servers and on arrival rates, leading to the need to explicitly consider such variations in a hypercube model extension not yet explored in the literature. As occurs in some SAMU's, which reserve their best equipped ambulances to exclusively serve life-threating requests. Therefore, the dispatch policy can be differentiated in order to completely reserve the service of some ambulances to more severe requests. These problems add up to the random nature of these systems with uncertainties upon ambulance availability or the arrival of a new request and its location. Thus, this study aims to: (i) extend the hypercube queueing model to be able to capture the complete capacity reservation of advanced ambulances, depending on the request classification; (ii) extend the hypercube model in order to make it more computationally efficient, without losing any information during modeling and resolution. (iii) propose an approach based on nonstationary hypercube queueing model to organize the operation of ambulances at any time of the day. To verify the feasibility of these approaches, a case study is carried out on the SAMU from Bauru city (SAMU-Bauru), which, in addition to the advanced ambulance reservation for life-threating requests, is affected by daily variations in demand and ambulance availability. In addition to the original configuration of SAMU-Bauru, studied on a two-step approach, we studied a total of four alternative scenarios that exploited important matters as: the impact of average demand increase on the congestion peak; mitigation of this impact by including a new ambulance; changing the schedule of daily breaks; and the... (Complect abstract electronic acess below) / Mestre

This thesis addresses and identifies outstanding challenges associated with the Multi user massive Multiple-Input Multiple-Output (MU massive MIMO) transmission, whereby various system scenarios have been considered to tackle these challenges. First, for a single cell scenario, the uplink effective capacity under statistical exponent constraints, the asymptotic error and outage probabilities in a multi user massive MIMO system are provided. The proposed approach establishes closed form expressions for the aforementioned metrics under both perfect and imperfect channel state information (CSI) scenarios. In addition, expressions for the asymptotically high signal-to-interference ratio (SIR) regimes are established. Second, the statistical queueing constraints, pilot contamination phenomenon and fractional power control in random or irregular cellular massive MIMO system are investigated, where base station locations are modelled based on the Poisson point process. Specifically, tractable analytical expressions are developed for the asymptotic SIR coverage, rate coverage and the effective capacity under the quality of service statistical exponent constraint. Laplace transform of interference is derived with the aid of mathematical tools from stochastic geometry. Simulation outcomes demonstrate that pilot reuse impairments can be alleviated by employing a cellular frequency reuse scheme. For example, with unity frequency reuse factor, we see that 40% of the total users have SIR above −10.5dB, whereas, with a reuse factor of 7, the same fraction of users have SIR above 20.5dB. In addition, for a certain parameters setting, the coverage probability in the lower 50th percentile can be maximized by adjusting power compensation fraction between 0.2 and 0.5. Also, for SIR threshold of 0dB, allocating 0.25 fraction of uplink transmit power can achieve approximately 6% improvement in coverage probability in the cell edge area compared to constant power policy and about 14% improvement compared to the full channel-inversion policy. Third and last, motivated by the powerful gains of incorporating small cells with macro cells, a massive MIMO aided heterogeneous cloud radio access network (H-CRAN) is investigated. More specific, based on Toeplitz matrix tool, tractable formulas for the link reliability and rate coverage of a typical user in H-CRAN are derived. Numerical outcomes confirm the powerful gain of the massive MIMO for enhancing the throughput of the H-CRAN while small remote radio heads (RRH cells) are capable of achieving higher energy efficiency.

If either the arrival rate or the service rate in an M/M/S queue exhibit variability over time, then no steady state solution is available for examining the system behavior. The arrival and service rates can be represented through Fourier series approximations. This permits numerical approximation of the system characteristics over time. An example of an M/M/S representation of the operations of emergency treatment at Logan Regional hospital is presented. It requires numerical integration of the differential equation for L(t), the expected number of customers in the system at time t.

In this thesis, we are interested in the modelling of queueing networks with finite buffers and with general service time distributions. Queueing networks models have shown to be very useful tools to evaluate the performance of complex systems in many application fields (manufacturing, communication networks, traffic flow, etc.). In order to analyze such networks, the original distributions are most often transformed into tractable distributions, so that the Markov theory can then be applied. Our main originality lies in this step of the modelling process. We propose to discretize the original distributions by probability mass fitting (PMF). The PMF discretization is simple: the probability masses on regular intervals are computed and aggregated on a single value in the corresponding interval. PMF has the advantage to be simple, refinable, and to conserve the shape of the distribution. Moreover, we show that it does not require more phases, and thus more computational effort, than concurrent methods. From the distributions transformed by PMF, the evolution of the system can then be modelled by a discrete Markov chain, and the performance of the system can be evaluated from the chain. This global modelling method leads to various interesting results. First, we propose two methodologies leading to bounds on the cycle time of the system. In particular, a tight lower bound on the cycle time can be computed. Second, probability mass fitting leads to accurate approximation of the performance measures (cycle time, work-in-progress, flow time, etc.). Together with the bounds, the approximations allow to get a good grasp on the exact measure with certainty. Third, the cycle time distribution can be computed in the discretized time and shows to be a good approximation of the original cycle time distribution. The distribution provides more information on the behavior of the system, compared to the isolated expectation (to which other methods are limited). Finally, in order to be able to analyze larger networks, the decomposition technique can be applied after PMF. We show that the accuracy of the performance evaluation is still good, and that the ability of PMF to accurately estimate the distributions brings an improvement in the application of the decomposition. In conclusion, we believe that probability mass fitting can be considered as a valuable alternative in order to build tractable distributions for the analytical modelling of queueing networks.

This thesis investigates the dynamic scheduling of computer communication networks that can be periodically overloaded. Such networks are modelled as mutliclass queueing networks in a slowly changing environment. A hierarchy framework is established to search for a suitable scheduling policy for such networks through its connection with stochastic fluid models. In this work, the dynamic scheduling of a specific multiclass stochastic fluid model is studied first. Then, a bridge between the scheduling of stochastic fluid models and that of the queueing networks in a changing environment is established. In the multiclass stochastic fluid model, the focus is on a system with two fluid classes and a single server whose capacity can be shared arbitrarily among these two classes. The server may be overloaded transiently and it is under a quality of service contract which is indicated by a threshold value of each class. Whenever the fluid level of a certain class is above the designated threshold value, the penalty cost is incurred to the server. The optimal and asymptotically optimal resource allocation policies are specified for such a stochastic fluid model. Afterwards, a connection between the optimization of the queueing networks and that of the stochastic fluid models is established. This connection involves two steps. The first step is to approximate such networks by their corresponding stochastic fluid models with a proper scaling method. The second step is to construct a suitable policy for the queueing network through a successful interpretation of the stochastic fluid model solution, where the interpretation method is provided in this study. The results developed in this thesis facilitate the process of searching for a nearly optimal scheduling policy for queueing networks in a slowly changing environment.

In this dissertation we study the problem of allocating computational resources and managing applications in a data center to serve incoming requests in such a way that the energy usage, reliability and quality of service considerations are balanced. The problem is motivated by the growing energy consumption by data centers in the world and their overall inefficiency. This work is focused on designing flexible and robust strategies to manage the resources in such a way that the system is able to meet the service agreements even when the load conditions change. As a first step, we study the control of a Markovian queueing system with controllable number of servers and service rates (M=Mt=kt ) to minimize effort and holding costs. We present structural properties of the optimal policy and suggest an algorithm to find good performance policies even for large cases. Then we present a reactive/proactive approach, and a tailor-made wavelet-based forecasting procedure to determine the resource allocation in a single application setting; the method is tested by simulation with real web traces. The main feature of this method is its robustness and flexibility to meet QoS goals even when the traffic behavior changes. The system was tested by simulating a system with a time service factor QoS agreement. Finally, we consider the multi-application setting and develop a novel load consolidation strategy (of combining applications that are traditionally hosted on different servers) to reduce the server-load variability and the number of booting cycles in order to obtain a better capacity allocation.

The transient analysis of large-scale systems is often difficult even when the systems belong to the simplest M/M/n type of queues. To address analytical difficulties, previous studies have been conducted under various asymptotic regimes by suitably accelerating parameters, thereby establishing some useful mathematical frameworks and giving insights into important characteristics and intuitions. However, some studies show significant limitations when used to approximate real service systems: (i) they are more relevant to steady-state analysis; (ii) they emphasize proofs of convergence results rather than numerical methods to obtain system performance; and (iii) they provide only one set of limit processes regardless of actual system size. Attempting to overcome the drawbacks of previous studies, this dissertation studies the transient analysis of large-scale service systems with time-dependent parameters. The research goal is to develop a methodology that provides accurate approximations based on a technique called uniform acceleration, utilizing the theory of strong approximations. We first investigate and discuss the possible inaccuracy of limit processes obtained from employing the technique. As a solution, we propose adjusted fluid and diffusion limits that are specifically designed to approximate large, finite-sized systems. We find that the adjusted limits significantly improve the quality of approximations and hold asymptotic exactness as well. Several numerical results provide evidence of the effectiveness of the adjusted limits. We study both a call center which is a canonical example of large-scale service systems and an emerging peer-based Internet multimedia service network known as P2P. Based on our findings, we introduce a possible extension to systems which show non-Markovian behavior that is unaddressed by the uniform acceleration technique. We incorporate the denseness of phase-type distributions into the derivation of limit processes. The proposed method offers great potential to accurately approximate performance measures of non-Markovian systems with less computational burden.

No description available.

The objective of this dissertation is to enhance the overall understanding of practical manufacturing systems by using rigorous academic approaches, primarily queueing theory. The scope spans from the performance of a single manufacturing process to the performance of a manufacturing system. Queueing models are commonly used to evaluate the performance of manufacturing systems. Exact M/M/1 or approximations of G/G/1 models are usually adopted to describe the behavior of a single machine system. However, when applying queueing models to a single machine, some practical issues are encountered. A real machine is subject to different types of interruptions, such as breakdowns, setups and routine maintenance. The proper queueing models under interruptions are presented. The behavior of manufacturing systems is explored by first investigating the underlying structure of tandem queues. We introduce two properties describing the dependence among servers in tandem queues, namely the intrinsic gap and intrinsic ratio, and develop a new approximation approach. The approach exploits what we call the nearly-linear and heavy-traffic properties of the intrinsic ratio. Across a broad range of examined cases, this new approach outperforms earlier approximations that are based on the parametric-decomposition and diffusion approximation approaches. We also demonstrate its use with historical data to achieve very accurate queue time estimates. Furthermore, based on the structure of tandem queues, a way to model the performance of manufacturing systems has been developed.

Several decades after A.K. Erlang originated the theory of queues and queueing networks, D.V. Lindley added impetus to the development of this field by determining a recursive relation for waiting times. Part I of this thesis provides a theoretical treatment of single-server and multiserver queues described by the basic Lindley relation and its extensions, which are referred to collectively as Lindley-Loynes equations. The concepts of stability, and minimal and maximal solutions are investigated. The interdependence of theory and practice becomes evident in Part II, where the results of recent and current research are highlighted. While the main aim of the first part of the thesis is to provide a firm theoretical framework for the sequel, the objective in Part II is to derive generalised forms of the Lindley-Loynes equations from different network protocols. Such protocols are regulated by different switching rules and synchronization constraints. Parts I and II of the thesis are preceded by Chapter 0 in which several fundamental ideas (including those on notation and probability) are described. It is in this chapter too that a more detailed overview of the concept of the thesis is provided. / Thesis (M.Sc.)-University of Natal, Durban, 1993.