The Efficiency of Two Groups of <Emphasis Type="Italic">N</Emphasis> Machines Served by a Single Robot

Many modern manufacturing facilities use carousel conveyors for storage of work-in-progress, and automatic devices to place and retrieve items in and from the storage locations. The ‘carousel conveyor problem’ is directly related to the ‘patrolling repairman problem’ reported by others. In this paper, we extend the model to include a single robot serving two or more carousels. The approach makes use of known results for the patrolling repairman.     

Cyclic multiple-robot scheduling with time-window constraints using a critical path approach

An automated production system is considered in which several robots are used for transporting parts between workstations following a given route in a carousel mode. The problem is to maximize the throughput rate. Extending previous works treating scheduling problems for a single robot, we consider a more realistic case in which workstations are served by multiple robots. A graph model of the production process is developed, making it possible to apply PERT–CPM solution techniques. The problem is proved to be solvable in polynomial time.     

Order sequencing on a unidirectional cyclical picking line

A real life order-picking configuration that requires multiple pickers to cyclically move around fixed locations in a single direction is considered. This configuration is not the same, but shows similarities to, unidirectional carousel systems described in literature. The problem of minimising the pickers’ travel distance to pick all orders on this system is a variant of the clustered travelling salesman problem. An integer programming (IP) formulation of this problem cannot be solved in a realistic time frame for real life instances of the problem. A relaxation of this IP formulation is proposed that can be used to determine a lower bound on an optimal solution. It is shown that the solution obtained from this relaxation can always be transformed to a feasible solution for the IP formulation that is, at most, within one pick cycle of the lower bound. The computational results and performance of the proposed methods as well as adapted order sequencing approaches for bidirectional carousel systems from literature are compared to one another by means of real life historical data instances obtained from a retail distribution centre.     

On the class of infinite horizon optimal control problems affine,which are structurally stable

We prove in this article that there is in the set of all problems we consider a subset, which is residual. Every problem in this subset is shown to be structurally stable and defines a dynamical system, which looks like the graph of the figure given in Section  1 , contrary to what happens for ordinary dynamical systems, that is, the ones associated with ODEs. There, the initial value problem (in the smooth case) is uniquely solvable; the structurally stable systems look like the figure given in Section  1 , but sources are equilibria. Copyright © 2015 John Wiley & Sons, Ltd.     

Multiple Order Pick Sequencing in a Carousel System: A Solvable Case of the Rural Postman Problem

We consider the problem of sequencing picks in a set of orders on a single carousel. First we consider the situation in which the sequence of the orders is given. For this problem we present an efficient dynamic programming algorithm. Second, we consider the problem without a given order sequence. We simplify this problem to a Rural Postman Problem on a circle and solve this problem to optimality. Finally, we show that the solution of the Rural Postman Problem requires at most 1.5 revolutions more than a lower bound of an optimum solution to the original problem.     

An Approximation Scheme for Uncertain Minimax Optimal Control Problems

In this work, we address an uncertain minimax optimal control problem with linear dynamics where the objective functional is the expected value of the supremum of the running cost over a time interval. By taking an independently drawn random sample, the expected value function is approximated by the corresponding sample average function. We study the epi-convergence of the approximated objective functionals as well as the convergence of their global minimizers. Then we define an Euler discretization in time of the sample average problem and prove that the value of the discrete time problem converges to the value of the sample average approximation. In addition, we show that there exists a sequence of discrete problems such that the accumulation points of their minimizers are optimal solutions of the original problem. Finally, we propose a convergent descent method to solve the discrete time problem, and show some preliminary numerical results for two simple examples.     

两种汇率制度的双币种期权定价模型及其解

采用人民币对美元的汇率数据、利用计量经济学方法得到:固定汇率并不意味着完全没有变化,它是时间的函数.在实证研究的基础上,提出了固定汇率制度和浮动汇率制度下的双币种期权定价模型,并得到该问题的闭式解.     

国家的可持续发展分析

以社会、经济、环境与资源和制度作为基础指标,建立了评价国家可持续发展的综合指标体系。首先,利用熵值法计算各基础指标值,并将每个国家的基础指标值画在同一轴线的雷达图上,直观描述和比较各个国家目前的可持续发展情况。同时,以4个基础指标值为顶点的四边形面积大小作为一个国家可持续发展的综合指数。通过对10个国家的分析,验证了模型的有效性。其次,综合考虑4个基础指标,建立了4维静态趋势分析的优化模型,用以描述每个国家可持续发展程度的变化过程及相关政策与援助对可持续发展指标的影响。最后,基于雷达图模型的分析,选取埃塞俄比亚作为研究对象,借助4维静态趋势分析模型,制定了埃塞俄比亚未来20年的发展规划,并通过雷达图模型验证了规划的有效性,同时对模型的优势与不足进行评述。     

Convergence of Rump's method for inverting arbitrarily ill-conditioned matrices

In this paper, the problem of inverting regular matrices with arbitrarily large condition number is treated in double precision defined by IEEE 754 floating point standard. In about 1984, Rump derived a method for inverting arbitrarily ill-conditioned matrices. The method requires the possibility to calculate a dot product in higher precision. Rump's method is of theoretical interest. Rump made it clear that inverting an arbitrarily ill-conditioned matrix in single or double precision does not produce meaningless numbers, but contains a lot of information in it. Rump's method uses such inverses as preconditioners. Numerical experiments exhibit that Rump's method converges rapidly for various matrices with large condition numbers. Why Rump's method is so efficient for inverting arbitrarily ill-conditioned matrices is a little mysterious. Thus, to prove its convergence is an interesting problem in numerical error analysis. In this article, a convergence theorem is presented for a variant of Rump's method.     

The accurate solution of certain continuous problems using only single precision arithmetic

A typical approach for finding the approximate solution of a continuous problem is through discretization with meshsizeh such that the truncation error goes to zero withh. The discretization problem is solved in floating point arithmetic. Rounding-errors spoil the theoretical convergence and the error may even tend to infinity.In this paper we present algorithms of moderate cost which use only single precision and which compute the approximate solution of the integration and elliptic equation problems with full accuracy. These algorithms are based on the modified Gill-Møller algorithm for summation of very many terms, iterative refinement of a linear system with a special algorithm for the computation of residuals in single precision and on a property of floating point subtraction of nearby numbers.On leave of absence from Institute of Informatics, University of Warsaw, 00-901 Warsaw, Poland.This research was supported in part by the National Science Foundation under Grant MCS-7823676.     

A packet filter placement problem with application to defense against spoofed denial of service attacks

We analyze a problem in computer network security, wherein packet filters are deployed to defend a network against spoofed denial of service attacks. Information on the Internet is transmitted by the exchange of IP packets, which must declare their origin and destination addresses. A route-based packet filter verifies whether the purported origin of a packet is correct with respect to the current route map. We examine the optimization problem of finding a minimum cardinality set of nodes to filter in the network such that no spoofed packet can reach its destination. We prove that this problem is NP-hard, and derive properties that explicitly relate the filter placement problem to the vertex cover problem. We identify topologies and routing policies for which a polynomial-time solution to the minimum filter placement problem exists, and prove that under certain routing conditions a greedy heuristic for the filter placement problem yields an optimal solution.     

A free boundary and an optimal shape problem of a floating body

The present article deals with a variational formulation of a floating body in a perfect fluid. Since the considered energy functional depends on both stream function and floating body, these two minimizations are realized in two separated steps. By the use of free boundary methods, existence and Lipschitz continuity of the minimizing stream function are proved. In addition, it is shown that the corresponding free surface has Hölder boundary. The dependence on the floating body leads to an optimal shape problem which is treated by the use of Hausdorff convergence. Under the postulate of a bounded density parameter of the domain, the existence of an optimal floating body is shown.     

The empirical bayes rules with floating optimal sample size for exponential conditional distributions

Summary We consider the empirical Bayes solution in such a situation where the sample size is successively determined by a rule which includes the Bayes risks and the observation costs. The empirical Bayes floating optimal sample size depends on current as well as on previous information assumed to be collected from earlier performances of similar decisions. The sampling is done from an exponential conditional distribution, with a single parameter. The proofs, which show the asymptotic optimality of the empirical Bayes solution, are presented for a hypotheses-testing problem. A straight generalization to a multiple decision problem is also given.     

两部件并联维修系统算子的性质

研究了两部件并联维修系统算子的性质,通过选取空间和定义算子将模型方程转化成了抽象柯西问题,证明了系统算子是定义域稠的预解正算子,0是系统算子的几何重数为1的本征值.讨论了系统算子的共轭算子及其定义域,证明了0是共轭算子的代数重数为1的特征值.     

Reducing trigonometric functions by using spokes on a carousel

In this note, a simple and quick method is shown for reducing some trigonometric expressions by using a diagram called a ‘carousel’. These expressions can be reduced using other methods, such as: (i) reduction formulae for sum/difference of angles; and (ii) graph shifting techniques.     

Voronoi drawings of trees

We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree T, can one represent T so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows.

• We characterize those trees that can be drawn as Voronoi diagrams in the Euclidean metric.

• We characterize those sets of points whose Voronoi diagrams are trees in the Manhattan metric.

• We show that the maximum vertex degree of any tree that can be drawn as a Manhattan Voronoi diagram is at most five and prove that this bound is tight.

• We characterize those binary trees that can be drawn as Manhattan Voronoi diagrams.

Equivalence of floating and fixed strike Asian and lookback options

We prove a symmetry relationship between floating strike and fixed strike Asian options for assets driven by general Lévy processes using a change of numéraire and the characteristic triplet of the dual process. We apply the same technique to prove a similar relationship between floating strike and fixed strike lookback options.     

Construction of a CPA contraction metric for periodic orbits using semidefinite optimization

A Riemannian metric with a local contraction property can be used to prove existence and uniqueness of a periodic orbit and determine a subset of its basin of attraction. While the existence of such a contraction metric is equivalent to the existence of an exponentially stable periodic orbit, the explicit construction of the metric is a difficult problem.In this paper, the construction of such a contraction metric is achieved by formulating it as an equivalent problem, namely a feasibility problem in semidefinite optimization. The contraction metric, a matrix-valued function, is constructed as a continuous piecewise affine (CPA) function, which is affine on each simplex of a triangulation of the phase space. The contraction conditions are formulated as conditions on the values at the vertices.The paper states a semidefinite optimization problem. We prove on the one hand that a feasible solution of the optimization problem determines a CPA contraction metric and on the other hand that the optimization problem is always feasible if the system has an exponentially stable periodic orbit and the triangulation is fine enough. An objective function can be used to obtain a bound on the largest Floquet exponent of the periodic orbit.     

Neutrally Floating Objects of Density ½ in Three Dimensions

This paper is concerned with the Floating Body Problem of S. Ulam: the existence of objects other than the sphere, which can float in liquid in any orientation. Despite recent results of F. Wegner pointing towards an affirmative answer, a full proof of their existence is still unavailable. For objects with cylindrical symmetry and density 1/2, the conditions of neutral floating are formulated as an initial value problem, for which a unique solution is predicted in certain cases by a suitable generalization of the Picard–Lindelöf theorem. Numerical integration of the initial value problem provides a rich variety of neutrally floating shapes.     

A multi-level bottleneck assignment approach to the bus drivers' rostering problem

The problem of finding a work assignment for drivers in a given time horizon, in such a way as to have an even distribution of the workload, is considered. This problem is formulated as a Multi-level Bottleneck Assignment Problem (MBA). The MBA problem is studied: it is shown that it is NP-complete and an asymptotically optimal algorithm is presented. Some computational results are illustrated which prove the efficiency of the algorithm.