Network flows and non-guillotine cutting patterns (Q795062)

Up till now there has been no exact and effective algorithm for the problem of finding optimal cutting patterns of rectangles which are not restricted to those with the ''guillotine'' property. This problem can be interpreted in a resource constrained scheduling context. The contribution of this paper to this topic is a good characterization of the flow functions and graphs corresponding to cutting patterns. This characterization makes it possible to look for good cutting patterns with the help of network flows and graph theoretical techniques.