||To determine the maximum rectangular block (MRB) from a rare material as larger as possible indicates to increase of the rate of material usage. The cutting problem has been addressed since 1984. But its applications were strongly restricted due to simple definition of the cutting problem. In order to expand the area of applications, in this dissertation, a general cutting problem will be considered. At first, the rectangular boundary of the original material is replaced by an arbitrary closed region. Due to the general material profile, many other materials can be involved. When the maximum rectangular block has been obtained, the remaining closed space (RCS) of the material can be divided again. A blind search algorithm (BSA), which globally searches the MRB point-by-point from the boundary points of the contour, will be developed. The BSA is able to acquire the MRB from mother material continuously from larger areas to smaller ones until a predefined threshold value is reached. |
Although the MRB in an arbitrary closed region can be successfully resolved, two problems are still unsolved. The first limitation is that both edges of the MRB must be parallel with image axes. The second limitation is that the mother material needs to be uniform, i.e., no defects inside the material. In order to release these two assumptions, some algorithms will be presented. Applications of those techniques to the leather material will be demonstrated. In spite of resolving the cutting problem by the presented algorithms, a possible improvement is needed for larger MRBs. The challenge about larger MRBs is that how to make the searching process more efficiently. Therefore, two new methods of GA to obtain the MRB are proposed. By comparing the results using the BSA, the GA approaches are verified to be able to reach the near-optimal performance. Even though only leather material is focused in this research, the proposed methods can be easily extended to other industrial materials, especially for those expensive materials.