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.

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.

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.

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.

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.

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.

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.

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.

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.

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.