Network flows and non-guillotine cutting patterns

DOI10.1016/0377-2217(84)90075-4MaRDI QIDQ795062zbMATH OpenOpenAlexWikidataFDO

Authors Milós Biró, Endre Boros

Publication date 1984

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(84)90075-4

zbMATH Keywords

cutting patternsnetwork flowsplanar graphs

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Graph theory (05C99) Applications of graph theory to circuits and networks (94C15)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 3174052
• Flows on networks: recent results and perspectives
• On continuous network flows
• scientific article; zbMATH DE number 42283
• Flows on networks and complicated domains
• Some Recent Advances in Network Flows
• Network flow interdiction on planar graphs
• scientific article; zbMATH DE number 2101425
• scientific article; zbMATH DE number 4207199
• Exact cuts in networks

Cites work

• A algorithm for two-dimensional packing
• A comparative study of heuristics for a two-level routing-location problem
• A Note on the Two-Dimensional Rectangular Cutting-Stock Problem
• A Solution of the Rectangular Cutting-Stock Problem
• An Algorithm for Two-Dimensional Cutting Problems
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Efficient Planarity Testing
• Matching problems
• Multistage Cutting Stock Problems of Two and More Dimensions
• On packing squares with equal squares
• Orthogonal Packings in Two Dimensions
• Packing the maximum number of m n tiles in a large p q rectangle
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• Recursive Computational Procedure for Two-dimensional Stock Cutting
• Scheduling subject to resource constraints: Classification and complexity
• Solving Resource-Constrained Network Problems by Implicit Enumeration—Nonpreemptive Case
• The dissection of rectangles into squares
• The trim-loss and assortment problems: A survey

Cited in

(6)

• Practical adaptations of the Gilmore-Gomory approach to cutting stock problems
• An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems
• Packing problems
• An exact algorithm for general, orthogonal, two-dimensional knapsack problems
• A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem
• Characterization and modelling of guillotine constraints

This page was built for publication: Network flows and non-guillotine cutting patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q795062)