日本オペレーションズ・リサーチ学会
2021年 秋季研究発表会

2-B-4

ボトルネック・シフティング法による建設施工計画立案時間の短縮
05001436 鹿島建設株式会社
鹿島建設株式会社
鹿島建設株式会社
鹿島建設株式会社
鹿島建設株式会社
1. はじめに筆者らは熟練労働者不足への対応、施工生産性の向上、労働災害の撲滅などの建設業界における重要な課題解決を目的とし、「現場の工場化」を目指して、建設機械の自動化を核とした次世代建設生産システ
ムの開発を進めている[1]。
自動化した建機を稼働させるためには全ての作業を定量的に指示する必要がある[2]。例えば、ダム建設工事で約 30 台の重機を稼働させるには 6 時間あたり約 750 の作業データ（施工計画）が必要となる（図1）。次世代建設生産システムでは、現場での運用を考え、これらの作業データの作成を 2 分程度で行うことを目標としている。しかしながら、人手により約750 もの作業データを 2 分程度で作成することは困難である。また、施工作業時間（メイクスパン）やコスト、さらには安全性がより高くなるように施工計画を立案することが重要である。
こうした課題を踏まえ、次世代建設生産システム
では、施工計画の立案・最適化を図るスケジューラ（以下、最適化スケジューラ）を開発している。しかしながら、現在、最適化スケジューラを用いた 6 時間分の施工計画の立案に 5 分程度かかっており、目標の 2 分程度には及ばない。
そこで、本稿では、施工計画立案時間の短縮を目的に、生産スケジューリングの分野で実績のあるボトルネック・シフティング法[3]に基づく局所探索法を最適化スケジューラに組み込んだ結果を報告する。
2. 最適化スケジューラ
最適化スケジューラは、製造工場の製造計画立案に使われていた生産スケジューラをベースに開発した。製造工場には、何千もの繰り返し作業があり、各作業時間のばらつきが小さいという特徴がある。次世代建設生産システムでは、自動化機械を使うため作業時間のばらつきが小さく、生産スケジューラの援用に適している。
また、ダム建設工事は、材料の切出し、ダンプト*高見出石青木浜本三浦聡
陽一
恒研一
悟TAKAMI Satoshi
IZUSHI Yoichi
AOKI Hisashi
HAMAMOTO Kenniti
MIURA Satoru

図 1 ダム建設工事の 6 時間分の作業データの例
ラックによる材料の運搬、ブルドーザによる材料のまき出し、振動ローラによる材料の転圧から成る一連の作業の繰り返しによって施工される。その一連の作業をジョブと見做し、各作業で使用する建機を機械とすると、我々の扱う問題は、生産スケジューラが扱うジョブ・ショップ型のスケジューリング問題となる。最適化スケジューラでは、このジョブ・ショップ問題を、施工作業時間やコストなどを評価指標とし、各作業を遺伝子と考えて遺伝的アルゴリズムを使って解く。
3. ボトルネック・シフティング法
遺伝的アルゴリズムに局所探索法を組合せることこで、解の収束が早くなる結果が従来から報告されている[4]。また、例えばイジェクション・チェイン法[5]など、局所探索法における近傍解の生成方法が異なる種々の手法が提案されている。その中で、ボトルネック・シフティング法は、我々が扱っているジョブ・ショップ型のスケジューリング問題などに適用され、実績のある手法である。
ボトルネック・シフティング法（以下、BS 法）は、施工作業時間を決めているのはクリティカルチェインなのだから、クリティカルチェイン上の作業を改善すれば、施工作業時間も改善する、という考えに基づく局所探索法である。
ダム工事は、ブルドーザによる材料のまき出しが終わっていなければ振動ローラによる転圧はできな

いなどの作業の順序関係が存在し、その順序関係によって全作業が、プロジェクト・スケジューリングと同様のネットワークを構成する。ダム工事の施工計画におけるクリティカルチェインは、このネットワークにおける最長のパスを構成するチェインとして定義する。そして、このクリティカルチェインの作業の処理順番を入れ換えて近傍解を生成するように最適化スケジューラを改良する。
4. 数値解析4.1 計算条件と結果
図 2 は、従来手法と提案手法を使って、6 時間分の施工計画を立案した時の施工作業時間の収束の様子を表している。ここで、6 時間分の施工計画とは、計算結果の施工作業時間が約 6 時間となるように、各作業の繰り返し回数を調整した施工計画である。計算のパラメータは、人口 100、突然変異確率は 0.001、交叉確率は 0.5 である。また、反復回数は、収束したかどうかに関わらず、100 回で計算を打ち切った。従来手法、および提案手法の計算をそれぞれ 3 回試行した。図中では、従来手法の計算結果を黒破線で、提案手法の計算結果を赤破線で囲んでいる。また、両手法で実用解が得られた反復回数の所に、従来手法は黒点線、提案手法は赤点線を記した。
4.2 考察表 1 に、従来手法と提案手法の収束に要した反復回数と計算時間をまとめた。従来手法は、収束に 40回の反復回数が必要であったのに対し、提案手法は反復回数 10 回で収束した。
従来手法の反復回数 40 回の計算時間は 4 分 48 秒なのに対し、提案手法の反復回数 10 回の計算時間は 2 分 6 秒となった。従来手法と提案手法の反復回数 100 回の計算時間は、それぞれ約 12 分と約 21 分である。提案手法は、個々の反復の計算時間が 2 倍になっているが、収束に必要な反復回数が 4 分の 1 になっているので、結果として計算時間を従来手法の約 2 分の 1 に短縮できた。
図 2 から判るように、従来手法の施工作業時間の収束値と、提案手法の施工作業時間の収束値に有意な差はなく、従来の遺伝的アルゴリズムに BS 法を組み込んでも同等な各評価値が得られた。
表 1 計算時間と必要反復回数
必要反復回数
計算時間
従来手法
40 回
4 分 48 秒
提案手法
10 回
2分6秒
5. まとめ施工計画立案時間の短縮を目的として、遺伝的アルゴリズムへ BS 法の組込みを行った。その結果、従来の手法と比較して、計算時間を半分程度に短縮できることが分かり、2 分程度という目標を達成した。
参考文献[1] 三浦悟，黒沼出，浜本研一：建設機械の自動化を核とした次世代施工システム，建設機械施工，Vol. 67, No. 12, 2015，
pp. 21-25．
[2] 高見聡，出石陽一，青木恒，浜本研一，三浦悟：自動化施工システムにおける施工計画作成への最適化手法の導入，土木学会第 75 回年次学術講演会，VI-1151，2020[3] J. Adams, E. Balas, D. Zawack：
The Shifting Bottleneck Procedure
for Job Shop Scheduling，MANAGEMENTSCIENCE, Vol. 34, No. 3, March 1988，
pp.391-401.
[4] 三宮信夫，玉置久，喜多一，岩本貴司：遺伝的アルゴリズムと最適化，
朝倉書店出版，1998．
[5] F. Glover ： Ejection Chain,reference

structures

andalternating

pathfortravelingsalesmanmethods

problems,

Discrete Applied Mathematics, Vol.
65, 1996, pp.223-253

図 2 施工作業時間の収束の様子