작업 할당 문제

여러 작업을 여러 리소스에 할당하는 것을 고려합니다. 특정 작업 쌍은 동일한 리소스에 할당할 수 없습니다. 선택한 직업의 가치의 합을 극대화합니다.

구체적인 예를 든다.

일부 녹화하고 싶은 방송 프로그램이 몇 개 있습니다.

여러 녹화 가능한 장비가 있습니다.

방송 시간이 겹치는 프로그램을 같은 기기로 녹화할 수 없습니다. (동시 녹화 금지)

녹화된 프로그램의 가치 합계를 극대화합니다.

사고방식

다음의 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


프로그램을 노드, 동시 녹화 금지를 엣지로 하는 그래프를 생각합니다.


이 그래프를 기기 마다 복제한 새로운 그래프를 생각해, 같은 프로그램간에도 엣지를 작성합니다.


이 그래프상에서 최대 안정 집합 문제를 풀면 "동시 녹화 금지를 충족하고 같은 프로그램을 하나까지의 기기에서만 녹화한다"해를 구할 수 있으므로 어느 기기에서 어느 프로그램을 녹화하면 좋은지 알 수 있습니다.

파이썬으로 풀어보세요

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를 녹화하면 좋은 것을 알 수 있습니다.

이상