A rapid scheduling method by using gradual assignment for a rectangular cutting stock problem for flawed and connectable resources

A rectangular cutting stock problem for flawed and connectable resources is a kind of a rectangular cutting stock problem where orders are assigned to resources. Each order has two types of size, width and a total length. The aim of the problem is that resources are divided into pieces, called "lumps", and the sum of length of the lumps whose width equals to a width of order satisfies a total length of the order, is decided. A resource is cut by "sets" which are combinations of fixed cutting blade for length direction, and cut end to end for width direction. Moreover, there are features that are flawed that cannot be assigned to orders existing on resources, and the connection that enables to cut several parts of resources by the same set is permitted. This research proposes the method that consists of two phases. In first phase, the rectangles called "available areas" which are generated by avoiding flaws and connecting, are created by deciding positions of set change according to an expected yield ratio and a number of set changes. In the second phase, assignment for each available area is done from an order with a larger width by using a branch and bound method in order to achieve a higher yield ratio. At this time, an effective degree of a set pattern is calculated for each available area. The effective degree means a rate of improvement of a yield ratio per length of an assigned target order. It is possible to decide an assignment rapidly by searching a set pattern that has a large effective degree earlier. The proposed method has been applied to a real cutting stock problem, and the effectiveness is confirmed.