Planificar trabajos en dos máquinas

Esta tarea trata de hallar un plan óptimo para $n$ trabajos en dos máquinas. Cada ítem debe procesarse primero en la primera máquina, y después en la segunda. El $i$-ésimo trabajo toma tiempo $a_i$ en la primera máquina, y tiempo $b_i$ en la segunda. Cada máquina solo puede procesar un trabajo a la vez.

Queremos hallar el orden óptimo de los trabajos, de modo que el tiempo de procesamiento final sea el mínimo posible.

Esta solución que se discute aquí se llama regla de Johnson (por S. M. Johnson).

Cabe señalar que la tarea se vuelve NP-completa si tenemos más de dos máquinas.

Construcción del algoritmo

Nótese primero que podemos asumir que el orden de los trabajos para la primera y la segunda máquina tiene que coincidir. De hecho, como los trabajos para la segunda máquina se vuelven disponibles después de procesarlos en la primera, y si hay varios trabajos disponibles para la segunda máquina, entonces el tiempo de procesamiento será igual a la suma de sus $b_i$, independientemente de su orden. Por lo tanto solo es ventajoso enviar los trabajos a la segunda máquina en el mismo orden en que los enviamos a la primera.

Consideremos el orden de los trabajos, que coincide con su orden de entrada $1, 2, \dots, n$.

Denotamos por $x_i$ el tiempo ocioso de la segunda máquina inmediatamente antes de procesar $i$. Nuestro objetivo es minimizar el tiempo ocioso total:

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

Para el primer trabajo tenemos $x_1 = a_1$. Para el segundo trabajo, como se envía a la máquina en el tiempo $a_1 + a_2$, y la segunda máquina se libera en $x_1 + b_1$, tenemos $x_2 = \max\left((a_1 + a_2) - (x_1 + b_1), 0\right)$. En general obtenemos la ecuación:

$$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)$$

Ahora podemos calcular el tiempo ocioso total $F(x)$. Se afirma que tiene la forma

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

donde

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

Esto se puede verificar fácilmente por inducción.

Ahora usamos el método de permutaciones: intercambiaremos dos trabajos vecinos $j$ y $j+1$ y veremos cómo esto cambiará el tiempo ocioso total.

Por la forma de la expresión de $K_i$, está claro que solo cambian $K_j$ y $K_{j+1}$; denotamos sus nuevos valores con $K_j’$ y $K_{j+1}‘$.

Si este cambio de los trabajos $j$ y $j+1$ aumentó el tiempo ocioso total, tiene que ser el caso que:

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

(Intercambiar dos trabajos también podría no tener ningún impacto. La condición de arriba es solo suficiente, pero no necesaria.)

Después de quitar $\sum_{i=1}^{j+1} a_i - \sum_{i=1}^{j-1} b_i$ de ambos lados de la desigualdad, obtenemos:

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

Y después de quitar los signos negativos:

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

Así obtuvimos un comparador: al ordenar los trabajos con él, obtenemos un orden óptimo de los trabajos, en el que ningún par de trabajos se puede intercambiar con una mejora del tiempo final.

Sin embargo se puede simplificar aún más el ordenamiento, si se mira el comparador desde otro ángulo. El comparador se puede interpretar de la siguiente manera: si tenemos los cuatro tiempos $(a_j, a_{j+1}, b_j, b_{j+1})$, y el mínimo de ellos es un tiempo correspondiente a la primera máquina, entonces el trabajo correspondiente debería hacerse primero. Si el tiempo mínimo es un tiempo de la segunda máquina, entonces debería ir después. Así podemos ordenar los trabajos por $\min(a_i, b_i)$, y si el tiempo de procesamiento del trabajo actual en la primera máquina es menor que el tiempo de procesamiento en la segunda, entonces este trabajo debe hacerse antes que todos los trabajos restantes, y en caso contrario después de todas las tareas restantes.

De una u otra forma, resulta que por la regla de Johnson podemos resolver el problema ordenando los trabajos, y así recibir una complejidad temporal de $O(n \log n)$.

Implementación

Aquí implementamos la segunda variación del algoritmo descrito.

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

Toda la información de cada trabajo se guarda en un struct. La primera función ordena todos los trabajos y computa el plan óptimo. La segunda función computa los tiempos de finalización de ambas máquinas dado un plan.