はじめに
今回も、応用情報技術者試験の過去問を解いていきます。
今回は、アローダイアグラムを使ったスケジュール計算に関する問題です。
プロジェクトマネジメント分野では、
- 最早結合点時刻
- 最遅結合点時刻
- クリティカルパス
- ダミー作業
といった用語がよく出てきます。
一見すると図が複雑で難しそうですが、基本は、
前から順番に日数を足し、複数の経路が合流するところでは最大値を選ぶ
というルールで解くことができます。
今回の問題では、特にダミー作業を無視してはいけないという点が重要です。
問題
図のアローダイアグラムで表されるプロジェクトがある。
結合点5の最早結合点時刻は、プロジェクトの開始から第何日目か。
ここで、プロジェクトの開始日は0日目とする。
引用元：独立行政法人情報処理推進機構（IPA）過去問
選択肢
| 選択肢 | 値 |
|---|---|
| ア | 4 |
| イ | 5 |
| ウ | 6 |
| エ | 7 |
解答
正解：エ（7日目）
解説
まず、「最早結合点時刻」とは何かを確認します。
最早結合点時刻とは、
その結合点に最も早く到達できる時刻
のことです。
ただし、ここで注意が必要です。
複数の作業が一つの結合点に集まっている場合、その結合点から先へ進むには、すべての先行作業が終わっている必要があります。
そのため、
複数の経路が合流する場合は、到達時刻の最大値を採用します。
図の作業を整理する
今回のアローダイアグラムを表にすると、次のようになります。
| 作業 | 開始点 | 終了点 | 所要日数 |
|---|---|---|---|
| A | 1 | 2 | 3 |
| B | 1 | 3 | 2 |
| C | 2 | 3 | 1 |
| D | 2 | 4 | 4 |
| E | 2 | 5 | 2 |
| F | 3 | 5 | 2 |
| G | 4 | 6 | 1 |
| H | 5 | 6 | 1 |
| ダミー作業 | 4 | 5 | 0 |
最早結合点時刻を順番に計算する
結合点1
プロジェクトの開始点です。
問題文では開始日を0日目としているので、
結合点1 = 0です。
結合点2
結合点1から作業Aを通ります。
作業Aの所要日数は3日なので、
0 + 3 = 3したがって、
結合点2の最早結合点時刻は3日目
です。
結合点3
結合点3には、2つの経路があります。
経路1：作業B
1 → 3
0 + 2 = 2経路2：作業A → 作業C
1 → 2 → 3
3 + 1 = 4結合点3では、作業Bと作業Cの両方が完了している必要があります。
したがって、
max(2, 4) = 4となり、
結合点3の最早結合点時刻は4日目
です。
結合点4
結合点4には、結合点2から作業Dを通って到達します。
結合点2：3日目
作業D：4日よって、
3 + 4 = 7したがって、
結合点4の最早結合点時刻は7日目
です。
結合点5
ここが今回の問題です。
結合点5には、3つの経路があります。
経路1：作業E
結合点2：3
作業E：2
3 + 2 = 5経路2：作業F
結合点3：4
作業F：2
4 + 2 = 6経路3：ダミー作業
結合点4の最早結合点時刻は7日目です。
ダミー作業の所要日数は0日なので、
7 + 0 = 7となります。
したがって、結合点5の最早結合点時刻は、
max(5, 6, 7) = 7です。
よって、
正解は「エ：7日目」
となります。
なぜ「最早」なのに最大値を取るのか
ここは非常に混乱しやすいポイントです。
「最早」と聞くと、
一番短い経路を選ぶのでは？
と思ってしまいがちです。
しかし、アローダイアグラムでは、結合点に入ってくるすべての先行作業が終わらないと次へ進めません。
今回の結合点5では、
作業E経由 → 5日目
作業F経由 → 6日目
ダミー経由 → 7日目となります。
5日目では、まだ作業Dが終わっていません。
6日目でも、まだ作業Dが終わっていません。
すべての条件がそろうのは7日目です。
つまり、
「最も早く次へ進める時刻」を求めるため、結果として最大値を取る
ということです。
ダミー作業は無視してはいけない
今回の問題で最も重要なのが、このポイントです。
ダミー作業とは、
実際の作業は行わないが、作業の前後関係を表すために使う仮想的な作業
です。
所要日数は0日です。
しかし、
0日だからといって計算上無視してよいわけではありません。
今回の図では、
結合点2
│
D：4日
↓
結合点4
│
ダミー：0日
↓
結合点5という関係があります。
つまり、結合点5に到達するためには、結合点4までの作業が完了している必要があります。
そのため、
結合点4：7日目
ダミー：0日
7 + 0 = 7を必ず考慮します。
問題の用語解説
アローダイアグラム
アローダイアグラムとは、プロジェクトにおける作業の順序や依存関係を、矢印を使って表した図です。
基本的には、
| 記号 | 意味 |
|---|---|
| ○ | 結合点 |
| → | 作業 |
| 数字 | 作業の所要時間 |
| 破線矢印 | ダミー作業 |
のように読みます。
PERTやCPMなど、プロジェクトの工程管理を考える際に使われます。
最早結合点時刻
最早結合点時刻とは、
その結合点に最も早く到達できる時刻
です。
開始点から前向きに計算します。
複数の経路が合流する場合は、
各経路の到達時刻の最大値
を採用します。
最遅結合点時刻
最遅結合点時刻とは、
プロジェクト全体を遅らせない範囲で、その結合点に到達していなければならない最も遅い時刻
です。
最早結合点時刻とは逆に、終了点から後ろ向きに計算します。
ダミー作業
ダミー作業とは、
実際の作業時間を持たず、作業の依存関係だけを表す仮想的な作業
です。
所要日数は、
0日
です。
ただし、今回の問題のように、
先行関係としては有効
なので、最早結合点時刻の計算では無視してはいけません。
クリティカルパス
クリティカルパスとは、
プロジェクト全体の所要期間を決める最も時間のかかる経路
です。
クリティカルパス上の作業が遅れると、基本的にはプロジェクト全体の完了も遅れます。
アローダイアグラムでは、最早結合点時刻や最遅結合点時刻と合わせてよく出題されます。
体系的位置づけ
今回の問題は、応用情報技術者試験のプロジェクトマネジメント分野に位置づけられます。
整理すると、次のようなイメージです。
マネジメント系
└─ プロジェクトマネジメント
└─ スケジュール管理
├─ アローダイアグラム
├─ 最早結合点時刻
├─ 最遅結合点時刻
├─ クリティカルパス
└─ 余裕時間また、関連するテーマとして、
- WBS
- ガントチャート
- EVM
- 工数見積り
- リスク管理
なども合わせて理解しておくとよいでしょう。
今回の問題の重要ポイント
今回の問題では、次の3点を押さえておきましょう。
① 最早結合点時刻は前から計算する
開始点を0として、前から順番に所要日数を足していきます。
② 複数の経路が合流したら最大値を取る
例えば、
5日
6日
7日の3つの経路が合流する場合、
max(5, 6, 7) = 7となります。
すべての先行作業が終わらないと、次の作業に進めないためです。
③ ダミー作業は0日だが無視しない
ダミー作業は、
所要時間 = 0です。
しかし、
作業の前後関係を表しているため、計算上の依存関係としては重要
です。
今回の問題では、まさにこの点が正解を分けています。
まとめ
今回の問題では、アローダイアグラムから結合点5の最早結合点時刻を求めました。
計算結果は、
E経由 ：3 + 2 = 5
F経由 ：4 + 2 = 6
ダミー経由 ：7 + 0 = 7したがって、
max(5, 6, 7) = 7となります。
よって、
正解は「エ：7日目」
です。
アローダイアグラムでは、
前から計算する → 合流点では最大値 → ダミー作業も依存関係として考える
という流れを覚えておくと、かなり解きやすくなります。
特に今回のような問題では、
「ダミーは0日だから無視する」のではなく、「0日だけれど先行関係は有効」
という点を覚えておくことが重要です。
コメント