| 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:
-
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?
-
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?
-
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?
-
Optimization Goals
- Minimize number of sheets?
- Minimize number of cuts?
- Minimize cutting time?
- Maximize material utilization?
- Balance multiple objectives?
-
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
self.is_cut = False
self.cut_position = None
self.cut_horizontal = None
self.left_child = None
self.right_child = None
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
"""
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
-
Equipment Compatibility
- Most cutting equipment naturally makes guillotine cuts
- Panel saws, guillotine shears work this way
- Simpler toolpath programming
-
Operational Simplicity
- Easier to execute
- Fewer setup changes
- Faster cutting process
-
Safety
- Straight cuts safer than complex paths
- Easier material handling
- Better piece stability
Disadvantages of Guillotine Constraint
-
Utilization Loss
- Typically 5-10% lower utilization vs. non-guillotine
- More waste due to constraint
-
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
- Must all cuts be guillotine?
- What cutting equipment is used?
- Two-stage or three-stage acceptable?
- Item dimensions and quantities?
- Can items rotate?
- 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
