プロジェクトスケジューリング問題 NetworkX

プロジェクトスケジューリング問題

プロジェクトスケジューリング問題は、タスクの完了時間やリソースの最適な割り当てを計画する問題です。

具体的な例として、4つのタスクとそれらの間の依存関係があるとしましょう。

  • Task A: 5日かかる
  • Task B: 3日かかる、Task A完了後に開始可能
  • Task C: 2日かかる、Task A完了後に開始可能
  • Task D: 4日かかる、Task BとTask C完了後に開始可能

これをPythonで解決してみましょう。

ここではnetworkxライブラリを使用してグラフを作成し、トポロジカルソートを行います。

まず、networkxをインストールします。

1
!pip install networkx

次に、Pythonコードで問題を解決します。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import networkx as nx
import matplotlib.pyplot as plt

# グラフの作成
G = nx.DiGraph()

# タスクの追加
tasks = {
    'A': {'duration': 5},
    'B': {'duration': 3},
    'C': {'duration': 2},
    'D': {'duration': 4}
}

# タスク間の依存関係を追加
dependencies = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')]

# グラフにタスクと依存関係を追加
for task, data in tasks.items():
    G.add_node(task, duration=data['duration'])

for dependency in dependencies:
    G.add_edge(dependency[0], dependency[1])

# トポロジカルソート
schedule = list(nx.topological_sort(G))

# タスクのスケジュール表示
print("スケジュール:")
for i, task in enumerate(schedule):
    print(f"Day {i + 1}: Task {task}")

# グラフの描画
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=800, node_color='skyblue', font_weight='bold', font_size=12, edge_color='gray', arrowsize=20)
plt.title('Project Scheduling')
plt.show()

このコードは、依存関係を持つタスクをグラフで表現し、トポロジカルソートを使ってスケジュールを作成します。

そして、タスクのスケジュールを表示し、グラフを描画します。

ソースコード解説

このコードは、Pythonのnetworkxとmatplotlibライブラリを使用してプロジェクトスケジュールを計画し、グラフで可視化するものです。

以下にコードの詳細を説明します：

1. ライブラリのインポート

1
2
import networkx as nx
import matplotlib.pyplot as plt
  • networkxはグラフの作成や操作、アルゴリズムの実行などをサポートするライブラリです。
  • matplotlib.pyplotはグラフを描画するためのライブラリです。

2. グラフの作成

1
G = nx.DiGraph()
  • DiGraph()関数を使って有向グラフを作成しています。

3. タスクの定義

1
2
3
4
5
6
tasks = {
    'A': {'duration': 5},
    'B': {'duration': 3},
    'C': {'duration': 2},
    'D': {'duration': 4}
}
  • タスクとその所要時間を辞書形式で定義しています。

4. タスク間の依存関係の定義

1
dependencies = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')]
  • タスク間の依存関係をタプルのリストとして定義しています。

5. グラフにタスクと依存関係を追加

1
2
3
4
5
for task, data in tasks.items():
    G.add_node(task, duration=data['duration'])

for dependency in dependencies:
    G.add_edge(dependency[0], dependency[1])
  • タスクとその所要時間をグラフにノードとして追加し、タスク間の依存関係をエッジとして追加しています。

6. トポロジカルソート

1
schedule = list(nx.topological_sort(G))
  • topological_sort()関数を使って、トポロジカルソートを行い、タスクのスケジュールを計画します。

7. タスクのスケジュール表示

1
2
3
print("スケジュール:")
for i, task in enumerate(schedule):
    print(f"Day {i + 1}: Task {task}")
  • タスクのスケジュールをコンソールに出力します。

8. グラフの描画

1
2
3
4
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True, node_size=800, node_color='skyblue', font_weight='bold', font_size=12, edge_color='gray', arrowsize=20)
plt.title('Project Scheduling')
plt.show()
  • spring_layout()関数でノードの位置を計算し、draw()関数でグラフを描画しています。
  • 各ノードはタスクを表し、エッジはタスク間の依存関係を示しています。

これにより、プロジェクトのタスクとその依存関係をグラフで視覚化し、トポロジカルソートによってスケジュールを立てています。

結果解説

この結果は、与えられたタスクとその依存関係に基づいて計画されたスケジュールを示しています。

それぞれのタスクが実行される日数と順序は以下のようになっています：

  • Day 1: Task A
  • Day 2: Task B
  • Day 3: Task C
  • Day 4: Task D

それぞれのタスクの日数に加え、依存関係がスケジュールに影響を与えています。
Task Aは最初に実行され、その後、Task BとTask Cがそれぞれ独立して実行されます。
最後に、Task BとTask Cの完了後にTask Dが実行されます。

グラフを見ると、各タスクがノードとして表され、依存関係が矢印で示されています。
このグラフは、タスク間の依存関係を視覚化し、トポロジカルソートによってタスクの実行順序が決定されました。
それにより、各タスクの開始と終了時期が特定されました。