資源分配與生產排程

問題描述

你的工廠收到 10 張訂單，但你只有有限的機器和工時。每張訂單的利潤不同、所需工時不同、截止日期不同。如何選擇接哪些訂單才能最大化利潤？

ILP 模型

import pulp

# === 訂單資料 ===
orders = [
    {"id": "A", "profit": 500, "hours": 40, "deadline": 5},
    {"id": "B", "profit": 300, "hours": 25, "deadline": 3},
    {"id": "C", "profit": 800, "hours": 60, "deadline": 7},
    {"id": "D", "profit": 200, "hours": 15, "deadline": 2},
    {"id": "E", "profit": 600, "hours": 45, "deadline": 6},
    {"id": "F", "profit": 400, "hours": 30, "deadline": 4},
    {"id": "G", "profit": 900, "hours": 70, "deadline": 8},
    {"id": "H", "profit": 350, "hours": 20, "deadline": 3},
    {"id": "I", "profit": 700, "hours": 50, "deadline": 6},
    {"id": "J", "profit": 250, "hours": 18, "deadline": 2},
]

# === 建立問題 ===
prob = pulp.LpProblem("生產訂單選擇", pulp.LpMaximize)

# 變數：x[i] = 1 表示接受訂單 i
x = {}
for i, order in enumerate(orders):
    x[i] = pulp.LpVariable(f"x_{order['id']}", cat="Binary")

# 目標：最大化總利潤
prob += pulp.lpSum(orders[i]["profit"] * x[i] for i in range(len(orders)))

# 限制 1：每週可用工時
max_hours_per_week = 100
weeks = 4
for week in range(weeks):
    week_orders = [i for i, o in enumerate(orders) if o["deadline"] >= week + 1]
    prob += pulp.lpSum(orders[i]["hours"] * x[i] for i in week_orders) <= max_hours_per_week

# 求解
prob.solve()

print(f"求解狀態: {pulp.LpStatus[prob.status]}")
print(f"最大利潤: {pulp.value(prob.objective)}")
print(f"\n接受的訂單:")
selected = []
for i, order in enumerate(orders):
    if x[i].value() == 1:
        selected.append(order)
        print(f"  {order['id']}: 利潤 {order['profit']}, 工時 {order['hours']}, 期限 {order['deadline']}天")

print(f"\n總工時: {sum(o['hours'] for o in selected)}")
print(f"總利潤: {sum(o['profit'] for o in selected)}")

應用場景

資源分配：在有限預算下最大化產出
排程問題：最小化工廠閒置時間
投資組合：在風險限制下最大化報酬

参考

資源分配問題は製造業、物流、クラウドコンピューティングなど幅広い分野で応用されている。

資源分配問題的商業價值

你現在遇到的情境在製造業、軟體開發、醫療排程中天天發生——有限資源下該選擇哪些專案來做？

為什麼這個問題這麼難？

| 因素 | 為什麼困難 | 現實影響 | |:----|:---------|:--------| | 多維度限制 | 不只有工時限制，還有 deadline、技能需求、機器型號 | 手工排程需要數天 | | 動態變化 | 訂單隨時進來、機器隨時可能故障 | 排程需要頻繁重算 | | 相互依存 | 某些訂單完成後才能開始其他訂單 | 增加了排程的序列性 | | 不確定性 | 工時是估計值，實際可能超時 | 最佳排程可能執行不下去 |

PuLP 與 CP-SAT 的選擇

| 比較 | PuLP（ILP） | OR-Tools CP-SAT | |:----|:----------|:--------------| | 問題類型 | 線性目標 + 線性限制 | 任意限制（含邏輯限制） | | 變數類型 | 連續 + 整數 + 二元 | 整數 + 二元 | | 速度 | 大規模線性問題快 | 組合問題通常更快 | | 內建限制 | 少（需自行轉換） | 多（AllDifferent、AddExactlyOne） |

對於資源分配問題，中小規模用 CP-SAT 更方便（不用手動轉線性限制），大規模用 PuLP（ILP 求解器更成熟）。這裡用 PuLP 是因為工廠排程通常需要整合進現有的排程系統。

實戰心法

先建最小可行模型：先忽略 deadline，只用工時限制，確認模型正確再逐步加限制
敏感度分析：工時估計不準時，改變工時參數看結果變化大不大
分批排程：超過 1000 筆訂單時，分批次排程而非一次全跑

下一章預告：供應鏈網路設計

資源分配解決的是單一工廠的問題。下一章的供應鏈網路設計延伸到多工廠、多倉庫、多配送中心的全球最佳化問題。