Spelling suggestions: "subject:"queueing"" "subject:"gueueing""
201 |
Border Crossing Modeling and Analysis: A Non-Stationary Dynamic Reallocation Methodology For Terminating Queueing SystemsMoya, Hiram 2012 August 1900 (has links)
The United States international land boundary is a volatile, security intense area. In 2010, the combined trade was $918 billion within North American nations, with 80% transported by commercial trucks. Over 50 million commercial vehicles cross the Texas/Mexico border every year, not including private vehicles and pedestrian traffic, between Brownsville and El Paso, Texas, through one of over 25 major border crossings called "ports of entry" (POE). Recently, securing our southwest border from terrorist interventions, undocumented immigrants, and the illegal flow of drugs and guns has dominated the need to efficiently and effectively process people, goods and traffic. Increasing security and inspection requirements are seriously affecting transit times. Each POE is configured as a multi-commodity, prioritized queueing network which rarely, if ever, operates in steady-state. Therefore, the problem is about finding a balance between a reduction of wait time and its variance, POE operation costs, and the sustainment of a security level.
The contribution of the dissertation is three-fold. The first uses queueing theory on the border crossing process to develop a methodology that decreases border wait times without increasing costs or affecting security procedures. The outcome is the development of the Dynamic Reallocation Methodology (DRM). Currently at the POE, inspection stations are fixed and can only inspect one truck type, FAST or Non-FAST program participant. The methodology proposes moveable servers that once a threshold is met, can be switched to service the other type of truck. Particular emphasis is given to inspection (service) times under time-varying arrivals (demands).
The second contribution is an analytical model of the POE, to analyze the effects of the DRM. First assuming a Markovian service time, DRM benefits are evaluated. However, field data and other research suggest a general distribution for service time. Therefore, a Coxian k-phased approximation is implemented. The DRM is analyzed under this new baseline using expected number in the system, and cycle times.
A variance reduction procedure is also proposed and evaluated under DRM. Results show that queue length and wait time is reduced 10 to 33% depending on load, while increasing FAST wait time by less than three minutes.
|
202 |
Abordagens de modelos de filas com abandono para análise de congestão em Call CentersFerrari, Sidney Carlos 22 June 2016 (has links)
Submitted by Izabel Franco (izabel-franco@ufscar.br) on 2016-10-26T17:09:15Z
No. of bitstreams: 1
TeseSCF.pdf: 10747360 bytes, checksum: 8a9b640ece219d76af8f66468c70af0a (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-11-08T18:25:43Z (GMT) No. of bitstreams: 1
TeseSCF.pdf: 10747360 bytes, checksum: 8a9b640ece219d76af8f66468c70af0a (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-11-08T18:25:51Z (GMT) No. of bitstreams: 1
TeseSCF.pdf: 10747360 bytes, checksum: 8a9b640ece219d76af8f66468c70af0a (MD5) / Made available in DSpace on 2016-11-08T18:25:59Z (GMT). No. of bitstreams: 1
TeseSCF.pdf: 10747360 bytes, checksum: 8a9b640ece219d76af8f66468c70af0a (MD5)
Previous issue date: 2016-06-22 / Não recebi financiamento / This work deals with the analysis of queueing systems for Call Centers regarding the possibility
of the customer abandon the system before being served, due to his/her impatience. The Call
Centers are service organizations that predominantly serve customers by phone calls and are
considered a particular kind of Contact Centers that serve their costumers through phone, fax,
e-mail, chat, mobile devices and other communication channels. From a business point of view,
the main concern on the management of the Call Center is the offer quality service with
minimum cost. The perception of the quality of services offered is expressed, by customer, for
example, through the abandonment of queue, which is considered one of the most important
operational measures to evaluate the performance of a Call Center. This work aims to present
and apply analytical queueing models with abandonment, represented by generic probability
distributions (particularly mixed distributions), as an effective analysis approach to represent
the problem of congestion in Call Center systems and support decisions of dimensioning and
operations on these systems. Two studies were conducted with Call Center extracted data of a
company located in the countryside of São Paulo State, Brazil and another located overseas, in
Israel. The parameters (e.g, arrival rate, service rate, abandonment rate) and some measures of
performance (e.g, average waiting time, waiting probability, abandonment probability and
traffic intensity) were established based on these data. These sampling measures were equated
with the same measures achieved by the analytical queueing models M/M/c+G, M/Gc/1+G and
M/G/c+G considered in this research, using the parameters obtained empirically and mixed,
Exponential, Fatigue Life, Normal and Lognormal distributions to represent the abandonment
(patience) of users. It was observed that in some cases, depending on the considered
performance measure, the queueing models with mixed distributions for the abandonment have
better results (minor deviations, compared to the real data) than their corresponding with nonmixed
distributions. It was observed, also, that independently of the analyzed performance
measures, the Call Centers may be represented by a analytical queueing model with a mixed
distribution for abandonment times, which behaves better than the others. There were no
evidences that the mixed distributions to represent the abandonment times were the best in all
analyzed performance measures, but they were always competitive. It was used, also, an
experimental model of discrete simulation that properly represents the Call Center in order to
check the results of the analytical models and explore alternative scenarios. The same scenarios
were considered with the theoretical model and the performance measures achieved by the
simulation and by the theoretical models were compared, showing the potential of the use of
the approaches based on analytical models with abandonment for the Call Centers analysis. / Este trabalho trata da análise de sistemas de filas para Call Center considerando a
possibilidade do cliente abandonar o sistema antes de ser servido, devido a sua impaciência. Os
Call Centers são organizações de serviço que predominantemente servem os clientes via
chamada telefônica e são considerados um tipo particular dos Centros de Contato, que atendem
seus clientes por meio de telefone, fax, e-mail, chat, dispositivos móveis e outros canais de
comunicação. Do ponto de vista dos negócios, a principal preocupação na gestão de um Call
Center é oferecer serviço de qualidade com mínimo custo. A percepção da qualidade dos
serviços oferecidos é manifestada, pelo cliente, por exemplo, por meio do abandono da fila de
espera, que é considerado uma das medidas operacionais mais importantes para avaliar o
desempenho de um Call Center. O objetivo deste trabalho é apresentar e aplicar modelos
analíticos de filas com abandono, representado por distribuições genéricas (particularmente
distribuições mistas), como uma abordagem de análise efetiva para representar o problema de
congestão em sistemas de Call Centers e apoiar decisões de dimensionamento e operação
nesses sistemas. Dois estudos foram conduzidos com dados extraídos do Call Center de uma
empresa localizada no interior do Estado de São Paulo e de outro localizado no exterior, em
Israel. Os parâmetros (por exemplo, taxa de chegada, taxa de serviço e taxa de abandono) e
algumas medidas de desempenho (por exemplo, tempo médio de espera, probabilidade de
esperar, probabilidade de abandonar e intensidade de tráfego) são determinadas com esses
dados. Essas medidas amostrais são comparadas com as mesmas medidas obtidas por meio dos
modelos analíticos de fila M/M/c+G, M/Gc/1+G e M/G/c+G considerados nesse estudo, que
utilizam os parâmetros obtidos empiricamente e as distribuições mistas, Exponencial, Fatigue
Life, Normal e Lognormal para representar o abandono (paciência) dos usuários. Observou-se
como resultado, que em alguns casos, dependendo da medida de desempenho considerada, os
modelos de fila com distribuição mista para o abandono têm apresentado resultados melhores
(desvios menores em relação aos dados reais) que os seus correspondentes com distribuições
não mistas. Observou-se, também, que independentemente das medidas de desempenho
analisadas, os Call Centers podem ser representados por um modelo analítico de fila com uma
distribuição mista para os tempos de abandono, que se comporta melhor do que os outros. Não
houve evidências que as distribuições mistas para representar os tempos de abandono foram as
melhores em todas as medidas de desempenho analisadas, mas foram sempre competitivas.
Utilizou-se, também, um modelo experimental de simulação discreta, que representa
apropriadamente o Call Center, para verificar os resultados dos modelos analíticos e explorar
cenários alternativos. Os mesmos cenários foram considerados com o modelo teórico e as
medidas de desempenho obtidas pela simulação e pelo modelo teórico foram comparadas,
mostrando o potencial do uso de abordagens baseadas em modelos analíticos com abandono
para análise de Call Centers.
|
203 |
A importância da rapidez de atendimento nos caixas de supermercados : um estudo de caso utilizando um modelo analítico de filas com trocas. / The importance of quick responsiveness in supermarket checkouts: a case study using an analytical queueing model with jockeying.Rinaldi, José Gilberto Spasiani 29 June 2007 (has links)
Made available in DSpace on 2016-06-02T19:50:01Z (GMT). No. of bitstreams: 1
TeseJGSR.pdf: 2611645 bytes, checksum: 6dbd36dc8e39b96d32bfddfeef61b88a (MD5)
Previous issue date: 2007-06-29 / Self-service companies have been concerned about improving their performance in face of
competition, either to conquer new markets or to keep in business. It is essential for them to
present good quality products and/or services. Thus, in this study, one of the aims was to
show that the waiting time in supermarket checkout lines is very important for service
speed and, therefore, for the service level of customers. Other aims include the reasons why
the customer goes regularly to a specific supermarket and, among these reasons, the
relevance of each one in contrast with the others, and its relative importance. As a result, it
was possible to contextualize the scenario in which customers view the importance of
queues and their waiting time. Also, the level of schooling of the customers was associated
with the factors that lead them to go regularly to the place. This is an interesting
contribution because in Brazil there is a relation between income and schooling. Besides,
the queueing models that may satisfactorily represent the supermarket checkouts were
studied and the one that best represents the system was identified. It was verified that the
customers change lines when they notice another line with fewer customers, and the size of
this difference was assessed. The queueing model with jockeying was the one to best
represent the situation commonly found in supermarkets, and it can offer subsidies for
service improvement. In order to carry out this research some companies in the city of São
Carlos/SP were contacted, and one among the ones that allowed the data collection was
selected. Therefore, this is a case study, thus presenting inferential limitations. / As empresas de auto-serviço, em geral, têm se preocupado em melhorar seu desempenho
em relação à concorrência, seja para ganhar mercado ou mesmo para sobreviver. É
essencial que apresentem boa qualidade nos produtos oferecidos e/ou serviços prestados.
Assim, neste trabalho, entre outros, um dos objetivos, foi mostrar que o tempo de espera na
fila de caixas de supermercados assume grande importância na rapidez de atendimento e,
portanto, para o nível de serviço dos clientes. Outros objetivos também foram considerados.
As causas pelas quais o cliente freqüenta aquele supermercado e, nestas, a relevância de
cada uma em contraste com as outras, e sua importância relativa. Assim, pôde-se
contextualizar o cenário no qual os clientes enxergam a importância da fila e de seu tempo
de espera. Também, associou-se a escolaridade do cliente a fatores pelos quais este
freqüenta o local, sendo esta uma contribuição interessante devido a existir, no Brasil, uma
relação entre renda e escolaridade. Também, estudaram-se modelos de filas que podem
representar satisfatoriamente o sistema de filas nos caixas de supermercados e identificouse,
entre eles, o que melhor representou o sistema. Para o modelo de filas com trocas, foi
verificado que os clientes trocam de fila quando percebem outra fila com menos clientes,
sendo que o tamanho desta diferença foi avaliado. Este modelo foi o que melhor
representou a situação comumente encontrada nos supermercados podendo fornecer
subsídios para melhoria de atendimento. Para a viabilização da pesquisa foram contatadas
algumas empresas da cidade de São Carlos/SP, sendo que, daquelas que permitiram a coleta
de dados, uma foi selecionada. Desta forma, este trabalho se trata de um estudo de caso,
tendo limitações inferenciais.
|
204 |
Avaliação do desempenho e cenários alternativos em um samu utilizando o modelo hipercubo estacionário e não-estacionário / Performance and alternative scenarios evaluation on a samu using the stationary and nonstationary hypercube modelBeojone, Caio Vítor [UNESP] 09 October 2017 (has links)
Submitted by Caio Vítor Beojone null (beojone@hotmail.com) on 2017-10-25T17:47:50Z
No. of bitstreams: 1
Caio Vitor Beojone - Dissertação.pdf: 10092472 bytes, checksum: 470115087a1c1f987a7a8e2cffec7cd4 (MD5) / Approved for entry into archive by Monique Sasaki (sayumi_sasaki@hotmail.com) on 2017-10-31T16:52:11Z (GMT) No. of bitstreams: 1
beojone_cv_me_bauru.pdf: 10092472 bytes, checksum: 470115087a1c1f987a7a8e2cffec7cd4 (MD5) / Made available in DSpace on 2017-10-31T16:52:11Z (GMT). No. of bitstreams: 1
beojone_cv_me_bauru.pdf: 10092472 bytes, checksum: 470115087a1c1f987a7a8e2cffec7cd4 (MD5)
Previous issue date: 2017-10-09 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / 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, além de reservar suas ambulâncias avançadas para ocorrências mais graves, é afetado pelas variações diárias na demanda e disponibilidade das ambulâncias. Além da configuração original do SAMU-Bauru, estudada em duas etapas, foram analisados um total de quatro cenários alternativos que consideram questões importantes: o impacto do aumento na demanda do período mais congestionado; a mitigação desse impacto incluindo uma nova ambulância; a alteração do horário das pausas diárias; e o impacto de aumentos na demanda em horários específicos do dia. Foram calculadas importantes medidas de desempenho para cada cenário como a carga de trabalho, tempos médios de espera e tempos médios de resposta. Os resultados mostram que as extensões realizadas no modelo hipercubo são capazes de analisar satisfatoriamente sistemas como o SAMU-Bauru, além de possibilitar a criação e mensuração de propostas de melhorias nos níveis táticos e operacionais. / 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 impact of increases in the demand at specific hours of the day. We calculated important performance measures for each scenario, such as workload, mean waiting times and mean response times. Results show that the proposed extensions to the hypercube model are capable of satisfactorily analyze systems such as SAMU-Bauru, besides making it possible to create and to measure improvements proposals in tactical and operational levels.
|
205 |
Pernambuco’s health sector: analysis of queueing problems and an economic growth modelROCHA, Tamires Taís Bezerra 04 April 2013 (has links)
Submitted by Caroline Falcao (caroline.rfalcao@ufpe.br) on 2017-06-05T16:18:45Z
No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
Tamires Taís.pdf: 9141530 bytes, checksum: dab991dd87283a9e223705028b80d093 (MD5) / Made available in DSpace on 2017-06-05T16:18:45Z (GMT). No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
Tamires Taís.pdf: 9141530 bytes, checksum: dab991dd87283a9e223705028b80d093 (MD5)
Previous issue date: 2013-04-04 / Esta dissertação apresenta um panorama do sistema de saúde brasileiro, com ênfase no
caso do Estado de Pernambuco. A gestão de sistemas de saúde se manifesta sob a forma
geral de longas filas de espera, que são analisados neste contexto, incluindo algumas
abordagens que têm sido propostas e implementadas em Pernambuco, a fim de resolver
o problema. Um modelo de crescimento econômico ótimo destacando o setor de saúde,
e, em seguida, operando em conjunto, os setores de saúde e educação é proposto. Os
resultados do princípio do máximo de Pontryagin aplicado a este modelo mostram os
benefícios mútuos para ambos os setores e os seus efeitos no bem-estar da sociedade. Um estudo de caso de filas de espera no Hospital da Restauração, em Recife, Pernambuco, é apresentado. / An overview of the Brazilian health care system is presented, with an emphasis in
the Pernambuco state case. One central issue concerning health systems management
manifests itself under the general form of long waiting lines, which are then here analyzed
in this context, including some approaches that have been proposed and implemented in
Pernambuco in order to tackle the problem. An optimal economic growth model highlighting
the health sector, and then, operating jointly, the health and education sectors, is
proposed. The results of the Pontryagin Maximum Principle applied to this model show
the mutual benefits for both sectors and their effects in the community welfare. A case
study of queueing systems in Hospital da Restaura¸c˜ao (an emergency hospital) in Recife,
Pernambuco, is presented.
|
206 |
Optimization of Just-in-Time Sequencing Problems and Supply Chain LogisticsThapa, Gyan January 2015 (has links)
This dissertation presents a comprehensive and comparative progress in sequencing approaches of mixed-model just-in-time (JIT) sequencing problem together with discrete apportioment problem (DAP). The goal of JIT sequencing problem (JITSP) is to keep the rate of usage of parts as constant as possible along the assembly lines, and the goal of DAP is to divide a given integer number of delegates proportionally among the states or the parties according to their population or votes. Furthermore, the supply chain logistics problem is also reported in here with some real life applications.The single-level JITSP, known as the product rate variation problem (PRVP), is pseudo-polynomially solvable. The total PRVP minimizes sum deviation and the bottleneck PRVP minimizes the maximum deviation between the actual production and the ideal production. The assignment approach solves total PRVP whereas the perfect matching works for bottleneck PRVP solving the problem in pseudo-polynomial time. The multi-level JITSP, known as the output rate variation problem (ORVP), is NP-hard in most of the cases. However, some sequencing heuristics and dynamic programming are devised for near optimal solutions. And the pegging assumption reduces the ORVP into weighted case of PRVP. In this dissertation, the total PRVP with square and absolute deviations are considered and mean-based divisor methods are devised for the equitably efficient solution. The simultaneous dealing to the PRVP and DAP establishes the interlink between the production sequencing problem and integer seat allocating problem. The new upper bottlenecks are investigated and the problems are solved comparatively. The bottleneck PRVP instances for small deviations and cyclic sequences for total PRVP are shown to be optimal. The bicriterion sequencing is discussed with Pareto optimal solutions.The production sequencing problem is simultaneously dealt with supply chain logistics to balance overall supply chain system. The cross-docking supply chain logistics problem is formulated with a proposition to be solved. The real-world applications of JITSP and supply chain are listed and some open problems are pointed out as the closing of the dissertation.
|
207 |
Efektivní využití konvergované sítě / Effective utilization of converged networkNesveda, Marek January 2011 (has links)
The Master´s thesis deals with the field of converged networks and their effective utilization, focusing specifically on telematic networks. For modelling of a specific application, the field of vehicle telematics has been chosen. The thesis consists of two series of simulations performed in Opnet Modeler network simulator. The first theoretic part gave an overview of protocols used in converged networks, with a more detailed description of routing protocols. The attention also centred on the mechanisms for assuring the quality of service in IP. The subsequent practical part consisted in creating the simulation of a converged telematic network in Opnet Modeler network simulator, configuration of scenarios for assuring QoS using RSVP and DSCP protocols and the simulation itself. The results of the simulations for both scenarios were compared and represented in graphic form. The second theoretic part described queueing disciplines, as well as congestion control and congestion avoidance mechanisms. The corresponding practical part compared FIFO, PQ and WFQ queueing algorithms within the same simulated converged telematic network, using DSCP protocol scenario, which gave much better results in the first series of simulations. Again, the results of the simulations were compared and represented in graphic form.
|
208 |
Resource management in computer clusters : algorithm design and performance analysis / Gestion des ressources dans les grappes d’ordinateurs : conception d'algorithmes et analyse de performanceComte, Céline 24 September 2019 (has links)
La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.
|
209 |
Resource management in computer clusters : algorithm design and performance analysis / Gestion des ressources dans les grappes d’ordinateurs : conception d'algorithmes et analyse de performanceComte, Céline 24 September 2019 (has links)
La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.
|
210 |
Resource management in computer clusters : algorithm design and performance analysis / Gestion des ressources dans les grappes d’ordinateurs : conception d'algorithmes et analyse de performanceComte, Céline 24 September 2019 (has links)
La demande croissante pour les services de cloud computing encourage les opérateurs à optimiser l’utilisation des ressources dans les grappes d’ordinateurs. Cela motive le développement de nouvelles technologies qui rendent plus flexible la gestion des ressources. Cependant, exploiter cette flexibilité pour réduire le nombre d’ordinateurs nécessite aussi des algorithmes de gestion des ressources efficaces et dont la performance est prédictible sous une demande stochastique. Dans cette thèse, nous concevons et analysons de tels algorithmes en utilisant le formalisme de la théorie des files d’attente.Notre abstraction du problème est une file multi-serveur avec plusieurs classes de clients. Les capacités des serveurs sont hétérogènes et les clients de chaque classe entrent dans la file selon un processus de Poisson indépendant. Chaque client peut être traité en parallèle par plusieurs serveurs, selon des contraintes de compatibilité décrites par un graphe biparti entre les classes et les serveurs, et chaque serveur applique la politique premier arrivé, premier servi aux clients qui lui sont affectés. Nous prouvons que, si la demande de service de chaque client suit une loi exponentielle indépendante de moyenne unitaire, alors la performance moyenne sous cette politique simple est la même que sous l’équité équilibrée, une extension de processor-sharing connue pour son insensibilité à la loi de la demande de service. Une forme plus générale de ce résultat, reliant les files order-independent aux réseaux de Whittle, est aussi prouvée. Enfin, nous développons de nouvelles formules pour calculer des métriques de performance.Ces résultats théoriques sont ensuite mis en pratique. Nous commençons par proposer un algorithme d’ordonnancement qui étend le principe de round-robin à une grappe où chaque requête est affectée à un groupe d’ordinateurs par lesquels elle peut ensuite être traitée en parallèle. Notre seconde proposition est un algorithme de répartition de charge à base de jetons pour des grappes où les requêtes ont des contraintes d’affectation. Ces deux algorithmes sont approximativement insensibles à la loi de la taille des requêtes et s’adaptent dynamiquement à la demande. Leur performance peut être prédite en appliquant les formules obtenues pour la file multi-serveur. / The growing demand for cloud-based services encourages operators to maximize resource efficiency within computer clusters. This motivates the development of new technologies that make resource management more flexible. However, exploiting this flexibility to reduce the number of computers also requires efficient resource-management algorithms that have a predictable performance under stochastic demand. In this thesis, we design and analyze such algorithms using the framework of queueing theory.Our abstraction of the problem is a multi-server queue with several customer classes. Servers have heterogeneous capacities and the customers of each class enter the queue according to an independent Poisson process. Each customer can be processed in parallel by several servers, depending on compatibility constraints described by a bipartite graph between classes and servers, and each server applies first-come-first-served policy to its compatible customers. We first prove that, if the service requirements are independent and exponentially distributed with unit mean, this simple policy yields the same average performance as balanced fairness, an extension to processor-sharing known to be insensitive to the distribution of the service requirements. A more general form of this result, relating order-independent queues to Whittle networks, is also proved. Lastly, we derive new formulas to compute performance metrics.These theoretical results are then put into practice. We first propose a scheduling algorithm that extends the principle of round-robin to a cluster where each incoming job is assigned to a pool of computers by which it can subsequently be processed in parallel. Our second proposal is a load-balancing algorithm based on tokens for clusters where jobs have assignment constraints. Both algorithms are approximately insensitive to the job size distribution and adapt dynamically to demand. Their performance can be predicted by applying the formulas derived for the multi-server queue.
|
Page generated in 0.0339 seconds