A cooperative appproach to queue allocation of indivisible objects

We consider the allocation of a finite number of indivisible objects to the same number of agents according to an exogenously given queue. We assume that the agents collaborate in order to achieve an efficient outcome for society. We allow for side-payments and provide a method for obtaining stable outcomes.

Probabilistic maximal covering location-allocation models with constrained waiting time or queue length for congested systems

When dealing with the design of service networks, such as healthand EMS services, banking or distributed ticket selling services, thelocation of service centers has a strong influence on the congestion ateach of them, and consequently, on the quality of service. In this paper,several models are presented to consider service congestion. The firstmodel addresses the issue of the location of the least number of single--servercenters such that all the population is served within a standard distance,and nobody stands in line for a time longer than a given time--limit, or withmore than a predetermined number of other clients. We then formulateseveral maximal coverage models, with one or more servers per service center.A new heuristic is developed to solve the models and tested in a 30--nodesnetwork.

Arquitectura wormhole per a una NoC 2D-Mesh

Aquest projecte presenta la implementació d'un disseny, i la seva posterior síntesi en una FPGA, d'una arquitectura de tipus wormhole packet switching per a una infraestructura de NetWork-On-Chip amb una topologia 2D-Mesh. Agafant un router circuit switching com a punt de partida, s'han especificat els mòduls en Verilog per tal d'obtenir l'arquitectura wormhole desitjada. Dissenyar la màquina de control per governar els flits que conformen els paquets dins la NoC,i afegir les cues a la sortida del router (outuput queuing) són els punts principals d'aquest treball. A més, com a punt final s'han comparat ambdues arquitectures de router en termes de costos en àrea i en memòria i se n’han obtingut diverses conclusions i resultats experimentals.

Coupling and monotonicity of queueing processes

The main purpose of this work is to give a survey of main monotonicity properties of queueing processes based on the coupling method. The literature on this topic is quite extensive, and we do not consider all aspects of this topic. Our more concrete goal is to select the most interesting basic monotonicity results and give simple and elegant proofs. Also we give a few new (or revised) proofs of a few important monotonicity properties for the queue-size and workload processes both in single-server and multi- server systems. The paper is organized as follows. In Section 1, the basic notions and results on coupling method are given. Section 2 contains known coupling results for renewal processes with focus on construction of synchronized renewal instants for a superposition of independent renewal processes. In Section 3, we present basic monotonicity results for the queue-size and workload processes. We consider both discrete-and continuous-time queueing systems with single and multi servers. Less known results on monotonicity of queueing processes with dependent service times and interarrival times are also presented. Section 4 is devoted to monotonicity of general Jackson-type queueing networks with Markovian routing. This section is based on the notable paper [17]. Finally, Section 5 contains elements of stability analysis of regenerative queues and networks, where coupling and monotonicity results play a crucial role to establish minimal suficient stability conditions. Besides, we present some new monotonicity results for tandem networks.

A general multiserver state-dependent queueing system

The work studies a general multiserver queue in which the service time of an arriving customer and the next interarrival period may depend on both the current waiting time and the server assigned to the arriving customer. Stability of the system is proved under general assumptions on the predetermined distributions describing the model. The proof exploits a combination of the Markov property of the workload process with a regenerative property of the process. The key idea leading to stability is a characterization of the limit behavior of the forward renewal process generated by regenerations. Extensions of the basic model are also studied.

Simulación de departamentos de urgencias empleando un modelo basado en agentes

Los servicios de salud son sistemas muy complejos, pero de alta importancia, especialmente en algunos momentos críticos, en todo el mundo. Los departamentos de urgencias pueden ser una de las áreas más dinámicas y cambiables de todos los servicios de salud y a la vez más vulnerables a dichos cambios. La mejora de esos departamentos se puede considerar uno de los grandes retos que tiene cualquier administrador de un hospital, y la simulación provee una manera de examinar este sistema tan complejo sin poner en peligro los pacientes que son atendidos. El objetivo de este trabajo ha sido el modelado de un departamento de urgencias y el desarrollo de un simulador que implementa este modelo con la finalidad de explorar el comportamiento y las características de dicho servicio de urgencias. El uso del simulador ofrece la posibilidad de visualizar el comportamiento del modelo con diferentes parámetros y servirá como núcleo de un sistema de ayuda a la toma de decisiones que pueda ser usado en departamentos de urgencias. El modelo se ha desarrollado con técnicas de modelado basado en agentes (ABM) que permiten crear modelos funcionalmente más próximos a la realidad que los modelos de colas o de dinámicas de sistemas, al permitir la inclusión de la singularidad que implica el modelado a nivel de las personas. Los agentes del modelo presentado, descritos internamente como máquinas de estados, representan a todo el personal del departamento de urgencias y los pacientes que usan este servicio. Un análisis del modelo a través de su implementación en el simulador muestra que el sistema se comporta de manera semejante a un departamento de urgencias real.

Disseny i implementació d'un sistema d'informació SMS

El TFC consisteix en el disseny i la implementació d'un sistema que, a partir d'una base de dades qualsevol, obtingui la informació proporcionada pels usuaris autoritzats mitjançant missatges SMS i la posi en una cua per a ser enviada via SMS també per un programari extern.

Apoyo a pantallas periféricas multiusuario: detección de presencias y gestión de la interacción

En este proyecto se han implementado dos sistemas: un sistema de gestión ytratamiento de la interacción multiusuario y un sistema de input mediante WebCam para lalocalización de usuarios, el cual se comunica con el sistema de gestión a través de XML. Se ha intentado conseguir un nivel de abstracción elevado de cara a que los futuros sistemas de interacción puedan añadir las funcionalidades implementadas para este proyecto.La idea nace de la limitación vigente de los sistemas interactivos que utilizan pantallasmultitouch ya que no existe ningún sistema que gestione a los múltiples usuarios que puedan interactuar al mismo tiempo en ellas. Se ha analizado el sistema de Vogel, en el cual se han intentado mejorar y solucionar ciertos aspectos de la interacción multiusuario.Se han diseñado e implementado dos métodos para tratar la gestión de la interacciónmultiusuario: sistema de elementos interactivos instanciables así como un sistema de cola (queue) dentro de los propios elementos interactivos. Todo ello basado en la idea de las áreasde interacción de los usuarios la cual es posible gracias al sistema de detección de presencias.Así pues, a través de este proyecto final de carrera se quiere mostrar que la interacciónmultiusuario en los sistemas interactivos periféricos puede gestionarse a través de diferentes métodos y de este modo mejorar la experiencia de los usuarios durante todo el proceso de interacción.

Locating emergency services with priority rules: The priority queuing covering location problem

One of the assumptions of the Capacitated Facility Location Problem (CFLP) is thatdemand is known and fixed. Most often, this is not the case when managers take somestrategic decisions such as locating facilities and assigning demand points to thosefacilities. In this paper we consider demand as stochastic and we model each of thefacilities as an independent queue. Stochastic models of manufacturing systems anddeterministic location models are put together in order to obtain a formula for thebacklogging probability at a potential facility location.Several solution techniques have been proposed to solve the CFLP. One of the mostrecently proposed heuristics, a Reactive Greedy Adaptive Search Procedure, isimplemented in order to solve the model formulated. We present some computationalexperiments in order to evaluate the heuristics performance and to illustrate the use ofthis new formulation for the CFLP. The paper finishes with a simple simulationexercise.

Parallel scheduling of multiclass M/M/m queues: Approximate and heavy-traffic optimization of achievable performance

We address the problem of scheduling a multiclass $M/M/m$ queue with Bernoulli feedback on $m$ parallel servers to minimize time-average linear holding costs. We analyze the performance of a heuristic priority-index rule, which extends Klimov's optimal solution to the single-server case: servers select preemptively customers with larger Klimov indices. We present closed-form suboptimality bounds (approximate optimality) for Klimov's rule, which imply that its suboptimality gap is uniformly bounded above with respect to (i) external arrival rates, as long as they stay within system capacity;and (ii) the number of servers. It follows that its relativesuboptimality gap vanishes in a heavy-traffic limit, as external arrival rates approach system capacity (heavy-traffic optimality). We obtain simpler expressions for the special no-feedback case, where the heuristic reduces to the classical $c \mu$ rule. Our analysis is based on comparing the expected cost of Klimov's ruleto the value of a strong linear programming (LP) relaxation of the system's region of achievable performance of mean queue lengths. In order to obtain this relaxation, we derive and exploit a new set ofwork decomposition laws for the parallel-server system. We further report on the results of a computational study on the quality of the $c \mu$ rule for parallel scheduling.

Optimization of multiclass queueing networks with changeover times via the achievable region method: Part II, the multi-station case

We address the problem of scheduling a multi-station multiclassqueueing network (MQNET) with server changeover times to minimizesteady-state mean job holding costs. We present new lower boundson the best achievable cost that emerge as the values ofmathematical programming problems (linear, semidefinite, andconvex) over relaxed formulations of the system's achievableperformance region. The constraints on achievable performancedefining these formulations are obtained by formulatingsystem's equilibrium relations. Our contributions include: (1) aflow conservation interpretation and closed formulae for theconstraints previously derived by the potential function method;(2) new work decomposition laws for MQNETs; (3) new constraints(linear, convex, and semidefinite) on the performance region offirst and second moments of queue lengths for MQNETs; (4) a fastbound for a MQNET with N customer classes computed in N steps; (5)two heuristic scheduling policies: a priority-index policy, anda policy extracted from the solution of a linear programmingrelaxation.

Location models for airline hubs behaving as M/D/c queues

Models are presented for the optimal location of hubs in airline networks, that take into consideration the congestion effects. Hubs, which are the most congested airports, are modeled as M/D/c queuing systems, that is, Poisson arrivals, deterministic service time, and {\em c} servers. A formula is derived for the probability of a number of customers in the system, which is later used to propose a probabilistic constraint. This constraint limits the probability of {\em b} airplanes in queue, to be lesser than a value $\alpha$. Due to the computational complexity of the formulation. The model is solved using a meta-heuristic based on tabu search. Computational experience is presented.