Heurística del cuello de botella cambiante

El primer paso consiste en representar gráficamente las restricciones de precedencia ( véase la imagen del dibujo original). Cada trabajo se origina en el origen, que denominaremos U en el gráfico. Cada trabajo finaliza en un destino, que denominaremos V en el gráfico. Cada fila de nodos representa un trabajo. Cada nodo representa una tarea que forma parte del trabajo; el segundo número confirma la tarea que se está realizando y el primero indica la máquina que se utiliza para dicha tarea. En este punto, se debe calcular el tiempo de procesamiento inicial de cada trabajo sumando los tiempos de procesamiento que requiere en cada una de las máquinas (o filas). Una vez calculado el tiempo de procesamiento de cada trabajo, el tiempo total de finalización del sistema se determina por el tiempo de procesamiento más largo de cualquier trabajo individual. Esto supone que no hay conflictos de recursos y da como resultado un tiempo total de finalización de 22.

El siguiente paso es determinar qué recurso/máquina es actualmente el cuello de botella . Esto se hace considerando el tiempo de producción, denotado p _ij , que cada trabajo requiere en cada máquina, el tiempo de liberación de cada trabajo en cada máquina respectiva y la fecha de vencimiento de cada trabajo para cada máquina respectiva. El tiempo de liberación, denotado r _ij , se determina sumando los tiempos de procesamiento del trabajo j en las máquinas que preceden a la máquina i en el orden de trabajo del trabajo j . La fecha de vencimiento, denotada d _ij , se determina restando los tiempos de procesamiento del trabajo j en las máquinas que siguen a la máquina i en el orden de trabajo del tiempo de finalización. Una vez que todo esto se ha determinado, es necesario determinar el retraso mínimo para cada máquina. Esto se logra encontrando la ruta para cada máquina que reduce el retraso máximo observado para todos los trabajos en la máquina respectiva. Esto se puede hacer utilizando una técnica de ramificación y acotación, por ejemplo. También se puede aproximar utilizando otra heurística, como la heurística de la fecha de vencimiento más temprana . Una vez determinado el retraso máximo para cada máquina, la que presente el mayor retraso máximo se convierte en el cuello de botella. Si ninguna máquina tiene un retraso máximo, se pueden representar todas las secuencias óptimas en el diagrama de trabajo. Si dos máquinas tienen el mismo retraso máximo, cualquiera de ellas puede ser elegida como cuello de botella. Todo este proceso constituye la primera iteración.

Una vez identificado el cuello de botella , la ruta de la máquina debe incluirse en el grafo de trabajos (véase el diagrama de la iteración 1, donde las flechas de colores representan restricciones disyuntivas). Estas nuevas rutas pueden considerarse restricciones disyuntivas y deben tenerse en cuenta al determinar el nuevo tiempo de finalización. Las restricciones disyuntivas son las restricciones de la máquina en nuestro taller . El nuevo tiempo de finalización será igual al tiempo de finalización anterior más el retraso máximo de la máquina identificada como cuello de botella.

El siguiente paso es realizar un nuevo análisis para cada una de las máquinas restantes. Las diferencias ahora son que hay un nuevo tiempo de finalización y que se deben considerar tanto las restricciones de precedencia como las disyuntivas al determinar la fecha de lanzamiento de cada trabajo en la máquina. La ruta más larga para llegar desde el origen U hasta el trabajo correspondiente, obtenida al comparar los tiempos de lanzamiento de los trabajos precedentes para las restricciones disyuntivas y de precedencia, será la nueva fecha de lanzamiento. Las fechas límite serán el tiempo que el trabajo dado debe terminarse en la máquina correspondiente para que aún haya tiempo suficiente para terminar el trabajo en las máquinas subsiguientes dentro del tiempo de finalización. Esta es la longitud de la ruta más larga desde el trabajo hasta el destino V. Los trabajos precedentes se conocen a partir de las restricciones de precedencia.

De nuevo, determine qué máquina es el nuevo cuello de botella . Añada las nuevas restricciones disyuntivas al grafo (véase la iteración 2). Esta se considera la segunda iteración. El nuevo tiempo de finalización es el anterior más el retraso máximo del nuevo cuello de botella. Si el retraso máximo en todas las máquinas es cero, utilice todas las rutas para las restricciones disyuntivas del dibujo y el tiempo de finalización seguirá siendo el mismo que antes.

Este proceso se repite hasta que se hayan considerado todas las máquinas o el retraso máximo sea cero en todas las máquinas restantes. Cada vez que se repite el proceso, se considera una iteración y todas las restricciones disyuntivas pueden representarse en el diagrama de trabajo y máquina. En nuestro ejemplo, la siguiente iteración nos proporcionó un retraso máximo de cero para las máquinas 3 y 4, por lo que sus secuencias óptimas pueden incluirse en el diagrama (véase la Iteración 3).

En este punto, la heurística del cuello de botella cambiante está completa. El diagrama ahora debe incluir todas las restricciones de precedencia y todas las restricciones disyuntivas. El tiempo de finalización final es el tiempo de finalización original más todos los retrasos máximos de cada uno de los cuellos de botella respectivos. Es el tiempo mínimo necesario para completar todos los trabajos dadas estas restricciones de máquina y precedencia.