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.

Efficient priority rules

We study the assignment of indivisible objects with quotas (houses, jobs, or offices) to a set of agents (students, job applicants, or professors). Each agent receives at most one object and monetary compensations are not possible. We characterize efficient priority rules by efficiency, strategy-proofness, and renegotiation-proofness. Such a rule respects an acyclical priority structure and the allocations can be determined using the deferred acceptance algorithm.

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.

Sistema integral d’anàlisi i avaluació d’un format general d’assignatura específic dels estudis de les arts

En el període 2006-2008, l'equip investigador de l'Observatori sobre la Didàctica de les Arts (ODAS) s'ha concentrat en la innovació i la investigació en el camp de la didàctica aplicada als estudis universitaris de les arts. Des del punt de vista propi de la investigació-acció, la finalitat ha estat la de plantejar i explorar una revisió integral de l'organització del treball a peu d'aula que fos extensible a d'altres assignatures i matèries. Així, prenent com a eix l'aprenentatge dels estudiants, les accions escomeses es fonamentaren en sis premisses: integració —de sessions de treball i activitats d'aprenentatge—, diversitat —d'escenaris, recursos i materials didàctics—, equilibri —entre coneixements i habilitats específiques i transversals—, modularitat —de les parts constitutives de la innovació proposada—, aplicabilitat —a d'altres assignatures i matèries— i progressió en la seva posada en marxa. I sobre aquestes bases, hom va establir cinc línies de treball: l'organització del treball a l'aula i del treball guiat de l'estudiant en diferents tipus de sessions, l'organització del treball autònom de l'alumne des dels pressupòsits d'una avaluació continuada, la incorporació de les TIC com autèntics recursos d'ensenyament-aprenentatge, la col·laboració amb d'altres unitats de la Universitat de Barcelona que tinguessin entre els seus objectius l'impuls de l'aprenentatge, i el seguiment del procés d'implantació de la iniciativa didàctica i l'anàlisi regular dels seus resultats. Pel que fa a aquest darrer punt, en aquest primer període, hom ha prioritzat l'estudi de les dades quantitatives i quasi-quantitatives derivades del judici dels alumnes que participaren en la nova proposta didàctica. En conseqüència, la investigació va acomplir una primera funció diagnòstica de la innovació docent duta a terme, i es va enquadrar en la categoria dels estudis descriptius transversals a través d'enquestes amb mostres probabilístiques.

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.

Locating emergency services with different priorities: The priority queuing covering location problem

Previous covering models for emergency service consider all the calls to be of the sameimportance and impose the same waiting time constraints independently of the service's priority.This type of constraint is clearly inappropriate in many contexts. For example, in urban medicalemergency services, calls that involve danger to human life deserve higher priority over calls formore routine incidents. A realistic model in such a context should allow prioritizing the calls forservice.In this paper a covering model which considers different priority levels is formulated andsolved. The model heritages its formulation from previous research on Maximum CoverageModels and incorporates results from Queuing Theory, in particular Priority Queuing. Theadditional complexity incorporated in the model justifies the use of a heuristic procedure.

On the throughput-WIP trade-off in queueing systems, diminishing returns and the threshold property: A linear programming approach

We present a new unifying framework for investigating throughput-WIP(Work-in-Process) optimal control problems in queueing systems,based on reformulating them as linear programming (LP) problems withspecial structure: We show that if a throughput-WIP performance pairin a stochastic system satisfies the Threshold Property we introducein this paper, then we can reformulate the problem of optimizing alinear objective of throughput-WIP performance as a (semi-infinite)LP problem over a polygon with special structure (a thresholdpolygon). The strong structural properties of such polygones explainthe optimality of threshold policies for optimizing linearperformance objectives: their vertices correspond to the performancepairs of threshold policies. We analyze in this framework theversatile input-output queueing intensity control model introduced byChen and Yao (1990), obtaining a variety of new results, including (a)an exact reformulation of the control problem as an LP problem over athreshold polygon; (b) an analytical characterization of the Min WIPfunction (giving the minimum WIP level required to attain a targetthroughput level); (c) an LP Value Decomposition Theorem that relatesthe objective value under an arbitrary policy with that of a giventhreshold policy (thus revealing the LP interpretation of Chen andYao's optimality conditions); (d) diminishing returns and invarianceproperties of throughput-WIP performance, which underlie thresholdoptimality; (e) a unified treatment of the time-discounted andtime-average cases.

Minimum price variations, time priority and quotes dynamics

We analyze the impact of a minimum price variation (tick) and timepriority on the dynamics of quotes and the trading costs when competitionfor the order flow is dynamic. We find that convergence to competitiveoutcomes can take time and that the speed of convergence is influencedby the tick size, the priority rule and the characteristics of the orderarrival process. We show also that a zero minimum price variation is neveroptimal when competition for the order flow is dynamic. We compare thetrading outcomes with and without time priority. Time priority is shownto guarantee that uncompetitive spreads cannot be sustained over time.However it can sometimes result in higher trading costs. Empiricalimplications are proposed. In particular, we relate the size of thetrading costs to the frequency of new offers and the dynamics of theinside spread to the state of the book.

Optimization of multiclass queueing networks with changeover times via the achievable region approach: Part I, the single-station case

We address the performance optimization problem in a single-stationmulticlass queueing network with changeover times by means of theachievable region approach. This approach seeks to obtainperformance bounds and scheduling policies from the solution of amathematical program over a relaxation of the system's performanceregion. Relaxed formulations (including linear, convex, nonconvexand positive semidefinite constraints) of this region are developedby formulating equilibrium relations satisfied by the system, withthe help of Palm calculus. Our contributions include: (1) newconstraints formulating equilibrium relations on server dynamics;(2) a flow conservation interpretation of the constraintspreviously derived by the potential function method; (3) newpositive semidefinite constraints; (4) new work decomposition lawsfor single-station multiclass queueing networks, which yield newconvex constraints; (5) a unified buffer occupancy method ofperformance analysis obtained from the constraints; (6) heuristicscheduling policies from the solution of the relaxations.

Headspace needle-trap analysis of priority volatile organic compounds from aqueous samples: application to the analysis of natural and waste waters

Combining headspace (HS) sampling with a needle-trap device (NTD) to determine priority volatile organic compounds (VOCs) in water samples results in improved sensitivity and efficiency when compared to conventional static HS sampling. A 22 gauge stainless steel, 51-mm needle packed with Tenax TA and Carboxen 1000 particles is used as the NTD. Three different HS-NTD sampling methodologies are evaluated and all give limits of detection for the target VOCs in the ng L−1 range. Active (purge-and-trap) HS-NTD sampling is found to give the best sensitivity but requires exhaustive control of the sampling conditions. The use of the NTD to collect the headspace gas sample results in a combined adsorption/desorption mechanism. The testing of different temperatures for the HS thermostating reveals a greater desorption effect when the sample is allowed to diffuse, whether passively or actively, through the sorbent particles. The limits of detection obtained in the simplest sampling methodology, static HS-NTD (5 mL aqueous sample in 20 mL HS vials, thermostating at 50 °C for 30 min with agitation), are sufficiently low as to permit its application to the analysis of 18 priority VOCs in natural and waste waters. In all cases compounds were detected below regulated levels

Research Priorities for seabirds: Improving seabird conservation and management in the 21st century

Seabirds are facing a growing number of threats in both terrestrial and marine habitats, and many populations have experienced dramatic changes over past decades. Years of seabird research have improved our understanding of seabird populations and provided a broader understanding of marine ecological processes. In an effort to encourage future research and guide seabird conservation science, seabird researchers from 9 nations identified the 20 highest priority research questions and organized these into 6 general categories: (1) population dynamics, (2) spatial ecology, (3) tropho-dynamics, (4) fisheries interactions, (5) response to global change, and (6) management of anthropogenic impacts (focusing on invasive species, contaminants and protected areas). For each category, we provide an assessment of the current approaches, challenges and future directions. While this is not an exhaustive list of all research needed to address the myriad conservation challenges seabirds face, the results of this effort represent an important synthesis of current expert opinion across sub-disciplines within seabird ecology. As this synthesis highlights, research, in conjunction with direct management, education, and community engagement, can play an important role in facilitating the conservation and management of seabird populations and of the ocean ecosystems on which they and we depend.

La Perspectiva biofísica de la relació home-natura: economia ecològica

L'estudi de la relació entre l'activitat econòmica i el medi que ens envolta és antiga en economia. No obstant és cert que darrerament la teoria econòmica sembla haver-la oblidada. És per això que quan sortí la disciplina que avui s’anomena "economia ecològica" va implicar una ruptura amb la manera amb la qual la teoria econòmica convencional descrivia nostra relació amb el medi ambient. El present capítol pretén descriure breument el que creiem són les característiques principals que la fan diferent de la resta de disciplines: la inconmensurabilitat de valors, la seva anàlisi en termes biofísics, i les seves repercussions al nivell de la generació de polítiques, que la fan ser un exemple del que es coneix com a ciència post-normal.

L'aventura d'apendre a parlar

Treball de recerca realitzat per un alumne d’ensenyament secundari i guardonat amb un Premi CIRIT per fomentar l'esperit científic del Jovent l’any 2005. L’objectiu fonamental ha estat la descripció i l’anàlisi lingüística de la parla dels nens petits, és a dir, dels nens de P-2 a P-5, mitjançant una aproximació eminentment pràctica amb un breu recolzament teòric. En una breu introducció teòrica es defineixen els termes lingüístics i les disciplines utilitzades en l’estudi, s’expliquen els diferents factors que intervenen en el procés de la parla, ja que el fet de parlar suposa haver arribat a un grau determinat de desenvolupament físic, motor, sensorial, cognitiu, etc. També s’esmenten les relacions entre llenguatge i pensament i les diverses teories que expliquen l’origen del llenguatge. I, per acabar, es fa una pinzellada a les característiques evolutives dels nens des del seu naixement fins que tenen cinc-sis anys. En la part pràctica, s’analitza la parla dels nens de P-2 a P-5 mitjançant el mètode de l’enquesta directa a una seixantena de nens i d’altres proves, fent referència a una sèrie d’aspectes lingüístics considerats importants per tal d’entendre l’evolució de la parla en cada edat com són els nivells morfològic, sintàctic, fonètic, lèxic, així com els elements de la comunicació no verbal.