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.     

高速色散补偿系统中喇曼放大器性能研究

利用喇曼放大器的非线性偏微分耦合方程组,对带喇曼放大器的色散补偿系统进行了仿真,并与传统的仿真方法进行了比较.结果表明:在色散完全补偿系统中,当传输速率较高时,忽略色散后的传统仿真方法的结果,与采用色散补偿技术后使整个系统色散为零的仿真结果有一定偏差,此时不能忽略色散的作用.还对前补偿系统和后补偿系统进行了研究,利用Q值性能判别法,分别得到了信号光脉冲的最佳占空比和最佳脉冲阶数.     

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.     

Vibrational control of crystal growth from liquid phase

Modeling and numerical simulations of the convective flows induced by the vibration of the monocrystal during crystal growth have been performed for two configurations simulating the Cz and FZ methods. This permitted to emphasize the role of different vibrational mechanisms in the formation of the average flows. It is shown that an appropriate combination of these mechanisms can be used to counteract the usual convective flows (buoyancy- and/or thermocapillary-driven) inherent to crystal growth processes from the liquid phase. While vibrational convection is rather complex due to these identified mechanisms, the new modeling used in the present paper opens up very promising perspectives to efficiently control heat and mass transfer during real industrial applications of crystal growth from the liquid phase.     

Two-dimensional numerical calculation of the flow field about a scoop inlet by the piecewise linear method

The piecewise linear method (PLM) based on time operator splitting is used to solve the unsteady compressible Euler equations describing the two-dimensional flow around and through a straight wall inlet placed stationary in a rapidly rotating supersonic flow. The PLM scheme is formulated as a Lagrangian step followed by an Eulerian remap. The inhomogeneous terms in the Euler equations written in cylindrical coordinates are first removed by Sod's method and the resulting set of equations is further reduced to two sets of one-dimensional Lagrangian equations, using time operator splitting. The numerically generated flow fields are presented for different values of the back pressure imposed at the downstream exit of the inlet nozzle. An oblique shock wave is formed in front of the almost whole portion of the inlet entrance, the incoming streamlines being deflected towards the higher pressure side after passing through the oblique shock wave and then bending down to the lower pressure side. A reverse flow appears inside the inlet nozzle owing to the recovery pressure of the incoming streams being lower than the back pressure of the inlet nozzle.     

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.     

Optimal design of a convergent-barrel cold spray nozzle by numerical method

A convergent-barrel (CB) cold spray nozzle was designed through numerical simulation. It was found that the main factors influencing significantly particle velocity and temperature include the length and diameter of the barrel section, the nature of the accelerating gas and its pressure and temperature, and the particle size. Particles can achieve a relatively low velocity but a high temperature under the same gas pressure using a CB nozzle compared to a convergent-divergent (CD) nozzle. The experiment results with Cu powder using the designed CB nozzle confirmed that particle deposition can be realized under a lower gas pressure with a CB nozzle.     

On the construction of samples for testing approximate optimization methods for estimate calculation algorithms

To validate approximate optimization schemes for estimate calculation algorithms (ECAs), it is necessary to compute the optimal height, which cannot be done in a reasonable amount of time. A variety of samples are built for which the optimal height of the ECAs is known by construction.