Meeting Room Scheduling Problem
회의실 스케줄링 문제
- 하나의 회의실을 여러 팀이 사용하고자 할 때,
회의들이 서로 겹치지 않게 하면서 최대한 많은 회의를 수용할 수 있도록 스케줄링하는 문제이다.
- 보통, 구현의 편의를 위해 한 팀의 회의 종료 시간과 다른 팀의 회의 시작 시간은 겹칠 수 있다고 가정한다.
(즉, 11시에 회의가 끝나고 곧바로 11시에 다른 팀이 회의를 시작하는 것이 가능하다.)
- \(n\)개의 회의가 요청된다 하고, 각각의 팀은 (회의 시작 시간, 회의 종료 시간) Pair를 넘겨준다.
- Greedy 알고리즘에서는 요청된 회의 시간들을 회의 종료 시간을 기준으로 오름차순으로 정렬한 다음,
종료 시간이 빠른 회의에 회의실을 배정한다.
(이때, 선택한 회의가 기존에 배정된 회의와 겹친다면, 배정을 포기하고 넘어간다.)
- 종료 시간이 빠른 회의를 선택하며 나간다는 점에서 "Greedy하다"고 표현할 수 있다.
(직관과 달리, 회의 시간이 짧은 회의들을 선택해나가는 것이 아니다.)
Mechanism (원리)
Implementation (구현)
Performance (성능)
Verification (검증)
Theorem. Greedy한 방법을 통한 회의실 스케줄링은 항상 Optimal Solution을 도출해낸다.
pf) 신청받은 회의들을 종료 시간이 빠른 순서대로 \(1, 2, \cdots, n\)까지 번호를 매긴다.
우선, 회의 1을 포함하는 최적해가 존재한다는 사실을 증명한다.
회의 1을 포함하지 않는 최적해 \(T\)가 있다 가정하자.
\(T\)에서 가장 먼저 끝나는 회의를 \(i\)라 할 때,
회의 \(i\)를 배고 회의 1을 넣어도 합법적인 스케줄이 된다.
즉, \(T \cup \{1\}-\{i\}\)로 바꾸어도 역시 최적해가 된다.
그러므로, 회의 1을 포함시켜 놓고,
나머지 중에서 같은 방식으로(재귀적으로) 최적해를 찾아간다.
Theorem. Complicated Scheduling Problem은 NP-Complete이다.
| Problem | Input | Query |
| Complicated Scheduling Problem (복잡한 회의실 스케줄링 문제) |
- 요청된 \(n\)개의 회의 - 각 회의의 소요 시간 - 각 회의별, 가능한 가장 이른 시작 시간 - 각 회의별, 가능한 가장 늦은 종료 시간 |
Input에서의 요구조건을 만족하도록 모든 회의를 한 줄로 스케줄링하는 방법이 존재하는가? |
| Subset-Sum Problem (부분 집합 합 문제) |
- \(n\)개의 양의 정수로 이루어진 집합 \(S\) - 양의 정수 \(t\) |
합이 \(t\)인 \(S\)의 부분 집합이 존재하는가? |
* 어떤 문제가 NP-Complete이려면, NP이고 NP-Hard이어야 한다.
- 이 때, NP-Hard임을 증명하는 것은
기존에 NP-Hard임이 증명된 문제를 해당 문제로 Reduction하여 논리적 관계를 보이는 것으로 이루어진다.
* 복잡한 회의실 스케줄링 문제가 NP-완비임을 보이기 위해,
기존에 NP-완비임이 증명된 "부분 집합 합 문제"를 이용한다.
pf)
1. Complicated Scheduling Problem이 NP(Nondeterministic Polynomial) 임을 증명한다.
입력의 요구조건을 만족하는 회의의 스케줄링 방법이 제공되었을 때,
(즉, 복잡한 회의실 스케줄링 문제의 Query에 Yes라 답할 근거가 주어질 때)
이것이 모든 요구조건을 만족하는지는 다항식 시간에 확인할 수 있다.
그러므로, 복잡한 회의실 스케줄링 문제는 NP이다.
2. Subset-Sum Problem \(\leq_{p}\) Complicated Scheduling Problem 임을 증명한다.
부분 집합 합 문제의 Instance에서 복잡한 회의실 스케줄링의 Instance로 아래와 같이 Reduction한다.
부분 집합 합 문제의 집합 \(S\) 의 원소들을 하나의 회의로 간주한다.
해당 원소의 값을 그 회의의 소요 시간으로 보고,
모든 회의의 가능한 가장 이른 시작 시간은 0,
모든 회의의 가능한 가장 늦은 종료 시간은 \(1 + \sum_{x\in S} x\) 로 할당한다.
추가로 하나의 회의를 생성하여 소요시간은 1,
가능한 가장 이른 시작 시간은 \(t\),
가능한 가장 늦은 종료 시간은 \(t+1\)로 할당한다.
(이러한 Reduction 과정들은 모두 다항식 시간에 이루어진다.)
이렇게 Reduction하면,
Subset-Sum Problem에서의
"합이 \(t\)인 \(S\)의 부분 집합이 존재하는가?"에 해당되는 Query는
Complicated Scheduling Problem에서의
"입력 요구조건을 만족하도록 모든 작업을 한 줄로 스케줄링하는 방법이 존재하는가?"에 해당되는 Query로
대치할 수 있는데, 근거는 아래와 같다.
Subset-Sum Problem에서 합이 \(t\)인 \(S\)의 부분 집합이 존재한다 가정하자.
이 부분 집합에 속하는 원소에 대응되는 회의들부터 임의의 순서로 수행된다.
시간 \(t\)가 되면 이 회의들은 모두 종료된 상태이다.
시간 \(t\)에 소요 시간이 1인 회의를 수행한다.
이후에 나머지 회의들을 임의의 순서로 수행한다.
시간 \(1 + \sum_{x\in S} x\) 가 되면, 모든 회의가 종료된 상태가 된다.
즉, 스케줄링이 가능하다.
또한, Complicated Scheduling Problem을 Subset-Sum Problem으로 대치하여 문제를 풀어낼 수도 있는데,
그 근거는 아래와 같다.
모든 회의의 요구 시간을 만족하는 회의 스케줄링 방법이 존재한다 가정하자.
시간 \(t\)부터 \(t+1\) 구간에 새로 만든 소요 시간이 1인 회의가 수행되므로,
나머지 회의들은 시간 \(0~t\)와 \(t+1~1+\sum_{x\in S} x\) 의 두 구간에 나누어져 있을 수밖에 없다.
두 구간 중 앞의 구간에 스케줄링된 회의에 대응되는 Subset-Sum의 원소들을 합하면 \(t\)가 된다.
그러므로, 합이 \(t\)인 \(S\)의 부분 집합이 존재한다.
Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)