CONTENIDO

Resumen………………………………………………………………………………..

Contenido….……………………………………………………………………………

Índice de tablas…………………………………………………………………………

Índice de figuras………………………………………………………………………..

1. Introducción………………………………………………………………….............

      1.1. Antecedentes…………………………………………………………...............

             1.1.1. La importancia del estudio de JSSP…………………………………….

             1.1.2. Tipos de problemas en JSSP…………………………………………….

             1.1.3. Procesos en un sistema operativo……………………………………….

             1.1.4. Aplicación de multiprocesamiento para JSSP…………………………..

             1.1.5. Enfoques cooperativos en JSSP…………………………………………

      1.2. Entorno y planteamiento del problema………………………………...............

      1.3. Objetivos de la investigación…………………………………………………..

      1.4. Alcance de la investigación……………………………………………………

      1.5. Contribuciones…………………………………………………………………

      1.6. Organización de la tesis………………………………………………………..

2. El problema de Job Shop Scheduling………………………………………………..

      2.1. Modelo de formulación disyuntiva……………………………………….........

      2.2. Modelo del grafo disyuntivo…………………………………………...............

      2.3. Tipos de schedules……………………………………………………………..

             2.3.1. Schedule semiactivo……………………………………….....................

             2.3.2. Schedule activo…………………………………………………….........

             2.3.3. Schedule sin demora……………………………………….....................

      2.4 Ciclos en el grafo disyuntivo…………………………………………………...

3. Métodos aplicados a JSSP…………………………………………………………...

3.1.   Reglas de Atención.............................................................................................

3.2.   Ramificación y Acotamiento..............................................................................

3.3.   Cuello de botella.................................................................................................

3.4.   Recocido simulado.............................................................................................

3.5.   Algoritmos Genéticos.........................................................................................

3.6.   Procedimiento GRASP……………………………………………….………..

3.7.   Búsqueda tabú....................................................................................................

3.8.   Sistema Hormiga................................................................................................

3.9.   Técnicas para satisfacción de restricciones........................................................

4. Algoritmo de recocido simulado con cooperación de procesos……………..............

      4.1. Algoritmo en paralelo RSCP…………………………………………………..

             4.1.1. Descripción y funcionamiento de los procesos en RSCP………….........

             4.1.2. Descripción del algoritmo RSCP…..………………………………........

      4.2. Algoritmo secuencial RSS……………………………………………………..

5. Implementación de RSCP para JSSP……...…………………………………………

      5.1. Representación simbólica de un schedule……………………………………..

      5.2. Solución inicial acotada………………………………………………………..

      5.3. Algoritmo de recocido simulado con reinicio……………………………........

      5.4. Etapa de cruzamiento…………………………………………………………..

6. Análisis de resultados..………………………………………………………............

      6.1. Benchmarks usados de JSSP y equipo de pruebas……………………….........

      6.2. Análisis comparativo de eficiencia de las vecindades N_src vs. N₁……………..

      6.3. Análisis de sensibilidad de los parámetros de recocido simulado para JSSP.

      6.4. Análisis de efectividad de la cooperación en JSSP………………………........

             6.4.1. Cooperación en base al número de procesos……………………………

             6.4.2. Cooperación en problemas pequeños………………………...................

             6.4.3. Cooperación en problemas medianos………………………...................

             6.4.4. Cooperación en problemas grandes……………………………………..

      6.5 Efectividad de la paralelización de RSCP………………………...……………

             6.5.1. Efecto en problemas pequeños…………………………………….........

             6.5.2. Efecto en problemas medianos…………………………………….........

             6.5.3. Efecto en problemas grandes………………………………....................

      6.6 Desempeño de los algoritmos en paralelo y secuencial………………..............

             6.6.1. Comparación de desempeño entre RSCP y RSS………………………..

             6.6.2. Comparación de resultados de RSCP y RSS con otros algoritmos...…...

      6.7 Degradación de RSCP al aumentar la instancia a resolver……………………..

7. Conclusiones y trabajo futuro……………………………………………..................

Referencias……………………………………………………………………………..

Apéndice A. Clase que genera los procesos en RSCP.………………………………...

Apéndice B. Resultados experimentales de la vecindad N_src…………………………..

Apéndice C. Abreviaciones y términos……………………………………….………..

Apéndice D. Ejemplos de algoritmos para JSSP……………………………………….

                 D.1. Algoritmo de ramificación y acotamiento………….………………….

                 D.2. Algoritmo de cuello de botella………….……………………………..

                 D.3. Algoritmo de recocido simulado………………………………………

                 D.4. Algoritmo genético...................................……………………………..

                 D.5. Algoritmo GRASP……………………………………………………..

                 D.6. Algoritmo sistema hormiga……………………………………………

                 D.7. Procedimiento básico de búsqueda……….……………………………

Anexo A. shopDlg.h: Archivo de cabecera en lenguaje C++, que define

                estructuras y clases usadas en el programa RSCP…………………………...

Anexo B. shopdlg.cpp: Definición de funciones miembro en C++, para la

     implementación del programa RSCP………………………………………..

i

ii

v

ix

1

2

2

4

7

10

11

11

12

13

14

14

16

16

18

19

20

21

21

22

25

25

28

33

35

42

46

48

50

53

55

55

57

60

65

67

67

69

72

78

84

84

85

90

93

93

100

101

102

105

105

108

109

112

112

116

121

124

127

136

138

139

140

140

153

157

161

163

166

170

173

176