Evolutionary-based hybrid algorithm for 2D cutting stock problem

摘要

Cutting stock problem (CSP) affects cost of production and stock use efficiency in many industries. The majority of such industries handle stock of raw material in sheet form with the priority of waste reduction. Thus, in this paper we study the two-dimensional CSP (2-D CSP) with main goal of minimizing trim loss. Current approaches are primarily designed to deal with regular stock sheets only and do not handle irregular or defective sheets. That is why the problem is considered to be partially solved from an industrial stand point. In this paper, we introduce a novel algorithm for 2D CSP to minimize the waste and address the issue of defective and/or irregular stock sheets. The algorithm utilizes image processing, evolutionary-programming (EP), and Linear programming (LP) to form a practical solution. Detection & Isolation of sheets' defects and conversion of irregular sheets to regular is accomplished by image processing. Further processing is done by the remaining techniques to efficiently minimize the waste. Experimental results show that the proposed algorithm succeeds in achieving lower waste values compared to conventional EP algorithms.