Search

In this paper, a new dataset, the driver emotion facial expression (DEFE) dataset for drivers spontaneous emotions analysis is introduced. The dataset includes facial expression recordings from 60 participants during driving. After watching a selected video-audio clip to elicit a specic emotion, each participant completed the driving tasks in the same driving scenario and rated his/her emotional responses during the driving processes from the aspects of dimensional emotion method and discrete emotion method. The study also conducted classication experiments to recognize the scales of arousal, valence, dominance, as well as the emotion category and intensity to establish baseline results for the proposed dataset. Furthermore, this paper compared emotion recognition results difference through facial expressions between dynamic driving and static life scenarios. The results showed signicant differences in the AUs presence of facial expressions between dynamic driving and static life scenarios, Therefore, to accurately recognize the drivers emotions to establish a reliable emotion-aware human-machine interaction system, thereby improving driving safety and comfort, publishing a human emotion dataset specically for the driver is necessary. The proposed dataset will be publicly available so that researchers worldwide can use it to develop and examine their driver emotion analysis methods.

Driver’s emotion affects driving safety Hu et al. (2013), therefore monitoring driver’s emotion could benefit road safety. However, the complex illumination conditions in a vehicle cockpit significantly challenge the effectiveness of camera-based facial expression recognition (FER) systems. To solve this problem, we proposed Multi-EmoNet, a novel multi-task neural network, to classify human facial expression under illumination variations and to restore noisy images. Our experiments demonstrate these two tasks are complementary and together facilitate better network representation learning. Our approach obtains significantly better classification accuracy on images with illumination variation compared to the baseline networks. More importantly, the proposed multi-task network is a general architecture that can be applied to any noise involved image classification problem.

Autonomous vehicles were experiencing rapid development in the past few years. However, achieving full autonomy is not a trivial task, due to the nature of the complex and dynamic driving environment. Therefore, autonomous vehicles are equipped with a suite of different sensors to ensure robust, accurate environmental perception. In particular, the camera-LiDAR fusion is becoming an emerging research theme. However, so far there has been no critical review that focuses on deep-learning-based camera-LiDAR fusion methods. To bridge this gap and motivate future research, this article devotes to review recent deep-learning-based data fusion approaches that leverage both image and point cloud. This review gives a brief overview of deep learning on image and point cloud data processing. Followed by in-depth reviews of camera-LiDAR fusion methods in depth completion, object detection, semantic segmentation, tracking and online cross-sensor calibration, which are organized based on their respective fusion levels. Furthermore, we compare these methods on publicly available datasets. Finally, we identified gaps and over-looked challenges between current academic researches and real-world applications. Based on these observations, we provide our insights and point out promising research directions.

Two near-infrared (NIR) dendrimers with TADF characteristics are reported to develop the non-doped solution-processed OLED for the first time. The rigid ring end-capped aliphatic chain dendrons are introduced to improve the dissolvability and film-forming ability. The dendrimers possess excellent thermal and morphological stabilities. Simultaneously, the dendrimers exhibit self-host feature that the peripheral carbazole/tricarbazole dendrons can encapsulate the core to prevent concentration quenching. Employing MPPA-3Cz as the emitter, the non-doped solution-processed device exhibits a maximum external quantum efficiency (EQE) of 0.254% with a peak wavelength at 715 nm, which is comparable to the most-efficient solution-processed NIR FOLEDs with similar electroluminescent spectra. Moreover, the device shows negligible efficiency roll-off at high current density. Our results indicate that the design of long-wavelength TADF dendrimers will be a promising strategy for the efficient non-doped solution-processed NIR OLEDs.

In the one-dimensional cutting stock problem with usable leftovers (1DCSPUL), items of the current order are cut from stock bars to minimize material cost. Here, stock bars include both standard ones bought commercially and old leftovers generated in processing previous orders, and cutting patterns often include new leftovers that are usable in processing subsequent orders. Leftovers of the same length are considered to be of the same type. The number of types of leftovers should be limited to simplify the cutting process and reduce the storage area. This paper presents an integer programming model for the 1DCSPUL with limited leftover types and describes a heuristic algorithm based on a column-generation procedure to solve it. Computational results show that the proposed approach is more effective than several published algorithms in reducing trim loss, especially when the number of types of leftovers is limited.

A triple-solution approach for the rectangular level strip packing problem is presented, where m item types with specified demands are packed in levels into a strip with definite width and infinite height to minimize the occupied height, with the constraint that the items in the same level cannot be placed one on top of the other. The approach contains two phases and considers three types of solutions. In phase one, two types of solutions, obtained respectively from solving residual problems using column generation and from looking ahead, are considered and the best is selected as phase-one solution. In phase two, an integer programming model is solved over the levels generated in phase-one to obtain phase-two solution. Finally the better one of the phase-one and phase-two solutions are selected. Computational results indicate that the approach is effective for both the instances with strongly heterogeneous items and those with weakly heterogeneous items.

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.

The primary objective in the one-dimensional cutting stock problem is to minimize material cost. In real applications it is often necessary to consider auxiliary objectives, one of which is to reduce the number of different cutting patterns (setups). This paper first presents an integer linear programming model to minimize the sum of material and setup costs over a given pattern set, and then describes a sequential grouping procedure to generate the patterns in the set. Two sets of benchmark instances are used in the computational test. The results indicate that the approach is efficient in improving the solution quality.

A heuristic approach for the two-dimensional bin-packing problem is proposed. The algorithm is based on the sequential heuristic procedure that generates each pattern to produce some items and repeats until all items are produced. Both guillotine and non-guillotine patterns can be used. Each pattern is obtained from calling a pattern-generation procedure, where the objective is to maximize the pattern value. The item values are adjusted after the generation of each pattern using a value correction formula. The algorithm is compared with five published algorithms, using 50 groups of benchmark instances. The results indicate that the algorithm is the most efficient in improving solution quality.

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.

A heuristic for the 2D arbitrary stock-size cutting stock problem is presented.A procedure with all-capacity property is proposed to obtain the patterns.The algorithm outperforms a published heuristic in solution quality.Trim loss can be reduced significantly by using the algorithm. A heuristic is presented for the two-dimensional arbitrary stock-size cutting stock problem, where a set of rectangular items with specified demand are cut from plates of arbitrary sizes that confirm to the supplier's provisions, such that the plate cost is minimized. The supplier's provisions include: the lengths and widths of the plates must be in the specified ranges; the total area of the plates with the same size must reach the area threshold. The proposed algorithm uses a pattern-generation procedure with all-capacity property to obtain the patterns, and combines it with a sequential heuristic procedure to obtain the cutting plan, from which the purchasing decision can be made. Practical and random instances are used to compare the algorithm with a published approach. The results indicate that the trim loss can be reduced by more than half if the algorithm is used in the purchasing decision of the plates.

In view of the cutting stock problem of the plate fragments and scrap cannot make full use, this paper introduces the concept of standard usage leftover, uses the recursive algorithm and the sequential heuristic procedure to solve the circle cutting problem, achieving the follow-up orders specification to use the usage leftover of the previous orders. This method can make the cutting process more simple, convenient usage leftovers inventory management, as well as conform to the requirements of the blanking for a long time. Computational experimental results show that the algorithm has a high material utilization, and playing a guiding role to the actual industrial production.

A pattern-set generation algorithm (PSG) for the one-dimensional multiple stock sizes cutting stock problem (1DMSSCSP) is presented. The solution process contains two stages. In the first stage, the PSG solves the residual problems repeatedly to generate the patterns in the pattern set, where each residual problem is solved by the column-generation approach, and each pattern is generated by solving a single large object placement problem. In the second stage, the integer linear programming model of the 1DMSSCSP is solved using a commercial solver, where only the patterns in the pattern set are considered. The computational results of benchmark instances indicate that the PSG outperforms existing heuristic algorithms and rivals the exact algorithm in solution quality.

This paper presents a heuristic algorithm for the rectangular two-dimensional cutting stock problem, where metal coils of multiple widths are divided into rectangular items with guillotine cuts. The cutting process contains two phases. Coils are cut into segments at the first phase and the segments into items at the second phase. A subset of three-staged patterns is considered in generating the cutting plan. The algorithm is used to accomplish the following tasks: (1) Generating cutting plans for the cutting process; (2) Selecting the coil widths to purchase; (3) Optimizing the segment lengths to order. Benchmark instances are used to demonstrate the effectiveness of the algorithm in improving material utilization, and examples are used to illustrate the decision methods for different tasks.

Two-staged patterns are often used in manufacturing industries to divide stock plates into rectangular items. A heuristic algorithm is presented to solve the rectangular two-dimensional single stock size cutting stock problem with two-staged patterns. It uses the column-generation method to solve the residual problems repeatedly, until the demands of all items are satisfied. Each pattern is generated using a procedure for the constrained single large object placement problem to guarantee the convergence of the algorithm. The computational results of benchmark and practical instances indicate the following: (1) the algorithm can solve most instances to optimality, with the gap to optimality being at most one plate for those solutions whose optimality is not proven and (2) for the instances tested, the algorithm is more efficient (on average) in reducing the number of plates used than a published algorithm and a commercial stock cutting software package.

This paper presents a heuristic algorithm for the rectangular strip packing problem, where a set of rectangular items are packed orthogonally into a strip of definite width and infinite height, so as to minimize the required height. The items cannot overlap and rotation by 90 degrees is allowed. The solution contains several sections. The algorithm is based on a sequential grouping and value correction procedure that considers multiple candidate solutions. It generates each next section using a subset of the remaining items and then corrects the values of the included items. The algorithm is used to solve 13 groups of benchmark instances. It is able to improve the solution quality for all groups.

This article deals with the guillotine-constrained two-dimensional cutting problem, where a guillotine is used to cut the stock plate into rectangular pieces, such that the pattern value (the total value of the pieces produced) is maximized, observing the constraint that the frequency of each piece type should not exceed the demand. Homogeneous two-segment (HTS) cutting patterns are considered to simplify the cutting process. Each HTS pattern includes two segments, each segment contains homogeneous strips of the same direction, and each homogeneous strip contains pieces of the same type. A heuristic is presented for generating HTS patterns. It is based on dynamic programming and branch-and-bound techniques. The computational results indicate that the heuristic is able to generate solutions close to optimal, and is adequate for solving large-scale instances.

T-shape patterns are often used in dividing stock plates into rectangular pieces, because they make good balance between plate cost and cutting complexity. A dividing cut separates the plate into two segments, each of which contains parallel strips, and the strip orientations of the two segments are perpendicular to each other. This paper presents a heuristic algorithm for constrained T-shape patterns, where the optimization objective is to maximize the pattern value, and the frequency of each piece type does not exceed the demand. The algorithm considers many dividing-cut positions, determines the pattern value associated to each position using a layout-generation procedure, and selects the one with the maximum pattern value as the solution. Pseudo upper bounds are used to skip some non-promising positions. The computational results show that the algorithm is fast and able to get solutions better than those of the optimal two-staged patterns in terms of material utilization. Highlights? We present a heuristic for the constrained two-dimensional cutting problem of rectangular pieces. ? T-shape patterns are used to simplify the cutting process. ? The approach can solve large-scale instances quickly. ? The computational results indicate that T-shape patterns can yield much better material utilization than both two-staged and homogenous T-shape 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.

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.

Guillotine patterns of specified features are often used in manufacturing industries to cut stock plate into rectangular pieces. The pattern type should be selected from considering both material utilization and cutting cost. This article proposes extended block patterns for the two-dimensional cutting stock problem, where each cut on the plate produces just one extended block. A recursion is used to generate the optimal pattern. It maximizes the difference between the total value of the included pieces and the cutting cost. The computational results indicate that extended block patterns are useful to reduce production cost.

This paper considers the one-dimensional cutting stock problem in which m types of items are cut from stock bars of multiple sizes such that the bar cost is minimized. A solution to this problem is a cutting plan consisting of a set of cutting patterns with specified frequency. A CAM system based on a sequential heuristic procedure is developed for generating cutting plans. The algorithm takes the reduction of bar cost as the primary objective, and considers two secondary objectives - pattern reduction and shorter stocks reduction. The system provides a set of non-dominated cutting plans so that the most appropriate one can be selected according to the specified circumstance. Computational results indicate that the algorithm can generate solutions comparable to or better than those of previously published algorithms that consider pattern reduction.

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 manufacturing industry often uses the two-phase process to divide stock plates into rectangular items. A guillotine machine cuts the plates into homogenous strips at the first phase, where each strip contains items of the same type. Either a guillotine machine or stamping press cuts the strips into items at the second phase. This paper presents a recursive branch-and-bound algorithm for generating constrained homogenous T-shape (HTS) cutting patterns at the first phase, where the frequency of an item type is constrained by its upper bound. A HTS pattern includes two segments. Each segment contains homogenous strips of the same direction. The strip directions of the two segments are perpendicular to each other. Two versions of the algorithm are presented. The first uses the unconstrained solutions to estimate the upper bounds, and the second uses the constrained solutions. The computational results indicate that the algorithm is much faster than existing algorithms.

The cutting and stamping process is often used to divide metal plate into circular items. It contains the cutting and stamping stages. A guillotine machine divides the plate into strips at the cutting stage. Each strip contains items of the same type. A press stamps out the items from the strips at the stamping stage. T-shape patterns are often used at the cutting stage. A cut divides a T-shape pattern into an X-segment of horizontal strips and a Y-segment of vertical strips. The position of the dividing cut should be determined such that the pattern value is maximized. A heuristic for constrained T-shape patterns is presented. For each position of the dividing cut, it generates an optimal strip layout on the Y-segment using all items, and generates another optimal strip layout on the X-segment using the remaining items. Computational results indicate that the algorithm is efficient in improving material utilization.

Some factories use the cutting and stamping processes to divide stock plates into circles to make products. A guillotine machine cuts the plate into strips in the cutting process and then a stamping press punches out circles from the strips in the stamping process. The circles in a strip have the same size. The number of rows of circles in each strip is limited. Under these constraints, this paper addresses the following primary objective: to cut a plate by a guillotine method so that the maximal number of circles is obtained. Then the secondary objective should be optimized: the cutting layout should use a minimal number of strips. The problem is formulated as a bi-objective optimization problem and a recursive algorithm is presented for it. The computational results indicate that the algorithm can efficiently simplify the cutting process.

The cutting and stamping process is often used to divide a stock plate into items to make products. It includes two phases. A guillotine machine cuts the plate orthogonally into homogenous strips at the cutting phase; then a stamping press stamps out the items from the strips at the stamping phase. A homogenous strip contains items of the same type. A one-stage homogenous strip cutting pattern (OSHSCP) contains parallel homogenous strips of the same length. The OSHSCP is useful because it can be used independently or as elements to compose other types of cutting patterns. This article presents a dynamic programming algorithm for generating the optimal constrained OSHSCP, where the maximum demand for each item type is specified and the objective is to maximize the total value of items included in the pattern. The computational results indicate that the computation time is reasonable.

A heuristic algorithm for the one-dimensional cutting stock problem with usable leftover (residual length) is presented. The algorithm consists of two procedures. The first is a linear programming procedure that fulfills the major portion of the item demand. The second is a sequential heuristic procedure that fulfills the remaining portion of the item demand. The algorithm can balance the cost of the consumed bars, the profit from leftovers and the profit from shorter stocks reduction. The computational results show that the algorithm performs better than a recently published algorithm.

Circular items are often produced from stock plates using the cutting and stamping process that consists of two stages. A guillotine machine divides the plate into strips at the cutting stage, and then a press punches out the items from the strips at the stamping stage. The cutting cost at the first stage often increases with the number of strips in the cutting plan. An approach is presented for the two-dimensional cutting stock problem of the strips at the cutting stage. The objective is to minimize the sum of the material and the cutting costs. The approach formulates the problem as an integer linear programming, and uses a column generation method for generating the cutting patterns. The cutting patterns have the feature that each cut on the plate produces just one strip. The computational results indicate that the approach can greatly reduce the number of strips in the cutting plan.

Circular pieces are often cut from stainless steel roll to make common commodities such as pots and cups. The related factories are often make-to-order ones. The stock rolls usually have the same width. Each working order requires pieces of the same size. Pieces of different sizes cannot appear in the same cutting pattern because the orders do not arrive simultaneously. The approach proposed in this paper assumes that the original roll can be slit into a strip and a partial roll. The strip is used to fulfill the current order. The partial roll will be used to fulfill future orders and cannot be slit further. The approach determines several standard widths for the partial rolls and uses a greedy procedure to select the roll (either the original roll or a partial roll) to fulfill the current order. The computational results indicate that the approach is efficient in improving material utilization.

A rectangular two-dimensional cutting stock problem in the steel bridge construction is discussed. It is the problem of cutting a set of rectangular items from plates with arbitrary sizes that lie in the supplier specified ranges, such that the necessary plate area is minimized. Several types of cutting patterns are used to compose the cutting plan. All of them are easy to generate and cut except the last one. The algorithm uses both recursive and dynamic programming techniques to generate patterns of the last type. The computational results of 22 practical instances indicate that the algorithm can produce solutions close to optimal, and the computation time is reasonable for practical use.

Stainless steel rolls are often cut into circular items to make such common commodities as water jugs, buckets, pails, pots, cups and basins. The items are often cut with the shearing and punching process that consists of three stages. A guillotine shear cuts the roll into sheets at the first stage, and cuts the sheets into strips at the second stage. A stamping press punches out the items from the strips at the third stage. The sheets and the strips may be either rectangles or parallelograms. The height of the sheets is the same as the roll width. A strip contains one or more rows of items, and is parallel to a side of the sheet. This paper presents an algorithm to generate optimal cutting patterns for the three-stage cutting process mentioned above. The algorithm uses a knapsack procedure to generate optimal cutting patterns on the sheets, and uses a linear programming approach to determine the number of sheets cut according to each pattern. The computational results indicate that the algorithm is efficient in both computation time and material utilization.

This paper presents an algorithm for the constrained, two-dimensional, rectangular multiple identical large object placement problem, where a set of small rectangular items must be cut from a specified number of identical plates, so as to maximize the value of the cut items. The algorithm generates optimal homogenous T-shape patterns that contain only homogenous strips. A homogenous strip contains items of the same type. A cut divides the plate into two segments. Each segment consists of strips with the same direction. The strips in the first segment are horizontal, and those in the second segment are vertical. The algorithm is based on the bottom-up tree-search approach. Both lower and upper bounds are used to prune the search tree. The computational results indicate that the algorithm is capable of solving problems of small and medium scales.

A heuristic recursive algorithm for the two-dimensional rectangular strip packing problem is presented. It is based on a recursive structure combined with branch-and-bound techniques. Several lengths are tried to determine the minimal plate length to hold all the items. Initially the plate is taken as a block. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. The dividing cut is vertical if the block width is equal to the plate width; otherwise it is horizontal. Both lower and upper bounds are used to prune unpromising branches. The computational results on a class of benchmark problems indicate that the algorithm performs better than several recently published algorithms.

An approach is proposed for generating homogenous three-staged cutting patterns for the constrained two-dimensional guillotine-cutting problems of rectangles. It is based on branch-and-bound procedure combined with dynamic programming techniques. The stock plate is divided into segments. Each segment consists of strips with the same direction. Only homogenous strips are allowed, each of which contains rectangles of the same size. The approach uses a tree-search procedure. It starts from an initial lower bound, implicitly generates all possible segments through the builds of strips, and constructs all possible patterns through the builds of segments. Tighter bounds are established to discard non-promising segments and patterns. Both heuristic and exact algorithms are proposed. The computational results indicate that the algorithms are capable of dealing with problems of larger scale. Finally, the solution to a cutting problem taken from a factory that makes passenger cars is given.

This paper presents an algorithm for unconstrained T-shape homogenous block cutting patterns of rectangular pieces. A vertical cut divides the stock sheet into two segments. Each segment consists of sections that have the same length and direction. A section contains a row of homogenous blocks. A homogenous block consists of homogenous strips of the same piece type. Each cut on the block produces just one strip. The directions of two strips cut successively from a block are either parallel or orthogonal. The algorithm uses a dynamic programming recursion to generate optimal blocks, solves knapsack problems to obtain the block layouts on the sections and the section layout on segments of various lengths, and optimally selects two segments to compose the cutting pattern. The computational results indicate that the algorithm is efficient in improving material usage, and the computation time is reasonable.

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.

The manufacture of parts made of metal sheet often includes two successive processes: the cutting process at which a guillotine shear cuts the sheet into strips, and the punching process at which a stamping press punches out the blanks from the strips. This paper presents an algorithm for generating optimal two-staged cutting patterns of strips for the cutting process. At the first stage the sheet is divided into segments with parallel cuts. Each segment contains strips with the same length and direction. The segments are cut into strips at the second stage. The algorithm calls a recursion function to determine the optimal strip layouts on segments of various lengths, and calls another recursion function to optimally arrange the segments in the sheet, so that the value of the pattern reaches maximum. The computational results indicate that the algorithm is efficient both in computation time and in material usage.

The manufacturing industry often uses the cutting and stamping process to divide stock plates into circles. A guillotine machine cuts the plate into strips for stamping at the cutting stage, and then a stamping press punches out the circles from the strips at the stamping stage. The problem discussed is to cut a plate into strips of identical circles such that the number of circles is maximized. A dynamic programming algorithm is presented for generating the simplest optimal cutting patterns of the strips. The computational results indicate that the algorithm is much efficient in simplifying the cutting process.

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.