No description available.

No description available.

Submitted by Douglas Yugi Bocal Harada null (doug_yugi@hotmail.com) on 2017-09-06T01:29:28Z No. of bitstreams: 1 Dissertação.pdf: 1782026 bytes, checksum: 4fca65d6b1b81ce49083cec1063ab88e (MD5) / Approved for entry into archive by Luiz Galeffi (luizgaleffi@gmail.com) on 2017-09-06T16:46:11Z (GMT) No. of bitstreams: 1 harada_dyb_me_sjrp.pdf: 1782026 bytes, checksum: 4fca65d6b1b81ce49083cec1063ab88e (MD5) / Made available in DSpace on 2017-09-06T16:46:11Z (GMT). No. of bitstreams: 1 harada_dyb_me_sjrp.pdf: 1782026 bytes, checksum: 4fca65d6b1b81ce49083cec1063ab88e (MD5) Previous issue date: 2017-08-10 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / O tempo de espera é uma variável muito estudada em nosso cotidiano e não pode ser desconsiderada ou minimizada, principalmente quando algum tempo é tomado de uma pessoa por outras que não respeitam uma ordenação estabelecida em sistemas de atendimento. No caso das filas, isso poderia ser evitado em boa parte, se todos entendessem sua estrutura e sua finalidade. Esta investigação tem como objetivo desenvolver um aprendizado sobre sistemas de filas e suas possíveis aplicações, além de estabelecer alguns aspectos educacionais sobre esse assunto. Este estudo foi desenvolvido no âmbito escolar, considerando o caso da educação em filas. A investigação iniciou-se com pesquisa bibliográfica de aspectos teóricos sobre filas e sobre os conceitos de tempo de espera, tipos de filas e suas aplicações. Seguidamente, foi realizado um questionário referente à estrutura de filas e sua educação básica, com a finalidade de avaliar o nível de conhecimento dos alunos. Após a aplicação dessa etapa, foi realizada uma apresentação sobre o tema tratado e, em seguida, aplicação de outro questionário, a fim de analisar a existência de melhoria na aprendizagem. Com o desenvolvimento e aplicação deste estudo, foi possível concluir que houve significativo ganho de conhecimento e de aprendizado dos alunos com relação à educação de filas e seus aspectos. Como motivações aos alunos, foram realizadas duas aplicações simples de filas com comportamentos distintos: uma situação em que os alunos presenciam no seu cotidiano, a fila da cantina, e outra com a teoria mais conhecida e regularmente aplicada. As situações estudadas fornecem subsídios aos alunos na compreensão e na aplicação da teoria em sistemas de filas de espera. / Waiting time is a very studied variable in our daily life and can not be disregarded or minimized, especially when some time is taken from a person by others who do not respect an ordering established in care systems. In the case of queues, this could be largely avoided if everyone understood its structure and purpose. This research aims to develop a learning about queuing systems and their possible applications, besides establishing some educational aspects about this subject. This study was developed in the school context, considering the case of education in queues. The investigation began with a bibliographical research of theoretical aspects about queues and about the concepts of waiting time, types of queues and their applications. Next, a questionnaire was carried out regarding the structure of queues and their basic education, with the purpose of evaluating the students' level of knowledge. After the application of this step, a presentation was made on the subject treated and then application of another questionnaire, in order to analyze the existence of improvement in learning. With the development and application of this study, it was possible to conclude that there was a significant gain in the knowledge and learning of students regarding the education of queues and their aspects. As motivations to the students, two simple applications of queues with different behaviors were carried out: a situation in which the students see in their daily lives, the canteen queue, and another with the best known and regularly applied theory. The situations studied provide support for students in the understanding and application of the theory in queuing systems.

This paper derives recursive algorithms for efficiently computing event probabilities related to order statistics and applies the results in a queue inferencing setting. Consider a set of N i.i.d. random variables in [0, 1]. When the experimental values of the random variables are arranged in ascending order from smallest to largest, one has the order statistics of the set of random variables. Both a forward and a backward recursive O(N3 ) algorithm are developed for computing the probability that the order statistics vector lies in a given N-rectangle. The new algorithms have applicability in inferring the statistical behavior of Poisson arrival queues, given only the start and stop times of service of all N customers served in a period of continuous congestion. The queue inference results extend the theory of the "Queue Inference Engine" (QIE), originally developed by Larson in 1990 [8]. The methodology is extended to a third O(N 3 ) algorithm, employing both forward and backward recursion, that computes the conditional probability that a random customer of the N served waited in queue less than r minutes, given the observed customer departure times and assuming first come, first served service. To our knowledge, this result is the first O(N3 ) exact algorithm for computing points on the in-queue waiting time distribution function,conditioned on the start and stop time data. The paper concludes with an extension to the computation of certain correlations of in-queue waiting times. Illustrative computational results are included throughout.

This paper examines the time lag between the peak in the arrival rate and the peaks in the mean and variance for the number of customers in an M(t)/M(t)/1l system. We establish a necessary condition for the time at which the peak in the mean is achieved. In cases in which system utilization exceeds one during some period, we show that the peak in the mean occurs after the end of this period. / Revised October 1994

In this dissertation, we develop analytical and computational tools for performance analysis and design of large-scale service systems. The dissertation consists of three main chapters. The first chapter is devoted to devising efficient task assignment policies for large-scale service system models from a rare event analysis standpoint. Specifically, we study the steady-state behavior of multi-server queues with general job size distributions under size-interval task assignment (SITA) policies. Assuming Poisson arrivals and the existence of the alpha-th moment of the job size distribution for some alpha> 1, we show that if the job arrival rate and the number of servers increase to infinity with the traffic intensity held fixed, a SITA policy parameterized by alpha minimizes in a large deviation sense the steady-state probability that the total number of jobs in the system is greater than or equal to the number of servers. The optimal large deviation decay rate can be arbitrarily close to the one for the corresponding probability in an infinite-server queue, which only depends on the system traffic intensity but not on any higher moments of the job size distribution. This supports in a many-server asymptotic framework the common wisdom that separating large jobs from small jobs protects system performance against job size variability. In the second chapter, we study constraint satisfaction problems for a Markovian parallel-server queueing model with impatient customers, motivated by large telephone call centers. To minimize the staffing level subject to different service-level constraints, we propose refined square-root staffing (SRS) rules, which preserve the insightfulness and computational scalability of the celebrated SRS principle and yet achieve a stronger form of optimality. In particular, using asymptotic series expansion techniques, we first develop refinements to a set of asymptotic performance approximations recently used in analyzing large call centers, namely, the Quality and Efficiency Driven (QED) diffusion approximations. We then use the improved performance approximations to explicitly characterize the error of conventional SRS and further obtain the refined SRS rules. Finally, we demonstrate how the explicit form of the staffing refinements enables an analytical assessment of the accuracy of conventional SRS and its underlying QED approximation. In the third chapter, we study a fluid model for many-server Markovian queues in changing environments, which can be used to model large-scale service systems with customer abandonments and time-varying arrivals. We obtain the stationary distribution of the fluid model, which refines and is shown to converge, as the environment changing rate vanishes in a proper way, to a simple discrete bimodal approximation. We also prove that the fluid model arises as a law of large number limit in a many-server asymptotic regime.

This dissertation consists of three essays in market design. The first essay studies a dynamic allocation problem. The second presents a new model for many-to-one matching markets where colleges are matched to a large number of students. The third analyzes the effect of the minimum wage on training in internships. In many assignment problems items arrive stochastically over time, and must therefore be assigned dynamically. The first essay studies the social planers ability to dynamically match agents with heterogenous preferences to their preferred items. Impatient agents may misreport their preferences to receive an earlier assignment, causing welfare loss. The first essay presents a tractable model of the problem and mechanisms that minimize the welfare loss. The second essay, which is joint work with Eduardo Azevedo, considers the classical many-to-one matching problem when many students are assigned to a few large colleges. We show that stable matchings have a simple characterization. Any stable matching is equivalent to market clearing cutoffs — admission thresholds for each college. The essay presents a model where a continuum of students is to be matched to a finite number of schools. Using the cutoff representation we show that under broad conditions there is a unique stable matching, and that it varies continuously with respect to the underlying economy. The third essay, which is joint work with Michael Schwarz, looks at on the job training in firms. The firm recovers the cost of training by gradually training the worker over time, paying a wage below the workers marginal product and providing the remaining compensation in the form of training. When the worker’s productivity is close to the minimum wage the firm finds it profitable to front-load training, making the worker more productive and the training faster. A decrease in the minimal wage reduces the firm's incentive to front-load training, and can make training less efficient.

We analyse the steady-state behaviour of two different models with collaborating queues: that is, models in which 'customers' can be served by many types of 'servers', and 'servers' can process many types of 'customers'. The first example is a large-scale service system, such as a call centre. Collaboration is the result of cross-trained staff attending to several different types of incoming calls. We first examine a load-balancing policy, which aims to keep servers in different pools equally busy. Although the policy behaves order-optimally over fixed time horizons, we show that the steady-state distribution may fail to be tight on the diffusion scale. That is, in a family of ever-larger networks whose arrival rates grow as O(r) (where r is a scaling parameter growing to infinity), the sequence of steady-state deviations from equilibrium scaled down by sqrt(r) is not tight. We then propose a different policy, for which we show that the sequence of invariant distributions is tight on the r (1/2+epsilon) scale, for any epsilon > 0. For this policy we conjecture that tightness holds on the diffusion scale as well. The second example models a limit order book, a pricing mechanism for a single-commodity market in which buyers (respectively sellers) are prepared to wait for the price to drop (respectively rise). We analyse the behaviour of a simplified model, in which the arrival events are independent of each other and the state of the limit order book. The system can be represented by a queueing model, with 'customers' and 'servers' corresponding to bids and asks; the roles of customers and servers are symmetric. We show that, with probability 1, the price interval breaks up into three regions. At small (respectively large) prices, only finitely many bid (respectively ask) orders ever get fulfilled, while in the middle region all orders eventually clear. We derive equations which define the boundaries between these regions, and solve them explicitly in the case of iid uniform arrivals to obtain numeric values of the thresholds. We derive a heuristic for the distribution of the highest bid (respectively lowest ask), and present simulation data confirming it.

A major cause of congestion in queuing situations, that is of immoderate waits and lengthening queues, is often the assumed independence of the arrival and service mechanisms. This dissertation is concerned with single server "correlated" models, defined to be such that either the service mechanism is somehow tailored to the arrival pattern, or vice versa. The greatest attention is given to a particular model in which the service time allotted to the nth arrival is λ Tn , where λ is a non-time dependent constant and numerically has the value of congestion index, and Tn is the interval between the (n-l)th and the nth arrivals which, it is important to note, could be observed by the server before service is initiated. It is shown that the effect of the correlation mechanism is to reduce congestion under a given level of traffic intensity, as compared with single server systems in which arrivals and service are independent. This result is achieved without inflicting on the service facility the penalty of increased periods of idleness. The particular model is a queuing interpretation of a stochastic-kinematic situation studied by B. W. Conolly in connection with a military tactical analysis. The dissertation is divided into two parts. Part I develops the theory of the main model with particular reference to state probabilities, waiting time, busy period, and output. Some consideration is also give to a related model where service depends on the arrival pattern, and to what is referred to as the "dual" problem in which the arrival mechanism is geared to service capability. Further, the state probabilities at arrival epochs for a conventional M/M/l queue are obtained by employing a simple probabilistic argument. This is needed for Part II. Part II applies the theory to give a practical comparison of the correlation mechanism with the elementary "independent" single server queues M/M/I, M/D/l and D/M/l; and it is shown in detail that the practical result referred to above is achieved. The superiority of the correlation mechanism increases with traffic intensity. State probability, busy period and output comparisons are made only with the M/M/l system. The main conclusions are found to extend also to these processes. It is concluded that, where its application is practicable, a mechanism of correlation can achieve important gains in efficiency. / Ph. D.

This research analyzed and evaluated a new strategy for preemption of emergency vehicles along a corridor, which is route-based and adaptive to real-time traffic conditions. The method uses dynamic offsets which are adjusted using congestion levels to provide uninterrupted preempted green signal for the emergency vehicle throughout its route. By achieving a higher average emergency vehicle speed, this method promises faster emergency response which results in saving life and property as well as larger emergency service radius for the dispatch stations. The research evaluated the effectiveness of two possible algorithms for offset adjustment using measured vehicle queues. It is showed to reduce the emergency vehicle travel-time by 31 percent when compared to cases without preemption and 13 percent when compared to traditional method of individual-intersection preemption. / Master of Science