METODOS PARA EL PROBLEMA DE JOB SHOP SCHEDULING

 

Contenido

 

 

Resumen.

 

 

1.      Introducción.

 

1.1.   Objetivo.

1.2.   Problema General de Asignación.

1.3.   El problema de scheduling

1.3.1.      Introducción

1.3.2.      Tipos de problemas

1.3.3.      Notación de los modelos de scheduling

1.3.3.1.           Notación Graham

1.3.3.2.           NotaciónConway

1.4.   Aspectos relevantes de JSSP.

 

2.      Job Shop Scheduling.

 

2.1.   Introducción.

2.2.   Representación en un grafo disyuntivo.

2.3.   Formulación Matemática.

2.4.   Análisis crítico.

 

3.      Modelos determinísticos

 

3.1.   Reglas simples.

3.2.   Ramificación y Acotamiento.

3.2.1.      Generalidades.

3.2.2.      Algoritmo de Carlier y Pinson.

3.2.3.      Algoritmo de Applegate y Cook.

3.2.4.      Algotitmo de Brucker et al.

3.2.5.      Algoritmo de Pinedo.

3.2.5.1.           Descripción.

3.2.5.2.           Ejemplo del algoritmo de pinedo.

3.2.6.      Algoritmo de Martín y Shmoys.

3.2.7.      Algoritmo de Perregaard y Clausen.

3.3.   Cuello de botella.

3.3.1.      Generalidades.

3.3.2.      Algoritmo de cuello de botella.

3.3.3.      Algoritmo de Cuello de botella GSL.

3.3.4.      Meta heurísticas que involucran a SB.

3.4.   Métodos Greedy

3.5.   CSP

3.6.   Métodos Lagrangeanos.

3.7.   Análisis crítico. 

 

4.      Modelos no deterministicos.

 

4.1.   Recocido simulado

4.1.1.      Generalidades.

4.1.1.1.           Optimización local.

4.1.1.2.           Procedimiento para Job Shop.

4.1.2.      Esquemas de perturbación.

4.1.3.      Recocido simulado cooperativo para JSSP.

4.2.   Algoritmos Genéticos.

4.2.1.      Generalidades.

4.2.2.      Componentes básicos de un GA.

4.2.3.      Algoritmo convencional de Nakano y Yamada.

4.2.4.      Constructores de schedules para GA.

4.2.5.      Cruzamientos en JSSP.

4.2.5.1.           Cruzamiento convencional.

4.2.5.2.           Cruzamiento de intercambio subsecuente.

4.2.5.3.           Cruzamiento que preserva precedencias.

4.3.   Procedimiento de búsqueda adaptable a través de un glotón aleatorio (GRASP).

4.3.1.      Generalidades.

4.3.2.      Búsquedas locales clásicas.

4.4.   Satisfactibilidad

4.4.1.      Generalidades.

4.4.2.      Codificación Crawford.

4.4.3.      Algoritmos aplicados.

4.4.4.      Algoritmo de tiempos tardíos.

4.5.   Búsqueda tabú

4.6.   Sistema Hormiga.

4.6.1.      Generalidades.

4.6.2.      Optimización por Colonia de Hormigas (ACO).

4.6.3.      Algoritmo Sistema de Hormiga (AS).

4.6.4.      ACO para JSSP.

4.7.   Análisis crítico.

 

5.      Conclusiones y líneas de investigación.

 

6.      Glosario.

 

7.      Referencias.