仕事の割当問題
複数の仕事を複数のリソースに割当てることを考えます。特定の仕事のペアは同じリソースに割当てることができません。選ばれた仕事の価値の和を最大化します。
具体例を挙げます。
- いくつかの録画したい放送番組がいくつかあります。
- いくつかの録画可能な機器があります。
- 放送時間が重なる番組を同じ機器で録画することはできません。(同時録画禁止)
- 録画された番組の価値の総和を最大化します。
考え方
以下の5番組を考えます。録画機器は3台あるとします。
| 名称 | 開始時刻 | 終了時刻 | 価値 |
|---|---|---|---|
| A | 9:00 | 9:30 | 1 |
| B | 9:30 | 10:00 | 1 |
| C | 9:00 | 10:00 | 1 |
| D | 9:00 | 9:30 | 1 |
| E | 9:30 | 10:00 | 1 |
番組をノード、同時録画禁止をエッジとするグラフを考えます。
このグラフを機器ごとに複製した新たなグラフを考え、同じ番組間にもエッジを作成します。
このグラフ上で最大安定集合問題を解くことにより、「同時録画禁止を満たし、同じ番組を1つまでの機器でしか録画しない」解を求めることができますので、どの機器でどの番組を録画したらよいかがわかります。
Pythonで解いてみる
python3
import networkx as nx
from itertools import combinations
from more_itertools import grouper
from ortoolpy import maximum_stable_set, Autodict
g = nx.Graph()
dc = Autodict()
for i in 'ABCDE':
for j in'123':
g.add_node(dc[i+j], weight=1)
for i, j in grouper(2, 'ACADBCBECDCE'):
for k in '123':
g.add_edge(dc[i+k], dc[j+k])
for i in 'ABCDE':
for j, k in combinations('123', 2):
g.add_edge(dc[i+j], dc[i+k])
print([dc.keys[i] for i in maximum_stable_set(g)[1]])
>>>
['A1', 'B3', 'C2', 'D3', 'E1']
機器1でAとE、機器2でC、機器3でBとDを録画すればよいことが分かります。
以上