4.1 従 前 の 解 法
シ フ ト ス ケ ジ ュ ー リ ン グ 問 題 は ， 整 数 変 数 を 含 ん だ 最 適 化 問 題 で あ る ． 解 法 と し て ， 解 の 最 適 性 の 保 証 を 持 っ た 厳 密 解 法 と 最 適 性 の 保 証 を 持 た な い 近 似 解 法 が あ る ．
ス ケ ジ ュ ー リ ン グ 問 題 の ほ と ん ど は ，NP 困 難 で あ り ， ど の く ら い の 規 模 の 問 題 で 計 算 量 の 増 大 が 発 生 す る か の 予 測 は 難 し く ， 同 じ 問 題 で も ， 実 際 に 数 値 を 入 れ た 問 題 の 構 造 に よ っ て 解 け る 規 模 が 全 く 異 な る ．そ の た め ， 厳 密 解 法 で は な く ， 遺 伝 的 ア ル ゴ リ ズ ム （GA） や タ ブ ー サ ー チ （TS）， 焼 き な ま し 法（SA）と い っ た ヒ ュ ー リ ス テ ィ ク ス に よ る 近 似 解 法 が 用 い ら れ る こ と も 多 い ．
し か し よ り 緻 密 な シ フ ト 構 築 を 行 う た め に は 厳 密 解 法 に よ る 最 適 性 の 保 証 さ れ た 最 適 解 を 求 め る 必 要 が あ る こ と は い う ま で も な い ．
一 般 に ス ケ ジ ュ ー リ ン グ 問 題 に つ い て の 厳 密 解 法 で は ， 整 数 計 画 問 題
（Integer Programming: IP） や 制 約 充 足 問 題 （Constraint Satisfaction Problem: CSP）な ど の 標 準 問 題 の 形 に 定 式 化 さ れ ，主 と し て 分 枝 限 定 法 が 用 い ら れ る こ と が 多 い ．
分 枝 限 定 法 で は ，部 分 問 題 を 生 成（ 分 枝 操 作 ），最 適 値 の 上 界 ，下 界 の 情 報 を 用 い て ， あ る 部 分 問 題 か ら 最 適 解 が 得 ら れ な け れ ば ， そ の 部 分 問 題 は 無 視 （ 限 定 操 作 ） す る ． し か し な が ら こ の 解 法 で は 1 時 間 単 位 で シ フ ト が
116
入 る こ と も あ る 緻 密 な パ ー ト タ イ ム 勤 務 者 の み の シ フ ト の 最 適 解 を 求 め る の に は 時 間 が か か り ， 効 率 的 な 解 法 で は な い ．
4.2 本 研 究 で の 手 法
そ こ で 本 章 で は ， 人 工 蜂 コ ロ ニ ー （Artificial Bee Colony）（ 以 下 ，ABC と 記 す ） ア ル ゴ リ ズ ム[17]の 考 え 方 を 組 み 入 れ る こ と で ， 分 枝 限 定 法 で 実 用 的 な 時 間 で 問 題 を 解 く こ と を 目 指 す ．
ABCア ル ゴ リ ズ ム は ，収 穫 蜂（Employed bees），追 従 蜂（Onlooker bees），
偵 察 蜂 （Scout bees） の 3 種 類 の 人 工 蜂 群 の 行 動 に 基 づ い た 3 フ ェ ー ズ か ら な る ．
収 穫 蜂 と 追 従 蜂 の フ ェ ー ズ で は ， 解 候 補 近 傍 の 局 所 探 索 を 行 う が ， 偵 察 蜂 フ ェ ー ズ は ， 採 餌 行 動 に お い て 尽 き た 食 糧 源 を 捨 て る 行 動 を 真 似 た も の で ， 探 索 の 進 捗 に お い て 有 益 で は な く な っ た 解 候 補 を 捨 て ， 探 索 空 間 の 新 た な 領 域 を 探 索 す る た め の 新 た な 解 候 補 を 挿 入 す る ．
本 章 で は ， 偵 察 蜂 フ ェ ー ズ で い く つ か の 解 候 補 を 作 成 し ， そ こ で 割 り 当 て ら れ た 勤 務 シ フ ト の う ち ， 特 定 の 時 間 帯 を 固 定 と し た 上 で ， 分 枝 限 定 法 で 問 題 を 解 く こ と と す る ． 従 前 の 解 法 と の 比 較 を 図 4.3 に ， 本 研 究 の 手 法 の 概 念 図 を 図 4.4 に 示 す ．
本 研 究 の 手 法 は ，近 似 解 法 で あ る ABC を 含 む も の で あ る が ，厳 密 解 法 に よ る 最 適 値 の 下 限 は ， 計 算 が 終 了 し て い な く て も 知 る こ と が で き る た め ， そ の 値 と 一 致 し て い れ ば ， 便 宜 上 ， 最 適 解 と 呼 ぶ こ と と す る ．
117
図 4.3 従 前 の 解 法 と の 比 較
図 4.4 本 研 究 の 手 法 の 概 念 図
最 適 解 最 適 解
118 4.3 定 式 化
本 章 で は ， 混 合 整 数 線 形 計 画 問 題 （Mixed In-teger Linear Program-ming : MILP） と し て 定 式 化 し ， 最 適 解 を 求 め る ．MILP を 採 用 し た 理 由 は ， 記 述 性 が 高 く ， 細 か い 拘 束 条 件 に つ い て の 数 式 を 用 い て の モ デ ル 化 に 対 応 で き る こ と に あ る ．
Minimize ∑𝑑𝑑∈𝐷𝐷∑ℎ∈𝐻𝐻∑𝑛𝑛∈𝑁𝑁∑𝑑𝑑∈𝐵𝐵𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑𝑀𝑀ℎ𝑛𝑛𝑑𝑑 (4.1) Subject to
∑𝑛𝑛∈𝑆𝑆𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑛𝑛 = 1, 𝑑𝑑 ∈ 𝐷𝐷,ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁 (4.2)
∑𝑐𝑐3 𝑦𝑦(𝑑𝑑−𝑖𝑖)𝑛𝑛
𝑖𝑖=0 ≤ 𝑠𝑠3, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝐺𝐺𝐺𝐺 (4.3)
𝑦𝑦𝑑𝑑𝑛𝑛 − ∑ℎ∈𝐻𝐻∑𝑑𝑑∈𝐵𝐵𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≤ 0, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁 (4.4)
𝑇𝑇𝑦𝑦𝑑𝑑𝑛𝑛− ∑ℎ∈𝐻𝐻∑𝑑𝑑∈𝐵𝐵𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≥ 0, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁 (4.5)
∑𝑐𝑐4 ∑ℎ∈𝐻𝐻𝑚𝑚(𝑑𝑑−𝑖𝑖)ℎ𝑛𝑛𝑑𝑑
𝑖𝑖=0 ≥ 1, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝐵𝐵 (4.6)
∑ℎ∈𝐻𝐻𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑝𝑝𝑖𝑖ℎ ≤ 𝑇𝑇 −1, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁, 𝑚𝑚= 1, . . ,𝑘𝑘1 (4.7)
∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≥ 𝑠𝑠1𝑑𝑑ℎ𝑔𝑔𝑑𝑑, 𝑑𝑑 ∈ 𝐷𝐷, ℎ ∈ 𝐻𝐻, 𝑔𝑔 ∈ 𝐺𝐺, 𝑠𝑠 ∈ 𝐵𝐵 (4.8)
∑𝑛𝑛∈𝑁𝑁𝑔𝑔𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≤ 𝑠𝑠2𝑑𝑑ℎ𝑔𝑔𝑑𝑑, 𝑑𝑑 ∈ 𝐷𝐷, ℎ ∈ 𝐻𝐻, 𝑔𝑔 ∈ 𝐺𝐺, 𝑠𝑠 ∈ 𝐵𝐵 (4.9)
∑𝑑𝑑∈𝐷𝐷𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≥ 𝑠𝑠5ℎ𝑛𝑛𝑑𝑑, ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝐵𝐵 (4.10)
∑𝑑𝑑∈𝐷𝐷𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 ≤ 𝑠𝑠6ℎ𝑛𝑛𝑑𝑑, ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝐵𝐵 (4.11)
∑𝑑𝑑∈𝐻𝐻𝑛𝑛𝐻𝐻𝑚𝑚𝑑𝑑ℎ𝑛𝑛休 ≥ 𝑠𝑠7𝑛𝑛, 𝑚𝑚 ∈ 𝑁𝑁 (4.12)
∑𝑑𝑑∈𝐻𝐻𝐻𝐻𝑑𝑑𝑚𝑚𝑑𝑑ℎ𝑛𝑛休 ≥ 𝑠𝑠8𝑛𝑛, 𝑚𝑚 ∈ 𝑁𝑁 (4.13)
𝐿𝐿+𝑑𝑑ℎ𝑛𝑛𝑑𝑑 − 𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑛𝑛 ≤ 0, 𝑑𝑑 ∈ 𝐷𝐷, ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝑆𝑆 (4.14)
𝑚𝑚𝑑𝑑𝑑𝑑𝑛𝑛𝑑𝑑 − 𝑚𝑚(𝑑𝑑+1)1𝑛𝑛𝑑𝑑 ≤ 0, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝐵𝐵 (4.15)
𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑛𝑛 ∈{0, 1}, 𝑑𝑑 ∈ 𝐷𝐷, ℎ ∈ 𝐻𝐻, 𝑚𝑚 ∈ 𝑁𝑁, 𝑠𝑠 ∈ 𝑆𝑆 (4.16)
𝑦𝑦𝑑𝑑𝑛𝑛 ∈ {0, 1}, 𝑑𝑑 ∈ 𝐷𝐷, 𝑚𝑚 ∈ 𝑁𝑁 (4.17)
目 的 関 数(4.1)式 は ， 人 件 費 の 総 和 を 最 小 化 す る ． こ こ で ，𝐷𝐷は 対 象 期 間 の 日 の 集 合 ，𝐻𝐻は 時 間 帯 の 集 合 ，𝑁𝑁は ス タ ッ フ の 集 合 ，𝐵𝐵は シ フ
119
ト(勤 務 場 所)の 集 合 で あ る ． 変 数𝑚𝑚𝑑𝑑ℎ𝑛𝑛𝑑𝑑 は ， 各 日𝑑𝑑， 各 時 間 帯ℎに ， 各 ス タ ッ フ𝑚𝑚に つ い て 割 り 当 て ら れ た 勤 務 が𝑠𝑠の 場 合 は 1， そ う で な い 場 合 は 0 と な る 2 値 整 数 変 数 で ，(4.16)式 で 定 義 さ れ て い る ．𝑀𝑀ℎ𝑛𝑛𝑑𝑑
は ， 各 時 間 帯ℎの 各 ス タ ッ フ𝑚𝑚の 勤 務 別 の 賃 金 で あ る ．
(4.2)式 は 各 ス タ ッ フ に つ い て 各 日𝑑𝑑， 各 時 間 帯ℎの 勤 務 で 必 ず 一 つ の 休 み を 含 む シ フ ト𝑠𝑠に 割 り 当 て ら れ る こ と を 表 す ． こ こ で ， 𝑆𝑆は𝐵𝐵 に 休 み を 加 え た シ フ ト の 集 合 で あ る ．
(4.3)式 は 拘 束 条 件(b)を 表 す 制 約 で あ り ， 出 勤 が 最 大 連 続 回 数𝑠𝑠3回 を 超 え て 連 続 し な い こ と を 示 す ．𝐺𝐺𝐺𝐺は 最 大 連 続 回 数 を 考 慮 す る 必 要 の あ る ス タ ッ フ の 集 合 で あ る ．
(4.4)，(4.5)式 は ス タ ッ フ が𝑚𝑚日 に 出 勤 す る か ど う か を 表 し て い る ． 変 数𝑦𝑦𝑑𝑑𝑛𝑛は ，1 な ら 出 勤 ，0 な ら ば 休 み の 2 値 整 数 変 数 で あ り ， (4.17)式 で 定 義 さ れ て い る ．(4.4)式 で ，𝑦𝑦𝑑𝑑𝑛𝑛が 1 な ら ば𝑑𝑑日 に ス タ ッ フ𝑚𝑚が 時 間 帯ℎ， シ フ ト （ 勤 務 場 所 ）𝑠𝑠に よ ら ず 出 勤 し て い る こ と を 制 約 し ， 逆 に(4.5)式 で ， 出 勤 な ら ば𝑦𝑦𝑑𝑑𝑛𝑛を 1 と し て い る ． こ こ で 定 数𝑇𝑇 は 1 日 の 時 間 帯 の 数 で あ る ．
(4.6)式 は 拘 束 条 件(c)に つ い て の シ フ ト （ 勤 務 場 所 ）𝑠𝑠毎 の 最 大 間 隔𝑠𝑠4に 関 す る 制 約 で あ り ，𝑠𝑠4日 の 間 に 必 ず 1 回 は 出 勤 し て い る こ と を 表 し て い る ．
(4.7)式 は ， 拘 束 条 件(d)に つ い て 表 し て い る ．𝑑𝑑日 の 1～𝑇𝑇の 時 間 帯 の 勤 務 が ， 禁 止 パ タ ー ン𝐺𝐺と 一 致 す る シ フ ト が 出 現 し な い よ う に す る 制 約 で あ る ．𝑘𝑘1は ， 禁 止 パ タ ー ン の 数 で あ る ．
(4.8)，(4.9)式 は ， 拘 束 条 件(a)に つ い て ，𝑑𝑑日 に お け る グ ル ー プ𝑔𝑔の 勤 務 シ フ ト𝑠𝑠に 対 す る 最 小 人 数𝑠𝑠1𝑑𝑑ℎ𝑔𝑔𝑑𝑑に 関 す る 制 約 お よ び 最 大 人 数
𝑠𝑠2𝑑𝑑ℎ𝑔𝑔𝑑𝑑に 関 す る 制 約 を 表 し て い る ．
(4.10)，(4.11)式 は ， 拘 束 条 件(e)に つ い て ， 対 象 期 間 に 関 す る 各 ス タ ッ フ の シ フ ト𝑠𝑠の 勤 務 数 を 最 小 回 数𝑠𝑠5ℎ𝑛𝑛𝑑𝑑， 最 大 回 数𝑠𝑠6ℎ𝑛𝑛𝑑𝑑で 制 約 し て い る ．
(4.12)，(4.13)式 は ， 拘 束 条 件(f)，(g)に つ い て の 制 約 で あ る ． 各 ス タ ッ フ の 土 曜 日 に 休 む 回 数 を 土 休 暇 の 最 小 日 数𝑠𝑠7𝑛𝑛以 上 ， 日 曜 日 ・ 祭 日 に 休 む 回 数 を 日 ・ 祭 日 休 暇 の 最 小 日 数𝑠𝑠8𝑛𝑛以 上 と し て い る ． こ こ
で𝐻𝐻𝑠𝑠𝑠𝑠は ， 対 象 期 間 の 土 曜 日 の 集 合 ，𝐻𝐻𝐻𝐻𝑑𝑑は ， 日 曜 日 ・ 祭 日 の 集 合 で
あ る ．
(4.14)式 は ， 拘 束 条 件(g)に 関 す る 制 約 で あ る ． 希 望 勤 務𝐿𝐿+𝑑𝑑ℎ𝑛𝑛𝑑𝑑を 使 っ て 特 定 の 日𝑑𝑑の 各 ス タ ッ フ𝑚𝑚の シ フ ト𝑠𝑠を 制 約 す る ．
120
(4.15)式 は ， 夜 勤 を 表 し て い る ．𝑑𝑑日 の 最 終 時 間 帯 の 勤 務 と 翌 日
（𝑑𝑑+1 日 ） の 最 初 の 時 間 帯 の 勤 務 が 連 続 （ 同 じ ） 勤 務 と な る ．
5. 数 値 実 験