不確実性の下での工数を考慮したプロジェクトスケジューリング問題のモデル化と解法

全文

(1)J Jpn Ind Manage Assoc 72, 1–9, 2021 J Jpn Ind Manage Assoc 72 , 37─45, 2021. Original OriginalPaper Paper. Modeling and Solution Algorithm for Project Scheduling Problem considering Man-hour under Uncertainty Takumi Kitamura. †1. and Takayuki Shiina. †1. Abstract Projects are often executed under uncertain circumstances and require prior decisions that take uncertainty into account. Among them, the schedule of the initial plan and the plan for additional decisions corresponding to the uncertainties become important. In this study, we developed a mathematical model of a twostage stochastic programming problem considering time and cost tradeoffs and crushing, which are important in project scheduling. An effective solution using a stochastic integer linear model and a moment matching method was presented for DTCTP-C with random fluctuations. In project management, the duration of a job is determined by the man-hour and the amount of resources required for the job. The duration can be shortened by increasing the amount of additional resources utilized. The cost increases according to the the amount of resources used. This problem is referred to as the Time/Cost Trade-off Problem (TCTP). In this study, the relation between time and cost is represented by an inverse proportional curve. We present a solution to the Stochastic Discrete TCTP-Curve (SDTCTP-C) in which the duration of the job is defined as a random variable. It may also be necessary to study mathematical models that require multiple resources. Future prospects include expanding the model to take into account the amount of resources available at each time period. Furthermore, by reducing the difference between the maximum number of resources used and the minimum number of resources used to the furthest possible extent, it can be said that more realistic scheduling can be performed. Key words: stochastic programming, time/cost trade-off problem, project scheduling. †1. Department of Industrial and Management Systems Engineering, School of Creative Science and Engineering, Waseda University Received : Jan 24, 2020 Accepted: Dec 2, 2020. Vol. 72 No. 1（2021）. 37.

(2) 不確実性の下での工数を考慮したプロジェクトスケジューリング問題のモデル化と解法北村拓海 †1，椎名孝之†1 プロジェクトの遂行において，作業の所要時間は作業の工数と作業へ投入される資源数によって決定される．資源の投入数を増加することによって，所要時間は短縮される．さらに資源の投入数の増加に伴い，作業にかかる費用は増加する．このような問題は，時間費用トレードオフ問題 (The Time/Cost Trade-off Problem) と呼ばれる．本研究では，時間と費用の関係が反比例の関係にあると仮定する．作業の所要時間が確率変数によって定義されるような曲線型時間費用トレードオフ問題に対して，確率計画法による定式化と解法および数値実験結果を示した．. キーワード：確率計画法, 時間費用トレードオフ問題, プロジェクトスケジューリング. 1 はじめに製品開発プロジェクトをはじめとして，現在では東京オリンピックに向けた大規模プロジェクトに注目が集まっている．大規模プロジェクトの成功は，社会的にも重要な課題といえる．ところが，特に複数の作業で構成されたプロジェクトをスムーズに進めることは困難である．作業を行うメンバーの能力偏差や突発的に発生するアクシデントといった不確実性により，プロジェクトの納期を超過してしまう可能性があるためである．そのためプロジェクトが開始される前に，様々な不確実性を考慮したプロジェクトスケジューリング手法が必要となる．プロジェクトスケジューリング問題 (Project Schedul-. ing Problem, PSP) とは，プロジェクトを構成する作業に対し，遂行順序や所要時間・開始時刻・完了時刻を決定するスケジューリングである．主にメイクスパンの最小化が目的とされ，他には納期遅れ最小化やコスト最小化等が目的関数となる．代表的な手法として. PERT や CPM がある．プロジェクトスケジューリング問題においては，各作業で使用または消費する資源数を考慮する場合があり，その資源数の考慮の手法として 2 つの方針が存在する．1 つは資源制約付きプロジェクトスケジューリング問題 (Resource Constrained PSP) である．これは同時刻に投入できる資源数に上限が存在するという制約が加わった問題である．もう 1 つは時間費用トレードオフ問題 (Time/Cost. Trade-off Problem, TCTP) である．ある作業に対して投入する資源数を増やすことで作業の所要時間は短 †1. 早稲田大学創造理工学部経営システム工学科受付：2020 年 1 月 24 日受理：2020 年 12 月 2 日. 38. くなり，プロジェクトも早く終わるがその分だけ費用が増加してしまう．本研究はこのようなプロジェクトスケジューリング問題においての時間と費用のトレードオフとなる関係に着目する．プロジェクトの各作業に対して工数を基に適切な資源投入数の決定を行うような TCTP のモデルを作成し，作業時間の不確実性を考慮に加えた確率計画モデルへの拡張を行う．これによりプロジェクトにおける時間と費用の関係を制御することで，適切な意思決定が可能となる．. 2 時間費用トレードオフ問題 (TCTP) 本研究においては，作業時間は工数と作業へ投入される資源数により決定されるものと仮定する．工数とは作業を完了させるために必要となる総作業量である．作業へ投入する資源数を増やすことで，作業の所要時間は短縮できるがその分費用が増加する．逆に投入資源数を減らすことで費用は減少するが，時間が長くなることが考えられる．このようなトレードオフの関係を考慮する問題において，作業への資源投入数を決定するため，変数は整数値をとるものとする．決定変数を離散値とするモデルは Discrete Time/Cost Trade-off. Problem(DTCTP) とよばれる．DTCTP の従来研究は以下のように分類することができる．納期問題 (DTCTP-D) 与えられた納期内でプロジェクトの総費用を最小化するモデルであり， Hazir et al.[1] による．予算問題 (DTCTP-B) 与えられた予算内でプロジェクトのメイクスパンを最小化させる．Hazir et al.[2] や Deˇ girmenci and Azizoˇ glu[3], Zhu et al.[4] により研究が行われた． Time/Cost 曲線型問題 (DTCTP-C) 総費用とメイクスパンの関係が曲線で表された日本経営工学会論文誌.

(3) モデルである．Jeang [5] は作業の経験曲線効果を考慮したモデルの研究を行った．工数を考慮したプロジェクトスケジューリングの研究はまだ少ないといえる．また人が行う作業の場合においては，スケジュールの作成時点では作業の進行度を定量的に予測することは困難である．作業時間の変動によっては，決定されたスケジュールに対して遅延や予算超過が発生する可能性があるためである．したがって不確実性を考慮した DTCTP のモデルへの拡張を行う．. 3 提案モデル 3.1 問題概要本研究ではスケジューリングのためのパラメータとして工数を定義する．工数とは作業を完了させるために必要な総作業量であり，(工数)=(投入資源数)×(所要時間) のような関係が成り立つと仮定し，2 段階確率計画問題として定式化を行う．第 1 段階では資源の投入数を定める．その後変動シナリオが判明し，作業の所要時間に確率変動が生じる．また変動に伴いクラッシング (作業時間の短縮) の長さが第 2 段階に決定さ. 3.3 費用設定工数 Mi をもつ作業 i に対して，まず第 1 段階で xi の資源を投入する．次に第 2 段階としてシナリオ s に応じて，作業時間は (Mi /xi )ξis となり，資源 yis の追加投入を行う．資源投入にかかる費用は作業の単位コスト c と作業の所要時間 d をかけた値となる．作業の単位コストは，Brooks[6], Jørgensen and Wallace [7] に基づいて投入資源数 n に対し O(n2 ) で増加するものとし，作業に依存しない．本研究では簡単のため c = n2 とした．シナリオ s での費用シナリオ s において，工数 Mi をもつ作業 i に対して資源 xi + yis が投入された場合，資源投入にかかるシナリオ s での費用は. c · dsi = (xi + yis )2 ×. Mi ξs xi +yis i. = Mi ξis (xi + yis ). と計算することができる．費用の期待値全シナリオを考慮するために，資源投入にかかる費用の期待値を求めると以下のようになる．. S ∑. れる．. s=1. πs. |N | ∑ i=1. {Mi ξis (xi + yis )}. 3.2 記号の定義パラメータ先行関係が存在する作業の組合せの集合. P N |N | S Mi Li Ui πs q D. 作業ノードの集合プロジェクト全体の終了を表すダミー作業番号所要時間の変動を表すシナリオ集合作業 i の工数作業 i への投入資源数の下限作業 i への投入資源数の上限シナリオ s の発生確率. 納期超過による単位ペナルティ費用プロジェクト全体の納期確率変数. ξis. シナリオ s での作業 i の所要時間の変動比率第 1 段階決定変数. 作業 i への資源投入数第 2 段階決定変数 tsi シナリオ s での作業 i の開始時刻. xi. t¯i yis y¯i dsi d¯i. =. |N | ∑ i=1. ¯ i xi + M. S ∑ s=1. πs (. |N | ∑. Mi ξis yis ). (1). i=1. ¯ i = ∑S π s ξis Mi ) (ただしM s=1 式 (1) の第 1 項は，第 1 段階決定の資源投入数に基づく費用であり，第 2 項は第 2 段階決定に基づく費用を表す．総費用総費用は第 1 段階における決定から生じる費用と，第 2 段階における費用との総和となる．第 1 項に加えて，第 2 項に w の重み係数 (w > 0) を与え，第 2 段階決定が第 1 段階決定と比べて費用が高くなるよう設定する．本研究では w = 1.5 とした．. 平均シナリオでの作業 i の開始時刻シナリオ s での作業 i への追加資源投入数平均シナリオでの作業 i への追加資源投入数作業 i のシナリオ s での所要時間作業 i の平均シナリオにおける所要時間. Vol. 72 No. 1（2021）. 3.4 定式化主問題として，第 1 段階決定変数による総費用最小化を目的としたモデル化を行った．さらに，第 2 段階費用には納期超過に対するペナルティを加えた． 39.

(4) [主問題] min. |N | ∑. ¯ i xi + Q(x) M. (2). Li ≤ xi ≤ Ui , i ∈ N. (3). π s v s (x). (4). i=1. s.t.. Q(x) =. S ∑ s=1. |N |. x ∈ Z+. (5). 主問題において決定された第 1 段階決定変数 x を用いて第 2 段階変数を決定する．目的関数に含まれる v s (x) は，第 2 段階問題の最適目的関数値を表す．さらに，第 2 段階問題の目的関数には，プロジェクト全体の締切に対するペナルティを加えた．. [第 2 段階問題] v s (x) = min q(ts|N | − D)+ + w tsj. dsi , (i, j). Mi ξis yis (6). i=1. ≥ ∈P (7) Mi dsi = ξis , i = 1, . . . , |N | (8) xi + yis Li ≤ xi + yis ≤ Ui , i = 1, . . . , |N | (9). s. t.. −. tsi. |N | ∑. |N |. ds ≥ 0, y s , ts ∈ Z+. (10). 目的関数 (6) の第 1 項における |N | はプロジェクト全体の終了を表すダミー作業であり，プロジェクトが納期 D までに終了しない場合のペナルティとなる．制約式 (7)(8) を考慮すると非線形の制約式となるが，一般的なモデリング言語では記述が行えない．よって (8) を線形制約式に変換するため，各作業 i に対して図 1 に示される以下の Mi − 1 本の妥当不等式を用いる．. Mi ξis 2Mi ξis k + Mi ξis (xi + yis ) + , k(k + 1) k(k + 1) k = 1, 2, · · · , Mi − 1 (11). dsi ≥ −. 3.5 変動の与え方プロジェクトスケジューリングでは，最頻値と楽観値, 悲観値を用いた 3 点見積もり手法が多く用いられる．確率計画法では，起こり得る実現値とその確率を用いて変動を表す．本研究での実験において確率変動は β 分布に従うと仮定する．β 分布の確率密度関数は以下のように表せる．. xα−1 (1 − x)β−1 B(α, β) ∫ 1 tα−1 (1 − t)β−1 dt B(α, β) = f (x) =. (12) (13). 図 1 制約式 (8) に対する妥当不等式. 本研究では α = 2, β = 5 とした．この場合での最頻値は x = 0.2 となり，この値を最頻値として標準所要時間を意味するものとする．この基準から楽観値として. x = 0.1(所要時間が半分)，悲観値として x = 0.6(所要時間 3 倍) と設定する．所要時間が半分になる確率を p1 ，変動が起きない確率を p2 ，3 倍になる確率を p3 とする ∫ 0.15 と，積分計算により p1 = 0 f (x)dx = 0.2233, p2 = ∫ 0.4 ∫1 f (x)dx = 0.5430, p3 = 0.4 f (x)dx = 0.2337 と 0.15. 求められた．これらの値をベンチマーク問題に用いる．. 4 確率計画法の評価方法 4.1 VSS 確率計画法の解を評価する指標として VSS(value. of the stochastic solution) が用いられる (Birge and Louveaux[8], 椎名 [9])．問題に含まれる確率変数 ξ が ξ となるとき，以下のように確率変数の値を固定した確定的最適化問題を定義する．ここで，c, q はそれぞれ第 1 段階決定 x および第 2 段階決定 y に対する費用であり，W, T は定数行列，h(ξ) は確率変数の実現値 ξ に依存するベクトルである． minx z(x, ξ) = ct x+miny {q t y|W y = h(ξ)−T x, y ≥ 0} (14) s.t. Ax = b, x ≥ 0 (15) 確率計画問題の最適目的関数値 RP(recourse problem) は以下のように求められる．. RP = min Eξ (z(x, ξ)) x. (16). 確率変数 ξ を，その平均値 ξ¯ に置き換えて得られる確定的な問題の最適目的関数値 EV(expected value prob-. ¯ とする． lem) を次のように定め，その最適解を x ¯(ξ) ¯ EV = min z(x, ξ) x. (17). 0. 40. 日本経営工学会論文誌.

(5) ¯ を確率計画問題に適用したときのその最適解 x ¯(ξ) 目的関数値 EEV(expected result of using the EV solution) は次のように求められる．. ¯ x + min w EEV = M. S ∑. πs. s=1. ¯ ξ)) EEV = Eξ (z(¯ x(ξ),. (18) s.t. (19). EEV を求める問題で得られる最適解は，RP を求める問題の実行可能解となるので，次の関係が成立する．. RP ≤ EEV. (20). つまり，VSS ≥ 0 となる．RP を求める問題は通常の. 2 段階確率計画モデルである．一方で，EEV を求める問題は，確率変数を平均値に固定して考慮した確定的モデルになる．本研究における EV を求める問題の定式化は，次節 4.2 の式 (21)–(25) である. EV を求める問題は確率変数を平均値に固定させた確定問題であり，EEV を求める問題は EV によって作成されたスケジュールに，変動シナリオをあてはめた場合の費用の期待値を求める問題である．EEV を求める数理モデルは 4.2 の (26)–(30) で示されている．. 4.2 等価確定問題の定式化 EV を求める定式化が以下に示される．ただし， ¯ ξi (i = 1, · · · , |N |) は作業 i における変動比率の期待値である．確率変数 ξi が期待値 ξ¯i をとるときの最適目的関数値 EV を，以下のように求める． ¯x+w EV = min M. |N | ∑. Mi ξis yis. i=1. π s q(ts|N | − D)+. (26). tsj − tsi ≥ dsi , (i, j) ∈ P, s ∈ S. (27). +. s=1. VSS は，次のように定義される． VSS = EEV − RP. S ∑. |N | ∑. L i ≤ xi +. yis. ≤ Ui ,. i = 1, . . . , |N |, s ∈ S (28) s M ξ i i (xi + yis ) dsi ≥ − k(k + 1) 2Mi ξis k + Mi ξis + , k = 1, 2, · · · , Mi − 1, k(k + 1) i = 1, . . . , |N |, s ∈ S (29) |N |. ds ≥ 0, y s , ts ∈ Z+ , s ∈ S. (30). 5 導入実験 5.1 問題設定初めに，確率変動が所要時間は変わらない場合 (50%) と 3 倍に伸びる場合 (50%) の 2 パターンのみとして実験を行う．プロジェクトの構成は Activity-on-Node(Ao-N) として図 2 のように与えた．ノード内の番号が作業の番号であり，各工数の値はノードの上に示されている．ノード 7 は完了を表すダミー作業である．変動は作業 3 と作業 4 で独立に発生するものとしたため，変動は 4 シナリオ存在する．. Mi ξ¯i y¯i. i=1. s.t.. +q(t¯|N | − D)+ t¯j − t¯i ≥ d¯i , (i, j) ∈ P. (21) (22). Li ≤ xi + y¯i ≤ Ui , i = 1, · · · , |N | (23) Mi ξ¯i d¯i ≥ − (xi + y¯i ) k(k + 1) 2Mi ξ¯i k + Mi ξ¯i + , k = 1, 2, · · · , Mi − 1, k(k + 1) i = 1, . . . , |N | (24) |N | d¯ ≥ 0, x, y, ¯ t¯ ∈ Z+. (25). この問題で得られた解 x を固定値として用いて以下の問題に当てはめ，EEV を求める．EV を求める問題では，平均値に相当するシナリオを 1 つのみ考えているのに対して，EEV を求める場合は全てのシナリオ s ∈ S を考慮していることに注意されたい． Vol. 72 No. 1（2021）. 図 2 A-o-N ネットワーク. 5.2 実験結果全ての作業に対して，投入資源数の下限を 1，上限を 10 とした．納期を超過した場合の単位罰金費用 q は 100, 200 の 2 通りを考慮した．図 3 は，数値実験における確率計画問題の結果 (RP) と等価確定計画問題の結果 (EEV) を比較したグラフである．このモデルは各作業それぞれにコストと時間のトレードオフの関係を想定したものであったが，加えて図 3 では納期と総費用の関係にもトレードオフの関係が表れていることがわかる．この実験では，時間が 1 倍または 3 倍の 2 通りの 41.

(6) 表1. 数値実験結果 (q = 100). 納期. RP. EEV. 15. 4851.25. 4915. 1.29. 20. 4351.25. 4415. 1.44. 25. 3851.25. 3915. 1.62. 30. 3366.25. 3490. 3.54. 35. 2976.25. 3370. 11.7. 40. 2658.5. 3001. 11.4. 45. 2398.75. 2997. 19.9. 表2. VSS(%). 数値実験結果 (q = 200). 納期. RP. EEV. 15. 6307. 6507. 3.17. 20. 5307. 5527. 4.15. 25. 4354.4. 4877. 12.0. VSS(%). 30. 3572. 4199. 17.6. 35. 3048.75. 4045. 32.7. 40. 2658.5. 3651. 37.3. 45. 2404. 3897. 62.1. 図4. 納期を 30 とした場合のガントチャート. たものであり，横軸が時間で縦軸が投入資源数を表している．なお，色付けされた作業 3 および 4 は，作業時間が変動することを表す．シナリオ 2 では作業 2 へ資源の追加投入が 4 だけ行われている．シナリオ 3 では作業 5 に 5 単位の資源が追加投入されている．シナリオ 4 では作業 2 および 5 にそれぞれ 2，3 の資源の追加投入が行われている．等価確定問題では，平均シナリオとなる条件の下で意思決定を行っているため，平均シナリオに合わせて. (21) の目的関数値が最適になるように，完了時刻を決めている．確率計画法では，複数のシナリオを同時に考慮しているため，ジョブの遂行時間が長くなるシナリオ 4 においては，納期を超過するリスクも考慮して意思決定を行っているといえる．また図 3 から，本研究の提案モデルによる確率計画問題と等価確定計画問題の最適値の差分は納期によって変動することがわかる．納期が小さければ総費用の差は小さいが，納期が大きくなるにつれて VSS が大きくなっていく傾向がみられる．EEV を求める問題においては，RP を最小化する解を求めているわけではないため，RP との差が生じるといえる．RP の代わりに，計算の容易さから EEV を求めたとしても，差が大きい可能性がある．さらに規模の大きい問題を扱う場合には，RP を求めるためにシナリオ数を削減して規模を小さくするような手法が必要になると思われる．. 6 ベンチマーク問題を用いた実験と解法. 図 3 総費用の推移 (Time/Cost Trade-off curve). 変動パターンが与えられているため，等価確定問題. (DTCTP) では変動が平均の 2 倍になるものと設定した．図 4 は納期が 30 である場合の RP を求める問題のスケジューリング結果をガントチャートとして示し 42. 6.1 Project Scheduling Problem Library Kolish and Sprecher[10] が作成したプロジェクトスケジューリングのデータファイル集合である Project Scheduling Problem Library(PSPLIB) から，作業数 60, NC(Network Complexity) が 1.5 のデータ (j6011.sm) をベンチマーク問題とする．Davis[11] によると，NC は以下のように定義される．日本経営工学会論文誌.

(7) NC =. |P | |N |. 表 3 作業数 60, N C = 1.5 の数値実験結果. (31). また工数を，データ内の各作業から (所要時間)×(使用資源数) として決定した．確率変動は，最大工数上位の 5 作業に 3 通りずつ発生するものとしたため，総シナリオ数は 35 = 243 本となった．数値実験では，データのサイズや問題の複雑さから実用的な時間で解が得られない場合がある．このような問題を解決するために，モーメントマッチング法. (moment matching method [12],[13]) を用いてシナリオの削減を行い，計算できる問題のサイズの拡張を考える．実験環境は CPU:Intel(R) Core(TM)i7-3770S. 3.10GHz, メモリ:8.0GB である．. 従来シナリオ納期. 総費用. 80 90 100 110. 9716.5 8994.54 8316.52 7810.91. を与えなおす手法である．各段階のシナリオに相当するノードに与える確率が 0 になる場合があるため，そのノードの子ノードの発生確率もすべて 0 になり，シナリオ数の削減を行うことができる．まず，以下の表 3 に作業数 60, N C = 1.5 の場合の厳密解 RP を求める問題に対する目的関数値を示す．. 3090.5 2531.54 2512.52 2250.91. 2254.03 2794.78 1662.89 1241.97. モーメントマッチング法の定式化のため，以下のように記号を定義する．パラメータ N′ 確率変動が発生するノード集合 bi 作業 i がとりうる変動数. Bi. シナリオツリーに対してモーメントマッチング法を用いる．シナリオがツリー型で与えられている場合において，元の確率分布の期待値や分散，歪度，尖度等の統計的性質を保つように，各段階毎のシナリオの確率. 6626 6463 5804 5560. 6.3 記号の定義. 6.2 モーメントマッチング法の概要本節では，モーメントマッチング法を用いてシナリオ数の削減を図る．本研究では確率変動は 5 つの作業に起きるものとしているため，図 5 のような 5 段階の. 第 1 段階第 2 段階計算時間 (s). ¯i M Σi , S i , Ki Xit λi ωi1 , ωi2 , ωi3. (i = 1, · · · , |N ′ |) 作業 1 から i までに相当するシナリオ ∏i ツリーのノードの総数，Bi = t=1 bt 作業 i の工数の期待値 ∑¯ s s Mi = S s=1 π ξi Mi 作業 i の工数の変動の分散，歪度，尖度作業 i の工数の変動のシナリオツリーにおける第 t 実現値，X i ∈ RBi 作業 i の重み係数作業 i の工数の分散，歪度，尖度に対する重み係数. 変数. pti − Σ+ i , Σi + − Si , S i Ki+ , Ki−. 作業 i の工数の変動のシナリオツリーにおける第 t 実現値の発生確率，pti ∈ RBi 作業 i の工数の分散の理論値との差分作業 i の工数の歪度の理論値との差分. 作業 i の工数の尖度の理論値との差分これより，(t mod bt ) を t を bt で除した剰余とすると，作業 i の工数のシナリオツリーにおける t 番目 (t mod bt ) の実現値は Xit = Mi ξi と表すことができる．ただし，(t mod bt ) = 0 の場合は，Xit = Mi ξibt とする．. 6.4 数理モデル目的関数式 (32) は，決定変数 pti による分散，歪度，尖度とそれぞれの理論値との差を最小化している．. min. |N ′ |. ∑ i=1. − 2 + − λi {ωi1 (Σ+ i + Σi ) + ωi (Si + Si ). +ωi3 (Ki+ + Ki− )} 図5. (32). 5 個の作業の工数の変動を表すシナリオツリー. Vol. 72 No. 1（2021）. 43.

(8) 表 4 作業数 60, N C = 1.5 へのモーメントマッチング法適用結果方針 (i) 納期. 総費用. 80. 9805.52. 6810. 90. 8973.84. 100 110. s.t.. 方針 (ii) 計算時間 (s). 誤差 (%). 総費用. 2995.52. 115.92. 0.92. 9685.47. 6859. 2826.47. 246.64. -0.32. 6265. 2708.84. 289.33. -0.23. 8772.01. 6477. 2295.01. 70.51. -2.47. 8288.28. 5710. 2578.95. 221.53. -0.33. 8047.68. 6062. 1985.68. 100.55. -3.23. 7657.57. 5280. 2377.47. 236.61. -1.96. 7396.65. 5540. 1856.65. 227.8. -5.30. Bi ∑ t=1. 第 1 段階第 2 段階. ¯ i , i = 1, . . . , |N ′ | Xit pti = M pti = pji−1 ,. t=jbi +1. i = 1, . . . , |N ′ |, j = 1, · · · , Bi−1. Bi ∑. − ¯ i )2 pti − Σ+ (Xit − M i + Σi = Σ i ,. Bi ∑. ¯ i )3 pti − Si+ + Si− = Si , (Xit − M. Bi ∑. ¯ i )4 pti − Ki+ + Ki− = Ki , (Xit − M. t=1. i = 1, . . . , |N ′ |. t=1. i = 1, . . . , |N ′ |. t=1. 計算時間 (s). 誤差 (%). ンにおいても従来シナリオ数をそのまま用いた場合と. (33). (j+1)bi. ∑. 第 1 段階第 2 段階. (34). (35). (36). 比べ，誤差を抑えながら計算時間をおおよそ 10 ∼ 20. 分の 1 程度の削減に成功した．重み λ の決定に関する方針については，方針 (ii) の方が誤差が大きくなった．これは作業の工数に対して重みの与え方が適切でないと考えられる．方針 (ii) では工数の差が非常に小さい場合にも明確に順序を付けてしまうため，差が小さい場合は重みの差も比較的小さくすべきであると考えられる．よって手法として方針 (i) が有効であると考えられる．さらにモーメントマッチング法適用後のシナリオ数を表 5 に示す．これによってシナリオ数が大幅に減少することがわかる．表 5 モーメントマッチング法適用後のシナリオの本数元のシナリオ数 243. i = 1, . . . , |N ′ |. (37). i = 1, . . . , |N ′ |. (38). i = 1, . . . , |N ′ |, t = 1, · · · , Bi. (39). − + − + − Σ+ i , Σi , Si , Si , Ki , Ki ≥ 0,. pti ≥ 0, p10 = 1,. 式 (33) は，実現値と確率の積が期待値の理論値と一致するという制約を表している．制約式 (34) では，シナリオツリーにおいて子ノードの確率の総和が親ノードの確率と一致させている．式 (35),(36),(37) はそれぞれ分散，歪度，尖度の期待値との差分を与えている．目的関数 (32) の λi , ωi1 , ωi2 , ωi3 の値の与え方が重要である．本研究では ωi1 = ωi2 = ωi3 = 4 と等しくし， λi の与え方について 2 通りの方針に基づいて実験を行った．方針 (i) 確率変動が起こる作業の工数の比をとって. λi の値とした．方針 (ii) 確率変動が起こる最も小さい工数をもつ作業から順に 1, 2, 3, · · · と与えた． 6.5 モーメントマッチング法適用結果. 方針 (i) 方針 (ii) 6. 5. 7 おわりにプロジェクトは不確実な状況で実行される場合も多く，不確実性を考慮した事前の決定が必要になる．そのなかで初期計画によるスケジュールと不確実性の判明に対応する追加決定の計画は重要となる．本研究では，プロジェクトスケジューリングにおいて重要である時間と費用のトレードオフとクラッシングを考慮した 2 段階確率計画問題の数理モデルを初めて示した．そして確率変動を伴う DTCTP-C に対して，妥当不等式とモーメントマッチング法を用いた効果的な解法を開発した．現実の問題への応用が今後は望まれる．また，複数の資源を必要とする作業をもつプロジェクトについての拡張が今後検討できる．1 種類だけでなく複数の資源を必要とする場合の数理モデルの研究が必要となる．今後の展望としては各時刻においての使用可能な資源量を考慮に加えたモデルの作成を行い，最大使用資源数と最小使用資源数の差を抑えることで，より現実的なスケジューリングを行うことが可能となる．. モーメントマッチング法を適用して得られた結果を表 4 に示す．また，表 3 の結果と比較すると，どの納期のパター 44. 日本経営工学会論文誌.

(9) 参. 考文献. ¨ Erel, E. and G¨ [ 1 ] Hazir, O., unalay, Y.: “Robust Optimization Models for the Discrete Time/Cost Trade-off Problem,” Int. J. Prod. Econ., Vol. 130, No. 1, pp. 87-95 (2011) ¨ Haouari, M. and Erel, E.: “Discrete [ 2 ] Hazir, O., Time/Cost Trade-off Problem: A Decompositionbased Solution Algorithm for the Budget Version,” Comp. & Oper. Res., Vol. 37, No. 4, pp. 649-655 (2010) [ 3 ] Deˇ girmenci, G. and Azizoˇ glu, M.: “Branch and Bound Based Solution Algorithms for the Budget Constrained Discrete Time/Cost Trade-off Problem,” J. Oper. Res. Soc., Vol. 64, pp. 1474-1484 (2013) [ 4 ] Zhu, G., Bard, J. F. and Yu, G.: “A Two-stage Stochastic Programming Approach for Project Planning with Uncertain Activity Durations,” J. Scheduling, Vol. 10, pp. 167-180 (2007) [ 5 ] Jeang, A.: “Project Management for Uncertainty with Multiple Objectives Optimisation of Time, Cost and Reliability,” Int. J. Prod. Res., Vol. 53, No. 5, pp. 1503-1526 (2015). Vol. 72 No. 1（2021）. [ 6 ] Brooks Jr, F. P.: The Mythical Man-Month, Essays on Software Engineering, Anniversary Edition, 2nd Edition, Addison-Wesley Professional (1995) [ 7 ] Jørgensen, T. and Wallace, S. W.: “Improving Project Cost Estimation by Taking into Account Managerial Flexibility,” Eur. J. Oper. Res., Vol. 127, No. 2, pp. 239-251 (2000) [ 8 ] Birge, J. R. and Louveaux, F.: “Introduction to Stochastic Programming,” Springer (1997) [ 9 ] 椎名孝之: 「確率計画法」, 朝倉書店 (2015) [10] Kolish, R. and Sprecher, A.: “PSPLIB-A Project Scheduling Library,” Eur. J. Oper. Res., Vol. 96, No. 1, pp. 205-216 (1997) [11] Davis, E. W.: “Project Network Summary Measures Constrained-resource Scheduling,” AIIE Trans., Vol. 7, No. 2, pp. 132-142 (1975) [12] Høyland, K. and Wallace, S. W.: “Generating Scenario Trees for Multistage Decision Problems,” Manage. Sci., Vol. 47, No. 2, pp. 295-307 (2001) [13] Xu, D., Chen, Z. and Yang, L.: “Scenario Tree Generation Approaches using K-means and LP Moment Matching Methods,” J. Comput. Appl. Math., Vol. 236, No. 17, pp. 4561-4579 (2012). 45.

(10)