Programación: tareas en las máquinas

Question

Consideremos un modelo de una máquina en el que queremos minimizar $\sum_{j=1} ^{n} T_j$ , donde $T_j $ es la tardanza de un trabajo. Definimos $T_j = max(0, L_j)$ con $L_j = C_j - d_j$ .

$C_j$ es el tiempo de finalización y $d_j$ es la fecha de vencimiento del trabajo $j$ Así que $L_j$ es la tardanza. Además, defina $p_j$ como el tiempo de procesamiento del trabajo $j$ en la máquina .

Demuestre que si $p_i < p_j$ y $d_i < d_j$ entonces existe una programación óptima en la que el trabajo $i$ está programado antes del trabajo $j$ .

¿Cómo podemos hacerlo? ¿Cuándo existe un horario óptimo y cómo podemos obtenerlo?

Answer 1

Demostrar por construcción incremental. Suponga que tiene un programa óptimo en el que $p_i < p_j$ y $d_i < d_j$ , pero el trabajo $i$ está programado después de trabajo $j$ . Entonces demuestre que si cambia de trabajo $i$ y el trabajo $j$ se obtiene un horario que es al menos tan bueno como el original (con respecto a la tardanza total). Repita la operación hasta que la secuencia de trabajos satisfaga la condición establecida para todos los pares de trabajos. (Que si $p_i < p_j$ y $d_i < d_j$ , entonces el trabajo $i$ está programado antes del trabajo $j$ .)

Específicamente, mostrar que si se cambian los dos trabajos, entonces el nuevo $C_i$ es antes que la antigua $C_j$ (por una cantidad igual a $p_j-p_i$ ), y cada trabajo entre el trabajo $i$ y el trabajo $j$ también se adelanta en esa misma cantidad; y el nuevo $C_j$ es igual al antiguo $C_i$ (y todos los trabajos posteriores también tienen su tiempo de finalización original). Por lo tanto, el retraso total es al menos tan bueno como el original.