The constrained two-dimensional guillotine cutting problem with defects: an ILP formulation,a Benders decomposition and a CP-based algorithm

This paper addresses a variant of two-dimensional cutting problems in which rectangular small pieces are obtained by cutting a rectangular object through guillotine cuts. The characteristics of this variant are (i) the object contains some defects, and the items cut must be defective-free; (ii) there is an upper bound on the number of times an item type may appear in the cutting pattern; (iii) the number of guillotine stages is not restricted. This problem commonly arises in industrial settings that deal with defective materials, e.g. either by intrinsic characteristics of the object as in the cutting of wooden boards with knotholes in the wood industry, or by the manufacturing process as in the production of flat glass in the glass industry. We propose a compact integer linear programming (ILP) model for this problem based on the discretisation of the defective object. As solution methods for the problem, we develop a Benders decomposition algorithm and a constraint-programming (CP) based algorithm. We evaluate these approaches through computational experiments, using benchmark instances from the literature. The results show that the methods are effective on different types of instances and can find optimal solutions even for instances with dimensions close to real-size.     

Dynamic allocation of surplus by-product gas in a steel plant by dynamic programming with a reduced state space algorithm

Surplus by-product gas (SBPG) in a steel plant is the difference between gas production and consumption. Dynamic programming (DP) has been observed to be a useful method for SBPG dynamic allocation. However, in the SBPG allocation problem, standard dynamic programming (SDP) usually suffers from dimensionality. In this study, a novel dynamic programming method with a reduced state space algorithm (RSS-DP) is proposed. By decomposing the amount of SBPG into the reference and subsequent allocation, RSS-DP reduces the state space of the SDP model significantly such that the computation time is significantly reduced. An example of a five-boiler allocation of SBPG and a real-world online allocation of SBPG in these five boilers of a steel plant are implemented to exhibit the effectiveness of the proposed algorithm. In both cases, the solutions obtained using the proposed method are better than those obtained by traditional methods, in both computation time and energy benefit.     

Maximum a posteriori probability direction finding and the dynamic programming algorithm

Abstract

In this paper, a dynamic programming (DP) algorithm is proposed to compute the maximum a posteriori probability (MAP) estimate of the random location of multiple sources by passive sensor array. Based on the principle of optimality, the multivariate MAP decision problem can be transformed into a multistage one‐dimensional maximization problem. By a recursive computation and backward optimum searching technique, the MAP solution can be obtained. The computational complexity is much less than that of the direct MAP searching method, especially when the number of sensors and/or the number of sources is large. In addition, the DP computation technique is equally applicable both in the case of correlated sources and the case of uncorrelated sources.     

Multi-period response management to contaminated water distribution networks: dynamic programming versus genetic algorithms

Previous studies on consequence management assume that the selected response action including valve closure and/or hydrant opening remains unchanged during the entire management period. This study presents a new embedded simulation-optimization methodology for deriving time-varying operational response actions in which the network topology may change from one stage to another. Dynamic programming (DP) and genetic algorithm (GA) are used in order to minimize selected objective functions. Two networks of small and large sizes are used in order to illustrate the performance of the proposed modelling schemes if a time-dependent consequence management strategy is to be implemented. The results show that for a small number of decision variables even in large-scale networks, DP is superior in terms of accuracy and computer runtime. However, as the number of potential actions grows, DP loses its merit over the GA approach. This study clearly proves the priority of the proposed dynamic operation strategy over the commonly used static strategy.     

A general quantity discount and supplier selection mixed integer programming model

Recently, new models and heuristics for exploiting quantity discounts have been proposed that are applicable in classical purchasing as well as in an e-business environment and can be implemented as part of an advanced planning system. These models can now handle both the single- and multi-item case with fixed cost to be shared among several products ordered at the same point in time from a single supplier. Furthermore, the supplier selection problem is addressed, i.e., how to best exploit quantity discounts over time offered by several suppliers. Last but not least, additional constraints on the buyer’s or on the supplier’s side may be included. While so far only purpose-built heuristics have been proposed for this generalized problem, we present a linear mixed integer programming (MIP) model, which not only represents the all-units discount but also the incremental discount case. Furthermore, the objective function chosen resolves (former) conflicts among proponents of a purely cost oriented and a cash flow oriented modeling approach. Computational tests show that our model yields near optimal solutions within a given CPU time limit by making use of a standard MIP solver.     

动态规划在运动图像分析中的应用

对运动图像序列中的目标进行运动跟踪和估计,可以分别采用变形模型和弹性配准的方法,两问题的求解均可归纳为成本函数的最优化问题。提出了应用动态规划算法求解离散成本函数最优化的方法,把问题分解成多个子问题分别求解,并存储子问题的解以避免重复计算。该方法不仅可保证解的全局最优性,而且计算量小,有利于实现实时处理。在对临床X射线冠状动脉造影图像序列的实验中得到了满意的结果,匹配大约2000个点的血管骨架只需要一秒钟左右的时间。对运动场已知的模拟图像的实验证明运动估计误差小于1个像素（1像素=0．3mm）。     

A mixed-integer programming formulation for the double row layout of machines in manufacturing systems

The Double Row Layout Problem (DRLP) is the problem of allocating a given set of machines on both sides of a straight line corridor so as to minimise the total cost of transporting materials among machines. The DRLP occurs in several manufacturing plants, particularly in semiconductor manufacturing. While it has a large practical importance, the problem is very difficult to solve to optimality. In this paper, we construct a mixed-integer programming (MIP) formulation of the problem, which favourably compares to a previously published MIP formulation. The new model is found to present similar performance to another published MIP formulation, and it has the advantage of being more intuitive for handling qualitative inputs that may be required in a layout refinement phase.     

Large neighbourhood search based on mixed integer programming and ant colony optimisation for car sequencing

We investigate the problem of scheduling a sequence of cars to be placed on an assembly line. Stations, along the assembly line install options (e.g. air conditioning), but have limited capacities, and hence cars requiring the same options need to be distributed far enough apart. The desired separation is not always feasible, leading to an optimisation problem that minimises the violation of the ideal separation requirements. In order to solve the problem, we use a large neighbourhood search (LNS) based on mixed integer programming (MIP). The search is implemented as a sliding window, by selecting overlapping subsequences of manageable sizes, which can be solved efficiently. Our experiments show that, with LNS, substantial improvements in solution quality can be found.     

Optimal scrap combination for steel production

In steel production, scrap metal is used for cooling the enormous quantity of heat produced by blowing oxygen on hot metal. Scrap differs in regard to the content of iron and of some tramp elements. The price of the scrap depends on these attributes. Each melting bath unit of steel has its own material constraints for the amount of iron and tramp elements in order to guarantee the desired quality. In addition, the transportation of scrap is restricted because it needs time and space: the scrap is kept in some railroad cars in the scrap hall; empty cars must leave the hall, filled cars must be taken from several railroad tracks in the scrap yard and assembled to a train before transportation to the hall. There are upper limits for the number of cars in the hall and in the train, also for the number of railroad tracks used for assembly.Our objective is to find a minimum cost scrap combination for each melting bath unit of steel that obeys the material and transportation constraints. We model the problem using a MIP (mixed integer linear programming) approach. Real-life situations are solved with the commercial MIP-solver CPLEX. We present computational results which show significant improvement compared to the strategy applied today.     

Optimal selection of machining rate variables by geometric programming

The selection of economically optimal machining rate variables, i.e. cutting speed and feed rate, is of major importance in the field of metal cutting.

In this paper, apart from the conventional methods used for optimization in machining economics, geometric programming, a relatively new non-linear programming technique, is employed to optimize the constrained unit cost problem in turning. The cutting power available from the machine tool and the permissible CLA value of surface roughness are used as the forced constraints in the primal programme.

Initially, the primal and dual programmes are formulated. Furthermore, a numerical example is presented to illustrate the application of geometric programming which has been proved successful.

It is pointed out that geometric programming may be also used for optimization of unit cost in machining processes other than turning under the assumption that the imposed restrictions, discussed in this paper, are valid.     

Robust envelope-constrained filter with orthonormal bases and semi-definite and semi-infinite programming

In this paper, the equivalence relation between a semi-infinite quadratically constrained convex quadratic programming problem and a combined semi-definite and semi-infinite programming problem is considered. Then, an efficient and reliable discretization algorithm for solving a general class of combined semi-definite and semi-infinite programming problems is developed. Both the continuous-time envelope-constrained optimal equalization filter and the corresponding robust envelope-constrained filter for a communication channel are solved by using the proposed algorithm. This research was partially supported by the Research Committee of The Hong Kong Polytechnic University and the National Natural Science Foundation of China (Grant numbers: 60574073 and 10471142).     

凹二次规划问题的一个融合割平面方法的分支定界混合算法

把割平面方法融于分支定界方法之中,本文提出了求解凹二次规划问题的一个融合割平面方法的分支定界混合算法,证明了该算法是收敛的.数值例子也表明这个算法是有效的,并且好于单纯形分支定界算法。     

A new deterministic global optimization method for general twice-differentiable constrained nonlinear programming problems

A deterministic global optimization method that is applicable to general nonlinear programming problems composed of twice-differentiable objective and constraint functions is proposed. The method hybridizes the branch-and-bound algorithm and a convex cut function (CCF). For a given subregion, the difference of a convex underestimator that does not need an iterative local optimizer to determine the lower bound of the objective function is generated. If the obtained lower bound is located in an infeasible region, then the CCF is generated for constraints to cut this region. The cutting region generated by the CCF forms a hyperellipsoid and serves as the basis of a discarding rule for the selected subregion. However, the convergence rate decreases as the number of cutting regions increases. To accelerate the convergence rate, an inclusion relation between two hyperellipsoids should be applied in order to reduce the number of cutting regions. It is shown that the two-hyperellipsoid inclusion relation is determined by maximizing a quadratic function over a sphere, which is a special case of a trust region subproblem. The proposed method is applied to twelve nonlinear programming test problems and five engineering design problems. Numerical results show that the proposed method converges in a finite calculation time and produces accurate solutions.     

Multiple sequence alignment using modified dynamic programming and particle swarm optimization

Abstract

Dynamic Programming (DP) is widely used in Multiple Sequence Alignment (MSA) problems. However, when the number of the considered sequences is more than two, multiple dimensional DP may suffer from large storage and computational complexities. Often, progressive pairwise DP is employed for MSA. However, such an approach also suffers from local optimum problems. In this paper, we present a hybrid algorithm for MSA. The algorithm combines the pairwise DP and the particle swarm optimization (PSO) techniques to overcome the above drawbacks. In the algorithm, pairwise DP is used to align sequences progressively and PSO is employed to avoid the result of alignment being trapped into local optima. Several existing MSA tools are employed for comparison. The experimental results show excellent performance of the proposed algorithm.     

Multi-product continuous plant scheduling: combination of decomposition,genetic algorithm,and constructive heuristic

We propose a polylithic method for medium-term scheduling of a large-scale industrial plant operating in a continuous mode. The method combines a decomposition approach, a genetic algorithm (GA) and a constructive MILP-based heuristic. In the decomposition, decisions are made at two levels, using the rolling horizon approach. At the upper level, a reduced set of products and the time period is chosen to be considered in the lower level. At the lower level, a short-term scheduling MILP-model with event-based representation is used. A heuristic solution to the lower level problem is found using a constructive Moving Window heuristic guided by a genetic algorithm. The GA is applied for finding efficient utilisation of critical units in the lower level problem. For solving the one unit scheduling problem, a parallel dynamic programming algorithm is proposed. Implementation of the dynamic programming algorithm for a graphics processing unit (GPU) is incorporated in the GA for improving its performance. The experimental study of the proposed method on a real case of a large-scale plant shows a significant improvement of the solution quality and the solving time comparing to the pure decomposition algorithm proposed in the earlier study, and confirmed suitability of the proposed approach for the real-life production scheduling. In particular, the reduction of the number of changeovers and their duration in the obtained solution as well as the CPU time of solving the problem was about 60% using the new approach.     

A tree-search method for solving a cutting stock assignment problem

Many production environments such as carpet or flat glass manufacturing have linked operations that perform completely different activities. In this paper, we consider a two-stage manufacturing process involving a cutting operation, followed by an assignment operation. Raw material is cut to meet product demand with minimum trim loss, and assignments are made to minimize resource requirements. This cutting stock assignment problem is formulated as a large-scale, mixed-integer nonlinear programming problem. We propose a solution methodology based on decomposition and tree search heuristic strategies. We report on extensive computational experiments on a wide range of problems, and apply statistical techniques to determine significant factors. For all small-size problems tested, our method found the exact optimal solution. For practical-size problems, our method was about two orders of magnitude faster and produced solutions that were one-third better than tabu search.     

冠状动脉造影图像序列中估计二维运动及变形的弹性配准算法

提出一种由单面血管造影图像序列分析心脏冠状动脉运动和变形的方法，即利用弹性配准算法，将动脉运动的估计简化为对连续两帧图像的骨架像素的匹配．采用动态规划的方法进行配准，同时引入自回归建模，二者结合起来互相作用：动态规划为自回归模型参数的估计提供样本值；自回归模型为动态规划提供适当的成本函数。采用临床得到的单面冠状动脉造影图像序列对该算法进行了验证。实验结果表明应用该方法计算血管骨架图像中各点的光滑移动向量场，能够得到精确的结果。     

Optimizing production smoothing decisions via batch selection for mixed-model just-in-time manufacturing systems with arbitrary setup and processing times

This paper is concerned with the production smoothing problem that arises in the context of just-in-time manufacturing systems. The production smoothing problem can be solved by employing a two-phase solution methodology, where optimal batch sizes for the products and a sequence for these batches are specified in the first and second phases, respectively. In this paper, we focus on the problem of selecting optimal batch sizes for the products. We propose a dynamic programming (DP) algorithm for the exact solution of the problem. Our computational experiments demonstrate that the DP approach requires significant computational effort, rendering its use in a real environment impractical. We develop three meta-heuristics for the near-optimal solution of the problem, namely strategic oscillation, scatter search and path relinking. The efficiency and efficacy of the methods are tested via a computational study. The computational results show that the meta-heuristic methods considered in this paper provide near-optimal solutions for the problem within several minutes. In particular, the path relinking method can be used for the planning of mixed-model manufacturing systems in real time with its negligible computational requirement and high solution quality.     

Mixed model disassembly line balancing problem with fuzzy goals

The collection of used products is the driving force of remanufacturing systems and enterprises can gain significant economic, technical and social benefits from recycling. All products are disassembled up to some level in remanufacturing systems. The best way to disassemble returned products is valid by a well-balanced disassembly line. In this paper, a mixed integer programming (MIP) model is proposed for a mixed model disassembly line balancing (MMDLB) problem with multiple conflicting objectives: (1) minimising the cycle time, (2) minimising the number of disassembly workstations and (3) providing balanced workload per workstation. In most real world MMDLB problems, the targeted goals of decision makers are frequently imprecise or fuzzy because some information may be incomplete and/or unavailable over the planning horizon. This study is the first in the literature to offer the binary fuzzy goal programming (BFGP) and the fuzzy multi-objective programming (FMOP) approaches for the MMDLB problem in order to take into account the vague aspirations of decision makers. An illustrative example based on two industrial products is presented to demonstrate the validity of the proposed models and to compare the performances of the BFGP and the FMOP approaches.