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.     

Fixed charge problems with identical fixed charges

The general problem considered by this paper is a special case of the fixed-charge problem. The further condition imposed is that all variables have the same associated fixed-charge. The problem is discussed in the context of a known commercial application, that being the cutting stock problem. The situation considered is that of cutting given numbers of small rectangles from large rectangular stock-plates. In many such situations major aims are to have low stock-plate usage and a low number of setups of the cutting equipment. These represent conflicting objectives capable of being combined by the use of fixed charges upon the setups but this paper presents an alternative approach incorporating direct manipulation of the number of setups involved in the solution. This approach is compared to a solution technique for the general fixed-charge problem.     

An Improved Algorithm for the Non-Guillotine-Constrained Cutting-Stock Problem

A personal-computer-based algorithm to solve the non-guillotine-constrained two-dimensional cutting-stock problem is developed. The problem is constrained to single-sized rectangles placed orthogonally on a larger containing rectangle. The algorithm uses the linear combination of box lengths and widths that minimizes waste along the cutting stock's length and width to determine an optimal layout. The algorithm's performance is evaluated using two sets of test cases and compared to the results of other algorithms.     

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 Practical Approach for Determining Rectangular Stock Sizes

In this paper we address the problem of determining what rectangular sizes should be stocked in order to satisfy a bill of materials composed of smaller rectangles. As is common in many manufacturing operations, the stock material will be cut using two-staged guillotine cutting patterns. We first generate a large number of stock sizes ideally suited to the bill of materials. Then we use a facility location algorithm to consolidate the stock sizes down to an acceptable number. Given the solution of what rectangular sizes to stock, a second program is used to map bills of materials into the stock rectangles. The effectiveness of our approach is demonstrated by generating stock sizes for a real-world bill of materials with 392 distinct order sizes and over 7700 order pieces.     

Network flows and non-guillotine cutting patterns

Up till now there has been no exact and effective algorithm for the problem of finding optimal cutting patterns of rectangles which are not restricted to those with the ‘guillotine’ property. This problem can be interpreted in a resource constrained scheduling context. The contribution of this paper to this topic is a good characterization of the flow functions and graphs corresponding to cutting patterns.     

A Note on the Two-Dimensional Rectangular Cutting-Stock Problem

The concept of orthogonality in the Two-Dimensional Rectangular Cutting-Stock Problem is introduced. None of the published approaches for solving this problem permit non-orthogonal cutting patterns. An example is given to show that this may prevent the optimal cutting pattern from being obtained. The application of orthogonality to the problem of obtaining the minimum area rectangular enclosure of a number of rectangles is also discussed.     

Staged and constrained two-dimensional guillotine cutting problems: An AND/OR-graph approach

An AND/OR-graph approach has been proposed by Morabito et al. to solve non-staged and unconstrained two-dimensional guillotine cutting problems. Basically, this approach consists of representing cutting patterns as complete paths in an AND/OR graph (where nodes and arcs correspond to rectangles and cuts, respectively) and choosing a search strategy to traverse or enumerate the nodes of the graph. In this present paper, the AND/OR-graph approach is extended to solve staged and constrained problems. Computational experiments with examples from the literature are performed and indicate that this approach generates good and fast solutions using a microcomputer. In addition to the fact that the AND/OR-graph approach can handle important constraints, it can be easily extended to solve cutting and packing problems with multiple dimensions.     

Simplest optimal cutting patterns for equal rectangles

This paper presents branch-and-bound algorithms that can guarantee the simplest optimal cutting patterns of equal rectangles. An existing linear algorithm determines the global upper bound exactly. The branching process ends when a branch of a lower bound equal to the global upper bound is found.     

An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem

This paper addresses a real-life 1.5D cutting stock problem, which arises in a make-to-order plastic company. The problem is to choose a subset from the set of stock rectangles to be used for cutting into a number of smaller rectangular pieces so as to minimize total production cost and meet orders. The total production cost includes not only material wastage, as in traditional cutting stock problems, but also production time. A variety of factors are taken into account, like cutter knife changes, machine restrictions, due dates and other work in progress limitations. These restrictions make the combinatorial structure of the problem more complex. As a result, existing algorithms and mathematical models are no longer appropriate. Thus we developed a new 1.5D cutting stock model with multiple objectives and multi-constraints and solve this problem in an incomplete enumerative way. The computational results show that the solution procedure is easy to implement and works very well.     

A reduction approach for solving the rectangle packing area minimization problem

In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.     

A Central Limit Theorem for linear random fields

A Central Limit Theorem is proved for linear random fields when sums are taken over union of finitely many disjoint rectangles. The approach does not rely upon the use of Beveridge-Nelson decomposition and the conditions needed are similar in nature to those given by Ibragimov for linear processes. When specializing this result to the case when sums are being taken over rectangles, a complete analogue of the Ibragimov result is obtained for random fields with a lot of uniformity.     

Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds

In this paper the problem of optimally guillotine cutting a rectangle (A, B  ) into small rectangles of two kinds is considered. Rectangles of the first kind (c,_ai),i∈I$(c\text{,}{a}_i)\text{,}i\in I$ have the same width, and their heights can be various. Rectangles of the second kind (_bj,d),j∈J$(b_j\text{,}d)\text{,}j\in J$ have the same height, and their widths can be various. The number of occurrences of each small rectangle in a cutting pattern is not restricted. Similar problems often appear in the furniture industry. This cutting problem is reduced to the shortest path problem in a special rectangular grid, for which a linear time algorithm is suggested. This approach generalizes the approach of [E. Girlich, A.G. Tarnowski, On polynomial solvability of two multiprocessor scheduling problems, Mathematical Methods of Operations Research 50 (1999) 27–51; A.G. Tarnowski, Advanced polynomial time algorithm for guillotine generalized pallet loading problem, in: The International Scientific Collection: Decision Making Under Conditions of Uncertainty (Cutting-Packing Problems), Ufa State Aviation Technical University, 1997, pp. 93–124] and allows us to construct polynomial algorithms for the guillotine cutting problem considered with a fixed number of small rectangles of two kinds.     

An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing

This paper presents a two-stage approach for pattern generation and cutting plan determination of the one-dimensional cutting stock problem. Calculation of the total number of patterns that will be cut and generation of the cutting patterns are performed in the first stage. On the other hand, the second stage determines the cutting plan. The proposed approach makes use of two separate integer linear programming models. One of these models is employed by the first stage to generate the cutting patterns through a heuristic procedure with the objective of minimizing trim loss. The cutting patterns obtained from Stage 1 are then fed into the second stage. In this stage, another integer linear programming model is solved to form a cutting plan. The objective of this model is to minimize a generalized total cost function consisting of material inputs, number of setups, labor hours and overdue time; subject to demand requirements, material availability, regular and overtime availability, and due date constraints. The study also demonstrates an implementation of the proposed approach in a coronary stent manufacturer. The case study focuses on the cutting phase of the manufacturing process followed by manual cleaning and quality control activities. The experiments show that the proposed approach is suitable to the conditions and requirements of the company.     

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50?000 instances). It is also effective for solving the instances of problem set Cover III (almost 100?000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes.     

二维等谱问题研究的计算数学框架

等谱问题是数学、物理诸学科关注的一个热点问题,本文总结并诠释了二维等谱问题的内在计算数学性质与规律:利用镜像反演讨论等谱对的几何结构(不等距而谱相等);把一般文献中假定的特殊三角形扩展到一般的三角形或者矩形;研究特征函数的正交结构,把特定的Laplace等谱问题扩展到一般零边值的二阶线性椭圆算子等谱问题.指出合理的粗网格对于研究等谱问题及其计算的重要性:两个连续问题等谱成立的充分必要条件是存在自然粗网格使其离散问题谱相等.文中给出的数值例子与特征值近似逼近验证了相应的结论,所用的方法原则上可用于研究三维乃至高维的PDE等谱问题.     

Data set generation for rectangular placement problems

This paper describes a recursive process for generating data sets of rigid rectangles that can be placed into rectangular regions with zero waste. The generation procedure can be modified to guarantee that the aspect and area ratios of the rectangles in the generated data sets satisfy user-specified parameters. This recursive process can thus be employed to create a variety of data sets that can be used to evaluate the efficiency and scalability of rectangular cutting and packing algorithms.     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20     

Covering a polygonal region by rectangles

The problem of covering a compact polygonal region, called target region, with a finite family of rectangles is considered. Tools for mathematical modeling of the problem are provided. Especially, a function, called Γ-function, is introduced which indicates whether the rectangles with respect to their configuration form a cover of the target region or not. The construction of the Γ-function is similar to that of Φ-functions which have been proved to be an efficient tool for packing problems. A mathematical model of the covering problem based on the Γ-function is proposed as well as a solution strategy. The approach is illustrated by an example and some computational results are presented.