工作排程 Job Scheduling

問題描述

假設你經營一家加工廠，有 3 台機器和 8 個待處理的工作。每個工作需要特定的機器、特定的處理時間，有些工作還有順序先後關係。如何安排才能讓所有工作在最短時間內完成？

from ortools.sat.python import cp_model
import matplotlib.pyplot as plt

# === 定義工作 ===
# (工作ID, 機器ID, 處理時間)
jobs = [
    (0, 0, 3),  # 工作 0，需機器 0 處理 3 小時
    (1, 1, 2),  # 工作 1，需機器 1 處理 2 小時
    (2, 2, 5),  # 工作 2，需機器 2 處理 5 小時
    (3, 0, 4),  # 工作 3，需機器 0 處理 4 小時
    (4, 1, 3),  # 工作 4，需機器 1 處理 3 小時
    (5, 2, 2),  # 工作 5，需機器 2 處理 2 小時
    (6, 0, 2),  # 工作 6，需機器 0 處理 2 小時
    (7, 1, 4),  # 工作 7，需機器 1 處理 4 小時
]

# 順序限制：(工作ID_A, 工作ID_B) 表示 A 必須在 B 之前完成
precedences = [(0, 3), (1, 4), (2, 5)]

# 機台數量
num_machines = 3
# 每個機台上的工作
machine_jobs = {m: [] for m in range(num_machines)}
for jid, mid, dur in jobs:
    machine_jobs[mid].append((jid, dur))

# === 建立模型 ===
model = cp_model.CpModel()

# 每個工作的開始時間
horizon = sum(dur for _, _, dur in jobs)  # 所有工作時間加總
start_times = {}
end_times = {}
intervals = {}

for jid, mid, dur in jobs:
    start = model.NewIntVar(0, horizon, f"start_{jid}")
    end = model.NewIntVar(0, horizon, f"end_{jid}")
    interval = model.NewIntervalVar(start, dur, end, f"interval_{jid}")
    start_times[jid] = start
    end_times[jid] = end
    intervals[jid] = interval

# 限制：同一機台上的工作不能重疊
for m in range(num_machines):
    model.AddNoOverlap([intervals[jid] for jid, _ in machine_jobs[m]])

# 限制：順序限制
for before, after in precedences:
    model.Add(start_times[after] >= end_times[before])

# 目標：最小化最大完成時間 (Makespan)
makespan = model.NewIntVar(0, horizon, "makespan")
model.AddMaxEquality(makespan, [end_times[jid] for jid, _, _ in jobs])
model.Minimize(makespan)

# === 求解 ===
solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10
status = solver.Solve(model)

if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    print(f"\n=== 排程結果 ===")
    print(f"最短完工時間 (Makespan): {solver.ObjectiveValue()}")
    
    # 輸出每個工作的排程
    result = []
    for jid, mid, dur in jobs:
        s = solver.Value(start_times[jid])
        e = solver.Value(end_times[jid])
        print(f"工作 {jid} (機器 {mid}, {dur}h): {s} → {e}")
        result.append((jid, mid, dur, s, e))
    
    # 畫出甘特圖
    fig, ax = plt.subplots(figsize=(12, 6))
    colors = ['#FF6B6B', '#4ECDC4', '#45B7D1', '#96CEB4', '#FFEAA7',
              '#DDA0DD', '#98D8C8', '#F7DC6F']
    
    for i, (jid, mid, dur, s, e) in enumerate(result):
        ax.barh(mid, e - s, left=s, height=0.5, color=colors[i], 
                edgecolor='black', label=f"Job {jid}")
        ax.text((s + e) / 2, mid, f"J{jid}", ha='center', va='center',
                fontweight='bold', fontsize=10)
    
    ax.set_yticks(range(num_machines))
    ax.set_yticklabels([f"機器 {m}" for m in range(num_machines)])
    ax.set_xlabel("時間")
    ax.set_title("工作排程甘特圖")
    ax.grid(True, alpha=0.3)
    plt.tight_layout()
    plt.show()
else:
    print("找不到解")