한 대의 기계에서 작업 스케줄링하기¶

이 문제는 작업 $i$를 처리하는 데 $t_i$의 시간이 걸리고, 작업을 처리하기 전에 $t$초 동안 기다리면 $f_i(t)$의 페널티를 내야 할 때, 한 대의 기계에서 $n$개의 작업에 대한 최적 스케줄을 찾는 문제입니다.

따라서 이 문제는 총 페널티가 최소가 되는 작업의 순열을 찾는 것입니다. 작업의 순열을 $\pi$로 나타내면($\pi_1$은 첫 번째로 처리되는 항목, $\pi_2$는 두 번째 항목 등), 총 페널티는 다음과 같습니다.

$$F(\pi) = f_{\pi_1}(0) + f_{\pi_2}(t_{\pi_1}) + f_{\pi_3}(t_{\pi_1} + t_{\pi_2}) + \dots + f_{\pi_n}\left(\sum_{i=1}^{n-1} t_{\pi_i}\right)$$

특수한 경우의 해법¶

선형 페널티 함수¶

먼저 모든 페널티 함수 $f_i(t)$가 선형인 경우, 즉 $c_i$가 음이 아닌 수일 때 $f_i(t) = c_i \cdot t$ 꼴인 경우의 문제를 풀어 보겠습니다. 이 함수들에는 상수항이 없다는 점에 유의하십시오. 상수항이 있다면 모든 상수항을 따로 더해 두고, 상수항 없이 문제를 다시 풀면 됩니다.

어떤 순열 $\pi$를 고정하고, 인덱스 $i = 1 \dots n-1$을 하나 잡읍시다. 순열 $\pi'$를 순열 $\pi$에서 원소 $i$와 $i+1$을 맞바꾼 순열이라고 합시다. 페널티가 얼마나 바뀌는지 살펴봅시다.

$$F(\pi') - F(\pi) =$$

변화는 $i$번째와 $(i+1)$번째 항에서만 일어난다는 것을 쉽게 알 수 있습니다.

$$\begin{align} &= c_{\pi_i'} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_{i+1}'} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_{i+1}} \cdot \sum_{k = 1}^{i-1} t_{\pi_k'} + c_{\pi_i} \cdot \sum_{k = 1}^i t_{\pi_k'} - c_{\pi_i} \cdot \sum_{k = 1}^{i-1} t_{\pi_k} - c_{\pi_{i+1}} \cdot \sum_{k = 1}^i t_{\pi_k} \\ &= c_{\pi_i} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \end{align}$$

스케줄 $\pi$가 최적이라면 여기에 어떤 변화를 주더라도 페널티가 증가한다는 것(또는 같은 페널티가 된다는 것)을 쉽게 알 수 있으므로, 최적 스케줄에 대해 다음 조건을 쓸 수 있습니다.

$$c_{\pi_{i}} \cdot t_{\pi_{i+1}} - c_{\pi_{i+1}} \cdot t_{\pi_i} \ge 0 \quad \forall i = 1 \dots n-1$$

이를 정리하면 다음을 얻습니다.

$$\frac{c_{\pi_i}}{t_{\pi_i}} \ge \frac{c_{\pi_{i+1}}}{t_{\pi_{i+1}}} \quad \forall i = 1 \dots n-1$$

따라서 작업을 분수 $\frac{c_i}{t_i}$의 비오름차순으로 정렬하기만 하면 최적 스케줄을 얻습니다.

이 알고리즘은 이른바 순열 방법으로 구성했다는 점에 유의하십시오. 인접한 두 원소를 맞바꿔 보고, 페널티가 얼마나 바뀌는지 계산한 다음, 최적의 방법을 찾는 알고리즘을 유도했습니다.

지수 페널티 함수¶

페널티 함수가 다음과 같다고 합시다.

$$f_i(t) = c_i \cdot e^{\alpha \cdot t},$$

여기서 모든 수 $c_i$는 음이 아니며 상수 $\alpha$는 양수입니다.

순열 방법을 적용하면, 작업을 다음 값의 비오름차순으로 정렬해야 한다는 것을 쉽게 알 수 있습니다.

$$v_i = \frac{1 - e^{\alpha \cdot t_i}}{c_i}$$

동일한 단조 페널티 함수¶

여기서는 모든 $f_i(t)$가 같고, 이 함수가 단조 증가하는 경우를 다룹니다.

이 경우 최적 순열은 작업을 처리 시간 $t_i$의 비내림차순으로 배열하는 것임이 자명합니다.

Livshits-Kladov 정리¶

Livshits-Kladov 정리에 따르면 순열 방법은 앞서 언급한 세 가지 경우에만 적용할 수 있습니다. 즉, 다음과 같습니다.

선형인 경우: $f_i(t) = c_i(t) + d_i$이며, 여기서 $c_i$는 음이 아닌 상수입니다.
지수인 경우: $f_i(t) = c_i \cdot e_{\alpha \cdot t} + d_i$이며, 여기서 $c_i$와 $\alpha$는 양의 상수입니다.
동일한 경우: $f_i(t) = \phi(t)$이며, 여기서 $\phi$는 단조 증가 함수입니다.

그 밖의 모든 경우에는 이 방법을 적용할 수 없습니다.

이 정리는 페널티 함수가 충분히 매끄럽다는(3계 도함수가 존재한다는) 가정 아래에서 증명됩니다.

세 가지 경우 모두 순열 방법을 적용하며, 이를 통해 원하는 최적 스케줄을 정렬로, 즉 $O(n \log n)$ 시간에 찾을 수 있습니다.