100本ノック / 数理最適化 / 数理最適化100本ノック
生産スケジューリングの近似解入門｜製造業で使うメタヒューリスティクス10選
納期遅延を現実的な時間で減らす：生産順序最適化の10本ノック
架空の多品種少量生産ラインを題材に、厳密解と近似解の使い分け、貪欲法、局所探索、焼きなまし法、遺伝的アルゴリズム、タブーサーチ、粒子群最適化、大規模近傍探索を比較します。対象は No.081〜No.090（ヒューリスティクス・メタヒューリスティクス） です。
[!NOTE] 本資料は、数理工房 (もしくは代表である和山個人) が過去に企業研修において使用した notebook を企業様の許可を得て再構成・編集のうえ公開しています。 掲載データはすべて架空のものであり、実在する企業・工場・数値とは一切関係ありません。
はじめに：この記事で扱う製造業の実務課題
受注ごとに加工時間、納期、重要度が異なるラインでは、投入順序が変わるだけで納期遅延が大きく変わります。本稿では、総加重遅れを抑える順序を限られた計算時間で決める問題を扱います。
現場でよくある状況
- 朝会後に特急品、設備停止、欠員が入り、計画を組み直す
- 数分以内に現場へ指示したいが、候補順序はジョブ数の階乗で増える
- 「最適」という言葉より、納期、安定性、説明可能性が重視される
なぜこの問題は判断が難しいのか
件の順序は 通りです。8件なら40,320通りですが、20件では約 通りです。また、目的値が同じでも段取りや重点顧客への影響が違うため、計算時間と解品質を含む運用設計が必要です。
今回扱うノックの全体像
| No. | テーマ | 現場での問い |
|---|---|---|
| 081 | 厳密解と近似解 | 最適性をどこまで保証するか |
| 082 | ヒューリスティクス | 業務知識をどう初期案へ変えるか |
| 083 | 貪欲法 | 逐次判断で素早く順序を作れるか |
| 084 | 局所探索法 | 近傍の入替えで改善できるか |
| 085 | 焼きなまし法 | 一時的な悪化を許して谷を越えられるか |
| 086 | 遺伝的アルゴリズム | 複数候補の組合せを活かせるか |
| 087 | タブーサーチ | 同じ解への循環を防げるか |
| 088 | 粒子群最適化 | 連続表現から良い順序を探索できるか |
| 089 | 大規模近傍探索 | 順序の一部を壊して作り直せるか |
| 090 | 厳密解へのこだわり | 意思決定に十分な解をどう選ぶか |
Python 環境の準備
外部データは使わず、乱数シードを固定します。比較の公平性のため、すべての手法で同じ評価関数を使用します。グラフはMatplotlibで作成します。
import platform, time, itertools, math
import numpy as np
import pandas as pd
import matplotlib
import matplotlib.pyplot as plt
from IPython.display import display
SEED = 42
rng = np.random.default_rng(SEED)
plt.rcParams["figure.figsize"] = (7.4, 4.5)
plt.rcParams["font.size"] = 10
print("Python:", platform.python_version())
print("numpy:", np.__version__, "pandas:", pd.__version__, "matplotlib:", matplotlib.__version__)Python: 3.13.1
numpy: 2.5.1 pandas: 3.0.3 matplotlib: 3.11.0架空データの作成
1台のボトルネック設備で8件のジョブを連続加工します。ジョブ の加工時間を 、納期を 、重要度を 、完了時刻を とし、KPIを総加重遅れ
とします。小さいほど良く、単位は「重要度加重・時間」です。簡潔な比較のため、本稿では段取り時間を省略します。
jobs = pd.DataFrame({
"job": list("ABCDEFGH"),
"processing_h": [5, 8, 4, 7, 3, 9, 6, 5],
"due_h": [14, 18, 11, 27, 9, 35, 23, 20],
"priority": [3, 5, 2, 4, 6, 2, 5, 3],
})
p = jobs.processing_h.to_numpy(); due = jobs.due_h.to_numpy(); weight = jobs.priority.to_numpy(); n = len(jobs)
def score(order):
order = np.asarray(order, dtype=int)
completion = np.cumsum(p[order])
return int(np.sum(weight[order] * np.maximum(completion - due[order], 0)))
def schedule(order):
order = np.asarray(order, dtype=int); completion = np.cumsum(p[order])
return pd.DataFrame({"sequence": np.arange(1, n+1), "job": jobs.job.to_numpy()[order],
"completion_h": completion, "due_h": due[order],
"tardiness_h": np.maximum(completion-due[order], 0), "priority": weight[order]})
display(jobs)
print("候補順序数:", math.factorial(n))| job | processing_h | due_h | priority | |
|---|---|---|---|---|
| 0 | A | 5 | 14 | 3 |
| 1 | B | 8 | 18 | 5 |
| 2 | C | 4 | 11 | 2 |
| 3 | D | 7 | 27 | 4 |
| 4 | E | 3 | 9 | 6 |
| 5 | F | 9 | 35 | 2 |
| 6 | G | 6 | 23 | 5 |
| 7 | H | 5 | 20 | 3 |
候補順序数: 40320No.081：厳密解と近似解
実務での意味
厳密解は最適性を保証しますが、件数が増えると計算が終わらない場合があります。近似解は保証を緩める代わりに、実務で使える時間内に良い計画を返します。
分析・モデル化の考え方
今回は全列挙で厳密解 を求め、後続手法の品質をギャップ で測ります。全列挙は小規模な検証用であり、大規模問題の標準解法ではありません。
Pythonで確認する
t0 = time.perf_counter(); exact_order = min(itertools.permutations(range(n)), key=score); exact_sec = time.perf_counter()-t0
exact_score = score(exact_order)
display(schedule(exact_order))
print("厳密解:", "-".join(jobs.job.iloc[list(exact_order)]), "目的値:", exact_score, "計算秒:", round(exact_sec, 4))| sequence | job | completion_h | due_h | tardiness_h | priority | |
|---|---|---|---|---|---|---|
| 0 | 1 | C | 4 | 11 | 0 | 2 |
| 1 | 2 | E | 7 | 9 | 0 | 6 |
| 2 | 3 | A | 12 | 14 | 0 | 3 |
| 3 | 4 | B | 20 | 18 | 2 | 5 |
| 4 | 5 | G | 26 | 23 | 3 | 5 |
| 5 | 6 | H | 31 | 20 | 11 | 3 |
| 6 | 7 | D | 38 | 27 | 11 | 4 |
| 7 | 8 | F | 47 | 35 | 12 | 2 |
厳密解: C-E-A-B-G-H-D-F 目的値: 126 計算秒: 0.1657結果の読み取り
8件では全列挙が可能で、比較基準となる最適値を得られます。一方、件数が増えれば列挙数は急増します。小規模インスタンスで近似法を校正し、本番規模では時間上限を置くのが現実的です。
No.082：ヒューリスティクスとは何か
実務での意味
ヒューリスティクスは、現場の経験則を再現可能な計算手順にします。納期の早い順（EDD）や優先度を考慮した指標は、説明しやすい初期案です。
分析・モデル化の考え方
単一ルールがあらゆるKPIに最適とは限りません。EDD、短時間順（SPT）、 順を同じ目的関数で評価します。
Pythonで確認する
t0=time.perf_counter()
rules={"EDD":np.argsort(due), "SPT":np.argsort(p), "due/priority":np.argsort(due/weight)}
rows=[]
for name,o in rules.items(): rows.append([name,"-".join(jobs.job.iloc[o]),score(o)])
heuristic_sec=time.perf_counter()-t0
heuristic_df=pd.DataFrame(rows,columns=["rule","order","objective"]).sort_values("objective")
display(heuristic_df)| rule | order | objective | |
|---|---|---|---|
| 0 | EDD | E-C-A-B-H-G-D-F | 133 |
| 1 | SPT | E-C-A-H-G-D-B-F | 136 |
| 2 | due/priority | E-B-G-A-C-H-D-F | 155 |
結果の読み取り
ルールによって結果が変わります。目的KPIと整合したルールを選び、例外処理を暗黙知のまま残さず記録することが重要です。
No.083：貪欲法
実務での意味
貪欲法は各時点で最も良い次ジョブを選び、短時間で完全な順序を作ります。緊急再計画の初期解に向きます。
分析・モデル化の考え方
未処理ジョブを末尾へ1件追加した際の遅れ増分が最小の候補を選びます。同点なら納期の早い方を優先します。ただし、先の影響を完全には見通しません。
Pythonで確認する
def greedy():
order=[]; remaining=set(range(n))
while remaining:
j=min(remaining,key=lambda x:(score(order+[x]),due[x],p[x]))
order.append(j); remaining.remove(j)
return np.array(order)
t0=time.perf_counter(); greedy_order=greedy(); greedy_sec=time.perf_counter()-t0
display(schedule(greedy_order))
print("貪欲解:", score(greedy_order))| sequence | job | completion_h | due_h | tardiness_h | priority | |
|---|---|---|---|---|---|---|
| 0 | 1 | E | 3 | 9 | 0 | 6 |
| 1 | 2 | C | 7 | 11 | 0 | 2 |
| 2 | 3 | A | 12 | 14 | 0 | 3 |
| 3 | 4 | H | 17 | 20 | 0 | 3 |
| 4 | 5 | G | 23 | 23 | 0 | 5 |
| 5 | 6 | F | 32 | 35 | 0 | 2 |
| 6 | 7 | D | 39 | 27 | 12 | 4 |
| 7 | 8 | B | 47 | 18 | 29 | 5 |
貪欲解: 193結果の読み取り
瞬時に実行可能案を返せますが、序盤の判断を後から取り消せません。この解を局所探索などの開始点にすると、速度と品質を両立しやすくなります。
No.084：局所探索法
実務での意味
既存計画の小さな入替えを繰り返すため、計画変更を段階的に改善できます。
分析・モデル化の考え方
2位置を交換する近傍を全て調べ、最良改善があれば移動します。近傍内で改善がなくなれば局所最適ですが、大域最適とは限りません。
Pythonで確認する
def local_search(start):
cur=np.array(start).copy(); history=[score(cur)]
while True:
best=cur; best_s=score(cur)
for i in range(n-1):
for j in range(i+1,n):
cand=cur.copy(); cand[i],cand[j]=cand[j],cand[i]
if score(cand)<best_s: best,best_s=cand,score(cand)
if best_s>=score(cur): break
cur=best.copy(); history.append(best_s)
return cur,history
t0=time.perf_counter(); local_order,local_hist=local_search(greedy_order); local_sec=time.perf_counter()-t0
plt.plot(local_hist,marker="o"); plt.title("Local search convergence"); plt.xlabel("Iteration"); plt.ylabel("Weighted tardiness"); plt.grid(True); plt.tight_layout(); plt.show()
print("局所探索解:",score(local_order),"反復:",len(local_hist)-1)
局所探索解: 126 反復: 2結果の読み取り
貪欲解から目的値が改善し、改善過程も追跡できます。初期解を複数変える、挿入近傍も加える、といった設計で局所最適への依存を弱められます。
No.085：焼きなまし法
実務での意味
焼きなまし法は、序盤には一時的な悪化も受け入れて局所最適を脱出し、終盤には改善へ集中します。
分析・モデル化の考え方
悪化量 の候補を確率 で受理し、温度 を徐々に下げます。乱数seed、初期温度、冷却率を保存すると再現できます。
Pythonで確認する
def anneal(start,seed=SEED,steps=2500):
r=np.random.default_rng(seed); cur=np.array(start).copy(); best=cur.copy(); hist=[]
for k in range(steps):
T=40*(0.002**(k/(steps-1))); i,j=r.choice(n,2,replace=False); cand=cur.copy(); cand[i],cand[j]=cand[j],cand[i]
delta=score(cand)-score(cur)
if delta<=0 or r.random()<np.exp(-delta/T): cur=cand
if score(cur)<score(best): best=cur.copy()
hist.append(score(best))
return best,hist
t0=time.perf_counter(); sa_order,sa_hist=anneal(greedy_order); sa_sec=time.perf_counter()-t0
plt.plot(sa_hist); plt.title("Simulated annealing: best-so-far"); plt.xlabel("Iteration"); plt.ylabel("Weighted tardiness"); plt.grid(True); plt.tight_layout(); plt.show()
print("焼きなまし解:",score(sa_order))
焼きなまし解: 126結果の読み取り
best-so-farを保存すれば、途中で悪化解を受理しても最良案を失いません。複数seedで品質の分布を確認し、時間上限内の安定性を評価します。
No.086：遺伝的アルゴリズム
実務での意味
複数の生産順序を同時に保持し、良い部分順序を組み合わせて探索します。候補の多様性を残せる点が特徴です。
分析・モデル化の考え方
順序交叉（OX）で重複のない子を作り、交換突然変異を加えます。エリート保存は最良解の劣化を防ぎます。
Pythonで確認する
def genetic(seed=SEED,pop_size=40,generations=100):
r=np.random.default_rng(seed); pop=[r.permutation(n) for _ in range(pop_size)]; hist=[]
for _ in range(generations):
pop=sorted(pop,key=score); new=[pop[0].copy(),pop[1].copy()]
while len(new)<pop_size:
a,b=r.choice(pop[:15],2,replace=False); lo,hi=sorted(r.choice(n,2,replace=False)); child=np.full(n,-1); child[lo:hi]=a[lo:hi]
fill=[x for x in b if x not in child]; child[child<0]=fill
if r.random()<.25: i,j=r.choice(n,2,replace=False); child[i],child[j]=child[j],child[i]
new.append(child)
pop=new; hist.append(score(min(pop,key=score)))
best=min(pop,key=score); return best,hist
t0=time.perf_counter(); ga_order,ga_hist=genetic(); ga_sec=time.perf_counter()-t0
plt.plot(ga_hist); plt.title("Genetic algorithm: best-so-far"); plt.xlabel("Generation"); plt.ylabel("Weighted tardiness"); plt.grid(True); plt.tight_layout(); plt.show()
print("遺伝的アルゴリズム解:",score(ga_order))
遺伝的アルゴリズム解: 126結果の読み取り
世代ごとの最良値が収束する様子を確認できます。集団が同じ順序ばかりになる場合は、突然変異率や初期集団の作り方を見直します。
No.087：タブーサーチ
実務での意味
直近の交換を一時的に禁止し、同じ順序を往復する循環を避けます。局所探索より広い探索を保ちやすい手法です。
分析・モデル化の考え方
交換したジョブ対を一定期間タブーリストへ入れます。ただし過去最良を更新する移動はアスピレーション基準により許可します。
Pythonで確認する
def tabu_search(start,iterations=120,tenure=7):
cur=np.array(start).copy(); best=cur.copy(); tabu={}; hist=[]
for k in range(iterations):
candidates=[]
for i in range(n-1):
for j in range(i+1,n):
cand=cur.copy(); moved=tuple(sorted((int(cur[i]),int(cur[j])))); cand[i],cand[j]=cand[j],cand[i]; s=score(cand)
if tabu.get(moved,-1)<=k or s<score(best): candidates.append((s,cand,moved))
s,cur,moved=min(candidates,key=lambda x:x[0]); tabu[moved]=k+tenure
if s<score(best): best=cur.copy()
hist.append(score(best))
return best,hist
t0=time.perf_counter(); tabu_order,tabu_hist=tabu_search(greedy_order); tabu_sec=time.perf_counter()-t0
plt.plot(tabu_hist); plt.title("Tabu search: best-so-far"); plt.xlabel("Iteration"); plt.ylabel("Weighted tardiness"); plt.grid(True); plt.tight_layout(); plt.show()
print("タブーサーチ解:",score(tabu_order))
タブーサーチ解: 126結果の読み取り
改善しない移動も使いながら探索を継続できます。タブー期間が短すぎると循環し、長すぎると探索の自由度が下がるため、問題規模に応じて検証します。
No.088：粒子群最適化
実務での意味
粒子群最適化（PSO）は、各候補が自身と集団の良い経験を共有して探索します。連続条件の最適化に強く、順序問題では表現上の工夫が必要です。
分析・モデル化の考え方
各ジョブへ連続値の優先キーを割り当て、その昇順を生産順序とする random-key 表現を使います。速度更新は です。
Pythonで確認する
def pso(seed=SEED,particles=35,steps=100):
r=np.random.default_rng(seed); x=r.normal(size=(particles,n)); v=np.zeros_like(x); pb=x.copy(); ps=np.array([score(np.argsort(z)) for z in x]); g=pb[np.argmin(ps)].copy(); hist=[]
for _ in range(steps):
v=.72*v+1.4*r.random(x.shape)*(pb-x)+1.4*r.random(x.shape)*(g-x); x+=v
s=np.array([score(np.argsort(z)) for z in x]); improve=s<ps; pb[improve]=x[improve]; ps[improve]=s[improve]; g=pb[np.argmin(ps)].copy(); hist.append(ps.min())
return np.argsort(g),hist
t0=time.perf_counter(); pso_order,pso_hist=pso(); pso_sec=time.perf_counter()-t0
plt.plot(pso_hist); plt.title("Particle swarm optimization: best-so-far"); plt.xlabel("Iteration"); plt.ylabel("Weighted tardiness"); plt.grid(True); plt.tight_layout(); plt.show()
print("粒子群最適化解:",score(pso_order))
粒子群最適化解: 126結果の読み取り
PSOでも順序を探索できますが、キーが変わっても順序が変わらない平坦領域があります。順序専用手法との比較なしに採用せず、表現変換の影響を確認します。
No.089：大規模近傍探索
実務での意味
計画の一部を大きく壊して作り直すため、複数ジョブをまとめて動かす必要がある局面に向きます。確定済み工程を固定する運用にも拡張できます。
分析・モデル化の考え方
ランダムに3ジョブを除去し、全挿入位置を調べながら1件ずつ戻します。現在解より良い場合に採用し、破壊・修復を反復します。
Pythonで確認する
def lns(start,seed=SEED,iterations=180,destroy=3):
r=np.random.default_rng(seed); cur=list(start); best=cur.copy(); hist=[]
for _ in range(iterations):
removed=list(r.choice(cur,destroy,replace=False)); partial=[x for x in cur if x not in removed]
for job in removed:
choices=[partial[:k]+[job]+partial[k:] for k in range(len(partial)+1)]; partial=min(choices,key=score)
if score(partial)<score(cur): cur=partial
if score(cur)<score(best): best=cur.copy()
hist.append(score(best))
return np.array(best),hist
t0=time.perf_counter(); lns_order,lns_hist=lns(greedy_order); lns_sec=time.perf_counter()-t0
plt.plot(lns_hist); plt.title("Large neighborhood search: best-so-far"); plt.xlabel("Iteration"); plt.ylabel("Weighted tardiness"); plt.grid(True); plt.tight_layout(); plt.show()
print("大規模近傍探索解:",score(lns_order))
大規模近傍探索解: 126結果の読み取り
小さな交換では越えにくい構造を、破壊と修復で探索できます。実務では「開始済みジョブは壊さない」「同一品種をまとめる」など、破壊可能範囲を業務制約に合わせます。
No.090：実務では厳密解にこだわりすぎない
実務での意味
現場価値は最適性だけで決まりません。再計画の速さ、解の安定性、説明可能性、運用制約への適合も含めて方式を選びます。
分析・モデル化の考え方
目的値、厳密解との差、計算時間を同じ表で比較します。許容ギャップ と時間上限を事前に定め、最良値更新が止まった場合の終了条件も設計します。
Pythonで確認する
methods={
"Exact enumeration":(exact_order,exact_sec), "Best rule":(rules[heuristic_df.iloc[0]["rule"]],heuristic_sec),
"Greedy":(greedy_order,greedy_sec), "Local search":(local_order,local_sec), "Simulated annealing":(sa_order,sa_sec),
"Genetic algorithm":(ga_order,ga_sec), "Tabu search":(tabu_order,tabu_sec), "PSO":(pso_order,pso_sec), "LNS":(lns_order,lns_sec)}
comparison=pd.DataFrame([[name,score(o),100*(score(o)-exact_score)/exact_score,sec,"-".join(jobs.job.iloc[list(o)])] for name,(o,sec) in methods.items()],columns=["method","objective","gap_pct","seconds","order"]).sort_values(["objective","seconds"])
display(comparison.round({"gap_pct":2,"seconds":4}))
plt.scatter(comparison.seconds,comparison.objective,s=55)
for _,r in comparison.iterrows(): plt.annotate(r["method"],(r.seconds,r.objective),xytext=(4,4),textcoords="offset points",fontsize=8)
plt.title("Solution quality and computation time"); plt.xlabel("Computation time (seconds)"); plt.ylabel("Weighted tardiness"); plt.grid(True); plt.tight_layout(); plt.show()| method | objective | gap_pct | seconds | order | |
|---|---|---|---|---|---|
| 3 | Local search | 126 | 0.00 | 0.0004 | E-C-A-B-G-H-D-F |
| 6 | Tabu search | 126 | 0.00 | 0.0179 | E-C-A-B-G-H-D-F |
| 7 | PSO | 126 | 0.00 | 0.0179 | C-E-A-B-G-H-D-F |
| 8 | LNS | 126 | 0.00 | 0.0212 | E-C-A-B-G-H-D-F |
| 4 | Simulated annealing | 126 | 0.00 | 0.0682 | E-C-A-B-G-H-D-F |
| 5 | Genetic algorithm | 126 | 0.00 | 0.1153 | C-E-A-B-G-H-D-F |
| 0 | Exact enumeration | 126 | 0.00 | 0.1657 | C-E-A-B-G-H-D-F |
| 1 | Best rule | 133 | 5.56 | 0.0005 | E-C-A-B-H-G-D-F |
| 2 | Greedy | 193 | 53.17 | 0.0002 | E-C-A-H-G-F-D-B |
結果の読み取り
この小規模例では厳密解を基準に各手法のギャップを確認できます。本番では、たとえば「60秒以内、基準計画比10%以上改善、既確定作業は固定」のように受入基準を業務単位で定めます。小さな目的値差のために指示が遅れたり計画が頻繁に変わったりするなら、厳密性より運用価値を優先すべきです。
対象ノックを通して見える実務上の示唆
- 厳密解は小規模データで近似法を検証する物差しとして有効です。
- 貪欲法は高速な初期解、局所探索は軽量な改善、メタヒューリスティクスは局所最適の脱出に使えます。
- ランダム手法はseedを固定するだけでなく、複数seedで目的値と所要時間の分布を評価します。
- 目的値だけでなく、計算時間、計画変更量、制約違反、説明可能性を運用KPIに含めます。
- 最良解、探索履歴、パラメータ、入力データ版を保存し、再現可能にします。
実務導入する場合に必要なこと
| 論点 | 確認事項 | 成果物 |
|---|---|---|
| 目的関数 | 遅延1時間の損失、顧客優先度、段取り費 | KPI定義書 |
| 制約 | 設備、人員、段取り、休憩、固定作業 | 制約一覧・例外一覧 |
| 品質基準 | 許容ギャップ、基準計画比、計算時間上限 | 受入基準 |
| 安定運用 | 複数seed、障害時のルール解、手修正 | 運用手順書 |
| 連携 | 受注・実績データ、計画確定時刻、出力先 | データ仕様・API仕様 |
| 監視 | 実績遅延、再計画回数、手修正率 | モニタリング画面 |
PoCでは、過去日の再現テストと担当者によるブラインド比較を行います。改善率だけでなく、入力不備や急な変更時にも安全な計画を返せるかを確認します。
まとめ
ヒューリスティクスとメタヒューリスティクスは、最適性の保証を捨てるための手法ではなく、限られた時間で意思決定価値を最大化するための選択肢です。小規模な厳密解で品質を測り、現場の時間制約と変更許容度に合わせて探索手法と終了条件を選ぶことが重要です。
法人向けのご相談
数理工房では、生産順序、設備・人員配置、配送、在庫などの最適化について、課題整理、データ診断、PoC、既存システムへの組込みまでご支援します。厳密解法と近似法を比較し、現場で継続利用できる意思決定プロセスを設計します。
📩 お問い合わせ: surikobo.co.jp/contact まずはお気軽にご相談ください。