1. Definiciones de Job Shop, Flow Shop y Flow Shop Permutacional

Job Shop (J)

Es el tipo de problema más general. En un Job Shop, cada pieza (orden) tiene su propio recorrido específico y potencialmente único a través de las máquinas. Para n piezas y m máquinas, el número de soluciones posibles es (n!)^m.

Flow Shop Genérico (F)

En un Flow Shop, todas las piezas siguen la misma secuencia o recorrido a través de las máquinas. Sin embargo, el transporte entre máquinas no es común, por lo que el orden de las piezas puede variar en las distintas máquinas. El número de soluciones posibles también es (n!)^m.

Flow Shop Permutacional (P)

Este es un caso específico de Flow Shop. Al igual que en el genérico, todas las piezas siguen la misma secuencia de máquinas. La restricción clave es que el orden (o permutación) de las piezas debe ser el mismo en todas las máquinas, como si estuvieran en una cinta transportadora. Esto reduce el espacio de búsqueda a n! soluciones posibles.

2. Problema de Programación Job-Shop (Regla SPT)

La regla SPT (Shortest Process Time) prioriza la orden de trabajo (OT) con el tiempo de operación más corto. FIFO (First In First Out) se usa para desempates, priorizando la OT que llegó primero a la cola.

¿Garantiza la regla SPT alcanzar un óptimo local? ¿Y global?

No, la regla SPT no garantiza alcanzar ni un óptimo global ni uno local.

Óptimo Global

SPT es una regla de prioridad heurística. Las heurísticas son fáciles de aplicar, pero las soluciones «en ocasiones no son muy buenas» y son una alternativa a los métodos exactos (que sí garantizan el óptimo) y a las metaheurísticas.

Óptimo Local

El concepto de «óptimo local» requiere la definición de un vecindario (como en la búsqueda local). SPT es una regla de construcción greedy (glotona) que construye una solución paso a paso, no una técnica de búsqueda por trayectoria que se mueva por un vecindario. Por lo tanto, no opera bajo el concepto de óptimos locales y no garantiza encontrar uno.

3. Casos para usar Técnicas Metaheurísticas

Conviene utilizar técnicas metaheurísticas en los siguientes casos:

• Problemas NP-duros: Cuando un método exacto es ineficiente, requiriendo demasiado tiempo de ejecución o memoria.
• Solución «Buena» es Suficiente: Cuando una solución óptima global no es estrictamente necesaria, y una solución de buena calidad obtenida en un tiempo razonable es aceptable.
• Instancias de Gran Tamaño: Cuando el tamaño del problema (dimensionalidad) es muy grande, incluso si el problema es computacionalmente sencillo.
• Limitaciones de Tiempo Real: Cuando existe un tiempo límite estricto (ej. segundos o fracciones) para obtener una solución.
• Paisajes de Búsqueda Complejos: En problemas de optimización continuos no lineales (NLP) donde el espacio de soluciones es «rugoso» (multimodal, no derivable, ruidoso, etc.), haciendo que los métodos basados en gradiente fallen.
• Optimización de «Caja Negra»: Cuando se deben optimizar modelos no analíticos, como los resultados de una simulación.

4. Vecindarios para Flow Shop Permutacional (FSP)

Un FSP se representa como una permutación (orden). Usaremos la solución ejemplo S=(1, 2, 3, 4, 5) para n=5.

a) Tres definiciones de vecindario

Intercambio (Swap)

Descripción

Selecciona dos posiciones en la permutación e intercambia los elementos que están en ellas.

Ejemplo

Intercambiar posiciones 2 y 4 en S. S’ = (1, 4, 3, 2, 5).

Número de Vecinos

Se deben elegir 2 posiciones de n para intercambiar. El número de combinaciones es: C(n, 2) = (n x (n-1))/2.

Inserción (Insertion / Shift)

Descripción

Selecciona un elemento y lo reubica (inserta) en una posición diferente, desplazando los elementos intermedios para hacer espacio.

Ejemplo

Seleccionar el elemento en la posición 2 (el ‘2’) e insertarlo en la posición 4. S’ = (1, 3, 4, 2, 5).

Número de Vecinos

Hay n elementos para elegir. Cada elemento se puede insertar en (n-1) posiciones nuevas (todas menos la suya). Número de vecinos = n x (n-1).

Inversión (2-Opt)

Descripción

Selecciona una subsecuencia de la permutación (eligiendo dos puntos de corte) e invierte el orden de los elementos dentro de esa subsecuencia.

Ejemplo

Invertir la subsecuencia de la posición 2 a la 4 en S. S = (1, /2, 3, 4/, 5) -> S’ = (1, /4, 3, 2/, 5).

Número de Vecinos

Es el número de subsecuencias únicas que se pueden elegir. Esto equivale a elegir 2 puntos de corte (posiciones) de n. Número de vecinos = C(n, 2) = (n x (n-1))/2.

b) ¿Cuál definición es más adecuada?

La adecuación de un vecindario depende de la localidad. Un vecindario tiene «localidad fuerte» si un pequeño cambio en la representación (genotipo) causa un pequeño cambio en la calidad de la solución (fenotipo). Esto permite una búsqueda con sentido, similar al descenso de gradiente.

• Inversión (2-Opt) es muy disruptivo. Invertir una larga secuencia cambia muchas adyacencias a la vez. Es excelente para el TSP (donde «desenreda» cruces de caminos), pero para el makespan de un Flow Shop, su localidad es débil.
• Intercambio (Swap) es menos disruptivo que la Inversión.
• Inserción (Shift) a menudo se considera el movimiento más «pequeño» y con mayor localidad para problemas de secuenciación. Mover un solo trabajo a una posición adyacente es el cambio más pequeño posible en la secuencia.

Por lo tanto, el vecindario de Inserción (o en su defecto, Intercambio) es el más adecuado, ya que proporciona una localidad más fuerte y permite una exploración más fina y gradual del espacio de soluciones comparado con la Inversión.