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

이 문제는 두 대의 기계에서 $n$개의 작업을 처리하는 최적의 스케줄을 찾는 문제입니다. 모든 항목은 먼저 첫 번째 기계에서 처리된 후, 이어서 두 번째 기계에서 처리되어야 합니다. $i$번째 작업은 첫 번째 기계에서 $a_i$의 시간이, 두 번째 기계에서 $b_i$의 시간이 걸립니다. 각 기계는 한 번에 하나의 작업만 처리할 수 있습니다.

최종 처리 시간이 가능한 한 최소가 되도록 하는 작업의 최적 순서를 찾고자 합니다.

여기서 다루는 이 풀이는 Johnson의 규칙이라고 불립니다(S. M. Johnson의 이름을 따서 명명되었습니다).

기계가 두 대보다 많으면 이 문제는 NP-완전이 된다는 점에 주목할 만합니다.

알고리즘의 구성¶

먼저, 첫 번째 기계와 두 번째 기계의 작업 순서가 일치해야 한다고 가정할 수 있다는 점에 주목하십시오. 실제로, 두 번째 기계의 작업은 첫 번째 기계에서 처리된 후에야 사용 가능해지며, 두 번째 기계에서 사용 가능한 작업이 여러 개 있다면 처리 시간은 순서와 관계없이 그 작업들의 $b_i$의 합과 같습니다. 따라서 작업을 첫 번째 기계에 보낸 것과 같은 순서로 두 번째 기계에 보내는 것은 이점만 있습니다.

작업의 순서가 입력 순서 $1, 2, \dots, n$과 일치한다고 가정해 봅시다.

작업 $i$를 처리하기 직전 두 번째 기계의 유휴 시간을 $x_i$로 표기합니다. 우리의 목표는 총 유휴 시간을 최소화하는 것입니다:

$$F(x) = \sum x_i ~ \rightarrow \min$$

첫 번째 작업에 대해서는 $x_1 = a_1$입니다. 두 번째 작업은 시각 $a_1 + a_2$에 기계로 보내지고, 두 번째 기계는 $x_1 + b_1$에 비게 되므로, $x_2 = \max\left((a_1 + a_2) - (x_1 + b_1), 0\right)$입니다. 일반적으로 다음 방정식을 얻습니다:

$$x_k = \max\left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1} b_i - \sum_{i=1}^{k-1} x_i, 0 \right)$$

이제 총 유휴 시간 $F(x)$를 계산할 수 있습니다. 이는 다음과 같은 형태를 가진다고 주장할 수 있습니다.

$$F(x) = \max_{k=1 \dots n} K_i,$$

여기서

$$K_i = \sum_{i=1}^k a_i - \sum_{i=1}^{k-1} b_i.$$

이는 귀납법을 이용하여 쉽게 확인할 수 있습니다.

이제 순열 방법을 사용합니다: 인접한 두 작업 $j$와 $j+1$을 교환하고, 이것이 총 유휴 시간을 어떻게 변화시키는지 살펴보겠습니다.

$K_i$ 식의 형태로부터 $K_j$와 $K_{j+1}$만 변한다는 것이 분명하며, 이들의 새 값을 $K_j'$와 $K_{j+1}'$로 표기합니다.

작업 $j$와 $j+1$의 이러한 교환이 총 유휴 시간을 증가시켰다면, 다음이 성립해야 합니다:

$$\max(K_j, K_{j+1}) \le \max(K_j', K_{j+1}')$$

(두 작업을 교환해도 아무런 영향이 없을 수도 있습니다. 위 조건은 충분조건일 뿐, 필요조건은 아닙니다.)

부등식의 양변에서 $\sum_{i=1}^{j+1} a_i - \sum_{i=1}^{j-1} b_i$를 제거하면 다음을 얻습니다:

$$\max(-a_{j+1}, -b_j) \le \max(-b_{j+1}, -a_j)$$

그리고 음의 부호를 없애면 다음과 같습니다:

$$\min(a_j, b_{j+1}) \le \min(b_j, a_{j+1})$$

따라서 비교자를 얻었습니다: 이를 기준으로 작업을 정렬하면, 어떤 두 작업을 교환해도 최종 시간이 개선되지 않는 최적의 작업 순서를 얻습니다.

하지만 비교 함수를 다른 관점에서 보면 정렬을 더 단순화할 수 있습니다. 비교 함수는 다음과 같이 해석할 수 있습니다. 네 개의 시간 $(a_j, a_{j+1}, b_j, b_{j+1})$이 있을 때 그중 최솟값이 첫 번째 기계에 해당하는 시간이라면, 해당 작업을 먼저 수행해야 합니다. 최솟값이 두 번째 기계의 시간이라면 해당 작업은 나중에 수행해야 합니다. 따라서 작업을 $\min(a_i, b_i)$ 기준으로 정렬할 수 있으며, 현재 작업의 첫 번째 기계에서의 처리 시간이 두 번째 기계에서의 처리 시간보다 작으면 이 작업은 남은 모든 작업보다 먼저 수행해야 하고, 그렇지 않으면 남은 모든 작업보다 나중에 수행해야 합니다.

어느 방식이든 Johnson의 규칙에 따라 작업을 정렬하여 문제를 풀 수 있으며, 그 결과 $O(n \log n)$의 시간 복잡도를 얻습니다.

구현¶

여기서는 앞서 설명한 알고리즘의 두 번째 변형을 구현합니다.

struct Job {
    int a, b, idx;

    bool operator<(Job o) const {
        return min(a, b) < min(o.a, o.b);
    }
};

vector<Job> johnsons_rule(vector<Job> jobs) {
    sort(jobs.begin(), jobs.end());
    vector<Job> a, b;
    for (Job j : jobs) {
        if (j.a < j.b)
            a.push_back(j);
        else
            b.push_back(j);
    }
    a.insert(a.end(), b.rbegin(), b.rend());
    return a;
}

pair<int, int> finish_times(vector<Job> const& jobs) {
    int t1 = 0, t2 = 0;
    for (Job j : jobs) {
        t1 += j.a;
        t2 = max(t2, t1) + j.b;
    }
    return make_pair(t1, t2);
}

각 작업에 대한 모든 정보는 구조체에 저장됩니다. 첫 번째 함수는 모든 작업을 정렬하고 최적의 스케줄을 계산합니다. 두 번째 함수는 주어진 스케줄에 대해 두 기계의 종료 시간을 계산합니다.