3 de mayo de 2016

Secuenciación con una máquina: 2 teoremas

Haciendo uso del razonamiento de 4 partes mencionado cerca del final del post anterior, demostraremos 2 teoremas que nos ayudarán a reducir el número de suposiciones que hicimos en el mismo, pues resulta que algunos de ellos son consecuencia de otros.

Teorema 2.1

Dado el problema de programación de una sola máquina con una medida de desempeño regular, los programas sin tiempos muertos insertados constituyen un conjunto dominante.

Demostración

Sea $S$ un programa que contiene tiempos muertos insertados. En particular, suponga que en S, la máquina está en desuso en un intervalo $(a, b)$.
Sea S' un programa idéntico a S hasta el instante a, y en el cual los trabajos que ocurren en S después del instante b están recorridos una tiempo $b-a \gt 0$. Entonces cualquier trabajo j para el cual $C_j \leq a$ en el programa $S$ tendrá $C'_j = C_j$ en $S'$. Por otro lado, para cualquier trabajo j tal que $C_j \gt a$ en S, se tiene que $C'_j = C_j -(b-a)$ en S'. Por lo tanto, $C'_j \leq C_j \forall j$
Se sigue que $Z' \leq Z$ para cualquier medida regular, de tal manera que remover tiempos muertos nunca puede resultar en peor desempeño. Por lo que los programas sin tiempos muertos insertados constituyen un conjunto dominante.

De manera similar, es posible mostrar que en este problema, el conjunto de programas de permutación sin interrupciones es un conjunto dominante para cualquier medida regular.
En otras palabras, la condición C7 puede ser relajada, permitiendo interrumpir las operaciones, pero las interrupciones jamás derivarán en un programa  con mejor desempeño. Lo anterior resulta en el segundo teorema:

Teorema 2.2

En el problema de una máquina con medida regular, los programas sin interrupciones constituyen un conjunto dominante.

Como consecuencia de estos dos teoremas se sigue que las condiciones C6 y C7 no se necesitan explícitamente para los problemas de una máquina con medida regular, porque ya caracterizan conjuntos dominantes con las suposiciones C1 a C5.

Resumen

Los teoremas que aquí hemos mencionado nos permiten relajar las suposiciones que hicimos anteriormente, pues 2 de ellas caracterizaban conjuntos dominantes que ya están contenidas en las suposiciones C1 a C5.