PCB拼板算法详解

一、算法概述

本系统采用 Nest算法（二维矩形装箱算法） 作为核心算法，结合 启发式算法 和 贪心算法，实现PCB拼板的自动化优化计算。

核心目标

在给定大料尺寸约束下，最大化PCB产出数量
满足Panel尺寸范围限制（300×300 \~ 600×600 mm）
提高大料利用率（目标≥60%）

二、算法流程

2.1 整体流程图

┌─────────────────────────────────────────────────────────────┐
│                     输入参数                                 │
│  PCB尺寸、大料尺寸、拼板间距、工艺边、Panel尺寸范围            │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Step 1: 生成所有可能的Panel配置                            │
│  - 遍历所有可能的行列组合                                   │
│  - 计算Panel尺寸并验证范围约束                              │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Step 2: 单一Panel方案计算                                  │
│  - 计算每个Panel在大料上的最大排版数量                       │
│  - 支持旋转优化（90°旋转）                                  │
│  - 计算利用率并过滤（≥60%）                                 │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Step 3: 多Panel组合方案计算                                │
│  - 2A+2B布局模式                                           │
│  - A+B布局模式                                             │
│  - 计算组合利用率并过滤                                     │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│  Step 4: 方案排序与去重                                    │
│  - 按利用率降序排序                                         │
│  - 利用率相同时按总PCB数降序                                │
│  - 去除重复方案                                            │
└───────────────────────┬─────────────────────────────────────┘
                        │
                        ▼
┌─────────────────────────────────────────────────────────────┐
│                     输出结果                                 │
│  最多8个优化方案，按利用率排序                               │
└─────────────────────────────────────────────────────────────┘

三、核心算法详解

3.1 Panel配置生成算法

3.1.1 尺寸计算公式

snippet.python

# Panel宽度 = 横向PCB数 × PCB宽度 + (横向PCB数-1) × 间距 + 2 × 工艺边
panel_width = cols * pcb_w + (cols - 1) * gap + 2 * border
 
# Panel高度 = 纵向PCB数 × PCB高度 + (纵向PCB数-1) × 间距 + 2 × 工艺边  
panel_height = rows * pcb_h + (rows - 1) * gap + 2 * border
 
# Panel内PCB数量
pcb_count = cols * rows

3.1.2 约束条件验证

snippet.python

# Panel尺寸范围约束
valid_size = False
 
# 原始方向
if (panel_min_w <= panel_w <= panel_max_w) and (panel_min_h <= panel_h <= panel_max_h):
    valid_size = True
# 旋转方向
elif (panel_min_w <= panel_h <= panel_max_w) and (panel_min_h <= panel_w <= panel_max_h):
    valid_size = True
 
# 大料尺寸约束
if (panel.width <= material_w and panel.height <= material_h) or \
   (panel.height <= material_w and panel.width <= material_h):
    # Panel可以放入大料（考虑旋转）

3.1.3 算法复杂度

维度	复杂度	说明
—–	————————	————-
时间复杂度	O(max_cols × max_rows)	遍历所有可能的行列组合
空间复杂度	O(max_cols × max_rows)	存储所有有效Panel配置

3.2 利用率计算算法

3.2.1 计算公式

snippet.python

# 利用率 = (总PCB面积 / 大料面积) × 100%
# 总PCB面积 = 总PCB数量 × 单个PCB面积
# 大料面积 = 大料宽度 × 大料高度
 
def calculate_utilization(total_pcb_count, pcb_w, pcb_h, material_w, material_h):
    total_pcb_area = total_pcb_count * pcb_w * pcb_h
    material_area = material_w * material_h
    return (total_pcb_area / material_area) * 100

3.2.2 计算示例

以案例参数为例：

PCB尺寸：130×250 mm
大料尺寸：1041×1245 mm
总PCB数：36个

总PCB面积 = 36 × 130 × 250 = 1,170,000 mm²
大料面积 = 1041 × 1245 = 1,296,045 mm²
利用率 = (1,170,000 / 1,296,045) × 100% ≈ 90.27%

3.3 单一Panel排版算法

3.3.1 计算逻辑

snippet.python

# 计算横向可放置数量
cols_in_material_w = material_w // panel.width
 
# 计算纵向可放置数量  
rows_in_material_h = material_h // panel.height
 
# 总拼板数
total_count = cols_in_material_w * rows_in_material_h
 
# 总PCB数
total_pcb = total_count * panel.pcb_count

3.3.2 旋转优化

snippet.python

# 旋转90°后重新计算
cols_in_material_w_rot = material_w // panel.height
rows_in_material_h_rot = material_h // panel.width
total_count_rot = cols_in_material_w_rot * rows_in_material_h_rot

3.3.3 启发式策略

首次适应（First Fit）：优先尝试原始方向
旋转优化（Rotation）：尝试90°旋转以找到更优布局

3.4 多Panel组合算法

3.4.1 2A+2B布局模式

布局示意图：
┌─────────┬─────────┐
│   A     │   B     │
│  Panel  │  Panel  │
├─────────┼─────────┤
│   A     │   B     │
│  Panel  │  Panel  │
└─────────┴─────────┘

布局尺寸计算：
layout_w = panel_a.width + panel_b.width
layout_h = panel_a.height + panel_b.height

总PCB数：2 × panel_a.pcb_count + 2 × panel_b.pcb_count

3.4.2 A+B布局模式

布局示意图：
┌─────────┐
│   A     │
│  Panel  │
├─────────┤
│   B     │
│  Panel  │
└─────────┘

布局尺寸计算：
layout_w = max(panel_a.width, panel_b.width)
layout_h = panel_a.height + panel_b.height

总PCB数：panel_a.pcb_count + panel_b.pcb_count

3.4.3 组合约束条件

snippet.python

# 过滤条件1：Panel尺寸范围
(panel_min_w <= panel.width <= panel_max_w) 
and (panel_min_h <= panel.height <= panel_max_h)
 
# 过滤条件2：最大拼板数限制
total_count <= max_panel_count
 
# 过滤条件3：最小利用率限制  
utilization >= min_utilization

3.5 方案排序算法

3.5.1 排序规则

snippet.python

# 排序优先级（从高到低）：
# 1. 利用率（降序）
# 2. 总PCB数（降序）
 
results.sort(key=lambda x: (-x['utilization'], -x['total_pcb']))

3.5.2 去重策略

snippet.python

# 基于Panel尺寸和数量去重
unique_results = []
seen = set()
 
for result in results:
    if result['type'] == 'single':
        key = (result['panel_w'], result['panel_h'], result['count'])
    else:
        key = tuple((p['panel_w'], p['panel_h'], p['count']) for p in result['panels'])
 
    if key not in seen:
        seen.add(key)
        unique_results.append(result)

四、代码结构

4.1 核心类与函数

类/函数	功能说明	位置
——————————————	——————	———
`Panel`	Panel配置类，封装尺寸计算逻辑	第25-41行
`generate_panels()`	生成所有有效Panel配置	第44-95行
`calculate_utilization()`	计算大料利用率	第348-371行
`optimize_panel_layout_with_utilization()`	主优化函数，支持尺寸范围和利用率过滤	第374-550行
`print_utilization_result()`	结果输出函数	第745-817行

4.2 关键数据结构

snippet.python

# Panel配置
Panel = {
    'cols': 横向PCB数,
    'rows': 纵向PCB数,
    'width': Panel宽度,
    'height': Panel高度,
    'pcb_count': Panel内PCB数量
}
 
# 单一Panel方案
single_result = {
    'type': 'single',
    'cols': Panel横向数,
    'rows': Panel纵向数,
    'panel_w': Panel宽度,
    'panel_h': Panel高度,
    'pcb_count': 每Panel PCB数,
    'count': 大料出板数,
    'total_pcb': 总PCB数,
    'layout_w': 排版宽度,
    'layout_h': 排版高度,
    'utilization': 利用率(%),
    'rotation': 'normal' | 'rotated'
}
 
# 多Panel组合方案
multi_result = {
    'type': 'multi',
    'layout': '2A+2B' | 'A+B',
    'panels': [panel_info_1, panel_info_2],
    'total_pcb': 总PCB数,
    'layout_w': 排版宽度,
    'layout_h': 排版高度,
    'utilization': 利用率(%)
}

五、算法优化策略

5.1 剪枝优化

snippet.python

# 提前终止无效搜索
if panel.width > material_w and panel.height > material_h:
    continue  # Panel过大，无法放入大料
 
# 最小PCB数量过滤
if panel.pcb_count < min_pcb_count:
    continue

5.2 缓存机制

snippet.python

# 预计算所有有效Panel配置
panels = generate_panels(pcb_w, pcb_h, material_w, material_h, ...)
 
# 后续计算直接使用缓存结果
for panel in panels:
    # 无需重复计算Panel尺寸

5.3 优先级队列

snippet.python

# 按利用率排序，优先处理高利用率方案
results.sort(key=lambda x: -x['utilization'])
 
# 限制输出数量，避免不必要的计算
return results[:max_results]

六、输入输出示例

6.1 输入参数

snippet.python

# Panel拼板参数
pcb_w = 130          # PCB宽度
pcb_h = 250          # PCB高度
gap = 5              # 拼板间距
border = 5           # 工艺边
 
# Panel尺寸范围
panel_min_w = 300    # 最小宽度
panel_max_w = 600    # 最大宽度
panel_min_h = 300    # 最小高度
panel_max_h = 600    # 最大高度
 
# 大料参数
material_w = 1041    # 大料宽度
material_h = 1245    # 大料高度
max_panel_count = 10 # 最大拼板数
min_utilization = 60 # 最小利用率(%)
max_results = 8      # 最大输出方案数

6.2 输出结果

【方案1】单一Panel (利用率: 90.27%)
  Panel配置：横2 x 纵3
  Panel尺寸：515x410 mm
  每Panel PCB数：6个
  大料出板：6个
  总PCB数：36个
  排版尺寸：1030x1230 mm
  输出格式：Panel 515×410 (横2×纵3，6个PCB)，大料出板6个 → 总36个PCB

七、边界情况处理

7.1 极端尺寸约束

snippet.python

# Panel尺寸超出范围
if panel.width > panel_max_w or panel.height > panel_max_h:
    continue
 
# 大料尺寸不足
if material_w < panel_min_w or material_h < panel_min_h:
    return []  # 无法生成有效方案

7.2 零值处理

snippet.python

# 防止除零错误
if material_area == 0:
    return 0.0
 
# 空结果处理
if not results:
    print("错误：没有找到符合条件的Panel配置！")

7.3 重复方案去重

snippet.python

# 基于关键特征去重
seen = set()
for result in results:
    key = generate_unique_key(result)
    if key not in seen:
        seen.add(key)
        unique_results.append(result)

八、性能分析

8.1 时间复杂度

步骤	复杂度	说明
———	————————	————————————
Panel生成	O(max_cols × max_rows)	默认max_cols=20, max_rows=20，共400次迭代
单一Panel方案	O(n)	n为有效Panel数量
多Panel组合	O(n²)	双重循环遍历所有Panel组合
排序	O(m log m)	m为方案总数
总计	O(n²)	主要瓶颈在多Panel组合计算

8.2 空间复杂度

存储对象	复杂度	说明
———	————	———–
Panel配置列表	O(n)	存储所有有效Panel
方案列表	O(m)	存储所有候选方案
总计	O(n + m)	线性空间复杂度

8.3 优化建议

限制搜索范围：合理设置max_cols和max_rows参数
提前剪枝：在生成阶段过滤无效配置
并行计算：多Panel组合计算可并行化
启发式排序：优先计算高潜力方案

九、扩展功能

9.1 支持的布局模式

模式	布局描述	优先级
——	—————————-	—
2A+2B	2个A Panel + 2个B Panel（2×2布局）	高
A+B	1个A Panel + 1个B Panel（纵向堆叠）	中
N×Same	N个相同Panel排版	中
Single	单一Panel重复排版	低

9.2 可扩展参数

参数	当前支持	扩展方向
———	——	——
Panel尺寸范围	固定范围	可配置范围
利用率阈值	单一阈值	动态阈值
旋转角度	0°/90°	任意角度
拼板间距	固定值	行列独立配置

十、总结

本算法系统通过以下核心技术实现PCB拼板的自动化优化：

Nest算法：实现二维矩形装箱，最大化空间利用率
启发式算法：支持旋转优化和多种布局模式
贪心算法：以利用率和PCB产出为目标进行方案选择
约束过滤：确保方案满足尺寸范围和利用率要求

算法具有良好的可扩展性，可根据实际生产需求调整参数和添加新的布局模式。

PCB拼板算法详解

一、算法概述

核心目标

二、算法流程

2.1 整体流程图

三、核心算法详解

3.1 Panel配置生成算法

3.1.1 尺寸计算公式

3.1.2 约束条件验证

3.1.3 算法复杂度

3.2 利用率计算算法

3.2.1 计算公式

3.2.2 计算示例

3.3 单一Panel排版算法

3.3.1 计算逻辑

3.3.2 旋转优化

3.3.3 启发式策略

3.4 多Panel组合算法

3.4.1 2A+2B布局模式

3.4.2 A+B布局模式

3.4.3 组合约束条件

3.5 方案排序算法

3.5.1 排序规则

3.5.2 去重策略

四、代码结构

4.1 核心类与函数

4.2 关键数据结构

五、算法优化策略

5.1 剪枝优化

5.2 缓存机制

5.3 优先级队列

六、输入输出示例

6.1 输入参数

6.2 输出结果

七、边界情况处理

7.1 极端尺寸约束

7.2 零值处理

7.3 重复方案去重

八、性能分析

8.1 时间复杂度

8.2 空间复杂度

8.3 优化建议

九、扩展功能

9.1 支持的布局模式

9.2 可扩展参数

十、总结

目录