7.3.2. Secuenciamiento de trabajos.

• Ejemplo. n = 4, p = (5, 10, 6, 3), d = (1, 3, 2, 1),

t = (1, 2, 1, 1)

Nodo actual: (1, 0, 1)

Cota inferior: CI = p2 = 10

Cota superior: CS = CI + p4 = 10 + 3 = 13

Estimación del coste: CE = (CI + CS)/2 = (10+13)/2 = 11.5

• Forma de realizar la poda:

  • El problema es de minimización y a partir de cada nodo existe al menos una solución. C: valor de la menor cota superior hasta ese punto.
  • Podar si la cota inferior es mayor que C.

• Estrategia de ramificación.

  • Supondremos LC-FIFO.

Diapositiva anterior

Diapositiva siguiente

Ir a la primera diapositiva

Ver versión gráfica