シ フ ト ス ケ ジ ュ ー リ ン グ 問 題 で は ， 解 法 と し て ，GA や TS，SA と い っ た ヒ ュ ー リ ス テ ィ ッ ク ス に よ る 近 似 解 法 が 用 い ら れ る こ と が 多 い ．し か し ， シ フ ト ス ケ ジ ュ ー リ ン グ の よ う な 公 平 性 を 重 視 し な け れ ば な ら な い 問 題 の 場 合 ， 解 が 最 適 で あ る こ と が 重 要 に な る た め ， 厳 密 解 法 で 求 め た 最 適 性 が 保 証 さ れ た 最 適 解 で あ る こ と が 望 ま し い ． ま た ， 最 適 解 を 得 ら れ な い 場 合 で も ， 問 題 が 複 雑 に な る と ， 手 作 業 に よ る 修 正 が 困 難 な こ と か ら ， 近 似 解
82
法 で あ っ て も ， 修 正 が 必 要 の な い 精 度 の 高 い 解 が 求 め ら れ る ．
そ こ で ， 混 合 整 数 線 形 計 画 問 題 （Mixed Integer Linear Programming : MILP）と し て 定 式 化 し た ．MILP を 採 用 し た 理 由 は ，記 述 性 が 高 く ，細 か い 拘 束 条 件 に つ い て の 数 式 を 用 い て の モ デ ル 化 に 対 応 で き る こ と に あ る ．
case1
Minimize ∑𝑑𝑑∈𝐷𝐷∑𝑛𝑛∈𝑁𝑁∑𝑑𝑑∈𝐵𝐵𝑧𝑧𝑑𝑑𝑛𝑛𝑑𝑑 (3.13) Subject to
∑𝑛𝑛∈𝑆𝑆𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑛𝑛 = 1, 𝑑𝑑 ∈ 𝐷𝐷, ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁 (3.14)
∑𝑐𝑐3 𝑦𝑦(𝑑𝑑−𝑖𝑖)𝑛𝑛
𝑖𝑖=0 ≤ 𝑠𝑠3, 𝑑𝑑 ∈ 𝐷𝐷,𝑚𝑚 ∈ 𝐺𝐺𝐺𝐺 (3.15)
𝑦𝑦𝑑𝑑𝑛𝑛 − ∑ℎ∈𝐻𝐻∑𝑑𝑑∈𝐵𝐵𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≤ 0, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁 (3.16)
𝑇𝑇𝑦𝑦𝑑𝑑𝑛𝑛− ∑ℎ∈𝐻𝐻∑𝑑𝑑∈𝐵𝐵𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≥ 0, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁 (3.17)
∑𝑐𝑐4 ∑ℎ∈𝐻𝐻𝑚𝑚(𝑑𝑑−𝑖𝑖)ℎ𝑛𝑛𝑑𝑑
𝑖𝑖=0 + 𝑧𝑧𝑑𝑑𝑛𝑛𝑑𝑑 ≥ 1, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝐵𝐵 (3.18)
∑𝑘𝑘 𝑚𝑚𝑑𝑑(𝑖𝑖+1)𝑛𝑛𝑝𝑝𝑖𝑖
𝑖𝑖=0 ≤ 𝑘𝑘, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁 (3.19)
∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≥ 𝑠𝑠1𝑑𝑑ℎ𝑔𝑔𝑑𝑑, 𝑑𝑑 ∈ 𝐷𝐷, ℎ ∈ 𝐻𝐻, 𝑔𝑔 ∈ 𝐺𝐺, 𝑠𝑠 ∈ 𝐵𝐵 (3.20)
∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≤ 𝑠𝑠2𝑑𝑑ℎ𝑔𝑔𝑑𝑑, 𝑑𝑑 ∈ 𝐷𝐷, ℎ ∈ 𝐻𝐻, 𝑔𝑔 ∈ 𝐺𝐺, 𝑠𝑠 ∈ 𝐵𝐵 (3.21)
∑𝑑𝑑∈𝐷𝐷𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≥ 𝑠𝑠5ℎ𝑛𝑛𝑑𝑑, ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝐵𝐵 (3.22)
∑𝑑𝑑∈𝐷𝐷𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≤ 𝑠𝑠6ℎ𝑛𝑛𝑑𝑑, ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝐵𝐵 (3.23)
∑𝑑𝑑∈𝐻𝐻𝑛𝑛𝑚𝑚𝑑𝑑ℎ𝑛𝑛休 ≥ 𝑠𝑠7𝑛𝑛, 𝑚𝑚 ∈ 𝑁𝑁 (3.24)
∑𝑑𝑑∈𝐻𝐻𝑛𝑛𝑚𝑚𝑑𝑑ℎ𝑛𝑛休 ≤ 𝑠𝑠8𝑛𝑛, 𝑚𝑚 ∈ 𝑁𝑁 (3.25)
𝐿𝐿+𝑑𝑑ℎ𝑛𝑛𝑑𝑑 − 𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑛𝑛 ≤ 0, 𝑑𝑑 ∈ 𝐷𝐷, ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝑆𝑆 (3.26)
𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑛𝑛 ∈{0, 1}, 𝑑𝑑 ∈ 𝐷𝐷, ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝑆𝑆 (3.27)
𝑦𝑦𝑑𝑑𝑛𝑛 ∈{0, 1}, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁 (3.28)
𝑧𝑧𝑑𝑑𝑔𝑔𝑑𝑑 ∈{0, 1}, 𝑑𝑑 ∈ 𝐷𝐷, 𝑔𝑔 ∈ 𝐺𝐺, 𝑠𝑠 ∈ 𝐵𝐵 (3.29)
変 数𝑧𝑧𝑑𝑑𝑔𝑔𝑑𝑑 は ，拘 束 条 件(c)に 違 反 す る ペ ナ ル テ ィ で あ り ，𝑑𝑑日 の ス タ ッ フ𝑚𝑚
の 勤 務 シ フ ト𝑠𝑠で 最 大 間 隔 を 超 え て し ま う 場 合 は 1 と な る ．𝑧𝑧𝑑𝑑𝑔𝑔𝑑𝑑 は ，(3.29)
83
式 で 定 義 さ れ て い る ．目 的 関 数(3.13)式 は こ の𝑧𝑧𝑑𝑑𝑔𝑔𝑑𝑑 の 和 を 最 小 化 す る ．こ こ で ，𝐷𝐷は 対 象 期 間 の 日 の 集 合 ，𝑁𝑁は ス タ ッ フ の 集 合 ，𝐵𝐵は シ フ ト(勤 務 場 所)の 集 合 で あ る ．
(3.14)式 は 各 ス タ ッ フ に つ い て 各 日𝑑𝑑， 各 時 間 帯ℎの 勤 務 で 必 ず 一 つ の 休 み を 含 む シ フ ト𝑠𝑠に 割 り 当 て ら れ る こ と を 表 す ． 変 数𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑛𝑛 は ， 割 り 当 て ら れ た 勤 務 が s の 場 合 は 1， そ う で な い 場 合 は 0 と な る 2 値 整 数 変 数 で ， (3.27)式 で 定 義 さ れ て い る ．こ こ で ，𝐻𝐻は 時 間 帯 の 集 合 ，𝑆𝑆は𝐵𝐵に 休 み を 加 え た シ フ ト の 集 合 で あ る ．
(3.15)式 は 拘 束 条 件(b)を 表 す 制 約 で あ り ， 出 勤 が 最 大 連 続 回 数𝑠𝑠3回 を 超 え て 連 続 し な い こ と を 示 す ．𝐺𝐺𝐺𝐺は 全 ス タ ッ フ の う ち パ ー ト タ イ ム の ス タ ッ フ の 集 合 で あ る ．
(3.16)，(3.17)式 は ス タ ッ フ が𝑚𝑚日 に 出 勤 す る か ど う か を 表 し て い る ． 変 数𝑦𝑦𝑑𝑑𝑛𝑛は ，1 な ら 出 勤 ，0 な ら ば 休 み の 2 値 整 数 変 数 で あ り ，(3.28)式 で 定 義 さ れ て い る ．
(3.16)式 で ，𝑦𝑦𝑑𝑑𝑛𝑛が 1 な ら ば𝑑𝑑日 に ス タ ッ フ𝑚𝑚が 時 間 帯ℎ， シ フ ト （ 勤 務 場 所 ）𝑠𝑠に よ ら ず 出 勤 し て い る こ と を 制 約 し ，逆 に(3.17)式 で ，出 勤 な ら ば𝑦𝑦𝑑𝑑𝑛𝑛 を 1 と し て い る ． こ こ で 定 数𝑇𝑇は 1 日 の 時 間 帯 の 数 で あ る ．
(3.18)式 は 拘 束 条 件(c)に つ い て の 勤 務 シ フ ト（ 勤 務 場 所 ）𝑠𝑠毎 の 最 大 間 隔 𝑠𝑠4に 関 す る 制 約 で あ り ，𝑠𝑠4日 の 間 に 必 ず 1 回 は 出 勤 し て い る こ と を 表 し て い る ．
(3.19)式 は ， 拘 束 条 件(d)に つ い て 表 し て い る ．𝑑𝑑日 の 0~ 𝑘𝑘の 時 間 帯 の 中 に お い て 勤 務 禁 止 パ タ ー ン𝐺𝐺と 一 致 す る シ フ ト が 出 現 し な い よ う に す る 制 約 で あ る ．
(3.20)，(3.21)式 は ，拘 束 条 件(a)に つ い て ，𝑑𝑑日 に お け る グ ル ー プ𝑔𝑔の 勤 務 シ フ ト𝑠𝑠に 対 す る 最 小 人 数𝑠𝑠1𝑑𝑑ℎ𝑔𝑔𝑑𝑑に 関 す る 制 約 お よ び 最 大 人 数𝑠𝑠2𝑑𝑑ℎ𝑔𝑔𝑑𝑑に 関 す る 制 約 を 表 し て い る ．
(3.22)，(3.23)式 は ，拘 束 条 件(e)に つ い て ，対 象 期 間 に 関 す る 各 ス タ ッ フ の シ フ ト𝑠𝑠の 勤 務 数 を 最 小 回 数𝑠𝑠5ℎ𝑛𝑛𝑑𝑑， 最 大 回 数𝑠𝑠6ℎ𝑛𝑛𝑑𝑑で 制 約 し て い る ．
(3.24)，(3.25)式 は ，拘 束 条 件(f)に つ い て の 制 約 で あ る ．各 ス タ ッ フ の 土 曜 日 に 休 む 回 数 を 最 小 日 数𝑠𝑠7𝑛𝑛・最 大 日 数𝑠𝑠8𝑛𝑛の 範 囲 内 と し て い る ．こ こ で𝐻𝐻𝑠𝑠 は ， 対 象 期 間 の 土 曜 日 の 集 合 で あ る ．
(3.26)式 は ，拘 束 条 件(g)に 関 す る 制 約 で あ る ．希 望 勤 務𝐿𝐿+𝑑𝑑ℎ𝑛𝑛𝑑𝑑を 使 っ て 特 定 の 日𝑑𝑑の 各 ス タ ッ フ𝑚𝑚の シ フ ト𝑠𝑠を 制 約 す る ．
84 case2
minimize ∑𝑑𝑑∈𝐷𝐷∑ℎ∈𝐻𝐻∑𝑛𝑛∈𝑁𝑁∑𝑑𝑑∈𝐵𝐵𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑𝑀𝑀ℎ𝑛𝑛𝑑𝑑 (3.13)’
Subject to
∑𝑐𝑐4 ∑ℎ∈𝐻𝐻𝑚𝑚(𝑑𝑑−𝑖𝑖)ℎ𝑛𝑛𝑑𝑑
𝑖𝑖=0 ≥ 1, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝐵𝐵 (3.18)’
∑ℎ∈𝐻𝐻𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑝𝑝𝑖𝑖ℎ ≤ 𝑇𝑇 −1,𝑑𝑑 ∈ 𝐷𝐷,𝑚𝑚 ∈ 𝑁𝑁,𝑚𝑚= 1, . . ,𝑘𝑘1 (3.19)’
case2 で は ，(3.13)式 ，(3.18)式 ，(3.19)式 を 変 更 し ，そ れ ぞ れ ，(3.13)’式 ，
(3.18)'式 ，(3.19)’式 と し た ．
(3.13)’式 は ， 人 件 費 の 総 和 を 最 小 化 す る よ う に ， 目 的 関 数 を 変 更 し て い る ． こ こ で ，𝑀𝑀ℎ𝑛𝑛𝑑𝑑 は ， 時 間 ， 勤 務 場 所 毎 の 各 ス タ ッ フ の 費 用 で あ る ．
(3.18)'式 は ，拘 束 条 件(c)に つ い て の 勤 務 シ フ ト（ 勤 務 場 所 ）𝑠𝑠毎 の 最 大 間 隔𝑠𝑠4に 関 す る 制 約 で あ る ． 拘 束 条 件(c)に 違 反 す る ペ ナ ル テ ィ を 許 さ な い よ う に 変 更 し て い る ．
(3.19)’式 は ， 拘 束 条 件(d)の 勤 務 禁 止 パ タ ー ン𝐺𝐺と 一 致 し な い よ う に す る 制 約 で あ る ． 勤 務 時 間 長 ， 退 勤 後 の 再 出 勤 禁 止 等 の 条 件 を 表 現 で き る よ う に 変 更 し て い る ．
そ の 他 の 式 は ，case1 と 同 じ で あ る ．