Search

In paper production, a jumbo reel is cut into multiple intermediate rolls, and each intermediate roll is then sheeted as finished goods. This problem is called a cutting stock problem and is proven to be NP-hard. The objective is to minimize material waste or trim loss from all the cuttings. In the case that any intermediate roll is not entirely used for its associated order, the intermediate roll itself could turn to be a dead stock. We use the concept of universal sizes of intermediate rolls to eliminate the dead stock. A pre-defined number of universal sizes of intermediate rolls is to be used to serve all the orders. The problem is solved using Reinforcement Artificial Bee Colony algorithm with Integer Linear Programming subroutine. This proposed approach is then tested with a set of 1,055 orders and 127 different sizes of sheet papers from a paper manufacturer. The results reveal that our method outperforms other algorithms. Our method offers the total trim loss of 3.51%, compared to the trim loss reported by the industry of at least 5%. This approach not only reduces the number of partially cut rolls, but also decreases the number of the jumbo reels needed to serve all the orders. Therefore, both the inventory cost and material cost can be saved.

Genetic programming approaches have been employed in the literature to automatically design constructive heuristics for cutting and packing problems. These heuristics obtain results superior to human-created constructive heuristics, but they do not generally obtain results of the same quality as local search heuristics, which start from an initial solution and iteratively improve it. If local search heuristics can be successfully designed through evolution, in addition to a constructive heuristic which initializes the solution, then the quality of results which can be obtained by automatically generated algorithms can be significantly improved. This paper presents a grammatical evolution methodology which automatically designs good quality local search heuristics that maintain their performance on new problem instances. [ABSTRACT FROM PUBLISHER]

The best-fit heuristic is a simple yet powerful one-pass approach for the two-dimensional rectangular stock-cutting problem. It had achieved the best published results on a wide range of benchmark problems until the development of the approaches described in this paper. Here, we illustrate how improvements in solution quality can be achieved by the hybridisation of the best-fit heuristic together with simulated annealing and the bottom-left-fill algorithm. We compare and contrast the new hybrid approach with other approaches from the literature in terms of execution times and the quality of the solutions achieved. Using a range of standard benchmark problems from the literature, we demonstrate how the new approach achieves significantly better results than previously published methods on almost all of the problem instances. In addition, we provide results on 10 new benchmark problems to encourage further research and greater comparison between current and future methods. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study the problem of packing a sequence of objects into bins. The objects are all either divisible or indivisible and occur in accordance with a certain probability distribution. We would like to find the average number of entries wasted in a bin if objects are indivisible and the probability of splitting the last object in a bin if objects are divisible. We solve this problem under a unified formulation by modeling a packing process as a Markov chain whose state transition probabilities are derived from an application of the partitions of integers. An application of this study to instruction cache design shows that a line size of 16bytes has minimized the probability of splitting the last ×86 instruction in a cache line. For micro-op cache design, a line size of four entries has minimized the number of entries wasted per line. [Copyright &y& Elsevier]

Abstract: Layout has a close relationship with product cost in the vein of how to most efficiently cut product patterns from raw materials. This is the so-called “nesting problem”, which occurs frequently in sheet metal and furniture industries, wherein material utilization needs to be maximized. In this paper, a quick location and movement (QLM) algorithm is proposed to solve the situation of irregular shapes nested on multiple irregular sheets. This approach includes two major parts: it first approximates irregular shapes to a polygon with the use of a cluster of straight lines, and second, it arranges the approximated shapes one-by-one with the proposed step-by-step rule. Finally, this study investigates and compares examples presented by other authors. The results show that the QLM algorithm takes less time to calculate a layout and the material utilization efficiency is higher compared to other methods. [Copyright &y& Elsevier]

Abstract: One-dimensional stock-cutting problem is a commonly encountered problem not only in shipbuilding and construction of coastal structures, but also in other engineering applications related to production and construction. The proposed approach achieves results using cutting patterns directly whereas analytical methods first need to establish a mathematical model. While obtaining ideal solutions of the analytical methods, the new approach limits the wastage to a minimum number of stock materials. In addition, the new approach allows the use of different sized stock materials while it creates various options for the use of single sized stock materials. Use of different sized stock materials broadens the point of view for the solution compared to the use of single sized stock material. Moreover, the new method yields integer results whereas the analytical methods using linear programming usually produce impractical non-integer results. To obtain integer results, the analytical methods need to solve the problem multiple times and screen the alternative solutions. [Copyright &y& Elsevier]

Abstract: One-dimensional stock cutting problems can be encountered at the production stage of many areas of engineering as well as in shipbuilding and coastal structures. In this paper, a novel approach is proposed to solve the problem directly by using the cutting patterns obtained by the analytical methods at the mathematical modeling stage. By minimizing both the number of different cutting patterns and material waste, the proposed method is able to capture the ideal solution of the analytical methods. The main advantage of the method comes from the fact that an integer solution is guaranteed. However, in analytical methods it is not always possible to produce integer solutions and the linear programming algorithm must be run repeatedly to select integer solutions from the alternatives to get practical results. The proposed nesting algorithm is a low-cost and efficient tool. Minimizing the number of cutting patterns contributes to time and material savings. Also, by using this method trim loss is minimized and stock usage is maximized. The efficiency of the proposed method is demonstrated by extensive numerical results. [Copyright &y& Elsevier]

Abstract: This paper presents a binary tree hierarchical representation for bounding boxes (rectangles) comprised of shapes (other rectangles in our case) that are to be cut from a two-dimensional sheet of material. Although tree-representations of this problem have been presented in the open literature extensively, the binary tree representation is shown in this work to be capable of capturing any configuration of such rectangular shapes in two-dimensional space, such as rotations through right angles and translations, and to be advantageous and more general over other approaches when local search optimization procedures are to be utilized. The construction is such that these boxes must be bound together in pairs having a common edge, and can be extended to contain constrains regarding vertical or horizontal space between the actual objects as well as special types of cuts, e.g. guillotine cuts used in the glass cutting industry. Finally, a simple continuous sheet application is shown as a demonstration of the capabilities of the algorithm in connection with a local search method, specifically threshold accepting. [Copyright &y& Elsevier]

We provide an O(logn)-approximation algorithm for the following problem. Given a convex n-gon P, drawn on a convex piece of paper, cut P out of the piece of paper in the cheapest possible way. No polynomial-time approximation algorithm was known for this problem posed in 1985. [Copyright &y& Elsevier]

A new approach has been developed for the arrangement of rectangular pieces in plates for the guillotine-cutting problem as encountered in ship production and similar manufacturing processes. The algorithm is quite novel in the sense that instead of making preliminary specifications and ignoring all the alternative arrangements, as is the case for most of the current models, it selectively considers feasible arrangements by eliminating the majority of the probable arrangements that render the problem insolvable. Intermediate steps of the algorithm produce results which cannot be obtained through integer programming. Losses are distributed to the minimum number of plates. The number of arrangement plans is also minimized. Overall the solution of the problem has been drastically simplified to allow even hand calculations instead of long computer runs. [Copyright &y& Elsevier]

In this study, two approaches are explored for the solution of the rectangular stock cutting problem: neuro-optimization, which integrates artificial neural networks and optimization methods; and genetic neuro-nesting, which combines artificial neural networks and genetic algorithms. In the first approach, an artificial neural network architecture is used to generate rectangular pattern configurations, to be used by the optimization model, with an acceptable scrap. Rectangular patterns of different sizes are selected as input to the network to generate the location and rotation of each pattern after they are combined. A mathematical programming model is used to determine the nesting of different sizes of rectangular patterns to meet the demand for rectangular blanks for a given planning horizon. The test data used in this study is generated randomly from a specific normal distribution. The average scrap percentage obtained is within acceptable limits. In the second approach, a genetic algorithm is used to generate sequences of the input patterns to be allocated on a finite width with infinite-length material. Each gene represents the sequence in which the patterns are to be allocated using the allocation algorithm developed. The scrap percentage of each allocation is used as an evaluation criterion for each gene for determining the best allocation while considering successive generations. The allocation algorithm uses the sliding method integrated with an artificial neural network based on the adaptive resonance theory (ART1) paradigm to allocate the patterns according to the sequence generated by the genetic algorithm. It slides an incoming pattern next to the allocated ones and keeps all scrap areas produced, which can be utilized in allocating a new pattern through the ART1 network. If there is a possible match with an incoming pattern and one of the scrap areas, the neural network selects the best match area and assigns the pattern. Both approaches gave satisfactory results. The second approach generated nests having packing densities in the range 95–97%. Improvement in packing densities was possible at the expense of excessive computational time. Parallel implementation of this unconventional approach could well bring a quick and satisfactory solution to this classical problem. [ABSTRACT FROM AUTHOR]