一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法

针对延迟工件数最小的混合流水车间调度问题,给出了一种改进的模拟退火求解算法. 该算法首先给出一个启发式算法来获得初始解,然后用模拟退火算法对初始解改进. 通过交换工件在第一阶段的排序来获得一个新的解,采用最先空闲设备分配规则和先到先被加工规则,对工件在剩余各级的工序进行调度. 实验仿真表明算法是可行有效的.     

离散变量结构优化设计的组合算法*

本文首先给出了离散变量优化设计局部最优解的定义,然后提出了一种综合的组合算法.该算法采用分级优化的方法,第一级优化首先采用计算效率很高且经过随机抽样性能实验表明性能较高的启发式算法─—相对差商法,求解离散变量结构优化设计问题近似最优解 X ;第二级采用组合算法,在 X 的离散邻集内建立离散变量结构优化设计问题的(-1,0.1)规划模型,再进一步将其化为(0,1)规划模型,应用定界组合算法或相对差商法求解该(0,1)规划模型,求得局部最优解.解决了采用启发式算法无法判断近似最优解是否为局部最优解这一长期未得到解决的问题,提高了计算精度,同时,由于相对差商法的高效率与高精度,以上综合的组合算法的计算效率也还是较高的.     

Stochastic Method for the Solution of Unconstrained Vector Optimization Problems

We propose a new stochastic algorithm for the solution of unconstrained vector optimization problems, which is based on a special class of stochastic differential equations. An efficient algorithm for the numerical solution of the stochastic differential equation is developed. Interesting properties of the algorithm enable the treatment of problems with a large number of variables. Numerical results are given.     

A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem

This paper presents an efficient solution algorithm for the multiconstraint zero-one knapsack problem through a branch and bound search process. The algorithm has been coded in FORTRAN; and a group of thirty 5-constraint knapsack problems with 30-90 variables were run on IBM 360/75 using two other codes as well, in order to compare the computational efficiency of the proposed method with that of the original Balas and an improved Balas additive algorithms. The computational results show that the proposed method is markedly faster with regard to the total as well as the individual solution times for these test problems, and such superiority becomes more evident as the number of variables and the difficulty of the problems increase. The results also indicated that the original Balas method is extremely inefficient for the type of problems being considered here. The total solution time for the thirty problems is 13 min for the proposed method, 109 min for the improved Balas algorithm, and over 380 min for the original Balas algorithm. Extension of the solution algorithm to the generalized knapsack problem is also suggested.     

Computation of the optimal tolls on the traffic network

The present paper is devoted to the computation of optimal tolls on a traffic network that is described as fuzzy bilevel optimization problem. As a fuzzy bilevel optimization problem we consider bilinear optimization problem with crisp upper level and fuzzy lower level. An effective algorithm for computation optimal tolls for the upper level decision-maker is developed under assumption that the lower level decision-maker chooses the optimal solution as well. The algorithm is based on the membership function approach. This algorithm provides us with a global optimal solution of the fuzzy bilevel optimization problem.     

Nonlinear Smoothing and the EM Algorithm for Positive Integral Equations of the First Kind

We study a modification of the EMS algorithm in which each step of the EMS algorithm is preceded by a nonlinear smoothing step of the form , where S is the smoothing operator of the EMS algorithm. In the context of positive integral equations (à la positron emission tomography) the resulting algorithm is related to a convex minimization problem which always admits a unique smooth solution, in contrast to the unmodified maximum likelihood setup. The new algorithm has slightly stronger monotonicity properties than the original EM algorithm. This suggests that the modified EMS algorithm is actually an EM algorithm for the modified problem. The existence of a smooth solution to the modified maximum likelihood problem and the monotonicity together imply the strong convergence of the new algorithm. We also present some simulation results for the integral equation of stereology, which suggests that the new algorithm behaves roughly like the EMS algorithm. Accepted 1 April 1997     

m步非线性多重分裂Newton法的收敛性

本文讨论了多重分裂算法在求解一类非线性方程组的全局收敛性和单侧收敛性．当用研步Newton法来代替求得每个非线性多重分裂子问题的近似解时，同样给出相应收敛性结论．数值算例证实了算法的有效性．     

A comparative analysis of adaptive algorithms in the finite element method for solving the boundary value problem for a stationary reaction-diffusion equation

A new adaptive algorithm is proposed for constructing grids in the hp-version of the finite element method with piecewise polynomial basis functions. This algorithm allows us to find a solution (with local singularities) to the boundary value problem for a one-dimensional reaction-diffusion equation and smooth the grid solution via the adaptive elimination and addition of grid nodes. This algorithm is compared to one proposed earlier that adaptively refines the grid and deletes nodes with the help of an estimate for the local effect of trial addition of new basis functions and the removal of old ones. Results are presented from numerical experiments aimed at assessing the performance of the proposed algorithm on a singularly perturbed model problem with a smooth solution.     

An efficient algorithm for the regular W<Subscript>1</Subscript> packing of polygons in the infinite plane

This paper describes a new algorithm, PLANEPACK, which determines an optimal or near optimal solution for the W₁ packing of identical shapes in the infinite plane. Restricted to polygons for computational convenience, it is based on the no-fit polygon/configuration space obstacle approach. The algorithm was tested on a modest set of fourteen polygons (thirteen non-interlocking and one interlocking) and yielded a feasible solution for each. The solutions were optimal for four of the non-interlocking polygons and near optimal for the other nine. As expected though, the solution for the one interlocking polygon was sub-optimal and enhancements to the algorithm would be required for such cases.     

Numerical solution of the differential equation describing the behavior of the zeroth-order boundary function

The asymptotic solution of the integro-differential plasma-sheath equation is considered. This equation is singularly perturbed because of the small coefficient multiplying the highest order (second) derivative. The asymptotic solution is obtained by the boundary function method. Equations are derived for the first two coefficients in the form of both a regular series expansion and an expansion in boundary functions. The equation for the first coefficient of the regular series has only a trivial solution. A numerical algorithm is considered for the solution of the second-order differential equation describing the behavior of the zeroth-order boundary function. The proposed algorithm efficiently solves the boundary-value problem and produces a well-behaved solution of the Cauchy problem. __________ Translated from Prikladnaya Matematika i Informatika, No. 23, pp. 24–35, 2006.     

Matching,Euler tours and the Chinese postman

The solution of the Chinese postman problem using matching theory is given. The convex hull of integer solutions is described as a linear programming polyhedron. This polyhedron is used to show that a good algorithm gives an optimum solution. The algorithm is a specialization of the more generalb-matching blossom algorithm. Algorithms for finding Euler tours and related problems are also discussed.     

A regularizing algorithm for the solution of the inverse problem for an inhomogeneous string

We consider uniqueness of the solution of the inverse problem of determining the coefficient of the one-dimensional wave equation on the real halfline. Necessary conditions of existence of a unique solution of this inverse problem are obtained. A Tikhonov regularizing algorithm is constructed for approximate solution of the inverse problem. The algorithm has an efficient numerical implementation.Translated from Vychislitel'naya Matematika i Matematicheskoe Obespechenie EVM, pp. 55–66, 1985.     

An optimal solution for the stochastic version of the Wagner–Whitin dynamic lot-size model

We present an algorithm for determining the optimal solution over the entire planning horizon for the dynamic lot-size model where demand is stochastic and non-stationary. The optimal solution to the deterministic problem is the well-known Wagner–Whitin algorithm. The present work contributes principally to knowledge building and provides a tool for researchers. One potentially useful contribution to practice is the solution to an important special case, where demand follows normal distributions. Other contributions to practice will likely flow from the development of improved heuristics and the improved basis to evaluate heuristic performance.     

On the Solution of the Inverse Eigenvalue Complementarity Problem

In this paper, we discuss the solution of an Inverse Eigenvalue Complementarity Problem. Two nonlinear formulations are presented for this problem. A necessary and sufficient condition for a stationary point of the first of these formulations to be a solution of the problem is established. On the other hand, to assure global convergence to a solution of this problem when it exists, an enumerative algorithm is designed by exploiting the structure of the second formulation. The use of additional implied constraints for enhancing the efficiency of the algorithm is also discussed. Computational results are provided to highlight the performance of the algorithm.     

A nonsmooth inexact Newton method for the solution of large-scale nonlinear complementarity problems

A new algorithm for the solation of large-scale nonlinear complementarity problems is introduced. The algorithm is based on a nonsmooth equation reformulation of the complementarity problem and on an inexact Levenberg-Marquardt-type algorithm for its solution. Under mild assumptions, and requiring only the approximate solution of a linear system at each iteration, the algorithm is shown to be both globally and superlinearly convergent, even on degenerate problems. Numerical results for problems with up to 10 000 variables are presented. Partially supported by Agenzia Spaziale Italiana, Roma, Italy.     

Expanding Neighborhood GRASP for the Traveling Salesman Problem

In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.     

On Warner's algorithm for the solution of boundary-value problems for ordinary differential equations

The paper discusses the solution of boundary-value problems for ordinary differential equations by Warner's algorithm. This shooting algorithm requires that only the original system of differential equations is solved once in each iteration, while the initial conditions for a new iteration are evaluated from a matrix equation. Numerical analysis performed shows that the algorithm converges even for very bad starting values of the unknown initial conditions and that the number of iterations is small and weakly dependent on the starting point. Based on this algorithm, a general subroutine can be realized for the solution of a large class of boundary-value problems.     

On a Numerical Algorithm for the Modeling of Processes in the Development of a Holographic Relief Image

We construct an algorithm for solving the problem of relief dynamics on the surface of a Newtonian fluid. The risk function is determined by the upper-relaxation method. The velocity field is found by using a two-step difference algorithm that allows one to simplify the calculations and increase the dimension of the system of finite-difference equations. A theorem on stability of the algorithm with respect to the initial data and on convergence of the numerical solution to an exact solution is proved.     

A technique for speeding up the solution of the Lagrangean dual

We propose techniques for the solution of the LP relaxation and the Lagrangean dual in combinatorial optimization and nonlinear programming problems. Our techniques find the optimal solution value and the optimal dual multipliers of the LP relaxation and the Lagrangean dual in polynomial time using as a subroutine either the Ellipsoid algorithm or the recent algorithm of Vaidya. Moreover, in problems of a certain structure our techniques find not only the optimal solution value, but the solution as well. Our techniques lead to significant improvements in the theoretical running time compared with previously known methods (interior point methods, Ellipsoid algorithm, Vaidya's algorithm). We use our method to the solution of the LP relaxation and the Langrangean dual of several classical combinatorial problems, like the traveling salesman problem, the vehicle routing problem, the Steiner tree problem, thek-connected problem, multicommodity flows, network design problems, network flow problems with side constraints, facility location problems,K-polymatroid intersection, multiple item capacitated lot sizing problem, and stochastic programming. In all these problems our techniques significantly improve the theoretical running time and yield the fastest way to solve them.