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.

Implementation, elimination of weakly dominated strategies and evolutionary dynamics

This paper is concerned with the realism of mechanisms that implementsocial choice functions in the traditional sense. Will agents actually playthe equilibrium assumed by the analysis? As an example, we study theconvergence and stability properties of Sj\"ostr\"om's (1994) mechanism, onthe assumption that boundedly rational players find their way to equilibriumusing monotonic learning dynamics and also with fictitious play. Thismechanism implements most social choice functions in economic environmentsusing as a solution concept the iterated elimination of weakly dominatedstrategies (only one round of deletion of weakly dominated strategies isneeded). There are, however, many sets of Nash equilibria whose payoffs maybe very different from those desired by the social choice function. Withmonotonic dynamics we show that many equilibria in all the sets ofequilibria we describe are the limit points of trajectories that havecompletely mixed initial conditions. The initial conditions that lead tothese equilibria need not be very close to the limiting point. Furthermore,even if the dynamics converge to the ``right'' set of equilibria, it stillcan converge to quite a poor outcome in welfare terms. With fictitious play,if the agents have completely mixed prior beliefs, beliefs and play convergeto the outcome the planner wants to implement.

Communication, coordination and efficiency in evolutionary one-population models

We analyze the role of commitment in pre-play communication for ensuringefficient evolutionarily stable outcomes in coordination games. All players are a priori identical as they are drawn from the same population. In games where efficient outcomes can be reached by players coordinating on the same action we find commitment to be necessary to enforce efficiency. In games where efficienct outcomes only result from play of different actions, communication without commitment is most effective although efficiency can no longer be guaranteed. Only when there are many messages then inefficient outcomes are negligible as their basins of attraction become very small.

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.

On forward induction and evolutionary and strategic stability

We analyze which normal form solution concepts capture the notion offorward induction, as defined by van Damme (JET, 1989) in the classof generic two player normal form games preceded by an outsideoption. We find that none of the known strategic stability concepts(including Mertens stable sets and hyperstable sets) captures this form of forward induction. On the other hand, we show that the evolutionary concept of EES set (Swinkels, JET, 1992) is always consistent with forward induction.

A new chance-constrained maximum capture location problem

The paper presents a new model based on the basic Maximum Capture model,MAXCAP. The New Chance Constrained Maximum Capture modelintroduces astochastic threshold constraint, which recognises the fact that a facilitycan be open only if a minimum level of demand is captured. A metaheuristicbased on MAX MIN ANT system and TABU search procedure is presented tosolve the model. This is the first time that the MAX MIN ANT system isadapted to solve a location problem. Computational experience and anapplication to 55 node network are also presented.

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.

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.

On the structural difference between the evolutionary approach of Young and that of Kandori, Mailath and Rob

We provide robust examples of symmetric two-player coordination games in normal form that reveal that equilibrium selection bythe evolutionary model of Young (1993) is essentially different from equilibrium selection by the evolutionary model of Kandori, Mailath and Rob (1993).

Improvement of the quality factor of RF integrated inductors by layout optimization

A systematic method to improve the quality (Q) factor of RF integrated inductors is presented in this paper. The proposed method is based on the layout optimization to minimize the series resistance of the inductor coil, taking into account both ohmic losses, due to conduction currents, and magnetically induced losses, due to eddy currents. The technique is particularly useful when applied to inductors in which the fabrication process includes integration substrate removal. However, it is also applicable to inductors on low-loss substrates. The method optimizes the width of the metal strip for each turn of the inductor coil, leading to a variable strip-width layout. The optimization procedure has been successfully applied to the design of square spiral inductors in a silicon-based multichip-module technology, complemented with silicon micromachining postprocessing. The obtained experimental results corroborate the validity of the proposed method. A Q factor of about 17 have been obtained for a 35-nH inductor at 1.5 GHz, with Q values higher than 40 predicted for a 20-nH inductor working at 3.5 GHz. The latter is up to a 60% better than the best results for a single strip-width inductor working at the same frequency.

Hamilton Jacobi theory for constrained systems

We extend the HamiltonJacobi formulation to constrained dynamical systems. The discussion covers both the case of first-class constraints alone and that of first- and second-class constraints combined. The HamiltonDirac equations are recovered as characteristic of the system of partial differential equations satisfied by the HamiltonJacobi function.

Equivalence Between the Lagrangian and Hamiltonian Formalisms for Constrained Systems

The equivalence between the Lagrangian and Hamiltonian formalism is studied for constraint systems. A procedure to construct the Lagrangian constraints from the Hamiltonian constraints is given. Those Hamiltonian constraints that are first class with respect to the Hamiltonian constraints produce Lagrangian constraints that are FL-projectable.

Lee HWA Chung theorem for presympectic manifolds. Canonical transformations for constrained systems

We generalize the analogous of Lee Hwa Chungs theorem to the case of presymplectic manifolds. As an application, we study the canonical transformations of a canonical system (M, S, O). The role of Dirac brackets as a test of canonicity is clarified.