guillotine-cutting

闸切

你是闸切优化和受限切割模式方面的专家。你的目标是帮助解决切割问题：所有切割都必须是闸切（从一条边直线切到对边），这在使用剪切机、闸式切割机、锯和板材锯的许多制造工艺中很常见。

初步评估

解决闸切问题之前，请先了解：

1. 切割约束

   • 所有切割都必须是闸切吗？（从一边到另一边）
   • 阶段结构是什么？（两阶段、三阶段、不限）
   • 可以混合水平和垂直切割吗？
   • 是否有首选的切割顺序？
   • 允许的最大阶段数是多少？

2. 设备特性

   • 使用什么切割设备？（闸式剪切机、板材锯、CNC 路由器）
   • 设备工作台尺寸／容量是多少？
   • 设备能否旋转工件？
   • 切割精度／公差是多少？
   • 每次切割的准备时间是多少？

3. 材料和物品

   • 板材／原料尺寸是多少？
   • 物品尺寸是多少（闸切中的物品都是矩形）？
   • 需要多少件物品？
   • 物品能否旋转 90 度？
   • 是否有材料纹理方向限制？

4. 优化目标

   • 尽量减少板材数量？
   • 尽量减少切割次数？
   • 尽量缩短切割时间？
   • 尽量提高材料利用率？
   • 平衡多个目标？

5. 实际考量

   • 最小切割长度是多少？
   • 最小工件尺寸是多少？
   • 锯缝（锯片宽度）是多少？
   • 是否需要跟踪切割顺序？
   • 需要实时优化还是批量优化？

---

闸切框架

了解闸切

定义： 闸切是指从矩形的一条边完全切到对边，将矩形分成两个较小矩形的直线切割。

特性：

• 切割必须平行于其中一条边
• 切割贯穿整个材料
• 形成两个矩形子块
• 不允许部分切割或 L 形切割

闸切与非闸切：

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

问题分类

1. 两阶段闸切

• **阶段 1：**将板材切成条带（水平或垂直）
• **阶段 2：**将条带切成物品（与阶段 1 垂直）
• 限制最多，但最简单
• 常见于工业板材锯

2. 三阶段闸切

• **阶段 1：**将板材切成区块
• **阶段 2：**将区块切成条带
• **阶段 3：**将条带切成物品
• 比两阶段更灵活
• 可实现更高的利用率

3. N 阶段闸切

• 阶段数不限
• 每次切割都会细分一个矩形
• 具有递归结构
• 可用树结构表示切割过程

4. 不限阶段的闸切

• 阶段数不限
• 所有切割都必须是闸切
• 灵活性最高的闸切变体
• 优化难度更高

5. 精确闸切

• 不允许修边废料
• 物品必须恰好填满矩形
• 限制非常严格
• 实际中很少见

---

数学建模

两阶段闸切问题

已知：

• W × H = 板材尺寸
• 物品：{(w₁, h₁, d₁), (w₂, h₂, d₂), ..., (wₙ, hₙ, dₙ)}
  • wᵢ、hᵢ = 物品尺寸
  • dᵢ = 需求数量

决策变量：

• 阶段 1 的条带模式
• 阶段 2 的条带内物品模式
• 每种模式的使用次数

阶段 1（条带）： 对于水平条带：

• 条带高度 h
• 此高度条带的数量
• 约束：Σ(高度) ≤ H

阶段 2（条带中的物品）： 对于每条条带：

• 能够放入条带高度的物品
• 在条带宽度内进行一维切割下料问题
• 约束：Σ(宽度) ≤ W

目标： 尽量减少所用板材数量

复杂度：

• 仍然是 NP-hard，但比一般二维切割问题更容易处理
• 阶段限制会缩小解空间
• 可使用一维算法进行条带装箱

---

算法和求解方法

方法 1：使用动态规划进行两阶段闸切

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
        """

        # Get unique heights from items
        unique_heights = set()

        for item in self.items:
            # Can use item in normal or rotated orientation
            unique_heights.add(item['height'])
            unique_heights.add(item['width'])

        # Filter heights that fit in sheet
        strip_types = [h for h in unique_heights if h <= self.sheet_height]

        return sorted(strip_types)

    def solve_1d_cutting_for_strip(self, strip_height, strip_width):
        """
        Solve 1D cutting stock for items that fit in a strip

        Returns best patterns for this strip type
        """

        # Get items that can fit in this strip height
        eligible_items = []

        for item in self.items:
            # Try both orientations
            if item['height'] <= strip_height:
                eligible_items.append({
                    'id': item['id'],
                    'length': item['width'],
                    'height': item['height'],
                    'quantity': item['quantity'],
                    'rotated': False
                })

            if item['width'] <= strip_height and item['width'] != item['height']:
                eligible_items.append({
                    'id': item['id'] + '_rot',
                    'length': item['height'],
                    'height': item['width'],
                    'quantity': item['quantity'],
                    'rotated': True
                })

        if not eligible_items:
            return []

        # Generate 1D patterns using dynamic programming
        patterns = self._generate_1d_patterns_dp(eligible_items, strip_width)

        return patterns

    def _generate_1d_patterns_dp(self, items, width):
        """
        Generate 1D cutting patterns using dynamic programming

        For each item type, find maximum number that fits
        """

        patterns = []

        # Simple patterns: one item type per pattern
        for item in items:
            max_fit = int(width / (item['length'] + self.kerf))
            if max_fit > 0:
                pattern = {
                    'items': {item['id']: max_fit},
                    'waste': width - (max_fit * item['length'] + (max_fit - 1) * self.kerf)
                }
                patterns.append(pattern)

        # Combined patterns: two item types
        for i, item1 in enumerate(items):
            for item2 in items[i:]:
                # Try different combinations
                for n1 in range(int(width / (item1['length'] + self.kerf)) + 1):
                    remaining = width - (n1 * item1['length'] + max(0, n1-1) * self.kerf)
                    n2 = int(remaining / (item2['length'] + self.kerf))

                    if n1 + n2 > 0:
                        pattern = {
                            'items': {},
                            'waste': 0
                        }

                        if n1 > 0:
                            pattern['items'][item1['id']] = n1

                        if n2 > 0:
                            pattern['items'][item2['id']] = n2

                        used = (n1 * item1['length'] + n2 * item2['length'] +
                               (n1 + n2 - 1) * self.kerf)
                        pattern['waste'] = width - used

                        if pattern not in patterns:
                            patterns.append(pattern)

        return patterns

    def solve_master_problem(self, strip_types, strip_patterns):
        """
        Solve master problem: select strips to pack into sheets

        This is simplified - full implementation uses integer programming
        """

        from pulp import *

        # Create problem
        prob = LpProblem("Two_Stage_Guillotine", LpMinimize)

        # Variables: number of each strip type pattern to use
        strip_vars = {}
        for strip_height in strip_types:
            for pattern_idx, pattern in enumerate(strip_patterns[strip_height]):
                var_name = f"strip_h{strip_height}_p{pattern_idx}"
                strip_vars[(strip_height, pattern_idx)] = LpVariable(
                    var_name, lowBound=0, cat='Integer'
                )

        # Objective: minimize number of sheets
        # Approximate: sum of strip heights / sheet height
        prob += lpSum(
            strip_vars[(h, p)] * h / self.sheet_height
            for h in strip_types
            for p in range(len(strip_patterns[h]))
        )

        # Demand constraints
        for item in self.items:
            item_id = item['id']

            # Sum across all strips and patterns
            prob += lpSum(
                strip_vars[(h, p)] * pattern['items'].get(item_id, 0) +
                strip_vars[(h, p)] * pattern['items'].get(item_id + '_rot', 0)
                for h in strip_types
                for p, pattern in enumerate(strip_patterns[h])
            ) >= item['quantity'], f"Demand_{item_id}"

        # Solve
        prob.solve(PULP_CBC_CMD(msg=0))

        # Extract solution
        solution = {
            'status': LpStatus[prob.status],
            'strip_usage': {}
        }

        for (h, p), var in strip_vars.items():
            if var.varValue and var.varValue > 0.5:
                if h not in solution['strip_usage']:
                    solution['strip_usage'][h] = []

                solution['strip_usage'][h].append({
                    'pattern_index': p,
                    'pattern': strip_patterns[h][p],
                    'quantity': int(var.varValue)
                })

        return solution

    def pack_strips_into_sheets(self, strip_usage):
        """
        Pack strips into sheets using FFD height

        Returns list of sheets with their strips
        """

        # Expand strips
        strips_to_pack = []

        for strip_height, patterns in strip_usage.items():
            for pattern_info in patterns:
                for _ in range(pattern_info['quantity']):
                    strips_to_pack.append({
                        'height': strip_height,
                        'pattern': pattern_info['pattern']
                    })

        # Sort by decreasing height
        strips_to_pack.sort(key=lambda s: s['height'], reverse=True)

        # Pack into sheets (FFD)
        sheets = []

        for strip in strips_to_pack:
            placed = False

            # Try existing sheets
            for sheet in sheets:
                if sheet['remaining_height'] >= strip['height']:
                    sheet['strips'].append(strip)
                    sheet['remaining_height'] -= strip['height']
                    placed = True
                    break

            # Need new sheet
            if not placed:
                sheets.append({
                    'strips': [strip],
                    'remaining_height': self.sheet_height - strip['height']
                })

        # Calculate utilization
        for sheet in sheets:
            used_area = 0
            for strip in sheet['strips']:
                # Calculate items in strip
                strip_used = 0
                for item_id, count in strip['pattern']['items'].items():
                    # Get item dimensions (need to look up)
                    # Simplified here
                    strip_used += count * 100  # Placeholder

                used_area += strip_used * strip['height']

            sheet['utilization'] = (used_area / (self.sheet_width * self.sheet_height) * 100)

        return sheets

    def solve(self):
        """
        Solve two-stage guillotine cutting problem

        Returns: cutting plan with sheets and patterns
        """

        print("Solving Two-Stage Guillotine Cutting...")

        # Step 1: Generate strip types
        strip_types = self.generate_strip_types()
        print(f"Strip types: {len(strip_types)}")

        # Step 2: For each strip type, generate 1D patterns
        strip_patterns = {}

        for strip_height in strip_types:
            patterns = self.solve_1d_cutting_for_strip(strip_height, self.sheet_width)
            strip_patterns[strip_height] = patterns
            print(f"Strip height {strip_height}: {len(patterns)} patterns")

        # Step 3: Solve master problem
        master_solution = self.solve_master_problem(strip_types, strip_patterns)

        if master_solution['status'] != 'Optimal':
            print(f"Warning: Status = {master_solution['status']}")

        # Step 4: Pack strips into sheets
        sheets = self.pack_strips_into_sheets(master_solution['strip_usage'])

        print(f"\nSolution: {len(sheets)} sheets needed")

        return {
            'num_sheets': len(sheets),
            'sheets': sheets,
            'strip_patterns': strip_patterns,
            'status': master_solution['status']
        }


# Example usage
def example_two_stage_guillotine():
    """Example: Two-stage guillotine cutting"""

    solver = TwoStageGuillotine(
        sheet_width=2440,
        sheet_height=1220,
        kerf=3
    )

    # Add items
    solver.add_item(800, 600, 12, 'A')
    solver.add_item(1000, 500, 10, 'B')
    solver.add_item(600, 400, 15, 'C')
    solver.add_item(1200, 300, 8, 'D')

    # Solve
    solution = solver.solve()

    print(f"\nSheets: {solution['num_sheets']}")

    return solution

方法 2：递归闸切分割

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

    def make_cut(self, node, position, horizontal=True):
        """
        Make guillotine cut at node

        Parameters:
        - node: CutNode to cut
        - position: cut position (relative to node origin)
        - horizontal: True for horizontal cut, False for vertical

        Returns: (left/bottom child, right/top child)
        """

        if node.is_cut:
            raise ValueError("Node already cut")

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

        if horizontal:
            # Horizontal cut: divide into bottom and top
            node.left_child = self.CutNode(
                node.x, node.y,
                node.width, position
            )

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

        else:
            # Vertical cut: divide into left and right
            node.left_child = self.CutNode(
                node.x, node.y,
                position, node.height
            )

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

        return node.left_child, node.right_child

    def assign_item(self, node, item_id, item_width, item_height):
        """
        Assign item to a leaf node

        Parameters:
        - node: leaf node
        - item_id: item identifier
        - item_width, item_height: item dimensions
        """

        if node.is_cut:
            raise ValueError("Cannot assign item to cut node")

        if item_width > node.width or item_height > node.height:
            raise ValueError("Item doesn't fit in node")

        node.item = {
            'id': item_id,
            'width': item_width,
            'height': item_height,
            'waste_width': node.width - item_width,
            'waste_height': node.height - item_height
        }

    def generate_cutting_sequence(self, node=None):
        """
        Generate cutting sequence from tree

        Returns list of cuts in execution order (depth-first)
        """

        if node is None:
            node = self.root

        if not node.is_cut:
            return []

        cuts = []

        # Add this cut
        cuts.append({
            'position': (node.x, node.y),
            'size': (node.width, node.height),
            'cut_position': node.cut_position,
            'horizontal': node.cut_horizontal,
            'cut_line': (
                (node.x, node.y + node.cut_position,
                 node.x + node.width, node.y + node.cut_position)
                if node.cut_horizontal else
                (node.x + node.cut_position, node.y,
                 node.x + node.cut_position, node.y + node.height)
            )
        })

        # Recursively add children cuts
        if node.left_child:
            cuts.extend(self.generate_cutting_sequence(node.left_child))

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

        return cuts

    def visualize_cut_tree(self, save_path=None):
        """
        Visualize guillotine cut pattern

        Shows all cuts and items
        """

        import matplotlib.pyplot as plt
        import matplotlib.patches as patches

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

        # Draw sheet boundary
        ax.add_patch(patches.Rectangle(
            (0, 0), self.width, self.height,
            fill=False, edgecolor='black', linewidth=3
        ))

        # Draw all cuts
        cuts = self.generate_cutting_sequence()

        for idx, cut in enumerate(cuts):
            x1, y1, x2, y2 = cut['cut_line']
            color = 'red' if cut['horizontal'] else 'blue'
            ax.plot([x1, x2], [y1, y2],
                   color=color, linewidth=2, alpha=0.7)

            # Label cut
            mid_x = (x1 + x2) / 2
            mid_y = (y1 + y2) / 2
            ax.text(mid_x, mid_y, f"{idx+1}",
                   fontsize=10, fontweight='bold',
                   bbox=dict(boxstyle='circle', facecolor='white'))

        # Draw items
        items = self._collect_items(self.root)

        colors = plt.cm.tab10(np.linspace(0, 1, 10))

        for idx, item_info in enumerate(items):
            node = item_info['node']
            item = item_info['item']

            color = colors[idx % 10]

            ax.add_patch(patches.Rectangle(
                (node.x, node.y),
                item['width'], item['height'],
                facecolor=color, edgecolor='black',
                linewidth=1.5, alpha=0.5
            ))

            # Label item
            cx = node.x + item['width'] / 2
            cy = node.y + item['height'] / 2
            ax.text(cx, cy, item['id'],
                   ha='center', va='center',
                   fontsize=11, fontweight='bold')

        ax.set_xlim(-50, self.width + 50)
        ax.set_ylim(-50, self.height + 50)
        ax.set_aspect('equal')
        ax.set_xlabel('Width', fontsize=12)
        ax.set_ylabel('Height', fontsize=12)
        ax.set_title('Guillotine Cutting Pattern\n'
                    'Red=Horizontal cuts, Blue=Vertical cuts',
                    fontsize=14, fontweight='bold')
        ax.grid(True, alpha=0.3)

        # Legend
        ax.text(0.02, 0.98, f"Total cuts: {len(cuts)}",
               transform=ax.transAxes,
               verticalalignment='top',
               bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.5))

        plt.tight_layout()

        if save_path:
            plt.savefig(save_path, dpi=300, bbox_inches='tight')

        plt.show()

    def _collect_items(self, node):
        """Collect all items from tree"""

        if node is None:
            return []

        if node.item:
            return [{'node': node, 'item': node.item}]

        items = []

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

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

        return items


# Example usage
def example_recursive_guillotine():
    """Example: Build guillotine cut tree"""

    # Create partitioner for 2400x1200 sheet
    gp = RecursiveGuillotinePartitioning(2400, 1200)

    # Create root node
    gp.root = gp.CutNode(0, 0, 2400, 1200)

    # Make first horizontal cut at 600
    bottom, top = gp.make_cut(gp.root, 600, horizontal=True)

    # Cut bottom into two vertical sections
    left1, right1 = gp.make_cut(bottom, 1200, horizontal=False)

    # Cut top into two vertical sections
    left2, right2 = gp.make_cut(top, 800, horizontal=False)

    # Assign items to leaves
    gp.assign_item(left1, 'A', 1200, 600)
    gp.assign_item(right1, 'B', 1200, 600)
    gp.assign_item(left2, 'C', 800, 600)
    gp.assign_item(right2, 'D', 1600, 600)

    # Get cutting sequence
    cuts = gp.generate_cutting_sequence()

    print("Cutting Sequence:")
    for idx, cut in enumerate(cuts):
        direction = "Horizontal" if cut['horizontal'] else "Vertical"
        print(f"Cut {idx+1}: {direction} at position {cut['cut_position']}")

    # Visualize
    gp.visualize_cut_tree()

    return gp

方法 3：三阶段闸切算法

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

---

断头台切割算法比较

算法比较

算法	最优性	速度	复杂度	最适用场景
两阶段 DP	良好	快	中等	标准制造
三阶段	更好	中等	高	复杂的工件组合
递归树	灵活	慢	高	定制需求
列生成	最佳	慢	很高	高价值材料

---

实际考量

断头台切割的优点

1. 设备兼容性

   • 大多数切割设备都能自然地进行断头台切割
   • 板锯、断头台剪切机都采用这种方式
   • 刀具路径编程更简单

2. 操作简便

   • 更容易执行
   • 需要更少的设置变更
   • 切割过程更快

3. 安全性

   • 直线切割比复杂路径更安全
   • 材料更易于处理
   • 工件稳定性更好

断头台约束的缺点

1. 利用率损失

   • 与非断头台切割相比，利用率通常低 5-10%
   • 受约束影响，浪费更多

2. 灵活性有限

   • 并非总能实现最佳排样
   • 某些工件组合的排样效果不佳

---

工具和库

软件

• CutList Optimizer：专注于断头台切割
• OptiCut：支持断头台约束
• Cutting Optimization Pro：提供断头台模式

---

需要了解的问题

1. 是否所有切割都必须采用断头台切割？
2. 使用什么切割设备？
3. 是否接受两阶段或三阶段切割？
4. 工件尺寸和数量是多少？
5. 工件是否可以旋转？
6. 材料成本和废料会产生什么影响？

---

相关技能

• 2d-cutting-stock：用于通用 2D 切割
• 1d-cutting-stock：用于条料的 1D 切割
• trim-loss-minimization：用于减少浪费
• nesting-optimization：用于非矩形形状的排样