Python实现的FFD棒材切割算法中部分零件缺失问题排查与修复请求

阿华AIGC实验室

2026-4-2

问题描述

我最近用Python写了一个基于**First Fit Decreasing（FFD）**的棒材切割优化工具，目标是把订单里的各种零件都分配到6000mm长的标准棒材中，最后生成可视化的切割报告。但现在遇到了一个头疼的问题：有些订单里的零件（比如XC9）明明在输入里有对应的数量，但是最终的切割计划里完全找不到它们的影子，用计数器核对数量时也显示这些零件根本没被分配进去。

我已经做的排查

确认所有需要切割的零件都完整出现在初始的输入订单列表里，没有遗漏
跟踪了代码里的分配循环流程，发现这些缺失的零件似乎根本没被添加到任何棒材中
用计数器对比请求数量和实际分配数量，确实存在明显的不匹配

我的实现代码

注：原始输入最后一行的订单条目是截断状态，我暂时标注了注释，默认是笔误导致的不完整条目

# -*- coding: utf-8 -*-
import pandas as pd
from collections import Counter

def optimize_cuts(stock_length, required_pieces):
    """
    Calculates the bar cutting plan using the First Fit Decreasing algorithm.
    """
    # 1. Create a complete list of individual pieces
    pieces_list = []
    for item in required_pieces:
        for _ in range(item['quantity']):
            pieces_list.append({
                'name': item['name'],
                'length': item['length']
            })

    # 2. Sort pieces from largest to smallest
    pieces_list.sort(key=lambda x: x['length'], reverse=True)

    used_bars = []
    # 3. Allocate each piece
    for piece in pieces_list:
        allocated = False
        # Try to fit the piece in an existing bar
        for bar in used_bars:
            used_length = sum(p['length'] for p in bar)
            if stock_length - used_length >= piece['length']:
                bar.append(piece)
                allocated = True
                break
        # If it doesn't fit in any existing bar, create a new one
        if not allocated:
            used_bars.append([piece])
    return used_bars

def generate_tabular_report(stock_length, cutting_plan):
    """
    Formats the cutting plan result into a table (DataFrame) using pandas.
    """
    print("=" * 80)
    print(" BAR CUTTING OPTIMIZATION PLAN (TABULAR)")
    print("=" * 80)

    table_data = []
    for i, bar in enumerate(cutting_plan, 1):
        piece_counter = Counter(p['name'] for p in bar)
        lengths = {p['name']: p['length'] for p in bar}

        row_data = {'SEQUENCE': f'CUT {i}'}
        piece_idx = 1
        for name, qty in piece_counter.items():
            row_data[f'NAME_{piece_idx}'] = name
            row_data[f'QTY_{piece_idx}'] = qty
            row_data[f'LENGTH_{piece_idx}'] = lengths[name]
            piece_idx += 1

        total_used = sum(p['length'] for p in bar)
        leftover = stock_length - total_used
        row_data['TOTAL USED'] = total_used
        row_data['LEFTOVER'] = leftover
        table_data.append(row_data)

    if not table_data:
        print("No pieces to process.")
        return

    df = pd.DataFrame(table_data)
    max_pieces = (len(df.columns) - 3) // 3
    ordered_columns = ['SEQUENCE']
    for i in range(1, max_pieces + 1):
        ordered_columns.extend([f'NAME_{i}', f'QTY_{i}', f'LENGTH_{i}'])
    ordered_columns.extend(['TOTAL USED', 'LEFTOVER'])

    for col in ordered_columns:
        if col not in df.columns:
            df[col] = ''
    df = df[ordered_columns]
    df.fillna('', inplace=True)

    print(df.to_string(index=False))

    total_bars = len(cutting_plan)
    total_leftover = df['LEFTOVER'].astype(float).sum()
    overall_utilization = ((total_bars * stock_length - total_leftover) / (total_bars * stock_length)) * 100

    print("\n" + "=" * 80)
    print(" SUMMARY")
    print("=" * 80)
    print(f"Total {stock_length}mm bars needed: {total_bars}")
    print(f"Overall material utilization: {overall_utilization:.2f}%")
    print("=" * 80)

def verify_quantities(order_list, final_plan):
    """
    Checks if the quantity of pieces in the final plan matches the initial order.
    """
    requested = {item['name']: item['quantity'] for item in order_list}
    allocated_pieces = []
    for bar in final_plan:
        for piece in bar:
            allocated_pieces.append(piece['name'])
    allocated = Counter(allocated_pieces)

    print("\n" + "=" * 80)
    print(" QUANTITY VERIFICATION")
    print("=" * 80)
    if dict(allocated) == requested:
        print("✅ SUCCESS: All requested quantities were correctly allocated in the plan!")
    else:
        print("❌ WARNING: There is a mismatch between the order and the final plan.")
        for name, qty_requested in requested.items():
            qty_allocated = allocated.get(name, 0)
            if qty_requested != qty_allocated:
                print(f" - Piece '{name}': Requested={qty_requested}, Allocated={qty_allocated}")
    print("=" * 80)

# --- INPUT DATA ---
if __name__ == "__main__":
    STOCK_BAR_LENGTH = 6000
    order_list = [
        {'name': '396', 'quantity': 290, 'length': 6000},
        {'name': 'XC21', 'quantity': 1, 'length': 4478},
        {'name': 'XC52', 'quantity': 1, 'length': 4308},
        {'name': 'XC19', 'quantity': 2, 'length': 4240},
        {'name': 'XC22', 'quantity': 1, 'length': 3759},
        {'name': 'XC48', 'quantity': 1, 'length': 3698},
        {'name': 'XC20', 'quantity': 20, 'length': 3514},
        {'name': 'XC10', 'quantity': 1, 'length': 3452},
        {'name': 'XC51', 'quantity': 4, 'length': 3382},
        {'name': 'XC41', 'quantity': 1, 'length': 3256},
        {'name': 'XC15', 'quantity': 1, 'length': 3239},
        {'name': 'XC8', 'quantity': 16, 'length': 3076},
        {'name': 'XC9', 'quantity': 2, 'length': 2732},
        {'name': 'XC1', 'quantity': 1, 'length': 2693},
        {'name': 'XC13', 'quantity': 2, 'length': 2631},
        # 注：原始输入此处截断，应为一个完整的订单条目，比如 {'name': 'XXX', 'quantity': N, 'length': L}
    ]
    cutting_plan = optimize_cuts(STOCK_BAR_LENGTH, order_list)
    generate_tabular_report(STOCK_BAR_LENGTH, cutting_plan)
    verify_quantities(order_list, cutting_plan)