여러분이 어떤 작업들을 처리해야 한다고 해봅시다. 작업들은 특수한 기계에 의해 처리되며, 여러분은 동일한 성능을 가진 기계를 여러 대 받았습니다. 작업들 사이에는 선후행 관계가 없습니다. 다시 말해, 어떤 작업을 처리하기 위해서 다른 어떤 작업이 처리되어야 한다는 식의 조건은 존재하지 않습니다. 당연히 여러분은 일을 빨리 끝내고 싶어 합니다. 과연 어떻게 작업을 기계에 할당해야 할까요?
만약 모든 작업이 수행되는 시간이 동일하면 이 문제는 쉽게 해결됩니다. 작업의 개수를 \(n\), 기계의 대수를 \(m\)이라고 했을 때, 각 기계마다 최대 \( \lceil n/m \rceil \) 개씩 넣어주면 되겠습니다. 모든 작업이 끝나는 시각이 이보다 빠를 수 없다는 것은 비둘기집 원리를 사용하면 쉽게 증명할 수 있습니다.
문제는 작업마다 수행되는 시간이 다를 경우입니다. 이때도 쉬운 해결 방법이 있을까요? 안타깝게도 그렇게 되면 문제는 어려워집니다. 정확히는 NP-난해(NP-hard)합니다. 즉, P와 NP가 같지 않은 이상에야 다항 시간에 이 문제를 해결할 수 있는 방법이 없다는 것이죠. 그러니 대신 이 문제를 근사적으로 해결할 방법을 찾아야 겠죠.
이 글은 위 문제를 해결하는 4/3-근사 알고리즘을 소개합니다. 아래는 다음과 같이 구성되어 있습니다. 먼저 문제를 엄밀히 정의한 후, 알고리즘을 제시하겠습니다. 그리고 먼저 해당 알고리즘이 2의 근사비를 갖는다는 것을 보이겠습니다. 다음, 그 분석을 수정하면 4/3이라는 훨씬 좋은 근사비를 갖는다는 것을 증명하겠습니다.
문제 정의 및 알고리즘
문제를 엄밀히 정의해 보겠습니다. 입력으로 우리에게 \(m\)개의 동일한 기계와 \(n\)개의 작업이 주어집니다. 각 작업 \(j\)는 총 \(p_j\) 시간 동안 수행되며, 이는 모든 기계에서 동일하게 적용됩니다. 한 기계에서는 두 개 이상의 작업을 동시에 처리할 수 없으며, 어떤 작업이 수행되기 시작하면 그 작업이 끝날 때까지 다른 작업을 할당할 수 없습니다. 모든 작업들을 기계에 할당했을 때, 어떤 작업 \(j\)가 끝나는 시각을 \( C_j \)라고 하겠습니다. 그러면 모든 작업이 끝나는 시각은 \( C_\mathsf{max} := \max_{j} C_j \)가 되겠죠. 우리의 목표는 \( C_\mathsf{max} \)를 최소화시키는 것입니다.
이제 이 문제를 해결하는 간단한 탐욕 알고리즘(greedy algorithm)을 소개하겠습니다.
알고리즘 1. A greedy algorithm for load-balancing
입력: 기계, 작업
출력: 할당 방법
- 일반성을 잃지 않고 작업의 인덱스가 수행 시간의 내림차순으로 정렬되었다고 가정하자. 즉, \[ p_1 \geq p_2 \geq \cdots \geq p_n \]을 만족한다.
- 각 작업 \(j = 1, \cdots, n\) 순서대로, 지금까지 기계 중에서 가장 먼저 완료되는 기계에 곧바로 해당 작업을 할당한다.
- 할당을 반환한다.
알고리즘이 동작하는 방식은 간단합니다. 먼저 작업들을 수행 시간의 내림차순으로 정렬합니다. 그 후, 수행 시간이 긴 것부터 순서대로 기계에 할당합니다. 이때 어느 기계에 할당하냐면, 지금까지 기계에 할당된 것을 보았을 때, 가장 먼저 끝나는 기계에 넣어주는 것이죠. 이 문제에서는 기계를 쉬게 할 필요가 없으므로 넣어줄 때는 유휴 시간 없이 곧장 넣어주면 됩니다.
2의 근사비 분석
먼저 알고리즘 1이 2-근사 알고리즘이라는 것을 보이겠습니다. 그러기 위해서는 다음의 두 정리가 필요합니다. 어떤 입력에서 모든 작업을 처리하는 가장 이른 시각, 즉 최적값은 \( C^\star_\mathsf{max} \)로 표기하겠습니다.
정리 1. 최적해의 하한 1
어떤 입력에서든 \( C^\star_\mathsf{max} \geq \frac{\sum_{j = 1}^n p_j}{m} \)을 만족한다.
[증명] 총 \(m\)개의 기계가 있기 때문에, 비둘기집의 원리에 의해 반드시 어떤 기계는 \( \frac{\sum_{j = 1}^n p_j}{m} \) 이후에 종료합니다. □
정리 2. 최적해의 하한 2
어떤 입력에서든 \( C^\star_\mathsf{max} \geq \max_{j = 1, \cdots, n} p_j \)을 만족한다.
[증명] 어떤 기계든 어떤 작업을 한번 처리하기 시작하면 끝날 때까지는 그 작업만 처리해야 합니다. 가장 수행 시간이 긴 작업이 분명 어느 기계에는 할당될 것이므로, 최소한 가장 수행 시간이 긴 작업을 처리할 때까지는 기다려야 합니다. □
알고리즘 1에 의해 각 작업 \(j\)가 완료된 시각을 \(C_j\)라고 했고, 그 중 가장 늦은 시각 \(C_\mathsf{max}\)가 우리가 최적화하고 싶은 값이었습니다. 위 정리를 활용하면 쉽게 이 알고리즘이 2-근사 알고리즘이라는 사실을 얻을 수 있습니다.
정리 3. 2의 근사비
\(C_\mathsf{max} \leq 2C^\star_\mathsf{max}\)를 항상 만족한다.
[증명] 가장 늦게 완료된 작업을 \(\ell\)이라고 하겠습니다. 즉, \( C_\mathsf{max} = C_\ell \)을 만족합니다. \(\ell\)이 시작할 때를 \( S_\ell := C_\ell - p_\ell \)이라고 하겠습니다. 알고리즘이 \(\ell\)을 넣을 때를 생각해 보겠습니다. 작업 \(\ell\)이 \(S_\ell\)에 시작했다는 뜻은, 시각 \(0\)부터 \(S_\ell\)까지는 모든 기계가 어떤 작업을 돌리고 있다는 뜻입니다. 다시 말해,
\[ m \times S_\ell \leq \sum_{j = 1}^n p_j\]
를 이끌어낼 수 있다는 것이죠. 양변에 \(m\)을 나누면,
\[S_\ell \leq \frac{\sum_{j = 1}^n p_j}{m} \leq C^\star_\mathsf{max} \]
라는 사실을 얻을 수 있습니다. 여기서 마지막 부등식은 정리 1을 통해 이끌어낼 수 있죠. 마지막으로 정리 2를 통해,
\[ C_\ell = S_\ell + p_\ell \leq 2 C^\star_\mathsf{max} \tag{1} \]
를 이끌어낼 수 있습니다. □
4/3의 근사비
더 세밀한 분석을 거치면 이 알고리즘이 훨씬 좋은 근사비를 갖는다는 것을 증명할 수 있습니다. 직관적인 설명을 먼저 드리도록 하겠습니다. 앞에서 2의 근사비는 식 1에서 얻을 수 있었습니다. 근데 만약 \( p_\ell \leq \alpha C^\star_\mathsf{max}\)이었다면, \( C_\ell \leq (1 + \alpha) C^\star_\mathsf{max} \)가 되었겠죠. 따라서 마지막에 끝나는 작업의 길이에 따라 알고리즘 1의 근사비가 결정된다는 것을 알 수 있습니다.
이 생각을 정형화하기 위해서는 한 가지 가정을 해줄 필요가 있습니다. 이는 바로 마지막에 끝나는 작업 \( \ell \)이 가장 수행 시간이 짧은 작업이라는 점입니다. 사실 이렇게 가정을 해도 일반성을 잃지 않습니다. 만약 \( \ell \)이 마지막 작업이 아니라고 하겠습니다. 이때, 그 후에 들어오는 작업들인 \( \ell + 1, \cdots, n\)을 모두 지운 새로운 입력을 생각해 봅시다. 새로운 입력에서 모든 작업이 완료되는데 걸리는 최소 시각을 \( D^\star_\mathsf{max} \)라고 부르도록 하죠. 이때, 새로운 입력은 원래 입력의 부분집합이므로 분명 \( D^\star_\mathsf{max} \leq C^\star_\mathsf{max} \)를 만족합니다.
하지만 알고리즘 1은 \( \ell \)을 처리할 때까지 정확히 동일하게 동작합니다. 여기서 원래 입력은 \( \ell + 1, \cdots, n\)을 처리해봐야 완료 시각을 늦추지 않았고, 반대로 새로운 입력은 \(\ell\)을 처리한 후에 바로 종료합니다. 따라서 두 입력 모두 완료 시각이 \( C_\ell \)이죠. 만약 이 알고리즘이 새로운 입력에 대해서 \( C_\ell \leq \rho D^\star_\mathsf{max} \)를 만족했다면, 자연스럽게 원래 입력에 대해 \( C_\ell \leq \rho C^\star_\mathsf{max} \)도 만족하게 됩니다.
이제 경우의 수를 \( p_\ell \)의 길이가 짧을 때와 길 때로 나누어 고려해 보겠습니다. 짧을 때는 앞에서 얘기한 대로 쉽게 증명할 수 있습니다.
정리 4. 마지막 작업의 수행 시간이 짧은 경우
만약 \( p_\ell \leq C^\star_\mathsf{max} / 3 \)라면, \( C_\ell \leq 4/3 \cdot C^\star_\mathsf{max} \)이다.
[증명] 식 1에서 바로 이끌어낼 수 있습니다.
안타깝게도 긴 경우에는 위 논의를 그대로 따라갈 수 없습니다. 하지만, 이 경우에는 처리해야할 작업이 그다지 많지 않다는 것을 유추할 수 있습니다. 따라서 다음과 같은 요긴한 정리를 얻을 수 있죠.
정리 5. 마지막 작업의 수행 시간이 긴 경우
만약 모든 작업 \(i\)의 수행 시간 \(p_i\)가 \( C^\star_\mathsf{max} / 3 \)보다 크다면, 알고리즘 1은 최적해를 출력한다.
[증명] 일반성을 잃지 않고 \( n > m\)이라고 가정하겠습니다. 그렇지 않으면 알고리즘 1은 기계에 작업을 하나씩 할당할 것이고, 이렇게 할당한 것이 최적해라는 사실도 쉽게 보일 수 있습니다.
이 입력에서 최적해가 어떻게 생겼을지 따져보겠습니다. 일단 한 가지 쉽게 확인할 수 있는 것은 최적해에서는 각 기계마다 최대 두 개의 작업을 처리한다는 것입니다. 그 이유는 만약 최적해에서 세 개 이상의 작업을 처리하는 기계가 있다면 완료 시각이 \( C^\star_\mathsf{max} \)를 넘어서 모순이 되기 때문입니다. 이를 통해 이러한 입력에서의 작업의 개수는 \(2m\)을 넘지 않는다는 것도 알 수 있습니다.
우리는 그러한 최적 할당 방법 중에서 특별한 모양의 것을 가지고 오겠습니다. 이는 다음과 같이 만들어집니다. 먼저 작업 \(1, \cdots, m\)까지는 각 기계에 하나씩 할당해 줍니다. 그 후, \(m + 1\)은 \(m\)이 할당된 기계에, \(m + 2\)는 \(m - 1\)이 할당된 기계에 할당해 줍니다. 이러한 방식으로 나머지 작업을 모두 할당해 주겠습니다. 다시 말하면, \( j = 1, \cdots, n - m \leq m\)에 대해, 작업 \( m + i \)는 작업 \( m - i + 1 \)과 같은 기계에 할당이 됩니다.
탐욕 알고리즘을 분석하는 일반적인 방법 중 'exchange argument'가 있습니다. 이를 활용하면 위 할당 방법이 최적해라는 것을 보일 수 있습니다. 그다지 어렵지 않으니 한번 직접 해보시는 것을 추천합니다.(사실 exchange argument는 항상 귀찮습니다. 허허.) 따라서 두 개씩 들어간 기계의 작업 각각은 모두 수행 시간이 \( 2/3 \cdot C^\star_\mathsf{max} \)보다 작다는 것을 알 수 있죠.
증명의 마지막 단계는 알고리즘 1이 위에서 만든 할당 방법과 동일한 것을 출력한다는 것입니다. 먼저 작업 \(1, \cdots, m\)까지는 동일합니다. 다음에 작업 \( m + 1 \)을 넣을 때는 \(m\)이 할당된 기계에 함께 할당해 줄 겁니다. 그렇다면 작업 \( m + 2 \)는 어떨까요? 가능한 경우는 두 가지가 있습니다. 작업 \(m - 1\)이 할당된 기계에 넣거나 작업 \( m \)과 \( m + 1\)이 할당된 기계에 넣는 것이죠.(왜 그럴까요?) 앞에서 우리는 \( p_{m - 1} < 2/3 \cdot C^\star_\mathsf{max} \)라는 사실을 이끌어 냈습니다. 동시에 우리는 \( p_m + p_{m + 1} > 2/3 \cdot C^\star_\mathsf{max} \)라는 사실도 쉽게 알 수 있습니다. 그러니 당연히 작업 \( m + 2 \)는 \( m - 1 \)이 할당된 기계에 함께 할당이 되게 됩니다. 이를 귀납적으로 보이면 우리가 원하는 바를 얻을 수 있습니다. □
위 두 정리를 통해 우리는 알고리즘 1이 4/3-근사 알고리즘이라는 사실을 증명할 수 있습니다.
정리 6. 4/3의 근사비
알고리즘 1은 이 문제를 해결하는 4/3-근사 알고리즘이다.
[증명] 앞에서 논의한 대로 일반성을 잃지 않고 알고리즘 1이 반환하는 할당 방법에서 가장 마지막으로 처리되는 작업은 수행 시간이 가장 짧은 작업 \(n\)이라고 가정할 수 있습니다. 만약 \( p_n > C^\star_\mathsf{max} / 3 \)이면 정리 5에 의해 이 알고리즘은 최적해를 출력합니다. 그렇지 않다면, 정리 4에 의해 \( C_n \leq 4/3 \cdot C^\star_\mathsf{max} \)라는 사실을 유도할 수 있습니다. 알고리즘이 다항 시간에 동작한다는 것은 쉽게 보일 수 있습니다. □
마치며
이번 시간에는 수행 시간이 다를 수 있는 작업과 이를 처리하기 위해 동일한 성능을 가진 기계가 함께 주어졌을 때, 최대한 이른 시간에 모든 작업을 처리하는 할당 방법을 근사적으로 해결하는 알고리즘에 대해서 알아보았습니다. 이렇게 작업을 균등하게 분포하여 최대한 이른 시각에 모든 작업을 해결하려는 문제를 부하 균형 문제(load balancing problem)이라고 부릅니다.
이 글에서는 이 문제를 해결하는 4/3-근사 알고리즘을 보였습니다. 과연 더 잘할 수 있을까요? 놀랍게도 이 문제는 다항 시간 근사 해법(polynomial-time approximation scheme, PTAS)이 존재합니다. 이에 대한 개념은 지난번 배낭 문제에서 다루었었죠.
2020/06/19 - [근사 알고리즘/Knapsack] - [배낭문제 / Knapsack Problem] 다항 시간 근사 해법 (PTAS)
[배낭문제 / Knapsack Problem] 다항 시간 근사 해법 (PTAS)
지난 포스트에서는 유명한 NP-난해(NP-hard) 문제 중 하나인 배낭 문제(knapsack problem)에 대해서 공부하였습니다. 어떤 문제인지 다시 정의하자면, 우리에게는 물건의 집합 \(I = \{1, \cdots, n\}\)와 배낭�
gazelle-and-cs.tistory.com
다음에는 이에 대해서 더 알아보도록 하겠습니다.
내용에 문제가 있거나 궁금하신 점이 있으시면 알려주세요. 고맙습니다. :)
참조
[1] David P. Williamson and David B. Shmoys. The design of approximation algorithms. Cambridge university press, 2011.
'근사 알고리즘 > Job scheduling' 카테고리의 다른 글
| 상관없는 기계에서 가중치 완성 시간 최소화하기 (Minimizing Weighted Completion Time on Unrelated Machines) (0) | 2023.12.02 |
|---|
