クレーン搬送を伴うジョブショップ
スケジューリング問題の厳密解法に関する研究
神奈川大学
小林幸祐

工学部 経営工学科
太田和希 周暁棟

指導教員

片桐英樹

1

CONTENTS
1.イントロダクション
・研究背景
・先行研究と研究目的
・問題設定

2.定式化
・集合、定数、決定変数
・目的関数
・制約式

3.数値実験
4.まとめ2

1.イントロダクション
研究背景：クレーンを使用する製造業

複数のクレーンを使用して搬送を行う施設は数多く存在する

例）鉄鋼の製造工場やバイオマス発電所など
少子高齢化による労働力人口の減少が問題となっている
2000年から2030年には600万人減少[1]DXによる業務効率化，生産性向上が求められている製造業における約70%[2]の企業がDXによる業務改善を期待

製品を効率よく製造するための生産スケジューリングの自動作成は益々重要になる
2021年

学生研究奨励賞

31.イントロダクション
研究背景：クレーン干渉
クレーンを用いた生産現場では，互いのクレーンが衝突を防ぐため安全距離を保っている
クレーン1がjob1を機械5に搬送し，クレーン2がjob2を機械3に搬送する状況
安全距離
クレーン１

クレーン同士の衝突を防ぐ必要あり

機械1

機械2

クレーン２
job
1

job
2

機械３

機械4

2021年

学生研究奨励賞

機械54

1.イントロダクション
研究背景：クレーン干渉
互いのクレーンが衝突を防ぐため，どちらかのクレーンが搬送先の機械とは反対方向の移動が必要

クレーン１
Job2の搬送を優先させると，クレーン1を左に移動させる必要がある

機械1

機械2

クレーン２
job
1job
2

機械３

機械4

2021年

学生研究奨励賞

機械55

1.イントロダクション
研究背景：クレーン干渉
クレーン1は，機械3の位置から左(搬送先とは反対方向)に移動したので，クレーン干渉が発生しクレーンの移動時間が増加

クレーン干渉は，生産スケジュールに大きな影響を与える
安全距離
クレーン２

クレーン１
job
1

クレーン干渉発生クレーン移動時間増加
job
2

機械1

機械2

機械３

機械4

2021年

学生研究奨励賞

機械5
6

1.イントロダクション
先行研究

クレーン干渉に関する研究(Ng[3](2005))
クレーン干渉を考慮する必要があるスケジューリング問題に対して，クレーン干渉を防ぐ整数プログラムを提案し，ヒューリスティックを用いて最適なスケジュールを導き出した
スケジューリング問題の定式化に関する研究(Zeng[4](2018))
2台のヤードクレーンを用いて，コンテナターミナルで発生する実用的な運用問題を整数線形計画モデルを構築した．タスクの数が少ない問題に対して厳密解法を用いて解の導出に成功した
ジョブショップスケジューリング問題に関する研究(片桐[5](2019))
クレーン搬送を伴うNP困難なジョブショップスケジューリング問題
に対し，ジョブ処理順序最適化とクレーン割り当て最適化を組み合わせたヒューリスティック解法を提案した
2021年

学生研究奨励賞

7

1.イントロダクション
本研究の目的ヤードクレーンの干渉を考慮した厳密解法についての定式化を行った研究は存在する
しかし，クレーン干渉を考慮したジョブショップスケジューリングに関する厳密解法についての研究は見受けられない

本研究の目的クレーン干渉を考慮したジョブショップスケジューリング問題に対しての厳密解法の提案

2021年

学生研究奨励賞

8

1.イントロダクション
問題設定
クレーン１

クレーン２

安全距離(アドレス1つ分)
job
2

機械1

機械2

job
1・・・・・・

機械3・・・・・・・・・・・・

機械𝑁

機械の位置はアドレスで与えられる
𝑙1 = 1𝑙2

𝑙𝑁 = 𝑙𝑚𝑎𝑥

𝑙3[アドレス]
機械1は，製造前のジョブが置いてある場所
機械𝑁は完成したジョブの置き場
機械1と機械𝑁はいくつでもジョブが置けるがそれ以外は1つしか置けない
処理時間は，機械1と機械𝑁は0としそれ以外の機械での処理時間を考慮する
2021年

学生研究奨励賞

91.イントロダクション
問題設定
クレーン１

クレーン２

クレーン ①1
割当
job
2

機械1

②2

③1

機械2

job
1・・・・・・

機械3

・・・・・・・・・・・・

機械𝑁

機械の位置はアドレスで与えられる
𝑙1 = 1𝑙2

𝑙𝑁 = 𝑙𝑚𝑎𝑥

𝑙3

クレーン作業順
クレーン割当① ② ③
12[アドレス]

1

各ジョブの処理順序に従って，ジョブの搬送に対するクレーン割当を決定する
2021年

学生研究奨励賞

10

2.定式化
集合・定数集合・定数

𝐽:ジョブの集合
𝑁:機械の数
𝑀 = 1,2 … , 𝑁 :機械の集合
𝐽𝑖 :機械𝑖 ∈ 𝑀で処理されるジョブの集合
𝐾 = 1,2 :クレーンの集合
𝐿 = 1,2, … , 𝑙𝑚𝑎𝑥 :クレーンが移動できる場所（アドレス）の集合
アドレス1つ分が安全距離とする
T = 0,1, … , 𝑡𝑚𝑎𝑥 :時刻の集合
𝐻𝑗 = 1,2 … , 𝑚𝑗 :ジョブ𝑗 で処理される作業番号の集合
𝑗𝑗𝑗𝑗𝑚𝑗 = {𝜎1 , 𝜎2 , … 𝜎ℎ , … 𝜎𝑚𝑗 }:ジョブ𝑗を処理する機械の集合

2021年

学生研究奨励賞

112.定式化集合・定数集合・定数
𝑙𝑖 :機械𝑖が位置するアドレス(ただし，𝑙1 = 1, 𝑙𝑁 = 𝑙𝑚𝑎𝑥 とする）
𝑚𝑗 :ジョブ𝑗 で処理される作業工程数
𝑗𝜎ℎ :ジョブ𝑗をℎ番目に処理する機械
𝑡 𝑖,𝑗 ,(𝑖 ′,𝑗) :ジョブ𝑗の機械𝑖における作業終了後に機械𝑖′へクレーンで搬送する時間（クレーンの上げ下げ時間を含む）
𝐺:大きな正数

2021年

学生研究奨励賞

122.定式化
決定変数(1)
決定変数

𝑥𝑖,𝑗,𝑡 :機械𝑖 におけるジョブ𝑗の作業を時刻𝑡に開始するならば1,開始しないならば0

𝜀𝑖,𝑗 :機械𝑖におけるジョブ𝑖の作業開始時刻
𝛿𝑖,𝑗 :機械𝑖 におけるジョブ𝑗の作業終了時刻
𝑠𝑖,𝑗 :機械𝑖 におけるジョブ𝑗の（作業終了後の）クレーン搬送開始時刻
𝑟𝑖,𝑗 :機械𝑖におけるジョブ𝑗の（作業終了後の）クレーン搬送終了時刻
𝜂𝑖,𝑗,𝑡 :機械𝑖 におけるジョブ𝑗の作業終了後に時刻𝑡でクレーン搬送を開始するならば1, 開始しないならば0𝐶𝑚𝑎𝑥 :最後のジョブが最後の機械に到着した時刻(メイクスパン)
2021年

学生研究奨励賞

13

2.定式化
決定変数(2)
決定変数𝑘
𝜏𝑖,𝑗,𝑡:時刻𝑡 にクレーン𝑘 がアドレス𝑙に位置していれば1, 位置していなければ0𝑘𝜉𝑖,𝑗,𝑡:機械𝑖 におけるジョブ𝑗 の作業終了後に時刻𝑡でクレーン𝑘 で搬送するならば1,搬送しないならば0𝛽𝑘𝑖,𝑗 ,(𝑖 ′ ,𝑗 ′ ) :クレーン𝑘で搬送する2つの異なるジョブ𝑗, 𝑗’ について，機械𝑖におけるジョブ𝑗の作業終了後のクレーン搬送開始時刻が機械𝑖′におけるジョブ𝑗′の作業終了後のクレーン搬送開始時刻よりも先ならば1,後ならば0𝑖
𝛾𝑗,𝑗′ :機械𝑖において（作業を終了した）ジョブ𝑗をジョブ𝑗′よりも先にクレーンで搬送するならば1, 搬送しないならば02021年

学生研究奨励賞

14

*制約式は一部抜粋したものだけ説明
2.定式化
目的関数と制約式(1)：メイクスパン
目的関数

min 𝐶𝑚𝑎𝑥

メイクスパンの最小化
制約式(1)𝑟𝜎𝑗

𝑚𝑗−1 ,𝑗≤ 𝐶𝑚𝑎𝑥 ∀𝑗 ∈ 𝐽

メイクスパン𝐶𝑚𝑎𝑥 は最後のクレーン搬送されるジョブの搬送終了時刻に等しい
最後のジョブが最後の機械に到着した時刻をメイクスパンとする

job
j

最後の機械に到着したとき
jobj𝑗𝜎𝑚𝑗−1
2021年

学生研究奨励賞

𝑡 = 𝑟𝜎𝑗𝑚𝑗−1 ,𝑗𝑗𝜎𝑚𝑗
15

*制約式は一部抜粋したものだけ説明
2.定式化
制約式(2)：2つ以上のジョブを同時に処理できない

制約式(2)m𝑖𝑛(𝑡,𝑡𝑚𝑎𝑥 −𝑝𝑖𝑗 +1)෍෍

𝑥𝑖,𝑗,𝑡 ′ ≤ 1𝑗∈𝐽𝑖𝑡 ′ =max(0,𝑡−𝑝𝑖𝑗 +1)∀𝑖 ∈ 𝑀 ∖ 1, 𝑁 , 𝑡 ∈ 𝑇

機械1と機械𝑁以外の機械は同時に２つ以上のジョブを処理できない

設置不可

job
j’job
j
機械𝑖
2021年

学生研究奨励賞

16

*制約式は一部抜粋したものだけ説明
2.定式化
制約式(3)：作業開始時刻と作業終了時刻の関係

制約式(3)
𝛿𝜎𝑗 ,𝑗 = 𝜖𝜎𝑗 ,𝑗 + 𝑝𝜎𝑗 ,𝑗 ∀𝑗 ∈ 𝐽, ℎ ∈ 𝐻𝑗 ∖ {𝑚𝑗 }ℎℎℎ

すべてのジョブの作業工程において，作業終了時刻は作業開始時刻に作業時間を加算した時刻に等しい

作業開始

作業終了

job
j𝑝𝜎𝑗 ,𝑗 時間後ℎ𝑗𝜎ℎjob
j𝑗𝜎ℎ𝑡𝑡𝜖𝜎𝑗 ,𝑗𝛿𝜎𝑗 ,𝑗ℎℎ2021年

学生研究奨励賞

17*制約式は一部抜粋したものだけ説明
2.定式化
制約式(4)：クレーン搬送開始時刻とクレーン搬送終了時刻の関係

制約式(4)
𝑟𝜎𝑗ℎ−1 ,𝑗= 𝑠𝜎 𝑗ℎ−1 ,𝑗+ 𝑡 𝜎𝑗∀𝑗 ∈ 𝐽, ℎ ∈ 𝐻𝑗 ∖ {1}𝑗ℎ−1 ,𝑗 , 𝜎ℎ ,𝑗

すべてのジョブの作業工程のおいて，(作業終了後の)クレーン搬送終了時刻はクレーン搬送開始時刻に施設間のクレーン搬送時間を加えた時刻に等しい②③①job
j𝑗

𝑗

𝜎ℎ−1
𝑠𝜎 𝑗

ℎ−1 ,𝑗2021年

𝜎ℎ𝑡 𝜎𝑗𝑗ℎ−1 ,𝑗 , 𝜎ℎ ,𝑗

学生研究奨励賞

𝑟𝜎𝑗ℎ−1 ,𝑗𝑡18*制約式は一部抜粋したものだけ説明
2.定式化
制約式(5)：クレーンは1秒につき1アドレス分しか移動できない

制約式(5)𝑘𝑘𝑘𝑘𝜏𝑙,𝑡≤ 𝜏𝑙−1,𝑡+1+ 𝜏𝑙,𝑡+1+ 𝜏𝑙+1,𝑡+1∀𝑙 ∈ 𝐿 ∖ {1, 𝑙𝑚𝑎𝑥 }, 𝑡 ∈ 𝑇 ∖ {𝑡𝑚𝑎𝑥 }, 𝑘 ∈ 𝐾

すべての時刻𝑡において，クレーン𝑘は1 秒で1 アドレス分しか移動できない
𝑘
𝜏𝑙,𝑡L
クレーン𝑘
1秒後

𝑘𝑘
𝜏𝑙,𝑡+1𝜏𝑙−1,𝑡+1𝑘𝜏𝑙+1,𝑡+111秒後には，もとの位置しかその両隣のアドレスにしか移動できないL

クレーン𝑘2021年

学生研究奨励賞

19

*制約式は一部抜粋したものだけ説明
2.定式化
制約式(6)：時刻0におけるクレーンの位置制約式(6)
1
𝜏1,0, 𝜏𝑙2𝑚𝑎𝑥,0

時刻0の初期状態においてのクレーンの初期位置は決まっている
1𝑙𝑚𝑎𝑥

時刻0におけるクレーンの位置状態L
クレーン１

クレーン２

𝑙𝑚𝑎𝑥 は機械の数に依存するEx)機械の数が5台なら𝑙𝑚𝑎𝑥 は機械5の位置を示す
機械1

機械𝑁
2021年

学生研究奨励賞

20

*制約式は一部抜粋したものだけ説明
2.定式化
制約式(7)：クレーン同士の入れ替わり，重なり合いは不可能

制約式(7)
21
෍ 𝑙 ・𝜏𝑙,𝑡≥ ෍ 𝑙 ・𝜏𝑙,𝑡+1𝑙∈𝐿∀𝑡 ∈ 𝑇𝑙∈𝐿

すべての時刻において，クレーン同士は入れ替わることも重なり合うこともない
1
𝜏𝑙,𝑡2
𝜏𝑙+1,𝑡1
𝜏𝑙+4,𝑡

クレーン１

クレーン２

クレーン１

お互いに追い越すことはできない

2021年

学生研究奨励賞

L21

*制約式は一部抜粋したものだけ説明
2.定式化
制約式(8)：クレーン𝑘は，搬送終了時刻には搬送先に位置する
制約式(8)𝑘𝑘
𝜏𝑙𝑘 𝑗 ,𝑡+𝑡 𝑗≥
𝜉+𝜂
−1𝑗𝑗𝑗
σℎ+1σℎ ,𝑗,𝑡(σ ,ℎ),(σ,ℎ)ℎℎ+1

σℎ ,𝑗,𝑡∀𝑗 ∈ 𝐽, ℎ ∈ 𝐻𝑗 ∖ 𝑚𝑗 , 𝑡 ∈ [0, 𝑡𝑚𝑎𝑥 − 𝑡(σ𝑗 ,ℎ),(σ𝑗ℎℎ+1 ,ℎ)], 𝑘 ∈ 𝐾

時刻𝑡 でクレーン𝑘 がジョブ𝑗 のℎ 番目の作業終了後の搬送を処理していて，かつその時刻に搬送処理を開始するならば，その搬送時間経過後の時刻に
クレーン𝑘 はジョブ𝑘の ℎ + 1 番目作業場所に位置している
クレーン𝑘

クレーン𝑘job
j𝑗

𝜎ℎ

2021年

𝑗

𝜎ℎ+1𝑡(クレーン搬送開始時刻） 𝑡 + 𝑡(σ𝑗ℎ,ℎ),(σ𝑗ℎ+1 ,ℎ)

学生研究奨励賞

𝑇22

*制約式は一部抜粋したものだけ説明
2.定式化
制約式(9)：搬送先にジョブがあるときのクレーン搬送終了時刻

制約式(9)
𝑖𝑟𝑖 ′ ,𝑗 ′ ≥ 𝑠𝑖,𝑗 + 1 − 1 − 𝛾𝑗,𝑗′ 𝐺𝑗′𝑗′𝑗∀𝑖, 𝑖 ′ ∈ 𝑀, 𝑖 ≠ 𝑖 ′ , 𝑗, 𝑗 ′ ∈ 𝐽𝑖, , 𝑗 ≠ 𝑗 ′ , 𝜎ℎ′ −1 = 𝑖 ′ , 𝜎ℎ′ = 𝜎ℎ = 𝑖, ℎ ∈ 𝐻𝑗 ∖ 𝑚𝑗 , ℎ′ ∈ 𝐻𝑗 ′ ∖ {1, 𝑚′𝑗 }同じ機械で処理する2つの異なるジョブについて，クレーンの搬送順序が𝑗, 𝑗′のときジョブ𝑗のクレーン開始時刻よりも後にジョブ 𝑗′のクレーン搬送終了時刻でなければいけない

job
j’

②

①
job
j
機械𝑖

𝑠𝑖,𝑗2021年

𝑠𝑖,𝑗 + 1
学生研究奨励賞

𝑇23

*制約式は一部抜粋したものだけ説明
2.定式化
制約式(10)：クレーン 𝑘で搬送する2つの異なるジョブ𝑗, 𝑗′の搬送開始時刻

制約式(10)𝑠σ𝑗 ,𝑗 ≥ 𝑟 𝑗′ ′ + 1 − 1 − 𝛽 𝑘 𝑗′ℎ𝑗

σ ′ ,𝑗 ′ , σℎ ,𝑗σ ′ ,𝑗ℎGℎ∀𝑗, 𝑗 ′ ∈ 𝐽𝑖, , 𝑗 ≠ 𝑗 ′ , ℎ ∈ 𝐻𝑗 ∖ 𝑚𝑗 , ℎ′ ∈ 𝐻𝑗 ′ ∖ {1, 𝑚′𝑗 }クレーン 𝑘で搬送する2つの異なるジョブ𝑗, 𝑗′について，ジョブ𝑗のℎ 番目の作業終了後の搬送をジョブ𝑗のℎ番目の作業終了後の搬送よりも先に行うならば，クレーン𝑘によるジョブの搬送開始時刻はクレーン搬送順序によって決まる

クレーン 𝑘クレーン 𝑘クレーン 𝑘
job
j’𝑗′

𝑗′

σℎ′ −1 , 𝑗 ′σℎ ′ , 𝑗 ′

𝑠 𝑗′

𝑟 𝑗′

σ ′

ℎ −1,𝑗 ′job
jσ ′ℎ,𝑗 ′2021年

𝑗σℎ ,j𝑟 𝑗′ ′ + 1
σ ′ ,𝑗ℎ

学生研究奨励賞

𝑠σ𝑗 ,𝑗𝑇ℎ24

*制約式は一部抜粋したものだけ説明
2.定式化
制約式(11)：クレーン𝑘は多くとも一つのジョブを搬送制約式(11)෍𝜉 𝑘𝑗

෍𝑗∈𝐽 ℎ∈𝐻𝑗 ∖{𝑚𝑗 }σℎ ,𝑗,𝑡≤ 1 ∀𝑡 ∈ 𝑇, 𝑘 ∈ 𝐾

時刻𝑡において，それぞれのクレーン𝑘は多くとも一つのジョブを搬送している（すべての時刻でクレーンは多くとも一つの搬送ジョブを処理している）
クレーン𝑘

クレーン𝑘
時刻𝑡において,クレーンは2つのジョブを搬送することはできない

job
jjob jobjj’

𝑗𝜎ℎ+1𝑗′

2021年

学生研究奨励賞

𝜎ℎ𝑗

25

25

3.数値実験①
ジョブ数2，機械数5のジョブショップの条件
表1:数値実験①の各ジョブの加工順序
加工順

12345job1

13425job2

12435ジョブNo.

表2：各機械のジョブに対する処理時間 単位[s]機械No.

12345job104580job2

07540ジョブNo.

表3：ジョブの搬送に対する移動時間 単位[s]
機械No.
機械No.

1

1234531119238162081223311841916852320

12

時刻0における初期状態において，クレーン1はアドレス1にクレーン2はアドレス24に位置する

4420-12=8s

12-1=11s

機械1

機械2

機械3

機械4

機械5

[アドレス]
14122021年

20

学生研究奨励賞

24

26

3.数値実験①
ジョブ数2，機械数5のジョブショップの結果：メイクスパン
メイクスパン:117

メイクスパン

図1：パターン①のガントチャート
2021年

学生研究奨励賞

27

3.数値実験①
ジョブ数2，機械数5のジョブショップの結果：クレーンの動き
アドレス1つ分だけずれて移動

図2：パターン①のクレーンの動き
2021年

学生研究奨励賞

28

3.数値実験②
ジョブ数2，機械数6のジョブショップの条件
表4:数値実験②の各ジョブの加工順序

表5：各機械のジョブに対する処理時間単位[s]加工順
ジョブNo.

123456

機械No.
ジョブNo.

job1

124356

job1036480

job2

154236job2054790

機械No.

11234563111923318162028

812204122

33118419168523

2012463128

20

128

3456

時刻0における初期状態において，クレーン1はアドレス1にクレーン2はアドレス32に位置する

84-1=3s

機械1

2単位[s]

表6：ジョブの搬送に対する移動時間
機械No.

132-12=20s

機械2

機械3

機械4

機械5

機械6[アドレス]14122021年

20
学生研究奨励賞

2432
29

3.数値実験②
ジョブ数2，機械数6のジョブショップの結果：メイクスパン

メイクスパン:142

メイクスパン

図3：パターン②のガントチャート
2021年

学生研究奨励賞

30

3.数値実験②
ジョブ数2，機械数6のジョブショップの結果：クレーンの動き

クレーンは重ならずに移動している

図4：パターン②のクレーンの動き
2021年

学生研究奨励賞

31

4.まとめ今後の課題➢ クレーン干渉を考慮したジョブショップスケジューリング問題に対して定式化を行った➢ ジョブ数2，機械数5と機械数6のジョブショップスケジューリング
問題に対して厳密解を求めることができた
今後の課題➢ ジョブの数，機械の数を増やしたより大規模な問題に対しての適用➢ 解導出時間の高速化

2021年

学生研究奨励賞

32

参考文献[1]厚生労働省,労働経済の基礎的資料,ホーム｜厚生労働省 (mhlw.go.jp)(2021/12/2参照)[2]日経XTEC，設計・生産革新，製造業300社と現場3000人に聞いたDXの本音,製造業300社と現場3000人に聞いたDXの本音 | 日経クロステック（xTECH） (nikkei.com)(2021/12/2参照)[3]W.C.Ng, “Crane scheduling in container yards with intercrane interference “European Journal of Opearational Research,vol.164,pp.64-78(2005)[4]Feifeng Zheng et al., “Two Yard Crane Scheduling With DynamicProcessing Time and Interference”,IEEE TRANSACTIONS ON INTELLIGENT
TRANSPORTATION SYSTEM,vol.19,pp.3775-3784(2018)[5]片桐英樹，谷崎隆士，宇野剛史，搬送設備の干渉を考慮したジョブショップ
スケジューリング問題に対するヒューリスティクス解法，vol.63,
pp.198-201(2019)

2021年

学生研究奨励賞

33