冲裁件条料最优四块剪切下料方案的生成算法

讨论冲裁件条料剪切下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成条料最优四块排样方式的背包算法,然后采用基于列生成的线性规划算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并确定各种冲裁件的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用例题将该排样方式生成算法和文献中多段排样方式生成算法进行比较,实验计算结果表明,该算法得到的排样方式排样价值较高。最后通过文献中实例的下料方案求解,可以看出该算法解决实际下料问题是有效的。     

二维板材切割下料问题的一种确定性算法

研究二维板材切割下料问题,即使用最少板材切割出一定数量的若干种矩形件。 提出一种结合背包算法和线性规划算法的确定性求解算法。首先构造生成均匀条带四块排样方 式的背包算法;然后采用线性规划算法迭代调用上述背包算法,每次均根据生产成本最小原则 改善目标函数并修正各种矩形件的当前价值,按照当前价值生成新的排样方式;最后选择最优 的一组排样方式组成排样方案。采用基准测题,将该算法与著名的T 型下料算法进行比较,实 验结果表明,该算法比T 型下料算法更能节省板材,计算时间能够满足实际应用需要。     

Cut scheduling in the apparel industry

A problem encountered in the apparel industry is that of producing, with no excess, a known number of different styles from the same cloth. This situation occurs, for instance, in the case of special order or made-to-order garments. In the cutting process, plies of cloth are spread on a cutting table, and several patterns are placed across the top ply. Cutting out the patterns through all plies creates a set of bundles of garment pieces, and several such lays may be required to satisfy all demands. The cut scheduling problem concerns finding a feasible cutting schedule having the minimum number of lays. We present an exact enumerative approach that identifies all optimal solutions to a practically important variant of this problem. The availability of multiple solutions allows greater flexibility and permits decision makers to apply additional criteria in selecting an appropriate cutting schedule. Computational evidence shows that our approach can efficiently solve standard test problems from the literature as well as some very challenging examples provided by a global garment manufacturer.     

A Cut-Based Algorithm for the Nonlinear Dual of the Minimum Cost Network Flow Problem

We consider a convex, or nonlinear, separable minimization problem with constraints that are dual to the minimum cost network flow problem. We show how to reduce this problem to a polynomial number of minimum s,t-cut problems. The solution of the reduced problem utilizes the technique for solving integer programs on monotone inequalities in three variables, and a so-called proximity-scaling technique that reduces a convex problem to its linear objective counterpart. The problem is solved in this case in a logarithmic number of calls, O(log U), to a minimum cut procedure, where U is the range of the variables. For a convex problem on n variables the minimum cut is solved on a graph with O(n²) nodes. Among the consequences of this result is a new cut-based scaling algorithm for the minimum cost network flow problem. When the objective function is an arbitrary nonlinear function we demonstrate that this constrained problem is solved in pseudopolynomial time by applying a minimum cut procedure to a graph on O(nU) nodes.     

Sequential value correction heuristic for the two-dimensional cutting stock problem with three-staged homogenous patterns

A sequential value correction heuristic is presented for the two-dimensional cutting stock problem with three-staged homogenous patterns, considering both input-minimization and simplicity of the cutting process. The heuristic constructs many cutting plans iteratively and selects the best one as the solution. The patterns in each cutting plan are generated sequentially using simple recursive techniques. The values of the item types are corrected after the generation of each pattern to diversify the cutting plans. Computational results indicate that the proposed heuristic is more effective in input minimization than published algorithms and commercial stock cutting software packages that use three-staged general or exact patterns.     

矩形件简单块占角排样方式的动态规划

目的 针对矩形件无约束2维剪切排样问题,提出一种可简化板材切割工艺的简单块占角排样方式,并构造这种排样方式的动态规划生成算法。方法 该排样方式在板材左下角按照简单块方式排样若干行若干列同种矩形件,将板材剩余部分划分为两个子板;将子板按照上述方法继续递归排样和划分,直至子板排满矩形件为止。采用动态规划确定所有可能尺寸的板材左下角排样的最优矩形件、矩形件的最优行列数和板材剩余部分的最优子板划分。运用规范尺寸排除不必要的计算。结果 将本文算法与目前常见的算法进行比较,实验结果表明本文算法计算时间合理,排样价值较高。在第1组41道基准例题中,本文算法所有例题均求出了精确解,同质块T型算法、同质块两段算法和复合条带两段算法分别有7道、5道和4道例题未求出精确解。在第2组20道基准例题中,本文算法只有1道例题未求出精确解,普通三阶段算法、同质块T型算法、同质块两段算法和匀质条带三块算法分别有18道、15道、15道和20道例题未求出精确解。在第3组50道随机例题中,本文算法、普通两段算法和同质块两段算法板材利用率分别为99.913 7%、99.862 3%和99.796 1%。在第4组31道基准例题中,本文算法所有例题均求出了精确解,普通占角排样算法有2道例题未求出精确解。结论 本文算法计算时间远小于精确算法,优化效果接近精确算法;本文算法计算时间与多种启发式算法接近,但优化效果好于多种启发式算法。     

A hybrid heuristic to reduce the number of different patterns in cutting stock problems

We propose a hybrid procedure to obtain a reduced number of different patterns in cutting stock problems. Initially, we generate patterns with limited waste that fulfill the demands of at least two items when the patterns are repeatedly cut as much as possible but without overproducing any of the items. The problem is reduced and the residual problem is solved. Then, pattern reduction techniques (local search) are applied starting with the generated solution. The scheme is straightforward and can be used in cutting stock problems of any dimension. Variations of the procedure are also indicated. Computational tests performed indicated that the proposed scheme provides alternative solutions to the pattern reduction problem which are not dominated by other solutions obtained using procedures previously suggested in the literature.     

基于价值修正的圆片下料顺序启发式算法

讨论圆片剪冲下料方案的设计问题。下料方案由一组排样方式组成。首先构造一种生成圆片条带最优四块排样方式的背包算法,然后采用基于价值修正的顺序启发式算法迭代调用上述背包算法,每次都根据生产成本最小的原则改善目标函数并修正各种圆片的当前价值,按照当前价值生成一个新的排样方式,最后选择最优的一组排样方式组成下料方案。采用文献中的基准测题将文中下料算法与文献中T 型下料算法和启发式下料算法分别进行比较。实验计算结果表明,该算法的材料利用率比T 型下料算法和启发式下料算法分别高0.83%和3.63%,且计算时间在实际应用中合理。     

Hybrid Intelligent Packing System (HIPS) through integration of Artificial Neural Networks,Artificial Intelligence,and mathematical programming

A successful solution to the packing problem is a major step toward material savings on the scrap that could be avoided in the cutting process and therefore money savings. Although the problem is of great interest, no satisfactory algorithm has been found that can be applied to all the possible situations. This paper models a Hybrid Intelligent Packing System (HIPS) by integrating Artificial Neural Networks (ANNs), Artificial Intelligence (AI), and Operations Research (OR) approaches for solving the packing problem. The HIPS consists of two main modules, an intelligent generator module and a tester module. The intelligent generator module has two components: (i) a rough assignment module and (ii) a packing module. The rough assignment module utilizes the expert system and rules concerning cutting restrictions and allocation goals in order to generate many possible patterns. The packing module is an ANN that packs the generated patterns and performs post-solution adjustments. The tester module, which consists of a mathematical programming model, selects the sets of patterns that will result in a minimum amount of scrap.     

Complex weight control of array pattern nulling

An efficient method based on the sequential quadratic programming (SQP) algorithm for the linear antenna arrays pattern synthesis with prescribed nulls in the interference direction and minimum side lobe levels by the complex weights of each array element is presented. In general, the pattern synthesis technique that generates a desired pattern is a greatly nonlinear optimization problem. SQP method is a versatile method to solve the general nonlinear constrained optimization problems and is much simpler to implement. It transforms the nonlinear minimization problem to a sequence of quadratic subproblem that is easier to solve, based on a quadratic approximation of the Lagrangian function. Several numerical results of Chebyshev pattern with the imposed single, multiple, and broad nulls sectors are provided and compared with published results to illustrate the performance of the proposed method. © 2007 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2007.     

生成矩形毛坯最优两段排样方式的确定型算法

排样价值、切割工艺和计算时间是排样问题主要考虑的3个因素.文中提出一个新的基于排样模式的确定型排样算法——同质块两段排样算法,此算法适合剪冲下料工艺,在实现工艺简化的同时提高了排样价值时间比.首先通过动态规划算法生成最优同质块,然后求解一维背包问题生成块在级中的最优排样方式和级在段中的最优排样方式,最后选择两个段生成最优的两段排样方式.通过3组经典测题对该文算法进行了测试,将算法与4种著名算法进行了比较.实验结果表明,该文算法的优化结果好于以上4种著名算法,有效地提高了板材利用率,并且计算时间合理.     

Mixed integer programming approaches to exact minimization of total treatment time in cancer radiotherapy using multileaf collimators

The effectiveness of radiation therapy for cancer depends on the patient remaining still during treatment. It is thus important to minimize the total treatment time (TTT). When such treatment is delivered using multileaf collimators in “step-and-shoot” mode, it consists of a sequence of collimator configurations, or patterns; for each, the patient is exposed to radiation for a specified time, or beam-on time. The TTT can thus be divided into the total beam-on time and the time spent reconfiguring the collimators. The latter can reasonably be approximated by the number of patterns, multiplied by a constant overhead time per pattern. Previous approaches to this problem have all been heuristic; in particular none of them actually use the pattern overhead time to ascertain the best trade-off between beam-on time and number of patterns. In this paper, we develop exact solution approaches, based on mixed integer programming (MIP) formulations, which minimize the TTT. We consider direct solution of MIP formulations, and then exploit the bicriteria structure of the objective to derive an algorithm that “steps up” through the number of patterns used, leading to substantial computational savings.     

A new approach to the learning effect: Beyond the learning curve restrictions

In this paper, we bring into the scheduling field a new model of the learning effect, where in two ways the existing approach is generalized. First we relax one of the rigorous constraints, and thus in our model each job can provide different experience to the processor. Second we formulate the job processing time as a non-increasing k-stepwise function, that, in general, is not restricted to a certain learning curve, thereby it can accurately fit every possible shape of a learning function. Furthermore, we prove that the problem of makespan minimization with the considered model is polynomially solvable if every job provides the same experience to the processor, and it becomes NP-hard if the experiences are diversified. The most essential result is a pseudopolynomial time algorithm that solves optimally the makespan minimization problem with any function of an experience-based learning model reduced into the form of the k-stepwise function.     

Minimum Distance between Pattern Transformation Manifolds: Algorithm and Applications

Transformation invariance is an important property in pattern recognition, where different observations of the same object typically receive the same label. This paper focuses on a transformation-invariant distance measure that represents the minimum distance between the transformation manifolds spanned by patterns of interest. Since these manifolds are typically nonlinear, the computation of the manifold distance (MD) becomes a nonconvex optimization problem. We propose representing a pattern of interest as a linear combination of a few geometric functions extracted from a structured and redundant basis. Transforming the pattern results in the transformation of its constituent parts. We show that, when the transformation is restricted to a synthesis of translations, rotations, and isotropic scalings, such a pattern representation results in a closed-form expression of the manifold equation with respect to the transformation parameters. The MD computation can then be formulated as a minimization problem whose objective function is expressed as the difference of convex functions (DC). This interesting property permits optimally solving the optimization problem with DC programming solvers that are globally convergent. We present experimental evidence which shows that our method is able to find the globally optimal solution, outperforming existing methods that yield suboptimal solutions.     

Sequential optimization approach for nesting and cutting sequence in laser cutting

The economy of the laser cutting process depends on two productivity issues: (i) nesting, a classic problem of finding the most efficient layout for cutting parts with minimum material waste; (ii) cutting sequence, which targets the optimal sequence of edges of the parts to be cut for minimum cycle time. This paper presents a two stage sequential optimization procedure for nesting and cutting sequence for the objectives of maximizing material utilization and minimization of ideal (non-cut) travel distance of laser cut tool. However, the focus of this paper is the development of solution technique for optimal cutting sequence to any given layout. Simulated annealing algorithm (SAA) is considered to evolve the optimal cutting sequence. The proposed SAA is illustrated with the optimal material utilization layout obtained using sheet cutting suite software, a professional rectangular nesting software package. The robust test carried out with five typical problems shows that the SAA proposed for cutting sequence is capable of providing near optimal solutions. The performance comparison with two literature problems reveals that the proposed SAA is able to give improved result than GA and ACO algorithms.     

多尺寸圆木二维下料问题研究

圆木二维下料问题是木材企业中常见问题,针对一些头部与尾部直径相差不大的木材,可以将这些木材看作是圆柱体,下料时将其切成和圆木长度相等的多个长方体毛坯,该问题可转化为二维下料问题。采用顺序价值校正框架和动态规划算法求解该下料问题。顺序生成排样图,每生成一个排样图便调整毛坯的价值,重复该过程直到满足毛坯需求为止。通过迭代生成多个下料方案以便优选。圆木下料的研究对减少木材企业的成本很有意义。     

Fuzzy random programming models for location-allocation problem with applications

Three types of fuzzy random programming models based on the mean chance for the capacitated location-allocation problem with fuzzy random demands are proposed according to different criteria, including the expected cost minimization model, the α-cost minimization model, and the chance maximization model. In order to solve the proposed models, some hybrid intelligent algorithms are designed by integrating the network simplex algorithm, fuzzy random simulation, and genetic algorithm. Finally, some numerical examples about a container freight station problem are given to illustrate the effectiveness of the devised algorithms.     

On the equivalence of minimum compliance and stress-constrained minimum weight design of trusses under multiple loading conditions

This article is devoted to topology optimization of trusses under multiple loading conditions. Compliance minimization with material volume constraint and stress-constrained minimum weight problem are considered. In the case of a single loading condition, it has been shown that the two problems have the same optimal topology. The possibility of extending this result for problems involving multiple loading conditions is examined in the present work. First, the compliance minimization problem is formulated as a multicriterion optimization problem, where the conflicting criteria are the compliances of the different loading conditions. Then, the optimal topologies of the stress-constrained minimum weight problem and the multicriterion compliance minimization problem for a simple test example are compared. The results verify that when multiple loading conditions are involved, the stress-constrained minimum weight topology cannot be obtained in general by solving the compliance minimization problem.     

A simple algorithm for generating optimal equal circle cutting patterns with minimum sections

The cutting and stamping process is often used to divide stock plates into circular items. A guillotine machine cuts the plates into strips at the cutting phase. A stamping press stamps out the items from strips at the stamping phase. Normal patterns have been proposed for the case of equal circles. They consist of sections that contain strips of the same direction. The cutting process can be simplified if the number of sections is reduced. This short communication presents a simple algorithm for selecting from the optimal patterns the one that has the minimum number of sections. It assumes that the pattern value equals the value of the produced items minus the cost of the sections. The expected solution can be obtained by using an adequate section cost. The algorithm is faster and much simpler to design than a recently published algorithm.     

Independence of Containing Patterns Property and Its Application in Tree Pattern Query Rewriting Using Views

We show that several classes of tree patterns observe the independence of containing patterns property, that is, if a pattern is contained in the union of several patterns, then it is contained in one of them. We apply this property to two related problems on tree pattern rewriting using views. First, given view V and query Q, is it possible for Q to have an equivalent rewriting using V which is the union of two or more tree patterns, but not an equivalent rewriting which is a single pattern? This problem is of both theoretical and practical importance because, if the answer is no, then, to find an equivalent rewriting of a tree pattern using a view, we should use more efficient methods, such as the polynomial time algorithm of Xu and Özsoyoglu (2005), rather than try to find the union of all contained rewritings (which takes exponential time in the worst case) and test its equivalence to Q. Second, given a set S of views, we want to know under what conditions a subset S′ of S is redundant in the sense that for any query Q, the contained rewritings of Q using the views in S′ are contained in those using the views in S???S′. Solving this problem can help us to, for example, choose the minimum number of views to be cached, or better design the virtual schema in a mediated data integration system, or avoid repeated calculation in query optimization. For the first problem, we identify several classes of tree patterns for which the equivalent rewriting can be expressed as a single tree pattern. For the second problem, we present necessary and sufficient conditions for S′ to be redundant with respect to some classes of tree patterns. For both problems we consider extension to cases where there are rewritings using the intersection of multiple views and/or where a schema graph is present.