Planificar trabajos en una máquina

Esta tarea trata de hallar un plan óptimo para $n$ trabajos en una sola máquina, si el trabajo $i$ se puede procesar en tiempo $t_i$, pero por los $t$ segundos de espera antes de procesar el trabajo hay que pagar una penalización de $f_i(t)$.

Así, la tarea pide hallar una permutación de los trabajos tal que la penalización total sea mínima. Si denotamos por $\pi$ la permutación de los trabajos ($\pi_1$ es el primer ítem procesado, $\pi_2$ el segundo, etc.), entonces la penalización total es igual a:

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

Soluciones para casos especiales

Funciones de penalización lineales

Primero resolveremos el problema en el caso de que todas las funciones de penalización $f_i(t)$ son lineales, es decir, tienen la forma $f_i(t) = c_i \cdot t$, donde $c_i$ es un número no negativo. Nótese que estas funciones no tienen un término constante. En caso contrario podemos sumar todos los términos constantes, y resolver el problema sin ellos.

Fijemos alguna permutación $\pi$, y tomemos un índice $i = 1 \dots n-1$. Sea la permutación $\pi’$ igual a la permutación $\pi$ con los elementos $i$ e $i+1$ intercambiados. Veamos cuánto cambió la penalización.

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

Es fácil ver que los cambios solo ocurren en los sumandos $i$-ésimo e $(i+1)$-ésimo:

$$\begin{array}{rllll}& {\displaystyle }& {\displaystyle =c_{{\pi }_i^{\mathrm{\prime }}}\cdot \sum _{k=1}^{i-1}{t}_{{\pi }_k^{\mathrm{\prime }}}+c_{{\pi }_{i+1}^{\mathrm{\prime }}}\cdot \sum _{k=1}^i{t}_{{\pi }_k^{\mathrm{\prime }}}-c_{{\pi }_i}\cdot \sum _{k=1}^{i-1}{t}_{{\pi }_k}-c_{{\pi }_{i+1}}\cdot \sum _{k=1}^i{t}_{{\pi }_k}}& & \\ & {\displaystyle }& {\displaystyle =c_{{\pi }_{i+1}}\cdot \sum _{k=1}^{i-1}{t}_{{\pi }_k^{\mathrm{\prime }}}+c_{{\pi }_i}\cdot \sum _{k=1}^i{t}_{{\pi }_k^{\mathrm{\prime }}}-c_{{\pi }_i}\cdot \sum _{k=1}^{i-1}{t}_{{\pi }_k}-c_{{\pi }_{i+1}}\cdot \sum _{k=1}^i{t}_{{\pi }_k}}& & \\ & {\displaystyle }& {\displaystyle =c_{{\pi }_i}\cdot t_{{\pi }_{i+1}}-c_{{\pi }_{i+1}}\cdot t_{{\pi }_i}}& & \end{array}$$\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}

Es fácil ver que si el plan $\pi$ es óptimo, entonces cualquier cambio en él lleva a una penalización aumentada (o a la penalización idéntica); por lo tanto para el plan óptimo podemos escribir la siguiente condición:

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

Y tras reordenar obtenemos:

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

Así obtenemos el plan óptimo simplemente ordenando los trabajos por la fracción $\frac{c_i}{t_i}$ en orden no creciente.

Cabe señalar que construimos este algoritmo por el llamado método de permutaciones: intentamos intercambiar dos elementos adyacentes, calculamos cuánto cambió la penalización, y luego derivamos el algoritmo para hallar el método óptimo.

Función de penalización exponencial

Sea que la función de penalización se ve así:

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

donde todos los números $c_i$ son no negativos y la constante $\alpha$ es positiva.

Aplicando el método de permutaciones, es fácil determinar que los trabajos deben ordenarse en orden no creciente del valor:

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

Función de penalización monótona idéntica

En este caso consideramos el caso de que todas las $f_i(t)$ son iguales, y esta función es monótona creciente.

Es obvio que en este caso la permutación óptima es disponer los trabajos por tiempo de procesamiento $t_i$ no decreciente.

El teorema de Livshits-Kladov

El teorema de Livshits-Kladov establece que el método de permutaciones solo es aplicable para los tres casos mencionados arriba, es decir:

• Caso lineal: $f_i(t) = c_i(t) + d_i$, donde $c_i$ son constantes no negativas,
• Caso exponencial: $f_i(t) = c_i \cdot e_{\alpha \cdot t} + d_i$, donde $c_i$ y $\alpha$ son constantes positivas,
• Caso idéntico: $f_i(t) = \phi(t)$, donde $\phi$ es una función monótona creciente.

En todos los demás casos el método no se puede aplicar.

El teorema se demuestra bajo el supuesto de que las funciones de penalización son suficientemente suaves (existen las terceras derivadas).

En los tres casos aplicamos el método de permutaciones, mediante el cual el plan óptimo deseado se puede hallar por ordenamiento, de ahí en tiempo $O(n \log n)$.