Industria

DIVISIÓN DE INGENIERÍA INDUSTRIAL

ALUMNO:
ERIK UREÑA HUERTA

MATERIA:
ADMINISTRACIÓN DE OPERACIONES II

CATEDRÁTICO:
JUDITH ORTIZ RAMOS

EJERCICIOS
VERANO
JUN/JUL2011

CALIFICACIÓN DEL TRABAJO
-------------------------------------------------

ALGORITMOS DE JOHNSON

El algoritmo de Johnson es una forma de encontrar el camino más corto entre todos los pares de vértices deun grafo dirigido disperso. Permite que las aristas tengan pesos negativos, si bien no permite ciclos de peso negativo. Funciona utilizando el algoritmo de Bellman-Ford para hacer una transformación en el grafo inicial que elimina todas las aristas de peso negativo, permitiendo por tanto usar el algoritmo de Dijkstra en el grafo transformado

PASOS A SEGUIR PARA EL LOGARITMO DE JOHNSON
1.Primero se añade un nuevo nodo q al grafo, conectado a cada uno de los nodos del grafo por una arista de peso cero.
2. En segundo lugar, se utiliza el algoritmo de Bellman-Ford, empezando por el nuevo vértice q, para determinara para cada vértice v el peso mínimo h(v) del camino de q a v. Si en este paso se detecta un ciclo negativo, el algoritmo concluye.
3. Seguidamente, a las aristas delgrafo original se les cambia el peso usando los valores calculados por el algoritmo de Bellman-Ford: una arista de u a v con tamaño w(u, v), da el nuevo tamaño w(u, v) + h(u) – h(v)
4. Por último, para cada nodo s se usa el algoritmo de Dijkstra para determinar el camino más corto entre s y los otros nodos, usando el grafo con pesos modificados.

CONDICIÓN DE JOHNSON

El problema bajoconsideración es el F2||Cmax, con todas las piezas y máquinas disponibles en el instante 0, y denominamos pj,ia la duración de la operación de la pieza i (i = 1, 2, ... , n) en la máquina j (j = 1, 2). Buscamos, en razón del primer lema, una única secuencia para ambas máquinas, ya que siempre existe una solución óptima de este tipo, lo que no descarta la posible existencia en algunos ejemplares desoluciones óptimas con secuencias diferentes en ambas máquinas. Johnson afirma que son óptimas las permutaciones en las que para cada pareja de piezas h e i tales que: min {p1,h , p2,i} < min {p2,h , p1,i}, la pieza h precede a la pieza i, pero pueden existir soluciones óptimas que no cumplan la condición. Si min {p1,h , p2,i} = min {p2,h , p1,i} la posición relativa de h e i en la secuencia noqueda definida, h puede estar antes que i o i antes que h, y en algunos casos esto puede llevar a la existencia de varias secuencias óptimas.
En el ejemplar 1 del problema F2||Cmax, Tabla1, muestra la existencia de soluciones óptimas que no cumplen esta condición. Las permutaciones {1,2,3}, {1,3,2} y {2,1,3} son óptimas, con Cmax = 9, y sin embargo la tercera no satisface la condición para las dosprimeras posiciones pues min {p1,2, p2,1} = min {2, 3} = 2; min {p1,1, p1,1} = min {2,1 } = 1.

MÉTODOS HEURÍSTICOS
Los métodos heurísticos específicos están relacionados con el conocimiento de un área en particular. Este incluye estructuras cognoscitivas más amplias para reconocer los problemas, algoritmos más complejos y una gran variedad de procesos heurísticos específicos
Es un métodobasado en la experiencia que puede utilizarse como ayuda para resolver problemas de diseño, desde calcular los recursos necesarios hasta en planear las condiciones de operación de los sistemas.

Función
Resolver mas rápido problemas conocidos o similares a otros conocidos.

Desventaja.
Dado que las heurísticas pueden equivocarse, es fundamental conocer los casos en los que son aplicables y loslímites a su uso.

En general
En la ingeniería, deben considerarse como ayudas o apoyos para hacer estimaciones rápidas y diseños preliminares, pero no como justificaciones finales de un diseño o proyecto.

MÉTODOS HEURÍSTICOS

N TRABAJOS EN UNA MÁQUINA
N TRABAJOS EN 2 MÁQUINAS
n Trabajos con Ruta Diferente en 2 Máquinas
n Trabajos en 3 Máquinas
N TRABAJOS EN M MÁQUINAS

“N” TRABAJOS...