Планування задач на двох машинах

Ця задача полягає в пошуку оптимального розкладу для $n$ задач на двох машинах. Кожен елемент спершу має бути оброблений на першій машині, а вже потім на другій. $i$-та задача займає $a_i$ часу на першій машині та $b_i$ часу на другій машині. Кожна машина може обробляти лише одну задачу за раз.

Ми хочемо знайти оптимальний порядок задач так, щоб підсумковий час обробки був якомога меншим.

Розв'язок, який ми тут обговорюємо, називається правилом Джонсона (на честь S. M. Johnson).

Варто зауважити, що задача стає NP-повною, якщо ми маємо більш ніж дві машини.

Коли підходить цей алгоритм?

• Чи машин рівно дві, і кожна задача проходить їх у фіксованому порядку (спершу перша, потім друга)? (якщо машина одна → Планування робіт на одній машині)
• Чи мета — мінімізувати загальний час завершення (makespan), а не штраф за очікування?
• Чи відомі для кожної задачі обидва часи $a_i$ та $b_i$, щоб застосувати компаратор $\min(a_i, b_i)$ правила Джонсона?

Побудова алгоритму

Зауважимо спершу, що ми можемо вважати, що порядок задач для першої та другої машини має збігатися. Справді, оскільки задачі для другої машини стають доступними після їх обробки на першій, і якщо є кілька задач, доступних для другої машини, то час обробки дорівнюватиме сумі їхніх $b_i$ незалежно від їхнього порядку. Тому вигідно відправляти задачі на другу машину в тому самому порядку, в якому ми відправляли їх на першу машину.

Розглянемо порядок задач, що збігається з порядком їх подачі на вхід $1, 2, \dots, n$.

Через $x_i$ позначимо час простою другої машини безпосередньо перед обробкою $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)$, і якщо час обробки поточної задачі на першій машині менший за час обробки на другій машині, то цю задачу треба виконати перед усіма рештою задач, інакше — після всіх решти задач.

Так чи інакше, виявляється, що за правилом Джонсона ми можемо розв'язати задачу сортуванням задач і таким чином отримати часову складність $O(n \log n)$.

Реалізація

Тут ми реалізуємо другий варіант описаного алгоритму.

C++

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);
}

Python

from dataclasses import dataclass


@dataclass
class Job:
    a: int
    b: int
    idx: int


def johnsons_rule(jobs: list[Job]) -> list[Job]:
    # Сортуємо за ключем min(a, b)
    jobs = sorted(jobs, key=lambda j: min(j.a, j.b))
    first: list[Job] = []
    last: list[Job] = []
    for j in jobs:
        if j.a < j.b:
            first.append(j)
        else:
            last.append(j)
    # Задачі другої групи додаємо у зворотному порядку
    return first + last[::-1]


def finish_times(jobs: list[Job]) -> tuple[int, int]:
    t1 = t2 = 0
    for j in jobs:
        t1 += j.a
        t2 = max(t2, t1) + j.b
    return t1, t2

TypeScript

interface Job {
  a: number;
  b: number;
  idx: number;
}

function johnsonsRule(jobs: Job[]): Job[] {
  // Сортуємо за ключем min(a, b)
  const sorted = [...jobs].sort((x, y) => Math.min(x.a, x.b) - Math.min(y.a, y.b));
  const first: Job[] = [];
  const last: Job[] = [];
  for (const j of sorted) {
    if (j.a < j.b) {
      first.push(j);
    } else {
      last.push(j);
    }
  }
  // Задачі другої групи додаємо у зворотному порядку
  return first.concat(last.reverse());
}

function finishTimes(jobs: Job[]): [number, number] {
  let t1 = 0;
  let t2 = 0;
  for (const j of jobs) {
    t1 += j.a;
    t2 = Math.max(t2, t1) + j.b;
  }
  return [t1, t2];
}

Go

type Job struct {
    a, b, idx int
}

func johnsonsRule(jobs []Job) []Job {
    // Сортуємо за ключем min(a, b)
    sorted := append([]Job(nil), jobs...)
    sort.Slice(sorted, func(i, j int) bool {
        return min(sorted[i].a, sorted[i].b) < min(sorted[j].a, sorted[j].b)
    })
    var first, last []Job
    for _, j := range sorted {
        if j.a < j.b {
            first = append(first, j)
        } else {
            last = append(last, j)
        }
    }
    // Задачі другої групи додаємо у зворотному порядку
    res := first
    for i := len(last) - 1; i >= 0; i-- {
        res = append(res, last[i])
    }
    return res
}

func finishTimes(jobs []Job) (int, int) {
    t1, t2 := 0, 0
    for _, j := range jobs {
        t1 += j.a
        t2 = max(t2, t1) + j.b
    }
    return t1, t2
}

Уся інформація про кожну задачу зберігається в структурі. Перша функція сортує всі задачі та обчислює оптимальний розклад. Друга функція обчислює моменти завершення для обох машин за заданим розкладом.

Відеоматеріали