guillotine-cutting

name

guillotine-cutting

description

When the user wants to solve cutting problems with guillotine constraints, implement edge-to-edge cutting, or optimize guillotine cutting patterns. Also use when the user mentions "guillotine cuts," "edge-to-edge cutting," "straight cuts only," "two-stage cutting," "three-stage cutting," "n-stage guillotine," or "guillotine cutting stock problem." For general cutting, see 2d-cutting-stock or 1d-cutting-stock. For irregular shapes, see nesting-optimization.

Guillotine Cutting

You are an expert in guillotine cutting optimization and constrained cutting patterns. Your goal is to help solve cutting problems where all cuts must be guillotine cuts (straight cuts that go from one edge to the opposite edge), which is common in many manufacturing processes using shears, guillotine cutters, saws, and panel saws.

Initial Assessment

Before solving guillotine cutting problems, understand:

1. Cutting Constraints

   • Must all cuts be guillotine? (edge-to-edge)
   • What stage structure? (two-stage, three-stage, unrestricted)
   • Can you mix horizontal and vertical cuts?
   • Any preferred cut sequence?
   • Maximum number of stages allowed?

2. Equipment Characteristics

   • What cutting equipment? (guillotine shear, panel saw, CNC router)
   • Equipment bed size/capacity?
   • Can equipment rotate pieces?
   • Cut accuracy/tolerance?
   • Setup time per cut?

3. Material and Items

   • Sheet/stock dimensions?
   • Item dimensions (all rectangular in guillotine cutting)?
   • Item quantities needed?
   • Can items be rotated 90 degrees?
   • Material grain direction constraints?

4. Optimization Goals

   • Minimize number of sheets?
   • Minimize number of cuts?
   • Minimize cutting time?
   • Maximize material utilization?
   • Balance multiple objectives?

5. Practical Considerations

   • Minimum cut length?
   • Minimum piece size?
   • Kerf (saw blade width)?
   • Need to track cutting sequence?
   • Real-time vs. batch optimization?

---

Guillotine Cutting Framework

Understanding Guillotine Cuts

Definition: A guillotine cut is a straight cut that goes completely from one edge of a rectangle to the opposite edge, dividing it into two smaller rectangles.

Properties:

• Cut must be parallel to one of the sides
• Cut extends fully across the material
• Creates two rectangular sub-pieces
• No partial cuts or L-shaped cuts

Guillotine vs. Non-Guillotine:

Guillotine Cut:                 Non-Guillotine:
┌────────────┐                 ┌────────────┐
│            │                 │ ┌──┐       │
│            │                 │ │  │       │
├────────────┤ ✓               │ └──┘   ┌──┤ ✗
│            │                 │        │  │
│            │                 │        └──┘
└────────────┘                 └────────────┘

Problem Classification

1. Two-Stage Guillotine Cutting

• Stage 1: Cut sheet into strips (horizontal OR vertical)
• Stage 2: Cut strips into items (perpendicular to stage 1)
• Most restrictive but simplest
• Common in industrial panel saws

2. Three-Stage Guillotine Cutting

• Stage 1: Cut sheet into sections
• Stage 2: Cut sections into strips
• Stage 3: Cut strips into items
• More flexible than two-stage
• Can achieve better utilization

3. N-Stage Guillotine Cutting

• Arbitrary number of stages
• Each cut subdivides a rectangle
• Recursive structure
• Tree representation of cuts

4. Unrestricted Guillotine Cutting

• No stage limit
• All cuts must be guillotine
• Most flexible guillotine variant
• Harder to optimize

5. Exact Guillotine Cutting

• No trim waste allowed
• Items must exactly fill rectangles
• Very restrictive
• Rare in practice

---

Mathematical Formulation

Two-Stage Guillotine Problem

Given:

• W × H = sheet dimensions
• Items: {(w₁, h₁, d₁), (w₂, h₂, d₂), ..., (wₙ, hₙ, dₙ)}
  • wᵢ, hᵢ = item dimensions
  • dᵢ = demand quantity

Decision Variables:

• Strip patterns for stage 1
• Item patterns within strips for stage 2
• Number of times each pattern is used

Stage 1 (Strips): For horizontal strips:

• Strip height h
• Number of strips with this height
• Constraint: Σ(heights) ≤ H

Stage 2 (Items in strips): For each strip:

• Items that fit in strip height
• 1D cutting stock problem in strip width
• Constraint: Σ(widths) ≤ W

Objective: Minimize number of sheets used

Complexity:

• Still NP-hard but more tractable than general 2D cutting
• Stage restriction reduces solution space
• Can use 1D algorithms for strip packing

---

Algorithms and Solution Methods

Method 1: Two-Stage Guillotine with Dynamic Programming

import numpy as np
from typing import List, Tuple, Dict

class TwoStageGuillotine:
    """
    Two-Stage Guillotine Cutting Solver

    Stage 1: Cut sheet into horizontal strips
    Stage 2: Cut strips into items using 1D algorithm

    This is practical and widely used in industry
    """

    def __init__(self, sheet_width, sheet_height, kerf=0):
        """
        Initialize solver

        Parameters:
        - sheet_width: sheet width
        - sheet_height: sheet height
        - kerf: saw kerf (material lost per cut)
        """
        self.sheet_width = sheet_width
        self.sheet_height = sheet_height
        self.kerf = kerf
        self.items = []

    def add_item(self, width, height, quantity, item_id=None):
        """Add rectangular item"""
        if item_id is None:
            item_id = f"Item_{len(self.items)}"

        self.items.append({
            'id': item_id,
            'width': width,
            'height': height,
            'quantity': quantity,
            'area': width * height
        })

    def generate_strip_types(self):
        """
        Generate all feasible strip types

        A strip type is defined by its height
        """

        
        unique_heights = ()

         item  .items:
            
            unique_heights.add(item[])
            unique_heights.add(item[])

        
        strip_types = [h  h  unique_heights  h <= .sheet_height]

         (strip_types)

     ():
        

        
        eligible_items = []

         item  .items:
            
             item[] <= strip_height:
                eligible_items.append({
                    : item[],
                    : item[],
                    : item[],
                    : item[],
                    : 
                })

             item[] <= strip_height  item[] != item[]:
                eligible_items.append({
                    : item[] + ,
                    : item[],
                    : item[],
                    : item[],
                    : 
                })

          eligible_items:
             []

        
        patterns = ._generate_1d_patterns_dp(eligible_items, strip_width)

         patterns

     ():
        

        patterns = []

        
         item  items:
            max_fit = (width / (item[] + .kerf))
             max_fit > :
                pattern = {
                    : {item[]: max_fit},
                    : width - (max_fit * item[] + (max_fit - ) * .kerf)
                }
                patterns.append(pattern)

        
         i, item1  (items):
             item2  items[i:]:
                
                 n1  ((width / (item1[] + .kerf)) + ):
                    remaining = width - (n1 * item1[] + (, n1-) * .kerf)
                    n2 = (remaining / (item2[] + .kerf))

                     n1 + n2 > :
                        pattern = {
                            : {},
                            : 
                        }

                         n1 > :
                            pattern[][item1[]] = n1

                         n2 > :
                            pattern[][item2[]] = n2

                        used = (n1 * item1[] + n2 * item2[] +
                               (n1 + n2 - ) * .kerf)
                        pattern[] = width - used

                         pattern   patterns:
                            patterns.append(pattern)

         patterns

     ():
        

         pulp  *

        
        prob = LpProblem(, LpMinimize)

        
        strip_vars = {}
         strip_height  strip_types:
             pattern_idx, pattern  (strip_patterns[strip_height]):
                var_name = 
                strip_vars[(strip_height, pattern_idx)] = LpVariable(
                    var_name, lowBound=, cat=
                )

        
        
        prob += lpSum(
            strip_vars[(h, p)] * h / .sheet_height
             h  strip_types
             p  ((strip_patterns[h]))
        )

        
         item  .items:
            item_id = item[]

            
            prob += lpSum(
                strip_vars[(h, p)] * pattern[].get(item_id, ) +
                strip_vars[(h, p)] * pattern[].get(item_id + , )
                 h  strip_types
                 p, pattern  (strip_patterns[h])
            ) >= item[], 

        
        prob.solve(PULP_CBC_CMD(msg=))

        
        solution = {
            : LpStatus[prob.status],
            : {}
        }

         (h, p), var  strip_vars.items():
             var.varValue  var.varValue > :
                 h   solution[]:
                    solution[][h] = []

                solution[][h].append({
                    : p,
                    : strip_patterns[h][p],
                    : (var.varValue)
                })

         solution

     ():
        

        
        strips_to_pack = []

         strip_height, patterns  strip_usage.items():
             pattern_info  patterns:
                 _  (pattern_info[]):
                    strips_to_pack.append({
                        : strip_height,
                        : pattern_info[]
                    })

        
        strips_to_pack.sort(key= s: s[], reverse=)

        
        sheets = []

         strip  strips_to_pack:
            placed = 

            
             sheet  sheets:
                 sheet[] >= strip[]:
                    sheet[].append(strip)
                    sheet[] -= strip[]
                    placed = 
                    

            
              placed:
                sheets.append({
                    : [strip],
                    : .sheet_height - strip[]
                })

        
         sheet  sheets:
            used_area = 
             strip  sheet[]:
                
                strip_used = 
                 item_id, count  strip[][].items():
                    
                    
                    strip_used += count *   

                used_area += strip_used * strip[]

            sheet[] = (used_area / (.sheet_width * .sheet_height) * )

         sheets

     ():
        

        ()

        
        strip_types = .generate_strip_types()
        ()

        
        strip_patterns = {}

         strip_height  strip_types:
            patterns = .solve_1d_cutting_for_strip(strip_height, .sheet_width)
            strip_patterns[strip_height] = patterns
            ()

        
        master_solution = .solve_master_problem(strip_types, strip_patterns)

         master_solution[] != :
            ()

        
        sheets = .pack_strips_into_sheets(master_solution[])

        ()

         {
            : (sheets),
            : sheets,
            : strip_patterns,
            : master_solution[]
        }



 ():
    

    solver = TwoStageGuillotine(
        sheet_width=,
        sheet_height=,
        kerf=
    )

    
    solver.add_item(, , , )
    solver.add_item(, , , )
    solver.add_item(, , , )
    solver.add_item(, , , )

    
    solution = solver.solve()

    ()

     solution

Method 2: Recursive Guillotine Partitioning

class RecursiveGuillotinePartitioning:
    """
    Recursive Guillotine Partitioning

    Recursively subdivides rectangle with guillotine cuts
    Can represent any guillotine cutting pattern

    Uses tree structure to represent cutting plan
    """

    def __init__(self, width, height):
        """
        Initialize with rectangle dimensions

        Parameters:
        - width: rectangle width
        - height: rectangle height
        """
        self.width = width
        self.height = height
        self.root = None

    class CutNode:
        """Node in guillotine cut tree"""

        def __init__(self, x, y, width, height):
            self.x = x
            self.y = y
            self.width = width
            self.height = height

            # Cut information
            self.is_cut = False
            self.cut_position = None
            self.cut_horizontal = None  # True=horizontal, False=vertical

            # Children (if cut)
            self.left_child = None   # or bottom child
            self.right_child = None  # or top child

            # Item assignment (if leaf)
            self.item = None

     ():
        

         node.is_cut:
             ValueError()

        node.is_cut = 
        node.cut_position = position
        node.cut_horizontal = horizontal

         horizontal:
            
            node.left_child = .CutNode(
                node.x, node.y,
                node.width, position
            )

            node.right_child = .CutNode(
                node.x, node.y + position,
                node.width, node.height - position
            )

        :
            
            node.left_child = .CutNode(
                node.x, node.y,
                position, node.height
            )

            node.right_child = .CutNode(
                node.x + position, node.y,
                node.width - position, node.height
            )

         node.left_child, node.right_child

     ():
        

         node.is_cut:
             ValueError()

         item_width > node.width  item_height > node.height:
             ValueError()

        node.item = {
            : item_id,
            : item_width,
            : item_height,
            : node.width - item_width,
            : node.height - item_height
        }

     ():
        

         node  :
            node = .root

          node.is_cut:
             []

        cuts = []

        
        cuts.append({
            : (node.x, node.y),
            : (node.width, node.height),
            : node.cut_position,
            : node.cut_horizontal,
            : (
                (node.x, node.y + node.cut_position,
                 node.x + node.width, node.y + node.cut_position)
                 node.cut_horizontal 
                (node.x + node.cut_position, node.y,
                 node.x + node.cut_position, node.y + node.height)
            )
        })

        
         node.left_child:
            cuts.extend(.generate_cutting_sequence(node.left_child))

         node.right_child:
            cuts.extend(.generate_cutting_sequence(node.right_child))

         cuts

     ():
        

         matplotlib.pyplot  plt
         matplotlib.patches  patches

        fig, ax = plt.subplots(figsize=(, ))

        
        ax.add_patch(patches.Rectangle(
            (, ), .width, .height,
            fill=, edgecolor=, linewidth=
        ))

        
        cuts = .generate_cutting_sequence()

         idx, cut  (cuts):
            x1, y1, x2, y2 = cut[]
            color =   cut[]  
            ax.plot([x1, x2], [y1, y2],
                   color=color, linewidth=, alpha=)

            
            mid_x = (x1 + x2) / 
            mid_y = (y1 + y2) / 
            ax.text(mid_x, mid_y, ,
                   fontsize=, fontweight=,
                   bbox=(boxstyle=, facecolor=))

        
        items = ._collect_items(.root)

        colors = plt.cm.tab10(np.linspace(, , ))

         idx, item_info  (items):
            node = item_info[]
            item = item_info[]

            color = colors[idx % ]

            ax.add_patch(patches.Rectangle(
                (node.x, node.y),
                item[], item[],
                facecolor=color, edgecolor=,
                linewidth=, alpha=
            ))

            
            cx = node.x + item[] / 
            cy = node.y + item[] / 
            ax.text(cx, cy, item[],
                   ha=, va=,
                   fontsize=, fontweight=)

        ax.set_xlim(-, .width + )
        ax.set_ylim(-, .height + )
        ax.set_aspect()
        ax.set_xlabel(, fontsize=)
        ax.set_ylabel(, fontsize=)
        ax.set_title(
                    ,
                    fontsize=, fontweight=)
        ax.grid(, alpha=)

        
        ax.text(, , ,
               transform=ax.transAxes,
               verticalalignment=,
               bbox=(boxstyle=, facecolor=, alpha=))

        plt.tight_layout()

         save_path:
            plt.savefig(save_path, dpi=, bbox_inches=)

        plt.show()

     ():
        

         node  :
             []

         node.item:
             [{: node, : node.item}]

        items = []

         node.left_child:
            items.extend(._collect_items(node.left_child))

         node.right_child:
            items.extend(._collect_items(node.right_child))

         items



 ():
    

    
    gp = RecursiveGuillotinePartitioning(, )

    
    gp.root = gp.CutNode(, , , )

    
    bottom, top = gp.make_cut(gp.root, , horizontal=)

    
    left1, right1 = gp.make_cut(bottom, , horizontal=)

    
    left2, right2 = gp.make_cut(top, , horizontal=)

    
    gp.assign_item(left1, , , )
    gp.assign_item(right1, , , )
    gp.assign_item(left2, , , )
    gp.assign_item(right2, , , )

    
    cuts = gp.generate_cutting_sequence()

    ()
     idx, cut  (cuts):
        direction =   cut[]  
        ()

    
    gp.visualize_cut_tree()

     gp

Method 3: Three-Stage Guillotine Algorithm

class ThreeStageGuillotine:
    """
    Three-Stage Guillotine Cutting

    More flexible than two-stage

    Stage 1: Cut sheet into large sections
    Stage 2: Cut sections into strips
    Stage 3: Cut strips into items
    """

    def __init__(self, sheet_width, sheet_height):
        self.sheet_width = sheet_width
        self.sheet_height = sheet_height
        self.items = []

    def add_item(self, width, height, quantity, item_id=None):
        """Add item"""
        if item_id is None:
            item_id = f"Item_{len(self.items)}"

        self.items.append({
            'id': item_id,
            'width': width,
            'height': height,
            'quantity': quantity
        })

    def solve(self):
        """
        Solve three-stage problem

        This is more complex - simplified implementation
        """

        # Stage 1: Decide on section cuts
        # Stage 2: For each section, decide on strip cuts
        # Stage 3: For each strip, pack items

        # This requires sophisticated algorithm
        # Typically uses dynamic programming or column generation

        # Placeholder for full implementation
        pass

---

Guillotine Cutting Algorithms Comparison

Algorithm Comparison

Algorithm	Optimality	Speed	Complexity	Best For
Two-Stage DP	Good	Fast	Medium	Standard manufacturing
Three-Stage	Better	Medium	High	Complex item mixes
Recursive Tree	Flexible	Slow	High	Custom requirements
Column Generation	Best	Slow	Very High	High-value materials

---

Practical Considerations

Advantages of Guillotine Cuts

1. Equipment Compatibility

   • Most cutting equipment naturally makes guillotine cuts
   • Panel saws, guillotine shears work this way
   • Simpler toolpath programming

2. Operational Simplicity

   • Easier to execute
   • Fewer setup changes
   • Faster cutting process

3. Safety

   • Straight cuts safer than complex paths
   • Easier material handling
   • Better piece stability

Disadvantages of Guillotine Constraint

1. Utilization Loss

   • Typically 5-10% lower utilization vs. non-guillotine
   • More waste due to constraint

2. Limited Flexibility

   • Cannot always achieve optimal packing
   • Some item combinations pack poorly

---

Tools & Libraries

Software

• CutList Optimizer: Guillotine cutting focus
• OptiCut: Supports guillotine constraints
• Cutting Optimization Pro: Guillotine modes

---

Questions to Ask

1. Must all cuts be guillotine?
2. What cutting equipment is used?
3. Two-stage or three-stage acceptable?
4. Item dimensions and quantities?
5. Can items rotate?
6. Material cost and waste impact?

---

Related Skills

• 2d-cutting-stock: For general 2D cutting
• 1d-cutting-stock: For 1D cutting in strips
• trim-loss-minimization: For waste reduction
• nesting-optimization: For non-rectangular shapes