Exact algorithm for generating two-segment cutting patterns of punched strips

Metal plates are often divided into items in two stages. First a guillotine shear cuts the plate into strips at the shearing stage, and then a stamping press punches out the items from the strips at the punching stage. This paper presents an algorithm for generating optimal two-segment cutting patterns of strips at the shearing stage. An orthogonal cut divides the plate into two segments, each of which contains strips of the same direction and length. The algorithm uses dynamic programming techniques to determine the optimal strip layouts on segments of various lengths, and selects two segments to appear in the optimal pattern. The segments are considered in increasing order of their lengths, so that dominant properties can be used to shorten the computation time. The computational results indicate that the algorithm is efficient in both material utilization and computation time.     

Simple block patterns for the two-dimensional cutting problem

This paper presents an algorithm for the unconstrained two-dimensional cutting problem of rectangular pieces. It proposes the simple block (SB) pattern consisting of simple blocks. The SB pattern is defined recursively. Each cut on the stock plate produces just one simple block. A horizontal cut produces a horizontal block with width equal to that of the leftmost piece in the block. A vertical cut produces a vertical block with length equal to that of the bottommost piece in the block. The algorithm generates the optimal SB pattern recursively, and selects optimally the first piece in each block. It uses upper bound to prune some unpromising branches during the searching process. The computational results indicate that the algorithm is highly efficient in improving material utilization, and the computation time is reasonable.     

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.     

Fast heuristic for constrained homogenous T-shape cutting patterns

Homogenous T-shape (HTS) cutting patterns are welcomed when the two-phase process is used to produce rectangular pieces from the stock plate, where the plate is cut into homogenous strips at the first phase, and the strips are divided into pieces at the second phase. A heuristic is presented for generating constrained HTS patterns, where the objective is to maximize the pattern value that is equal to the total value of the included pieces, observing the upper bound constraint on the frequency of each piece type. The heuristic is based on dynamic programming and branch-and-bound techniques. It can yield solutions close to optimal with short computation time. By providing good initial solutions, the heuristic can greatly improve the time efficiency of an existing exact branch-and-bound algorithm.     

Heuristic for constrained two-dimensional three-staged patterns

Three-staged cutting patterns are often used in dividing large plates into small rectangular items. Vertical cuts separate the plate into segments in the first stage, horizontal cuts split each segment into strips in the second stage, and vertical cuts divide each strip into items in the third stage. A heuristic algorithm for generating constrained three-staged patterns is presented in this paper. The optimization objective is to maximize the pattern value that is the total value of the included items, while the frequency of each item type should not exceed the specified upper bound. The algorithm uses an exact procedure to generate strips and two heuristic procedures to generate segments and the pattern. The pattern-generation procedure first determines an initial solution and then uses its information to generate more segments to extend the solution space. Computational results show that the algorithm is effective in improving solution quality.     

Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors

The author presents a method to generate optimal multi-segment cutting patterns to improve the material usage of the circular blanks in the manufacturing of rotors and stators of electric motors. In the patterns generated, the sheet is divided into segments with cut lines perpendicular to the sheet length. The width of the segments equals to the sheet width. The lengths of the segments may be different. A segment includes one or more strips that are parallel to the sheet length. More than one row of identical blanks can appear in a strip. The method applies the property of the optimal patterns to reduce the number of segment lengths that should be considered. It uses the knapsack algorithm to determine the optimal arrangement of blanks on each segment and the numbers of the segment lengths in the sheet to make the material usage reach its maximum. The computational results indicate that the method is efficient both in computation time and in material usage. The solution to an example is given.     

A new dynamic programming procedure for three-staged cutting patterns

Three-staged patterns are often used to solve the 2D cutting stock problem of rectangular items. They can be divided into items in three stages: Vertical cuts divide the plate into segments; then horizontal cuts divide the segments into strips, and finally vertical cuts divide the strips into items. An algorithm for unconstrained three-staged patterns is presented, where a set of rectangular item types are packed into the plate so as to maximize the pattern value, and there is no constraint on the frequencies of each item type. It can be used jointly with the linear programming approach to solve the cutting stock problem. The algorithm solves three large knapsack problems to obtain the optimal pattern: One for the item layout on the widest strip, one for the strip layout on the longest segment, and the third for the segment layout on the plate. The computational results indicate that the algorithm is efficient.     

Branch and bound algorithm for a transfer line design problem: Stations with sequentially activated multi-spindle heads

In this paper, a new transfer line balancing problem is considered. The main difference from the simple assembly line balancing problem is that the operations are grouped into blocks (batches). All the operations of the same block are carried out simultaneously by one piece of equipment (multi-spindle head). Nevertheless, the blocks assigned to the same workstation are executed in series. The line cost consists of the sum of block and workstation costs. At the considered line design stage, the set of all available blocks is given. The aim is to find a subset from the given set of available blocks and to find a partition of this subset to workstations such that each operation is executed once and the line cost is minimal while all the precedence, cycle time, and compatibility (operation inclusion and block exclusion) constraints are respected. A new lower bound based on solving a special set partitioning problem is presented and a branch and bound algorithm is developed. The experimental results prove the quality of the lower bound and applicability of the suggested branch and bound algorithm for medium sized industrial cases.     

A tabu search algorithm for a two-dimensional non-guillotine cutting problem

In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.     

Dynamic Programming Algorithms for Generating Optimal Strip Layouts

This paper presents dynamic programming algorithms for generating optimal strip layouts of equal blanks processed by shearing and punching. The shearing and punching process includes two stages. The sheet is cut into strips using orthogonal guillotine cuts at the first stage. The blanks are punched from the strips at the second stage. The algorithms are applicable in solving the unconstrained problem where the blank demand is unconstrained, the constrained problem where the demand is exact, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. When the sheet length is longer than the blade length of the guillotine shear used, the dynamic programming algorithm is applied to generate optimal layouts on segments of lengths not longer than the blade length, and the knapsack algorithm is employed to find the optimal layout of the segments on the sheet. Experimental computations show that the algorithms are efficient.     

On a control algorithm for a linear system with measurements of a part of coordinates of the phase vector

We consider a feedback control problem for a system of ordinary differential equations in the case when only a part of coordinates of the phase vector are measured and propose a solution algorithm that is stable to perturbations. The algorithm is based on a combination of the theories of dynamical inversion and guaranteed control. It consists of two blocks: a block for the dynamical reconstruction of unmeasured coordinates and a control block.     

Optimisation of multi-position machines and transfer lines

A new optimisation problem for design of multi-position machines and automatic transfer lines is considered. To reduce the number of pieces of equipment, machining operations are grouped into blocks. The operations of the same block are performed simultaneously by one piece of equipment (multi-spindle head). At the studied design stage, constraints related to the design of blocks and workstations, as well as precedence constraints for operations are known. The problem consists in an optimal grouping of the operations into blocks minimizing the total number of blocks and workstations while reaching a given cycle time (productivity). A constrained shortest path algorithm is developed and tested.     

Flow-shop scheduling with setup and assembly operations

A scheduling model for a production system including machining, setup and assembly operations is considered. Production of a number of single-item products is ordered. Each product is made by assembling a set of several different parts. First, the parts are manufactured in a flow-shop consisting of multiple machines. Then, they are assembled into products on a single assembly stage. Setup operation and setup time are needed when a machine starts processing the parts or it changes items. The operations are partitioned into several blocks. Each block consists of the machining operations, the setup operations, and the assembly operation(s) for one or several products. The parts of the same item in a block are processed successively. The objective function is the mean completion time for all products. We consider a problem to partition the operations into blocks and sequence the parts in each block so as to minimize the objective function. Solution procedures using pseudo-dynamic programming and a branch-and-bound method are proposed. Computational experiments are carried out to evaluate the performance of the solution procedures. It has been found that a good near-optimal schedule is obtained efficiently by the proposed solution procedures.     

Numerical Determination of a Canonical Form of a Symplectic Matrix

We propose an algorithm that transforms a real symplectic matrix with a stable structure to a block diagonal form composed of three main blocks. The two extreme blocks of the same size are associated respectively with the eigenvalues outside and inside the unit circle. Moreover, these eigenvalues are symmetric with respect to the unit circle. The central block is in turn composed of several diagonal blocks whose eigenvalues are on the unit circle and satisfy a modification of the Krein-Gelfand-Lidskii criterion. The proposed algorithm also gives a qualitative criterion for structural stability.     

The cutting stock problem for large sections in the iron and steel industries

The characteristics of a cutting stock problem for large sections in the iron and steel industries are as follows:(1) There is a variety of criterions such as maximizing yield and increasing effeciency of production lines. (2) A cutting stock problem is accompanied by an optimal stock selection problem. A two-phase algorithm is developed, using an heuristic method. This algorithm gives nearly optimal solutions in real time. It is applied to both batch-solving and on-line solving of one-dimensional cutting of large section. The new algorithm has played an important role in a large-section production system to increase the yield by approximately 2.5%.     

Block Squares

A block square is a certain 1–block design. We show that there are exactly two block squares in which each block consists of 5 elements and each element is contained in 6 blocks.     

A two-dimensional strip cutting problem with sequencing constraint

We study a strip cutting problem that arises in the production of corrugated cardboard. In this context, rectangular items of different sizes are obtained by machines, called corrugators, that cut strips of large dimensions according to particular schemes containing at most two types of items. Because of buffer restrictions, these schemes have to be sequenced in such a way that, at any moment, at most two types of items are in production and not completed yet (sequencing constraint). We show that the problem of finding a set of schemes of minimum trim loss that satisfies an assigned demand for each item size is strongly NP-hard, even if the sequencing constraint is relaxed. Then, we present two heuristics for the problem with the sequencing constraint, both based on a graph characterization of the feasible solutions. The first heuristic is a two-phase procedure based on a mixed integer linear programming model. The second heuristic follows a completely combinatorial approach and consists of solving a suitable sequence of minimum cost matching problems. For both procedures, an upper bound on the number of schemes (setups) is found. Finally, a computational study comparing the quality of the heuristic solutions with respect to an LP lower bound is reported.     

An optimization model for trim loss minimization in an automotive glass plant

This paper deals with glass cutting in an Italian plant producing parts for the automotive market. Glass cutting is basically organised in two phases: first, large rectangular sheets of the same type are obtained from a ribbon of flat glass and sent to warehouse; then, sheets of various types are taken from the warehouse and cut into small rectangular parts of various sizes according to demand. In both phases, trim loss is generated. A problem then arises of fulfilling the demand of small parts using a limited assortment of large sheets and minimizing the total trim loss. In this paper we describe a heuristic algorithm based on a p-median model with additional constraints that take into account all the relevant shop floor requirements. A computational study conducted on real instances provided by the plant is presented and discussed.     

Finitely convergent cutting planes for concave minimization

In 1964 Tuy introduced a new type of cutting plane, the concavity cut, in the context of concave minimization. These cutting planes, which are also known as convexity cuts, intersection cuts and Tuy cuts, have found application in several algorithms, e.g., branch and bound algorithm, conical algorithm and cutting plane algorithm, and also in algorithms for other optimization problems, e.g., reverse convex programming, bilinear programming and Lipschitzian optimization. Up to now, however, it has not been possible to either prove or disprove the finite convergence of a pure cutting plane algorithm for concave minimization based solely on these cutting planes. In the present paper a modification of the concavity cut is proposed that yields deeper cutting planes and ensures the finite convergence of a pure cutting plane algorithm based on these cuts.     

On designing a reconstruction-control algorithm for an ecological-economic model

A control problem for the Nordhaus ecological-economic model is considered. The problem consists in constructing an algorithm for the stable generation of control characteristics that provide a given quality of the process in the case when only a part of the phase coordinates are measured and uncontrolled disturbances act on the system. We design such an algorithm (a reconstruction-control controller) using the feedback control method. The algorithm consists of two blocks, the online reconstruction and positional control, which are based on appropriate modifications of N.N. Krasovskii’s extremal shift method.