Asymptotic analysis of the effect of arrival model uncertainties in some optimal routing problems

We study the effect of arrival model uncertainties on the optimal routing in a system of parallel queues. For exponential service time distributions and Bernoulli routing, the optimal mean system delay generally depends on the interarrival time distribution. Any error in modeling the arriving process will cause a model-based optimal routing algorithm to produce a mean system delay higher than the true optimum. In this paper, we present an asymptotic analysis of the behavior of this error under heavy traffic conditions for a general renewal arrival process. An asymptotic analysis of the error in optimal mean delay due to uncertainties in the service time distribution for Poisson arrivals was reported in Ref. 6, where it was shown that, when the first moment of the service time distribution is known, this error in performance vanishes asymptotically as the traffic load approaches the system capacity. In contrast, this paper establishes the somewhat surprising result that, when only the first moment of the arrival distribution is known, the error in optimal mean delay due to uncertainties in the arrival model is unbounded as the traffic approaches the system capacity. However, when both first and second moments are known, the error vanishes asymptotically. Numerical examples corroborating the theoretical results are also presented.This work was supported by the National Science Foundation under Grants ECS-88-01912 and EID-92-12122 and by NASA under Contract NAG 2-595.The authors wish to thank an anonymous referee for pointing out Ref. 20, thus avoiding the need for an explicit proof of convexity of the cost function considered in the paper.     

Investigation on chaotic motion in hysteretic non-linear suspension system with multi-frequency excitations

This paper presents the investigation on possible chaotic motion in a vehicle suspension system with hysteretic non-linearity, which is subjected to the multi-frequency excitation from road surface. The Melnikov’s function is used to derive the critical condition for the chaotic motion, and then it is investigated that the effects of parameters in non-linear damping on the chaotic field. The path from quasi-periodic to chaotic motion is found via Poincaré map and Lyapunov exponents.     

m-aryn-cube网络的最优路由

基于可选邻接点的概念,在m-ary n-cube网络中提出一种新的最优寻径算法.这种算法始终在当前结点的可选邻接点中选取最空闲邻接点作为下一个信息传输点.该算法使得从源结点到达目的结点路由是最短路由也是最快速路由,而且在多项式时间内可以完成.     

ICP－AES法测定富锗酵母中微量元素

本文采用美国ＬｅｅｍａｎＬａｂｓ公司中阶梯光栅光谱仪测定了人工培养的富锗酵母中高含量锗及镁、铜、锌、铁、钾、钠等微量元素，研究了富锗样品的前处理方法，样品加标回收率在９０％－１０３％之间，测量相对标准偏差：锗１０％，镁、铜、锌、铁、钾、钠等元素小于７％。     

Vehicle and personnel routing optimization in the service sector: application to water distribution and treatment

We present an overview of the author’s Ph.D. thesis, supervised by P. Dejax and N. Bostel, which was defended in February 2006 at école des Mines de Nantes, France. The thesis is written in French, and is available at . It was conducted in the context of a research contract with a water distribution company. In a first section, we define multiperiod routing problems for service technicians. In a second section, we present some heuristics and a memetic algorithm used to solve these problems. The third section introduces optimal and near-optimal approaches based on column generation. Finally, we present some applications to the real-life case. The methods presented in Sects. 2, 3 and 4 were tested over several sets of problems, based on real-life statistics provided by the company.      

Optimale Quantisierung

Zusammenfassung. Optimale Quantisierungen oder – damit ?quivalent – minimale Summen von Momenten spielen in mehreren Zweigen der Mathematik und ihrer Anwendungen eine Rolle. Ausgehend von der Fejes Tóth'schen Ungleichung für Summen von Momenten in der euklidischen Ebene und einem zugeh?rigen Stabilit?tssatz, werden gewisse Erweiterungen auf normierte R?ume und riemannsche Mannigfaltigkeiten h?herer Dimension besprochen. Die Ergebnisse werden dann auf Probleme aus folgenden Bereichen angewendet: (i) Datenübertragung, (ii) Wahrscheinlichkeitstheorie, (iii) numerische Integration, (iv) Approximation konvexer K?rper und (v) isoperimetrische Probleme. Eingegangen am 29. Mai 2002 / Angenommen am 8. Juli 2002     

A competitive (dual) simplex method for the assignment problem

Where there is abundance of mystery and confusion in every direction, the truth seldom remains hidden for long. It's a matter of having plenty of angles to go at it from. Only the utterly simple crimes - the simplex crimes, you may say - have the trick of remaining baffling. - Sir John (from Michael Innes,The Open House (A Sir John Appleby Mystery), Penguin Books, 1974).A dual simplex method for the assignment problem leaves open to choice the activity (i,j) of rowi and columnj that is to be dropped in pivoting so long asx _ij < 0. A choice (i,j) over columnsj having at least 3 basic activities that minimizesx _ij is shown to converge in at most ( ₂ ^n-1 ) pivots, and at most O(n ³) time, and it is argued that on average the number of pivots is at mostn logn. Dedicated with affection to George B. Dantzig on the occasion of his seventieth birthday.     

Tight bounds for christofides' traveling salesman heuristic

Christofides [1] proposes a heuristic for the traveling salesman problem that runs in polynomial time. He shows that when the graphG = (V, E) is complete and the distance matrix defines a function onV × V that is metric, then the length of the Hamiltonian cycle produced by the heuristic is always smaller than 3/2 times the length of an optimal Hamiltonian cycle. The purpose of this note is to refine Christofides' worst-case analysis by providing a tight bound for everyn 3, wheren is the number of vertices of the graph. We also show that these bounds are still tight when the metric is restricted to rectilinear distances, or to Euclidean distances for alln 6.This work was supported, in part, by NSF Grant ENG 75-00568 to Cornell University. This work was done when the authors were affiliated with the Center for Operations Research and Econometrics, University of Louvain, Belgium.     

A variable dimension algorithm for the linear complementarity problem

A variable dimension algorithm is presented for the linear complementarity problems – Mz = q; s,z 0; s _i z _i = 0 fori = 1,2, ,n. The algorithm solves a sequence of subproblems of different dimensions, the sequence being possibly nonmonotonic in the dimension of the subproblem solved. Every subproblem is the linear complementarity problem defined by a leading principal minor of the matrixM. Index-theoretic arguments characterize the points at which nonmonotonic behavior occurs.     

Cost operator algorithms for the transportation problem

A primal transportation algorithm is devised via post-optimization on the costs of a modified problem. The procedure involves altering the costs corresponding to the basic cells of the initial (primal feasible) solution so that it is dual feasible as well. The altered costs are then successively restored to their true values with appropriate changes in the optimal solution by the application of cell or area cost operators discussed elsewhere. The cell cost operator algorithm converges to optimum within (2T – 1) steps for primal nondegenerate transportation problems and [(2T + 1) min (m, n)] – 1 steps for primal degenerate transportation problems, whereT is the sum of the (integer) warehouse availabilities (also the sum of the (integer) market requirements) andm andn denote the number of warehouses and markets respectively. For the area cost operator algorithm the corresponding bounds on the number of steps areT and (T + 1) min (m, n) respectively.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie—Mellon University, under Contract N00014-67-A-0314-0007 NR 047-048 with the U.S. Office of Naval Research.