An iterated greedy metaheuristic for the blocking job shop scheduling problem

In this paper we consider a job shop scheduling problem with blocking (BJSS) constraints. Blocking constraints model the absence of buffers (zero buffer), whereas in the traditional job shop scheduling model buffers have infinite capacity. There are two known variants of this problem, namely the blocking job shop scheduling with swap allowed (BWS) and the one with no swap allowed (BNS). This scheduling problem is receiving an increasing interest in the recent literature, and we propose an Iterated Greedy (IG) algorithm to solve both variants of the problem. IG is a metaheuristic based on the repetition of a destruction phase, which removes part of the solution, and a construction phase, in which a new solution is obtained by applying an underlying greedy algorithm starting from the partial solution. A comparison with recent published results shows that the iterated greedy algorithm outperforms other state-of-the-art algorithms on benchmark instances. Moreover it is conceptually easy to implement and has a broad applicability to other constrained scheduling problems.     

Adaptive and restarting techniques-based algorithms for circular packing problems

In this paper, we study the circular packing problem (CPP) which consists of packing a set of non-identical circles of known radii into the smallest circle with no overlap of any pair of circles. To solve CPP, we propose a three-phase approximate algorithm. During its first phase, the algorithm successively packs the ordered set of circles. It searches for each circle’s “best” position given the positions of the already packed circles where the best position minimizes the radius of the current containing circle. During its second phase, the algorithm tries to reduce the radius of the containing circle by applying (i) an intensified search, based on a reduction search interval, and (ii) a diversified search, based on the application of a number of layout techniques. Finally, during its third phase, the algorithm introduces a restarting procedure that explores the neighborhood of the current solution in search for a better ordering of the circles. The performance of the proposed algorithm is evaluated on several problem instances taken from the literature.     

Transient thermal model for the hot chamber injection system in the pressure die casting process

This paper describes a three-dimensional numerical model that is used to predict the transient thermal behaviour of the metal injection system of a hot chamber pressure die casting machine. The behaviour of the injection system is considered in conjunction with that of the die. The Boundary Element Method (BEM) is used to model the transient thermal behaviour of the injection system elements and the die blocks. A perturbation approach is adopted. By adopting this approach, only those surfaces over which a significant transient variation in temperature occurs need be considered. The model assumes that a corresponding steady-state analysis has first been performed so that time-averaged thermal information is available. A finite element based technique is used to model the phase change of the liquid metal in the die cavity and in the injection system. At injection the nozzle and die are assumed to be instantly filled with liquid metal, however, a procedure is presented that attempts to model the heat transfer associated with the flow through the nozzle, gate, and runner regions during injection. Model predictions are compared against thermocouple readings and thermal images obtained from experimental tests. Good agreement is obtained between predicted and measured temperatures. The transient thermal behaviour of an existing hot chamber injection system is investigated in detail and recommendations for improved performance are made. In an attempt to improve the solidification pattern of the casting and the thermal behaviour of the injection system, a redesign of the experimental die is considered. The numerical predictions indicate that the redesign will have a beneficial effect on the solidification pattern of the casting, and on the performance of the injection system.     

Numerical study of Sivashinsky equation using a splitting scheme based on Crank‐Nicolson method

The mathematical modeling of a planar solid‐liquid interface in the solidification of a dilute binary alloy is formulating by one of nonintegrable, nonlinear evolution equation known as Sivashinsky equation. In the first part of this paper, the mathematical modeling of Sivashinsky equation is briefly discussed. Since, the exact solutions of this equation is yet unknown, obtaining its numerical solution plays an important role to simulate its behavior. Therefore, in the second part, a second‐order splitting finite difference scheme, based on Crank‐Nicolson method, is investigated to approximate the solution of the Sivashinsky equation with homogeneous boundary conditions. We prove the solvability of the present scheme and establish the error estimate of the numerical scheme.     

On diagonally preconditioning the truncated Newton method for super-scale linearly constrained nonlinear programming

We present an algorithm for super-scale linearly constrained nonlinear programming (LCNP) based on Newton's method. In large-scale programming solving the Newton equation at each iteration can be expensive and may not be justified when far from a local solution. For super-scale problems, the truncated Newton method (where an inaccurate solution is computed by using the conjugate-gradient method) is recommended; a diagonal BFGS preconditioning of the gradient is used, so that the number of iterations to solve the equation is reduced. The procedure for updating that preconditioning is described for LCNP when the set of active constraints or the partition of basic, superbasic and nonbasic (structural) variables have been changed.     

Mathematical modeling and study of the process of solidification in metal casting

The process of melting and solidification in metal casting is considered. The process is modeled by a three-dimensional two-phase initial-boundary value problem of the Stefan type. The mathematical formulation of the problem and its finite-difference approximation are given. A numerical algorithm is presented for solving the direct problem. The results are described and analyzed in detail. Primary attention is given to the evolution of the solidification front and to how it is affected by the parameters of the problem. Some of the results are illustrated by plots.     

在纵向自由薄膜凝固期内温度分布的数值分析

考虑到薄膜表面的热通量主要是来自辐射，因而采用一个依赖时间的拟二维拟线性扩散方程的Ｓｔｅｆａｎ问题（混合初边值问题）作为该问题的数学模型。用一种具有Ｃｒａｎｋ－Ｎｉｃｈｏｌｓｏｎ格式的无条件稳定的有限差分析来求解抛物型偏微分方程的定解问题。用追赶法求解离散化的三对角方程组，然后用预估校正法求解拟线性扩散方程，从而避免了示解非线性差分方程组，琥珀亚硝酸酯在纵向自由薄膜凝固期内的温度分布数值计算结果和     

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 a Moving Boundary Problem from Biomechanics

A moving boundary problem arising in biomechanical diffusiontheory which has previously been investigated by Crank &Gupta (1972a, b) is studied using a different method of solution.The method is based on an integral equation for the functiondefining the position of the moving boundary and an integralformula for the concentration. The integral equation is solvedasymptotically for small times and numerically during the entiremotion of the boundary. The concentration is estimated asymptoticallyfor small times and computed by numerical quadrature at laterinstants. The results are compared with those of Crank &Gupta. In most cases the agreement is fair.     

A reliable algorithm of homotopy analysis method for solving nonlinear fractional differential equations

In this paper, based on the homotopy analysis method (HAM), a powerful algorithm is developed for the solution of nonlinear ordinary differential equations of fractional order. The proposed algorithm presents the procedure of constructing the set of base functions and gives the high-order deformation equation in a simple form. Different from all other analytic methods, it provides us with a simple way to adjust and control the convergence region of solution series by introducing an auxiliary parameter ?$?$. The analysis is accompanied by numerical examples. The algorithm described in this paper is expected to be further employed to solve similar nonlinear problems in fractional calculus.     

Adaptive operator splitting finite element method for Allen–Cahn equation

In this paper, a new numerical method is proposed and analyzed for the Allen–Cahn (AC) equation. We divide the AC equation into linear section and nonlinear section based on the idea of operator splitting. For the linear part, it is discretized by using the Crank–Nicolson scheme and solved by finite element method. The nonlinear part is solved accurately. In addition, a posteriori error estimator of AC equation is constructed in adaptive computation based on superconvergent cluster recovery. According to the proposed a posteriori error estimator, we design an adaptive algorithm for the AC equation. Numerical examples are also presented to illustrate the effectiveness of our adaptive procedure.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

A finite element method for steady-state conduction-advection phase change problems

A new finite element: technique is developed to solve steady-state conduction-advection problems with a phase change. The energy balance equation at the solid/liquid interface is employed to calculate the velocity of the solid/liquid interface in the Lagrangian frame. The position of the solid/liquid interface in the Eulerian frame is determined based on the composition of the velocity of the solid/liquid interface in the Lagrangian frame and the steady-state velocity of a rigid body. The interface position and the finite element mesh are continuously updated during an incremental process. No artificial diffusion is needed with this new finite element approach. An analytical solution for solidification of a pure material with a radiative boundary condition is also developed in this paper. Numerical experimentation is conducted and the corresponding results are compared with analytical solutions. The numerical results agree well with analytical solutions.     

偏微分方程组的Lie群与高阶对称群的Taylor多项式逐步精化算法

本文基于生成函数的Ｔａｙｌｏｒ展开式及逐步简化步骤，提出了计算偏微分方程组的Ｌｉｅ群与高阶对称群的Ｔａｙｌｏｒ多项式算法，把标准算法中的求解超定偏微分方程组的问题转化为求解代数方程组的问题，降低了求解的难度，提高了计算效率，并且易用计算机代数系统在计算机上全过程实现，并得到重要的对称群     

A general method for determining the set of all efficient solutions to a linear vectormaximum problem

To solve a linear vectormaximum problem means, in general, to determine the set E of all efficient solutions. A multiparametric method based on earlier works of the author is presented. In the procedure efficient vertices and efficient edges are generated via one subprogram, which works as a simple linear programming problem, and just by inspection of these results higher dimensional efficient faces are determined. The procedure does not depend on special properties of the restriction set and/or of the system of given objective functions. Illustrative examples are presented. Two appendixes provide a survey on a multiparametric algorithm and on a solution procedure for the auxiliary problem, both of which are the background for the method.     

Global solution of bilevel programs with a nonconvex inner program

A bounding algorithm for the global solution of nonlinear bilevel programs involving nonconvex functions in both the inner and outer programs is presented. The algorithm is rigorous and terminates finitely to a point that satisfies ε-optimality in the inner and outer programs. For the lower bounding problem, a relaxed program, containing the constraints of the inner and outer programs augmented by a parametric upper bound to the parametric optimal solution function of the inner program, is solved to global optimality. The optional upper bounding problem is based on probing the solution obtained by the lower bounding procedure. For the case that the inner program satisfies a constraint qualification, an algorithmic heuristic for tighter lower bounds is presented based on the KKT necessary conditions of the inner program. The algorithm is extended to include branching, which is not required for convergence but has potential advantages. Two branching heuristics are described and analyzed. Convergence proofs are provided and numerical results for original test problems and for literature examples are presented.     

A Reactive Local Search-Based Algorithm for the Multiple-Choice Multi-Dimensional Knapsack Problem

In this paper, we approximately solve the multiple-choice multi-dimensional knapsack problem. We propose an algorithm which is based upon reactive local search and where an explicit check for the repetition of configurations is added to the local search. The algorithm starts by an initial solution and improved by using a fast iterative procedure. Later, both deblocking and degrading procedures are introduced in order (i) to escape to local optima and, (ii) to introduce diversification in the search space. Finally, a memory list is applied in order to forbid the repetition of configurations. The performance of the proposed approaches has been evaluated on several problem instances. Encouraging results have been obtained.     

Problem of the Motion of an Elastic Medium Formed at the Solidification Front

The following self-similar problem is considered. At the initial instant of time, a phase transformation front starts moving at constant velocity from a certain plane (which will be called a wall or a piston, depending on whether it is assumed to be fixed or movable); at this front, an elastic medium is formed as a result of solidification from a medium without tangential stresses. On the wall, boundary conditions are defined for the components of velocity, stress, or strain. Behind the solidification front, plane nonlinear elastic waves can propagate in the medium formed, provided that the velocities of these waves are less than the velocity of the front. The medium formed is assumed to be incompressible, weakly nonlinear, and with low anisotropy. Under these assumptions, the solution of the self-similar problem is described qualitatively for arbitrary parameters appearing in the statement of the problem. The study is based on the authors’ previous investigation of solidification fronts whose structure is described by the Kelvin–Voigt model of a viscoelastic medium.     

Error analysis of a fully discrete finite element variational multiscale method for time‐dependent incompressible Navier–Stokes equations

A finite element variational multiscale method based on two local Gauss integrations is applied to solve numerically the time‐dependent incompressible Navier–Stokes equations. A significant feature of the method is that the definition of the stabilization term is derived via two local Guass integrations at element level, making it more efficient than the usual projection‐based variational multiscale methods. It is computationally cheap and gives an accurate approximation to the quantities sought. Based on backward Euler and Crank–Nicolson schemes for temporal discretization, we derive error bounds of the fully discrete solution which are first and second order in time, respectively. Numerical tests are also given to verify the theoretical predictions and demonstrate the effectiveness of the proposed method. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

A branch-and-price algorithm for the capacitated facility location problem

The capacitated facility location problem (CFLP) is a well-known combinatorial optimization problem with applications in distribution and production planning. It consists in selecting plant sites from a finite set of potential sites and in allocating customer demands in such a way as to minimize operating and transportation costs. A number of solution approaches based on Lagrangean relaxation and subgradient optimization has been proposed for this problem. Subgradient optimization does not provide a primal (fractional) optimal solution to the corresponding master problem. However, in order to compute optimal solutions to large or difficult problem instances by means of a branch-and-bound procedure information about such a primal fractional solution can be advantageous. In this paper, a (stabilized) column generation method is, therefore, employed in order to solve a corresponding master problem exactly. The column generation procedure is then employed within a branch-and-price algorithm for computing optimal solutions to the CFLP. Computational results are reported for a set of larger and difficult problem instances.