前面寫了一篇〈OR-Tools 從小白到入門〉，裡面的範例是簡單的線性方程式問題，對追求在實際應用發揮的我輩搬磚工程師來說有點不夠，這篇來談談一個具體而微的排工案例。
在進入案例前，還是用最短的篇幅介紹一下 OR-Tools 是什麼。
OR-Tools
OR-Tools 的「OR」意思是 operations research（作業研究），這是一門研究作業（或者稱為運籌）的學科，OR-Tools 則是 Google 開發的針對規劃問題的求解器，規劃問題指的是：
- 排程、排工、排課問題
- 路徑規劃問題
- 裝箱、裁切利用率最佳化問題
- 賽程規劃問題
這類問題的特色是「運算複雜、驗證簡單」，運算複雜因為路徑可以有千百條，驗證簡單因為有沒有到達目的地一翻兩瞪眼，這類問題因為可能性太多，難以窮舉找出真．最佳解，才需要依賴求解器幫我們找出可接受的近似最佳解。
OR-Tools 內建有幾款針對不同問題類型的求解器，我們會用到的是 CP-SAT 求解器，這是針對 constraint programming（約束編程）類型問題的求解器，什麼是約束，以排程為例，必須先排 A 再排 B 就是約束，排工最後交期不能晚於某月某日也是約束，工期越短越好、成本越低越好也都是約束。
不論是何種形式的問題，在 OR-Tools 都有相同的幾大步驟：
- 創建變數
- 制定約束
- 制定目標
- 執行求解
不論是這裡的排工問題還是其它問題，只要掌握思路，大都可以順利求解，在這幾個步驟背後，其實真正重要的是解題人的邏輯思維，我們必須把問題盡可能解構為能以 OR-Tools 特有的形式表達。
排工案例
引入套件
在本篇案例中，有六個工作，彼此間有一些先後關係，在深入認識它們的特性前，我們先開立一個 example.py，引入 OR-Tools 與一些基礎套件：
from dataclasses import dataclass, field
from itertools import groupby
from ortools.sat.python import cp_model
建立 data class
下面用 data class 來建立 Work 類，並收納相關特性，至於那 groupby() 當然就是來把 Work 群組化的，就像 SQL 的 GROUP BY 一樣。
開始建立 Work data class 與實例：
# Data class
@dataclass
class Work:
id: int
idno: str
order_id: int
part_id: int
line_id: int
processing_time: int
sequence: int # 工序
start_time: int | None = None
end_time: int | None = None
start_var: cp_model.IntVar | None = field(default=None, repr=False)
end_var: cp_model.IntVar | None = field(default=None, repr=False)
interval_var: cp_model.IntervalVar | None = field(default=None, repr=False)
work_list = [
Work(id=1, idno='WORK-1-1A', order_id=1, part_id=1, line_id=1, processing_time=2, sequence=1),
Work(id=2, idno='WORK-1-1B', order_id=1, part_id=2, line_id=2, processing_time=1, sequence=1),
Work(id=3, idno='WORK-1-2', order_id=1, part_id=3, line_id=3, processing_time=3, sequence=2),
Work(id=4, idno='WORK-1-3', order_id=1, part_id=4, line_id=4, processing_time=4, sequence=3),
Work(id=5, idno='WORK-2-1', order_id=2, part_id=5, line_id=1, processing_time=1, sequence=1),
Work(id=6, idno='WORK-2-2', order_id=2, part_id=6, line_id=2, processing_time=3, sequence=2),
]
其中屬性 order_id 表示該項工作來自哪張訂單，在關聯性資料結構的概念下，這邊僅以訂單 ID 表示，這裡我們有六個工作，分別來自兩張訂單。
後面的 part_id 是該工件的 ID，line_id 是加工該工件的產線 ID，processing_time 表示該工件的加工耗時，sequence 表示工件間的加工順序，WORK-1-1A 與 WORK-1-1B 的順序都是 1，表示它們先分別在不同的產線加工，再組裝成 WORK-1-2。
再後面的 start_time、end_time 是工件的開始時間點與結束時間點，因為還沒排定，目前沒有值。
最後面那幾個 xxx_var 則是預留給之後存放 OR-Tools 變數之用，目前也沒有值。
以上六個工作，利用我輩工人智慧可以描繪出下面這張甘特圖：
---
displayMode: compact
---
gantt
todayMarker off
dateFormat HH
axisFormat %H:%M
section Line 1
WORK-1-1A : 1-1A, 08, 2h
WORK-2-1 : 2-1, after 1-1A, 1h
section Line 2
WORK-1-1B : 1-1B, 08, 1h
WORK-2-2 : 2-2, after 1-1B 2-1, 3h
section Line 3
WORK-1-2 : 1-2, after 1-1A, 3h
section Line 4
WORK-1-3 : 1-3, after 1-2, 4h
問題是，如何在不寫特用演算法的情況下，用通用求解器取得類似的排程呢？
建立 CP-SAT 模型實例
首先來建立一個 CpModel 實例 model：
# Solver model
model = cp_model.CpModel()
這個模型會是稍後求解器運算的對象主體，可以把它視為一個容器，下面會陸續操作這個 model，在其中建立各個變數與約束。
制定變數
接著制定求解器變數：
sum_of_work_list_processing_time = sum([work.processing_time for work in work_list]) + 1
# Solver variables
for work in work_list:
start_var = model.NewIntVar(
lb=1, ub=sum_of_work_list_processing_time,
name='start_var-' + work.idno,
)
end_var = model.NewIntVar(
lb=1, ub=sum_of_work_list_processing_time,
name='end_var-' + work.idno,
)
interval_var = model.NewIntervalVar(
start=start_var, size=work.processing_time, end=end_var,
name='interval_var-' + work.idno,
)
work.start_var = start_var
work.end_var = end_var
work.interval_var = interval_var
此處為每個工作定義了之前預留的幾個變數：開始時間、結束時間、工作時間段。
開始時間與結束時間皆為整數，下限可能為 1，表示第一個工作小時，上限我們取所有工作加工時間的總和來權當，或是你認為這些工作必然會在一天內做完，那直接取 24 也無妨。
工作時間段用到的是 NewIntervalVar() 方法，顧名思義，這個方法建立的變數就是一個時間段變數，而一個工作的時間段變數的「時間段」是已知的，就是工作的加工時間，但它的開始與結束時間還是未知的，以前面的開始時間變數與結束時間變數填入。
至此工作的變數制定完畢，除了以時間段變數設定一個工作本身開始與結束時間之間的長度外，工作與工作之間的次序尚未定義，目前的狀態我們可以描繪成下面這張甘特圖：
---
displayMode: compact
---
gantt
todayMarker off
dateFormat HH
axisFormat %H:%M
section Line 1
WORK-1-1A : 1-1A, 08, 2h
WORK-2-1 : 2-1, 08, 1h
section Line 2
WORK-1-1B : 1-1B, 08, 1h
WORK-2-2 : 2-2, 08, 3h
section Line 3
WORK-1-2 : 1-2, 08, 3h
section Line 4
WORK-1-3 : 1-3, 08, 4h
所有的工作都擠在同一個起點，但實際上一條產線一次只能處理一份工作，另外同一張訂單下的幾個工作之間也應有先後，這些條件在 OR-Tools 中稱為約束，透過制定約束，OR-Tools 才能幫我們求出符合需求的解。
制定約束
接著來制定約束，第一個約束是「同一 order 且同一 line 的工作時段不可重疊」，這個約束以程式碼的形式呈現如下：
# Constraint
# No overlap
# 跑 groupby() 之前一定要先對 key 排序
work_list.sort(key=lambda work: work.order_id)
order_id_groups = groupby(
iterable=work_list, key=lambda work: work.order_id,
)
for order_id, order_subgroups in order_groups:
# Sub-group 只能使用一次，最好另外存起來。
order_subgroup_list = list(order_subgroups)
order_subgroup_list.sort(key=lambda work: work.line_id)
line_subsubgroups = groupby(
iterable=order_subgroup_list, key=lambda work: work.line_id,
)
for line_id, line_subsubgroup in line_subsubgroups:
model.AddNoOverlap(
interval_vars=[
work.interval_var for work in line_subsubgroup
],
)
這裡我們用 groupby() 來分組，在跑 groupby() 前一定要先排序，例如針對 order ID 分群組，就一定要先以 order ID 排序，這是使用 groupby() 的標準姿勢，詳情可參見 Python 標準庫文件，groupby() 的使用細節不是本文主題。
所謂「同一 order 且同一 line」在此以兩次 groupby() 實現，先針對 order ID 分出第一階群組 order sub-groups，然後再對 order sub-groups 以 line ID 分組，此為第二階群組 line sub-sub-groups，此群組下之每一組 line-sub-sub-group 就是那「同一 order 且同一 line」的工作，最後針對這些細分好的工作群組我們以 AddNoOverlap() 方法對其制定工作時段不可重疊之約束。
第二個約束為「相同 line ID 的工作時段不可以重疊」，程式碼如下：
# 跑 groupby() 之前一定要先對 key 排序
work_list.sort(key=lambda work: work.line_id)
line_groups = groupby(
iterable=work_list, key=lambda work: work.line_id,
)
for line_id, line_subgroups in line_groups:
# Sub-group 只能使用一次，最好另外存起來。
line_subgroup_list = list(line_subgroups)
model.AddNoOverlap(
interval_vars=[
work.interval_var for work in line_subgroup_list
],
)
添加這兩款約束後，甘特圖大概會長這樣：
---
displayMode: compact
---
gantt
todayMarker off
dateFormat HH
axisFormat %H:%M
section Line 1
WORK-1-1A : 1-1A, 08, 2h
WORK-2-1 : 2-1, after 1-1A, 1h
section Line 2
WORK-1-1B : 1-1B, 08, 1h
WORK-2-2 : 2-2, after 1-1B, 3h
section Line 3
WORK-1-2 : 1-2, 08, 3h
section Line 4
WORK-1-3 : 1-3, 08, 4h
至此每條產線就不會同時有兩份工作了，但工作間還沒有照順序進行，例如照理說 WORK-1-2 應該要在 WORK-1-1A、WORK-1-1B 之後，其它工作也都有類似的問題，所以我們還需要添加「相同 order ID 的工作必須照順序」的約束，程式碼如下：
# Constraint
# 跑 groupby() 之前一定要先對 key 排序
work_list.sort(key=lambda work: work.order_id)
order_groups = groupby(iterable=work_list, key=lambda work: work.order_id)
for order_id, order_subgroups in order_groups:
# Sub-group 只能使用一次，最好另外存起來。
order_subgroup_list = list(order_subgroups)
work_sequence_set = {work.sequence for work in order_subgroup_list} # EX: {1, 3, 4}
work_sequence_list = list(work_sequence_set)
work_sequence_list.sort() # EX: [1, 3, 4]
for index, sequence in enumerate(iterable=work_sequence_list):
this_sequence = sequence
try: next_sequence = work_sequence_list[index + 1]
except: continue
this_sequence_works = list(
filter(
lambda work: work.sequence == this_sequence,
order_subgroup_list,
),
)
next_sequence_works = list(
filter(
lambda work: work.sequence == next_sequence,
order_subgroup_list,
),
)
for this_sequence_work in this_sequence_works:
for next_sequence_work in next_sequence_works:
model.Add(
ct=next_sequence_work.start_var >= this_sequence_work.end_var,
)
上面這段程式真正的重點只有最尾巴那行：
model.Add(
ct=next_sequence_work.start_var >= this_sequence_work.end_var,
)
這裡的 Add() 方法是泛用的添加約束的方法，參數 ct 接受任意的數學關係式，這裡我們用的是「下一順序的工作之開始時間必須大於等於前一順序工作之結束時間」，而前面那堆程式碼不過是為了把順序理出來而已。
添加以上所有約束後，甘特圖大概會長這樣：
---
displayMode: compact
---
gantt
todayMarker off
dateFormat HH
axisFormat %H:%M
section Line 1
WORK-1-1A : 1-1A, 08, 2h
WORK-2-1 : 2-1, after 1-1A, 1h
section Line 2
WORK-1-1B : 1-1B, 08, 1h
WORK-2-2 : 2-2, after 1-1B 2-1, 3h
section Line 3
WORK-1-2 : 1-2, after 1-1A 1-1B, 3h
section Line 4
WORK-1-3 : 1-3, after 1-2, 4h
看起來好像是最佳解了，但實際上這是工人智慧干預下的結果，電腦並沒有這麼聰明「想當然爾」的把工作往前排，得透過制定目標來達成。
制定目標
接著來制定目標，前面提到「想當然爾」指的是把工作往前排，換句話說就是追求產能效率、提高產線稼動，避免產線閒置，問題是，如何在 OR-Tools 中表示這類需求呢？
在此我們制定一個新變數「整體結束時間」，並且以它為基礎建立目標，希望它越小越好，它越小，意味著這把六項工作就越早結束，也意味著 OR-Tools 會盡可能找出符合約束與目標的解。
加入以下程式碼：
# Objective
obj_var = model.NewIntVar(
lb=0,
ub=sum_of_work_list_processing_time,
name='overall_end_time',
)
model.AddMaxEquality(
target=obj_var,
exprs=[work.end_var for work in work_list]
)
model.Minimize(obj=obj_var)
在上面程式碼中，首先制定了一個 obj_var，它是 OR-Tools 的整數變數，具體值在解算前未知。
第二部份，我們用 AddMaxEquality() 方法，設定 obj_var 的值為所有工作中 end_var 的最大值，也就是最後一個工作的結束時間，這部份的程式可以簡單的理解為：
obj_var = max([work.end_var for work in work_list])
不過因為前面制定一系列 OR-Tools 的變數截至目前為止都沒有值，也就無法直接以 max() 取最大值，因此得利用 OR-Tools 的 AddMaxEquality() 方法在 CP model 內制定 A 變數為 XXX 群體中 YY 的最大值的關係式。
第三部份就是 model 的目標，盡可能讓 obj_var 小。
執行求解
前面我們透過 CP model 的一些 AddXXX() 方法制定了一系列變數、約束、目標，在此我們將該 model 餵給求解器，求解器會以各種變數組合來找出同時符合約束與目標的解，並在不無限窮舉的情況下以求解器內的神奇演算法找到近似最佳解，這也呼應了本文最初提到規劃問題的性質「運算複雜、驗證簡單」，可能性有那麼多，但用於驗證可不可行的約束與目標就那幾項。
萬事具備，來求解吧：
# Solve
solver = cp_model.CpSolver()
status = solver.Solve(model=model)
檢視一下求解概況：
print(solver.ResponseStats())
輸出如下：
CpSolverResponse summary:
status: OPTIMAL
objective: 10
best_bound: 10
integers: 8
booleans: 8
conflicts: 0
branches: 8
propagations: 6
integer_propagations: 29
restarts: 1
lp_iterations: 0
walltime: 0.0572581
usertime: 0.0572614
deterministic_time: 5.3936e-06
gap_integral: 5.97731e-07
solution_fingerprint: 0x57ace85ecf9f2ae3
現在每個工作的 start_var 與 end_var 都有值了，把值填入對應的 start_time 與 end_time：
for work in work_list:
work.start_time = solver.Value(expression=work.start_var)
work.end_time = solver.Value(expression=work.end_var)
print(work)
輸出如下：
Work(id=1, idno='WORK-1-1A', order_id=1, part_id=1, line_id=1, processing_time=2, sequence=1, start_time=1, end_time=3)
Work(id=2, idno='WORK-1-1B', order_id=1, part_id=2, line_id=2, processing_time=1, sequence=1, start_time=1, end_time=2)
Work(id=3, idno='WORK-1-2', order_id=1, part_id=3, line_id=3, processing_time=3, sequence=2, start_time=3, end_time=6)
Work(id=4, idno='WORK-1-3', order_id=1, part_id=4, line_id=4, processing_time=4, sequence=3, start_time=6, end_time=10)
Work(id=5, idno='WORK-2-1', order_id=2, part_id=5, line_id=1, processing_time=1, sequence=1, start_time=3, end_time=4)
Work(id=6, idno='WORK-2-2', order_id=2, part_id=6, line_id=2, processing_time=3, sequence=2, start_time=4, end_time=7)
以甘特圖表示如下：
---
displayMode: compact
---
gantt
todayMarker off
dateFormat HH
axisFormat %H:%M
section Line 1
WORK-1-1A : 1-1A, 08, 2h
WORK-2-1 : 2-1, after 1-1A, 1h
section Line 2
WORK-1-1B : 1-1B, 08, 1h
WORK-2-2 : 2-2, after 1-1B 2-1, 3h
section Line 3
WORK-1-2 : 1-2, after 1-1A 1-1B, 3h
section Line 4
WORK-1-3 : 1-3, after 1-2, 4h
跟我們最初以工人智慧排出來的一模一樣。
透過這個具體而微的案例，我們可以認識倒把問題轉化為 OR-Tools 形式的一些思路與方法。
結語
本文的排工案例較為貼近真實，但依然是簡化過的案例，現實中的問題還要更複雜，例如：
- 加工時間也是變數。
- 產線可用時間不連續，要考慮到前面已經排定之工作。
- 工作本身也是變數，並且與產線可用時間互為變數。
- 工作之間的順序關係不只 end-to-start，還有 start-to-start、end-to-end 等等。
以上這些都會增加 model 的複雜度，總之問題沒有最複雜，只有更複雜，要如何建立它們的變數、約束、目標，有機會再研究囉。
Share
作者：Leon
一直卡關的卡關小編。
