合理下料问题的多目标规划模型

本文从现有的四种合理下料问题的单目标线性规划模型中,发现在有关合理下料的问题中并非仅含有一个目标,而是具有双重目标,一个是余料最少;一个是下料最少。这两个目标在一般情况下并非一致的。因此,在此基础上提出了关于合理下料问题的多目标规划模型,并给出了有效解的判定方法及实际中寻求满意解的途径。     

有交货时间限制的大规模实用下料问题

研究的是有交货时间限制的单一原材料下料问题(规模较大).对于一维下料问题,本文得到一个有各自交货时间的模型.针对该模型提出一种新的算法:DP贪婪算法.计算结果是总用料800根即可完成需求任务,材料利用率为99.6%.对于二维下料问题,在一维的基础上建立了二维的求解模型,运用我们自己设计的降维思想结合一维的DP贪婪算法,给出解决该模型的算法.计算结果是总用料451块即可完成需求任务,材料利用率位99.2%.算法设计时考虑了普遍的情况,所以算法在解决大多数实际下料问题,特别是大规模下料问题时是切实有效的.     

下料问题数学模型研究

本文讨论了关于合理下料问题线性规则模型的建立，给出了该问题正确的线性规划模型，用反例说明了某些模型的错误并进行了分析。     

不同目标的连续型下料问题的关系

不同目标的连续型下料问题的关系赵东方（华中师范大学）一般的一维下料问题是一个整数线性规划，其表述如下［‘］，［２］：某类钢材其长度为ｌ，要为。种零件的毛坯下料，共有。种下料方式，第ｊ种下料方式可得第ｆ种零件出ｊ个，第Ｉ种零件的长度为Ａ，共需要么设。；...     

实用下料的数学模型

考虑到整数规划模型的下料方式数量难以穷尽的问题,本文以原材料最少为目标,采用启发式多级序列线性优化的方法建立一维下料模型.对于二维下料问题,采用降维启发式的方法即通过形成“板条”把二维下料问题化为一维下料问题.     

二维实用下料问题的数学模型及较优解

二维下料问题是2004年首届全国部分高校研究生数学建模竞赛B题.建立了二维下料问题的数学模型,找到了用料451块,下料方式数为37的较优解,并证明了此问题总用料的下界是449块.     

关于三种规格的配套下料问题

<正> 文献[1]中指出,“对于n=2时有配套要求的条材下料问题,我们可以在平面坐标图上很快地加以解决。然而,在n≥3时,要用坐标作图法来解决这类问题,就不那么好办了。”“本文对n=3的情形——这是实践中最常遇到的——给出一个坐标作图解法定理。该解法简单易行,有在实践中推广的价值。     

线性规划模型建立的一个原则

本以运输问题,下料问题和人员班次安排为例,论述了建立线性规划数学模型的一个原则,即尽量使用不等式约束来建立模型的原则。     

线性规划模型建立的一个原则

本文以运输问题、下料问题和人员班次安排为例 ,论述了建立线性规划数学模型的一个原则 ,即尽量使用不等式约束的来建立模型的原则 .     

一类板材下料计量问题

一张矩形铝板,需要冲压（剪裁）成一定规格的板料．问如何下料才能使得铝板的利用率最高？这是一类矩形薄板下料的计量问题．问题的数学提法是：一个平面图形（矩形）面积为Ｓ,需要无重叠地、完整地放入面积为Ａ的某种规格的纸片．设放入纸片的个数为ｎ,求ｎ的最大值．显然ｎ≤［ＳＡ］．其中［ｘ］表示不超过ｘ的最大整数．至于ｎ的最大值能否达到［ＳＡ］,这与纸片形状有关．因此,要设计一种实现ｎ＝［ＳＡ］的方案或者给出ｎ≠［ＳＡ］的证明,然后再验证ｎ能否达到［ＳＡ］－１．这样依次验证下去,总可以找到ｎ的最大值．以上给出…     

Characterization and modelling of guillotine constraints

This paper focuses on guillotine cuts which often arise in real-life cutting stock problems. In order to construct a solution verifying guillotine constraints, the first step is to know how to determine whether a given cutting pattern is a guillotine pattern. For this purpose, we first characterize guillotine patterns by proving a necessary and sufficient condition. Then, we propose a polynomial algorithm to check this condition. Based on this mathematical characterization of guillotine patterns, we then show that guillotine constraints can be formulated into linear inequalities. The performance of the algorithm to check guillotine cutting patterns is evaluated by means of computational results.     

On polynomial solvability of two multiprocessor scheduling problems

We discuss a new approach for solving multiprocessor scheduling problems by using and improving results for guillotine pallet loading problem. We introduce a new class of schedules by analogy with the guillotine restriction for cutting stock problem and show that many well-known algorithms from classical scheduling theory construct schedules only from this class. We also consider two multiprocessor scheduling problems and prove that they can be solved in polynomial time.     

An algorithm for the two-dimensional assortment problem

In this paper we consider the two-dimensional assortment problem. This is the problem of choosing from a set of stock rectangles a subset which can be used for cutting into a number of smaller rectangular pieces. Constraints are imposed upon the number of such pieces which result from the cutting.A heuristic algorithm for the guillotine cutting version of the problem is developed based on a greedy procedure for generating two-dimensional cutting patterns, a linear program for choosing the cutting patterns to use and an interchange procedure to decide the best subset of stock rectangles to cut.Computational results are presented for a number of test problems which indicate that the algorithm developed produces good quality results both for assortment problems and for two-dimensional cutting problems.     

An application of simulated annealing to the cutting stock problem

We solve a two-dimensional cutting stock problem by applying a general global optimization algorithm, the simulated annealing. Our algorithms applied to the cutting problems involving both the guillotine and non-guillotine constraints, underlying that the latter is to be preferred for a big number of items. Several tests prove the validity of the algorithms.     

Reducing the number of cuts in generating three-staged cutting patterns

Three-staged guillotine patterns are widely used in the manufacturing industry to cut stock plates into rectangular items. The cutting cost often increases with the number of cuts required. This paper focuses on the rectangular two-dimensional cutting stock problem, where three-staged guillotine patterns are used, and the objective is to minimize the sum of plate and cutting costs. The column generation framework is used to solve the problem. It uses a pattern-generation procedure to obtain the patterns. The cutting cost is considered in both the pattern-generation procedure and the objective of the linear programming formulation. The computational results indicate that the approach can reduce the number of cuts, without increasing the plate cost.     

The solution of two-stage guillotine cutting stock problems having extremely varying order demands

In this paper the solution of two-stage guillotine cutting stock problems is considered. Especially such problems are under investigation where the sizes of the order demands differ in a large range. We propose a new approach dealing with such situations and compare it with the classical Gilmore-Gomory approach. We report results of extensive numerical experiments which show the advantages of the new approach.     

A branch-and-price algorithm for the two-stage guillotine cutting stock problem

We investigate the two-stage guillotine two-dimensional cutting stock problem. This problem commonly arises in the industry when small rectangular items need to be cut out of large stock sheets. We propose an integer programming formulation that extends the well-known Gilmore and Gomory model by explicitly considering solutions that are obtained by both slitting some stock sheets down their widths and others down their heights. To solve this model, we propose an exact branch-and-price algorithm. To the best of our knowledge, this is the first contribution with regard to obtaining integer optimal solutions to Gilmore and Gomory model. Extensive results, on a set of real-world problems, indicate that the proposed algorithm delivers optimal solutions for instances with up to 809 items and that the hybrid cutting strategy often yields improved solutions. Furthermore, our computational study reveals that the proposed modelling and algorithmic strategy outperforms a recently proposed arc-flow model-based solution strategy.     

Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem

In this paper, we propose approximate and exact algorithms for the double constrained two-dimensional guillotine cutting stock problem (DCTDC). The approximate algorithm is a two-stage procedure. The first stage attempts to produce a starting feasible solution to DCTDC by solving a single constrained two dimensional cutting problem, CDTC. If the solution to CTDC is not feasible to DCTDC, the second stage is used to eliminate non-feasibility. The exact algorithm is a branch-and-bound that uses efficient lower and upper bounding schemes. It starts with a lower bound reached by the approximate two-stage algorithm. At each internal node of the branching tree, a tailored upper bound is obtained by solving (relaxed) knapsack problems. To speed up the branch and bound, we implement, in addition to ordered data structures of lists, symmetry, duplicate, and non-feasibility detection strategies which fathom some unnecessary branches. We evaluate the performance of the algorithm on different problem instances which can become benchmark problems for the cutting and packing literature.     

Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints

The paper examines a new problem in the irregular packing literature that has many applications in industry: two-dimensional irregular (convex) bin packing with guillotine constraints. Due to the cutting process of certain materials, cuts are restricted to extend from one edge of the stock-sheet to another, called guillotine cutting. This constraint is common place in glass cutting and is an important constraint in two-dimensional cutting and packing problems. In the literature, various exact and approximate algorithms exist for finding the two dimensional cutting patterns that satisfy the guillotine cutting constraint. However, to the best of our knowledge, all of the algorithms are designed for solving rectangular cutting where cuts are orthogonal with the edges of the stock-sheet. In order to satisfy the guillotine cutting constraint using these approaches, when the pieces are non-rectangular, practitioners implement a two stage approach. First, pieces are enclosed within rectangle shapes and then the rectangles are packed. Clearly, imposing this condition is likely to lead to additional waste. This paper aims to generate guillotine-cutting layouts of irregular shapes using a number of strategies. The investigation compares three two-stage approaches: one approximates pieces by rectangles, the other two approximate pairs of pieces by rectangles using a cluster heuristic or phi-functions for optimal clustering. All three approaches use a competitive algorithm for rectangle bin packing with guillotine constraints. Further, we design and implement a one-stage approach using an adaptive forest search algorithm. Experimental results show the one-stage strategy produces good solutions in less time over the two-stage approach.     

A recursive algorithm for constrained two-dimensional cutting problems

This paper presents a recursive algorithm for constrained two-dimensional guillotine cutting problems of rectangular items. The algorithm divides a stock plate into a sequence of small rectangular blocks. For the current block considered, it selects an item, puts it at the left-bottom corner of the block, and determines the direction of the dividing cut that divides the unoccupied region of the block into two smaller blocks for further consideration. The dividing cut is either along the upper edge or along the right edge of the selected item. The upper bound obtained from the unconstrained solution is used to shorten the searching space. The computational results on benchmark problems indicate that the algorithm can improve the solutions, and is faster than other algorithms.