Equivalence of two linear programming relaxations for broadcast scheduling

A server needs to compute a broadcast schedule for n pages whose request times are known in advance. Outputting a page satisfies all outstanding requests for the page. The goal is to minimize the average waiting time of a client. In this paper, we show the equivalence of two apparently different relaxations that have been considered for this problem.     

Strongly polynomial-time approximation for a class of bicriteria problems

Consider the following problem: given a ground set and two minimization objectives of the same type find a subset from a given subset-class that minimizes the first objective subject to a budget constraint on the second objective. Using Megiddo's parametric method we improve an earlier weakly polynomial time algorithm.     

Low‐gain adaptive stabilization of semilinear second‐order hyperbolic systems

In this paper low‐gain adaptive stabilization of undamped semilinear second‐order hyperbolic systems is considered in the case where the input and output operators are collocated. The linearized systems have an infinite number of poles and zeros on the imaginary axis. The adaptive stabilizer is constructed by a low‐gain adaptive velocity feedback. The closed‐loop system is governed by a non‐linear evolution equation. First, the well‐posedness of the closed‐loop system is shown. Next, an energy‐like function and a multiplier function are introduced and the exponential stability of the closed‐loop system is analysed. Some examples are given to illustrate the theory. Copyright © 2004 John Wiley & Sons, Ltd.     

Decomposition Methods for Differentiable Optimization Problems over Cartesian Product Sets

This paper presents a unified analysis of decomposition algorithms for continuously differentiable optimization problems defined on Cartesian products of convex feasible sets. The decomposition algorithms are analyzed using the framework of cost approx imation algorithms. A convergence analysis is made for three decomposition algorithms: a sequential algorithm which extends the classical Gauss-Seidel scheme, a synchronized parallel algorithm which extends the Jacobi method, and a partially asynchronous parallel algorithm. The analysis validates inexact computations in both the subproblem and line search phases, and includes convergence rate results. The range of feasible step lengths within each algorithm is shown to have a direct correspondence to the increasing degree of parallelism and asynchronism, and the resulting usage of more outdated information in the algorithms.     

Parallel Algorithm for Unconstrained Optimization Based on Decomposition Techniques

We present a numerical implementation of the parallel gradient distribution (PGD) method for the solution of large-scale unconstrained optimization problems. The proposed parallel algorithm is characterized by a parallel phase which exploits the portions of the gradient of the objective function assigned to each processor; then, a coordination phase follows which, by a synchronous interaction scheme, optimizes over the partial results obtained by the parallel phase. The parallel and coordination phases are implemented using a quasi-Newton limited-memory BFGS approach. The computational experiments, carried out on a network of UNIX workstations by using the parallel software tool PVM, show that parallelization efficiency was problem dependent and ranged between 0.15 and 8.75. For the 150 problems solved by PGD on more than one processor, 85 cases had parallelization efficiency below 1, while 65 cases had a parallelization efficiency above 1.     

Adaptive remeshing for ductile fracture prediction in metal formingRemaillage adaptatif pour la prévision de la rupture ductile en mise en forme

The analysis of mechanical structures using the Finite Element Method in the framework of large elastoplastic strain, needs frequent remeshing of the deformed domain during computation. Indeed, the remeshing is due to the large geometrical distortion of finite elements and the adaptation to the physical behavior of the solution. This paper gives the necessary steps to remesh a mechanical structure during large elastoplastic deformations with damage. An important part of this process is constituted by geometrical and physical error estimates. The proposed method is integrated in a computational environment using the ABAQUS/Explicit solver and the BL2D-V2 adaptive mesher. To cite this article: H. Borouchaki et al., C. R. Mecanique 330 (2002) 709–716.     

浅水中污染物扩散的自适应有限元分析法

介绍浅水中污染物扩散分析中的有限元法.分析包括两个部分:1)流场速度、水面高度的计算;2)根据扩散模型计算污染物浓度场.联合使用了自适应网格技术以期提高解的精度,同时减少计算时间和计算机内存的消耗.通过几个有已知解的实例验证了有限元公式和计算机程序.最后,使用这种联合方法分析泰国Chao Phraya河附近海湾中的污染物扩散.     

Locally Adaptive Wavelet Empirical Bayes Estimation of a Location Parameter

The traditional empirical Bayes (EB) model is considered with the parameter being a location parameter, in the situation when the Bayes estimator has a finite degree of smoothness and, possibly, jump discontinuities at several points. A nonlinear wavelet EB estimator based on wavelets with bounded supports is constructed, and it is shown that a finite number of jump discontinuities in the Bayes estimator do not affect the rate of convergence of the prior risk of the EB estimator to zero. It is also demonstrated that the estimator adjusts to the degree of smoothness of the Bayes estimator, locally, so that outside the neighborhoods of the points of discontinuities, the posterior risk has a high rate of convergence to zero. Hence, the technique suggested in the paper provides estimators which are significantly superior in several respects to those constructed earlier.     

Scheduling orders for multiple product types to minimize total weighted completion time

We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (?2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space.     

松纵坑切梢小蠹虫害的仿真模型与生态防治的优化策略

根据松纵坑切梢小蠹的主要生物学特征,通过分析抚育间伐持续控制松纵坑切梢小蠹虫害的机理,应用复杂适应系统(CA S)理论,建立了模拟松纵坑切梢小蠹虫害的一种动态演化数学模型,并讨论了模型的收敛性.然后选用昆明小哨林场为背景,进行了各种抚育间伐决策的仿真,从中优选抚育间伐决策.结果表明:模拟优化方案与实际调查统计分析结果一致:均为弱度间伐与中弱度间伐控制蠹害效果最好.最后通过森林积材量与虫害程度之间的优化,给出了抚育间伐的优化策略.