ともかく入門 › メタヒューリスティクスと生産計画スケジューリング › 用語集と参考文献 Appendix 用語集と参考文献 A.1 用語集 (英日)
最適化の基礎
英語 日本語 備考 Combinatorial Optimization 組合せ最適化 離散変数を持つ最適化 Decision Variable 決定変数 モデルの未知数 Objective Function 目的関数 f Feasible Region 実行可能領域 F 制約を満たす解の集合 Optimal Solution 最適解 x* Lower / Upper Bound 下界 / 上界 LB ≤ f* ≤ UB Optimality Gap 最適性ギャップ (UB - LB) / LB NP-hard NP困難 すべての NP 問題と等価に難しい Polynomial Time 多項式時間 P クラス Pseudo-polynomial 擬多項式 入力数値にも依存 Approximation Ratio 近似比 近似解 / 最適
解法
英語 日本語 備考 Heuristic ヒューリスティック 経験則的解法 Metaheuristic メタヒューリスティック 上位枠組み Matheuristic マッチヒューリスティック 数理計画 × メタ Local Search 局所探索 Hill Climbing 山登り法 改善のみ Simulated Annealing (SA) 焼きなまし法 確率的悪化受入 Tabu Search タブー探索 禁止リストで循環防止 Iterated Local Search (ILS) 反復局所探索 摂動 + 局所探索 Variable Neighborhood Search (VNS) 可変近傍探索 複数近傍の切替 GRASP — 貪欲ランダム + 局所探索 Genetic Algorithm (GA) 遺伝的アルゴリズム 集団 + 交叉 Evolution Strategy (ES) 進化戦略 連続向け、CMA-ES Ant Colony Optimization (ACO) 蟻コロニー最適化 フェロモン構築 Particle Swarm Optimization (PSO) 粒子群最適化 群知能 Large Neighborhood Search (LNS) 大規模近傍探索 destroy-repair Adaptive LNS (ALNS) 適応的大規模近傍探索 オペレータ重みを学習 Path Relinking パスリリンキング 解間の中間解探索 Hyper-heuristic ハイパーヒューリスティック 選択 / 生成型 Branch and Bound 分枝限定法 厳密列挙 Branch and Cut 分枝カット法 B&B + 切除平面 Mixed Integer Programming (MIP) 混合整数計画 線形 + 整数 Constraint Programming (CP) 制約プログラミング 論理 + 伝播 Lagrangean Relaxation ラグランジュ緩和 下界の作成 Column Generation 列生成 大規模 LP の分解 Logic-Based Benders Decomposition (LBBD) 論理ベンダース分解 マスター + サブ問題
スケジューリング
英語 日本語 備考 Job / Task / Operation ジョブ / タスク / 工程 用語は文脈で混在 Makespan (Cmax ) 最大完了時刻 Tardiness (Tj ) 遅れ max(Cj −dj , 0) Lateness (Lj ) 遅刻 Cj −dj (負も可) Flow time (Fj ) フロータイム Cj −rj Setup time (sij ) 段取り時間 順序依存 Release time (rj ) リリース時刻 開始可能時刻 Due date (dj ) 納期 Dispatching Rule ディスパッチ規則 SPT, EDD 等 Critical Path クリティカルパス makespan を決める経路 Disjunctive Graph 対立グラフ JSP の表現 NoOverlap / Cumulative 排他 / 累積制約 CP の大域制約 Flexible Job Shop (FJSP) 柔軟ジョブショップ 機械選択あり Permutation Flow Shop (PFSP) 順列フローショップ
運用と業務
英語 日本語 備考 APS (Advanced Planning & Scheduling) 先進計画スケジューリング 商用パッケージカテゴリ MRP / MPS 資材所要量計画 / 基準生産計画 上位層 S&OP 販売生産計画 戦略層 BOM 部品表 製造の依存関係 Rolling Horizon ローリングホライズン 窓を前進させ再計画 Frozen Zone 凍結期間 計画変更を禁ずる近未来 Reactive Scheduling 再計画 イベント駆動 Robust Optimization ロバスト最適化 最悪を想定 Stochastic Programming 確率計画 分布を想定 Sample Average Approximation SAA シナリオの平均 Pareto Optimum パレート最適 多目的の支配されない解 What-if Analysis 反実仮想分析 L3 説明可能性
A.2 参考文献
教科書
Pinedo, M. — Scheduling: Theory, Algorithms, and Systems (Springer, 6th ed., 2022). スケジューリングの定番。第7章の Graham 表記、ベンチマーク、各種多項式アルゴリズムの出典。
Wolsey, L. — Integer Programming (Wiley, 2nd ed., 2021). 整数計画の標準教科書。
Rossi, F.; van Beek, P.; Walsh, T. — Handbook of Constraint Programming (Elsevier, 2006). CP の包括的リファレンス。
Gendreau, M.; Potvin, J.-Y. — Handbook of Metaheuristics (Springer, 3rd ed., 2019). メタヒューリスティクスの最も網羅的なハンドブック。
Talbi, E.-G. — Metaheuristics: From Design to Implementation (Wiley, 2009). 実装視点の解説。
Hooker, J.N. — Integrated Methods for Optimization (Springer, 2nd ed., 2012). CP, MIP, LBBD の融合。LBBD の原典近く。
原著論文 (主要なもの)
Kirkpatrick, S.; Gelatt, C.D.; Vecchi, M.P. — “Optimization by Simulated Annealing,” Science , 1983.
Glover, F. — “Tabu Search — Part I,” ORSA Journal on Computing , 1989.
Lin, S.; Kernighan, B.W. — “An Effective Heuristic Algorithm for the Traveling-Salesman Problem,” OR , 1973.
Holland, J.H. — Adaptation in Natural and Artificial Systems , 1975.
Dorigo, M. — “Optimization, Learning and Natural Algorithms” (PhD), 1992 — ACO 原典。
Ropke, S.; Pisinger, D. — “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows,” Transportation Science , 2006.
Nowicki, E.; Smutnicki, C. — “A Fast Taboo Search Algorithm for the Job Shop Problem,” Management Science , 1996.
Sörensen, K. — “Metaheuristics—the metaphor exposed,” ITOR , 2013 — 動物名アルゴリズム批判。
Wolpert, D.H.; Macready, W.G. — “No Free Lunch Theorems for Optimization,” IEEE TEC , 1997.
近年の研究 (2020〜2026 主要)
Kool, W.; van Hoof, H.; Welling, M. — “Attention, Learn to Solve Routing Problems!,” ICLR , 2019.
Zhang, C. et al. — “Learning to Dispatch for Job Shop Scheduling via Deep RL,” NeurIPS , 2020 (L2D).
Kwon, Y.-D. et al. — “POMO: Policy Optimization with Multiple Optima,” NeurIPS , 2020.
Wang, R. et al. — “Flexible Job Shop Scheduling via Dual Attention Network Based RL,” arXiv:2305.05119 , 2023.
Liu, Z. et al. — “Multi-Agent Deep RL for Dynamic Flexible Job Shop Scheduling,” Processes , 2025.
Mao, X. et al. — “An adaptive large neighborhood search algorithm for parallel machine scheduling,” 2024.
Xu, Y. et al. — “Learning-Guided Rolling Horizon Optimization for Long-Horizon Flexible Job-Shop Scheduling,” arXiv:2502.15791 , 2025.
ライブラリと実装
ベンチマーク
A.3 学び続けるための導線
論文 : arXiv の cs.AI / math.OC / cs.DM、Computers & Operations Research、European Journal of OR、Transportation Science、International Journal of Production Research。カンファレンス : INFORMS Annual Meeting、CPAIOR (CP + AI + OR)、MIC (Metaheuristics International Conference)、IJCAI、NeurIPS の OR ワークショップ。コミュニティ : OR-Exchange (Stack Exchange 系)、Google OR-Tools discuss。ベンチマーク参戦 : ROADEF Challenge、DIMACS Implementation Challenge、Google Hash Code (引退) の後継。
A.4 索引 (主要キーワード)
第何章で詳しく扱ったかを索引化する。深掘りの起点として。
キーワード 章 2-opt / 3-opt 3 ACO 5 ALNS 5, 9 Branch & Bound 6 Clarke-Wright 2 Column Generation 6 CP-SAT 6, 7, 9 Critical Path 3, 7 Disjunctive Graph 7 Dispatching Rules 2 EDD / SPT 2 Frozen Zone 8 FJSP 7, 8 GA 5 Graham 表記 7 GRASP 2, 4 Hill Climbing 3 ILS 4 JSP 1, 3, 7 Lagrangean Relaxation 6 LBBD 6 Lin-Kernighan 3 LNS 5 Matroid 2 MIP 6 Neural Combinatorial Optimization 5, 9 NP-hard 1 No Free Lunch 1 NoOverlap / Cumulative 6, 7 Pareto 8 Path Relinking 5 PSO 5 Robust Optimization 8 Rolling Horizon 8 Simulated Annealing 4 Tabu Search 4 VNS 4 What-if 8, 9