Cambio heurístico de cuello de botella
La heurística de cambio de cuello de botella es un procedimiento destinado a minimizar el tiempo que se tarda en hacer el trabajo, o específicamente, el doespan en un taller de trabajo . El intervalo de producción se define como la cantidad de tiempo, de principio a fin, para completar un conjunto de trabajos de varias máquinas donde el orden de las máquinas está preestablecido para cada trabajo. Suponiendo que los trabajos realmente compiten por los mismos recursos (máquinas), siempre habrá uno o más recursos que actuarán como un " cuello de botella " en el procesamiento. Este procedimiento heurístico o de "regla general" minimiza el efecto del cuello de botella. La heurística de cuello de botella cambiante está diseñada para talleres con un número finito de trabajos y un número finito de máquinas.
La heurística de cambio de cuello de botella se utiliza en las industrias de fabricación y servicios que incluyen talleres de trabajo con restricciones en el orden en que se deben usar las máquinas para cada trabajo. Un buen ejemplo de una industria de servicios que puede usar esta técnica es un hospital. Las diferentes áreas dentro de un hospital, como el examen físico, la cabina de rayos X, la tomografía computarizada o la cirugía, podrían considerarse máquinas para esta aplicación en particular. Una restricción de precedencia en este contexto es cuando una máquina debe usarse antes que otra máquina en cualquier trabajo (o paciente). Se sabe que este tipo de problemas con múltiples máquinas son computacionalmente muy difíciles . Se proporciona el tiempo de procesamiento de cada trabajo en cada máquina (consulte el gráfico a la derecha para ver un ejemplo). Trabajoj que se realiza en la máquina i se denota ij . Se supone que cada máquina solo puede trabajar en un trabajo a la vez. El objetivo es determinar el programa que producirá el intervalo de tiempo más corto.
El primer paso es dibujar las restricciones de precedencia en una forma gráfica llamada gráfico (vea la imagen del dibujo original). Cada trabajo se origina en la "fuente", que etiquetaremos como U en el gráfico. Cada trabajo terminará en un "sumidero" de trabajos, que etiquetaremos como V en el gráfico. Cada fila de nodos en el gráfico representa un trabajo. Cada nodo del gráfico representa una tarea que forma parte del trabajo, el segundo número confirma el trabajo que se está realizando y el primer número indica qué máquina se está utilizando para esta tarea. En este punto, el tiempo de producción inicial de cada trabajo debe calcularse sumando los tiempos de procesamiento que toma el trabajo en cada una de las máquinas (o filas). Una vez que se ha calculado el tiempo de procesamiento de cada trabajo, el rendimiento 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 un MakeSpan 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 toma cada trabajo 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, denominado rij , 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, denominada d ij , se determina restando los tiempos de procesamiento del trabajo j en las máquinas que suceden a la máquina ien la orden de trabajo. el delmakespan. Una vez que se determina todo esto, se debe determinar la demora mínima para cada máquina. Esto se logra encontrando la ruta para cada máquina que reduce el retraso máximo visto para todos los trabajos en la máquina respectiva. Una forma de encontrar la ruta óptima es usar una rama y un límitetécnica. Consulte el gráfico de la derecha para ver un ejemplo de estos datos. Una vez que se determina la demora máxima para cada una de las máquinas respectivas, la máquina con la demora máxima más grande es el cuello de botella. Si no hay retraso máximo en ninguna de las máquinas, se pueden dibujar todas las secuencias óptimas de las máquinas en el diagrama de trabajo. Si hay dos máquinas con el mismo retraso máximo, se puede elegir cualquiera de ellas para el cuello de botella. Todo este trabajo se considera la primera iteración.
