A note on scheduling to meet two min-sum objectives

We consider a single machine scheduling problem with two min-sum objective functions: the sum of completion times and the sum of weighted completion times. We propose a simple polynomial time (1+(1/γ),1+γ)-approximation algorithm, and show that for γ>1, there is no (x,y)-approximation with 1<x<1+(1/γ) and 1<y<1+(γ-1)/(2+γ).     

Asymptotics in the Baum—Katz formula for random fields

In 1996, D. Deng established an analog of the Baum—Katz theorem on the convergence rate in the law of large numbers for multi-indexed random variables. The series describing the convergence rate depends, in a natural way, on the parameter characterizing the excess of the normalized sums over some level. In this paper, we find the precise asymptotics of the sum of this series with respect to the above-mentioned parameter. Thus, a generalization of a recent result due to A. Gut and A. Spataru is obtained.     

Stationary remaining service time conditional on queue length

In Mandelbaum and Yechiali [The conditional residual service time in the M/G/1 queue, http://www.math.tau.ac.il/∼uriy/publications (No. 30a), 1979] and in Fakinos [The expected remaining service time in a single-server queue, Oper. Res. 30 (1982) 1014-1018] a simple formula is derived for the (stationary) expected remaining service time in a M/G/1 queue, conditional on the number of customers in the system. We give a short new proof of the formula using Rate Conservation Law, and generalize to handle higher moments.     

Estimating tail probabilities of heavy tailed distributions with asymptotically zero relative error

Efficient estimation of tail probabilities involving heavy tailed random variables is amongst the most challenging problems in Monte-Carlo simulation. In the last few years, applied probabilists have achieved considerable success in developing efficient algorithms for some such simple but fundamental tail probabilities. Usually, unbiased importance sampling estimators of such tail probabilities are developed and it is proved that these estimators are asymptotically efficient or even possess the desirable bounded relative error property. In this paper, as an illustration, we consider a simple tail probability involving geometric sums of heavy tailed random variables. This is useful in estimating the probability of large delays in M/G/1 queues. In this setting we develop an unbiased estimator whose relative error decreases to zero asymptotically. The key idea is to decompose the probability of interest into a known dominant component and an unknown small component. Simulation then focuses on estimating the latter ‘residual’ probability. Here we show that the existing conditioning methods or importance sampling methods are not effective in estimating the residual probability while an appropriate combination of the two estimates it with bounded relative error. As a further illustration of the proposed ideas, we apply them to develop an estimator for the probability of large delays in stochastic activity networks that has an asymptotically zero relative error.      

Error estimate for the approximation of nonlinear conservation laws on bounded domains by the finite volume method

In this paper we derive a priori and a posteriori error estimates for cell centered finite volume approximations of nonlinear conservation laws on polygonal bounded domains. Numerical experiments show the applicability of the a posteriori result for the derivation of local adaptive solution strategies.

     

TDI线扫相机光学通道建模与仿真

卫星相机建模与仿真研究不论在民用还是军事领域都具有重要的理论研究和实际应用价值。根据TDI线扫相机的工作原理建立了一个TDI线扫相机光学通道的数学模型,该模型包括从景物到TDI CCD离散图像的几何投影关系和能量传递关系两部分,对于确定的成像系统,给定景物参数和光学系统参数,就可以确定对应图像传感器上的离散图像。为了验证模型,对一幅卫星图像进行了计算机仿真。建立的模型可以用来研究当成像条件改变时对图像的影响,进一步还可以用来发展虚拟卫星相机系统。     

Colliding stacks: A large deviations analysis

We analyze the performance of a prototypical scheme for shared storage allocation: two initially empty stacks evolving in a contiguous block of memory of size m. We treat the case in which the stacks are more likely to shrink than grow, but with the probabilities of insertion and deletion allowed to depend arbitrarily on stack height as a fraction of m. New results are obtained on the m → ∞ asymptotics of the stack collision time, and of the final stack heights. The results of Wentzell and Freidlin on the large deviations of Markov chains are used, and the relation of their formalism to the Hamiltonian formulation of classical mechanics is emphasized. Certain results on higher-order asymptotics follow from WKB expansions.     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

Convergence Rate of The Trust Region Method for Nonlinear Equations Under Local Error Bound Condition

In this paper, we present the new trust region method for nonlinear equations with the trust region converging to zero. The new method preserves the global convergence of the traditional trust region methods in which the trust region radius will be larger than a positive constant. We study the convergence rate of the new method under the local error bound condition which is weaker than the nonsingularity. An example given by Y.X. Yuan shows that the convergence rate can not be quadratic. Finally, some numerical results are given. This work is supported by Chinese NSFC grants 10401023 and 10371076, Research Grants for Young Teachers of Shanghai Jiao Tong University, and E-Institute of Computational Sciences of Shanghai Universities. An erratum to this article is available at .     

Computing Aviation Sparing Policies: Solving a Large Nonlinear Integer Program

Deployed US Navy aircraft carriers must stock a large number of spare parts to support the various types of aircraft embarked on the ship. The sparing policy determines the spares that will be stocked on the ship to keep the embarked aircraft ready to fly. Given a fleet of ten or more aircraft carriers and a cost of approximately 50 million dollars per carrier plus the cost of spares maintained in warehouses in the United States, the sparing problem constitutes a significant portion of the Navy’s resources. The objective of this work is to find a minimum-cost sparing policy that meets the readiness requirements of the embarked aircraft. This is a very large, nonlinear, integer optimization problem. The cost function is piecewise linear and convex while the constraint mapping is highly nonlinear. The distinguishing characteristics of this problem from an optimization viewpoint are that a large number of decision variables are required to be integer and that the nonlinear constraint functions are essentially “black box” functions; that is, they are very difficult (and expensive) to evaluate and their derivatives are not available. Moreover, they are not convex. Integer programming problems with a large number of variables are difficult to solve in general and most successful approaches to solving nonlinear integer problems have involved linear approximation and relaxation techniques that, because of the complexity of the constraint functions, are inappropriate for attacking this problem. We instead employ a pattern search method to each iteration of an interior point-type algorithm to solve the relaxed version of the problem. From the solution found by the pattern search on each interior point iteration, we begin another pattern search on the integer lattice to find a good integer solution. The best integer solution found across all interations is returned as the optimal solution. The pattern searches are distributed across a local area network of non-dedicated, heterogeneous computers in an office environment, thus, drastically reducing the time required to find the solution.