實戰：排程最佳化 API
Vibe Prompt
「幫我用 FastAPI 建立一個工作排程 API，使用最早截止時間優先 (EDD) 策略。」
from fastapi import FastAPI
from pydantic import BaseModel
app = FastAPI(title="排程最佳化 API")
class Job(BaseModel):
id: str
deadline: int
profit: int
duration: int
class ScheduleRequest(BaseModel):
jobs: list[Job]
class ScheduleResponse(BaseModel):
scheduled: list
total_profit: int
algorithm: str
@app.post("/schedule", response_model=ScheduleResponse)
def schedule_jobs(req: ScheduleRequest):
# 使用最早截止時間優先 (EDD)
sorted_jobs = sorted(req.jobs, key=lambda j: j.deadline)
scheduled = []
current_time = 0
for job in sorted_jobs:
if current_time + job.duration <= job.deadline:
scheduled.append(job)
current_time += job.duration
return ScheduleResponse(
scheduled=[j.id for j in scheduled],
total_profit=sum(j.profit for j in scheduled),
algorithm="貪婪 EDD"
)
if __name__ == "__main__":
import uvicorn
uvicorn.run(app, host="0.0.0.0", port=8000)
本日總結
完成了貪婪演算法課程！
- ✅ Kruskal / Prim MST
- ✅ Huffman 編碼
- ✅ 集合覆蓋
- ✅ 排程 API
深入理解：排程演算法的選擇
常見排程策略比較
| 策略 | 英文 | 目標 | 特性 | |------|------|------|------| | FCFS | First-Come-First-Serve | 公平性 | 簡單但平均等待時間長 | | SJF | Shortest Job First | 最小化平均完成時間 | 需知道工作長度 | | EDD | Earliest Due Date | 最小化最大延遲 | 貪婪，直觀 | | Moore-Hodgson | — | 最小化延遲工作數 | 複雜但最佳 |
更多排程 API 端點
@app.post("/schedule/weighted", response_model=ScheduleResponse)
def schedule_weighted_jobs(req: ScheduleRequest):
"""加權最短處理時間優先 (WSPT)"""
weighted_jobs = sorted(req.jobs,
key=lambda j: j.duration / j.profit if j.profit > 0 else float('inf'))
# ... 排程邏輯
return schedule_response(weighted_jobs, algorithm="WSPT")
@app.post("/schedule/parallel")
def schedule_parallel_machines(req: ScheduleRequest, machines: int = 2):
"""多機台排程 (List Scheduling)"""
machines_load = [0] * machines
schedule = [[] for _ in range(machines)]
for job in sorted(req.jobs, key=lambda j: -j.duration):
min_machine = min(range(machines), key=lambda m: machines_load[m])
schedule[min_machine].append(job)
machines_load[min_machine] += job.duration
return {"makespan": max(machines_load), "schedule": schedule}
課程總結
你完成了貪婪演算法的五堂課程！
| 章節 | 核心技能 | |------|---------| | 1️⃣ Kruskal & Union-Find | 最小生成樹 + 近乎 O(1) 的集合操作 | | 2️⃣ Prim 演算法 | 割性質與 MST 的正確性 | | 3️⃣ Huffman 編碼 | 最佳前綴碼與無失真壓縮 | | 4️⃣ 集合覆蓋 | NP-Hard 問題的貪婪近似 | | 5️⃣ 排程 API | 將貪婪演算法包裝成服務 |
下一步
- 比較 Kruskal vs Prim 在稀疏/密集圖上的實際效能
- 實作 Huffman 解碼 完成完整的壓縮/解壓流程
- 研究更進階的排程問題：Flow Shop、Job Shop
讓你能夠將所學應用到實際專案中
## 常見錯誤
## 程式碼範例
## 為什麼排程問題無所不在？
從工廠生產線到雲端伺服器資源分配，從飛機航班調度到外送平台的訂單指派——排程問題（Scheduling）是電腦科學中最實用的領域之一。
### 貪婪排程的關鍵洞見
| 策略 | 核心想法 | 最佳化目標 |
|:----|:--------|:---------|
| **EDD** | 最早截止時間優先 | 最小化最大延遲 |
| **SJF** | 最短工作優先 | 最小化平均完成時間 |
| **WSPT** | 加權最短處理時間 | 最小化加權完成時間 |
| **List Scheduling** | 按某種順序分配給空閒機器 | 最小化完工時間（Makespan） |
這些策略的共同點是：**在每一步做當下看起來最好的選擇**——這就是貪婪演算法的精神。
### 實戰應用的關鍵心法
- **演算法選擇比實作更重要**：EDD 跟 SJF 的程式碼只差一行排序 key，但它們的最佳化目標完全不同
- **真實資料不完美**：實際的 deadline 可能會變、工作時間是估計值——你的系統要能容忍誤差
- **動態排程**：真實世界的工作是陸續進來的，不是一次全部給你的
### 課程總結
貪婪演算法這堂課你從數學證明（MST 割性質）、資料壓縮（Huffman）、NP-hard 近似（Set Cover）到實戰 API（排程服務），已經掌握了貪婪策略的全貌。**貪婪不一定最佳，但它是你在面對任何最佳化問題時，第一個該嘗試的解法。**