Ventajas-aplicacion-metaheuristicas-algoritmos-geneticos-busqueda-tabu-solucion-problemas-Job-Shop-Scheduling

Vista previa del material en texto

repositorio.uptc@uptc.edu.corepositorio.uptc@uptc.edu.co
VENTAJAS DE LA APLICACIÓN DE LAS METAHEURÍSTICAS, ALGORITMOS GENÉTICOS Y 
BÚSQUEDA TABÚ EN LA SOLUCIÓN DE PROBLEMAS DE JOB SHOP SCHEDULING 
 
ADVANTAGES OF APPLYING METAHEURISTICS GENETIC ALGORITHMS 
AND TABU SEARCH IN SOLVING PROBLEMS OF JOB SHOP SCHEDULING 
Yeimy Andrea Becerra1 
Fredy Enrique Alvarado2 
 
RESUMEN 
 
La tendencia actual en la investigación de métodos que resuelvan los problemas 
presentados en la programación de tareas dentro de los procesos de producción, 
se enmarca en la aplicación de metodologías inteligentes llamadas 
metaheurísticas en su forma pura e hibrida, ya que han mostrado ventajas en 
cuanto a costos, tiempos computacionales de procesamiento y en la calidad de la 
soluciones entregadas en problemas con complejidad computacional de tipo NP-
hard o no polinomiales duros como es el caso del problema de Job Shop 
Scheduling JSS. (Duarte et al, 2007). 
 
En este artículo se lleva a cabo el análisis y la revisión a las investigaciones de 
mayor rigor científico que han dado solución al problema de JSS mediante las 
metaheurísticas Búsqueda Tabú BT y Algoritmos Genéticos AG, brindando al 
lector una visión detallada de las ventajas que se obtienen con estas técnicas de 
optimización; los diferentes tiempos computacionales que se pueden alcanzar; la 
 
1Pregrado. Ingeniera Industrial. Investigadora UPTC. Calle 4 Sur No.15 -134 Sogamoso, Boyacá. 
yeimy.becerracastro@uptc.edu.co 
 
2Maestría. Ingeniero Industrial. Docente de planta e investigador. UPTC. Calle 4 Sur No.15 -134 
Sogamoso, Boyacá
. 
fredy.alvarado@uptc.edu.co 
 
 
mailto:yeimy.becerracastro@uptc.edu.co
mailto:fredy.alvarado@uptc.edu.co
importancia de los software, lenguajes de programación y equipos de cómputo 
empleados; características de los algoritmos y sus resultados computacionales. 
 
(Palabras clave: Job shop scheduling, metaheurísticas, algoritmos genéticos, 
búsqueda tabú) 
 
ABSTRACT 
 
The current trend in research on methods to solve the problems in scheduling 
tasks within the production process, is part of the implementation of intelligent 
methodologies called metaheuristics in its pure and hybrid form, as they have 
shown advantages in costs; computational processing times and the quality of the 
solutions delivered in computational complexity problems type NP-hard or hard 
Polynomial not, as in the case of job shop scheduling problem JSS. (Duarte et al, 
2007). 
 
This article carries out the analysis and review the investigations of greater 
scientific rigor that have given solution to the problem of JSS by metaheuristic 
Tabu Search TS and Genetic Algorithms GA, providing the reader with a detailed 
overview of the advantages gained with these optimization techniques; different 
computational times that can be achieved; the importance of software, 
programming languages and computer equipment used; characteristics of 
algorithms and computational results. 
 
(Keywords: Job shop scheduling, metaheuristics, genetic algorithms, tabu search) 
 
1. INTRODUCCIÓN 
 
En el problema del Job Shop JSSP se tienen n trabajos a secuenciar en m 
máquinas, teniendo en cuenta restricciones de diversa naturaleza y con el objetivo 
de optimizar uno o más criterios, teniendo como resultado la planificación de las 
actividades, su número total de posibles soluciones es (n!)m(French, 1982). 
 
El crecimiento exponencial del número de posibles soluciones hace que este 
problema sea reconocido como NP–hard (Jain y Meeran, 1999), es decir, no existe 
ningún algoritmo que en un tiempo polinomial pueda resolverlos de forma exacta, 
por lo cual aparecen los métodos aproximados como las metaheurísticas que 
permiten encontrar soluciones próximas de alta calidad en tiempos razonables. 
 
Dado todoello, investigadores de todo el mundo se han puesto en la tarea de 
solucionar esta clase de problemas, obteniendo métodos aproximados que no 
llegan a la solución exacta pero si encuentran una eficiente y en tiempo 
razonable, dentro de estos métodos se encuentran las metaheurísticas y en su 
versión más avanzada los híbridos metaheurísticos, los cuales han llegado a un 
gran reconocimiento en el ámbito científico y empresarial por sus excelentes 
resultados solucionando todo tipo de problemas NP. 
 
Las soluciones óptimas en la industria a problemas de Job shop scheduling 
son de vital importancia dadas las implicaciones económicas que traen consigo, 
por lo cual esta investigación analiza y expone las ventajas que se han logrado 
con la aplicación de técnicas inteligentes como los Algoritmos Genéticos (Genetic 
Algorithm–GA) y la Búsqueda Tabú (Tabu Search–TS). 
 
Las metaheurísticas: Búsqueda Tabú y Algoritmos Genéticos son unas de las 
técnicas más relevantes en la solución de problemas de optimización combinatoria 
como el problema de JSS, las cuales se potencian al ser hibridadas entre sí. 
 
Algoritmos Genéticos propuestos por Holland (Holland, 1975), seguido por 
Goldberg (Goldberg, 1989) y se basan en una población de soluciones candidatas, 
que evolucionan por medio de los mecanismos genéticos neo-darwinistas de 
selección, cruce y mutación. Son importantes ya que su aplicación más común ha 
sido la solución de problemas de optimización, donde han mostrado ser muy 
eficientes y confiables. 
 
La Búsqueda Tabú fue desarrollada por Fred Glover en 1989 y es de gran 
importancia debido a que combina procedimientos heurísticos de búsqueda local 
con la utilización “inteligente” de memoria. Estos elementos, combinados con 
estrategias de intensificación y diversificación, permiten “escapar” de óptimos 
locales y explorar distintas regiones del espacio de soluciones. Además, la técnica 
de búsqueda tabú es considerada en la actualidad, gracias a los resultados 
reportados por muchos autores, como una de las mejores heurísticas para 
solucionar problemas de optimización combinatoria(Glover y Laguna, 1997). 
 
Esta investigación se exponen en los siguientes numerales: el numeral 2, 
describe los materiales y métodos empleados para llevar a cabo este estudio. En 
el numeral 3, se exponen los resultados y la discusión de este estudio. En el 
numeral 3.1, se describen las características de los Algoritmos Genéticos 
aplicados al problema de JSS, los resultados computacionales obtenidos y sus 
ventajas. El numeral 3.2, se detallan las características de los algoritmos de 
Búsqueda Tabú empleados en el problema de JSS, los resultados 
computacionales obtenidos y sus ventajas. En el 3.3, se presentan las 
características de los algoritmos híbridos entre Algoritmos Genéticos y Búsqueda 
Tabú aplicados en la solución del problema del JSS y sus ventajas de 
implementación. En el numeral 4, se muestran las conclusiones. 
 
1. MATERIALES Y MÉTODOS 
 
Para la elaboración de esta revisión se consultó la base de datos SCOPUS, 
elegida debido a que es una amplia base de artículos científicos de gran rigor 
académico, lo cual permite realizar estudios de calidad. Los filtros de búsqueda 
empleados fueron los artículos científicos y de revisión más citados del año 2000 
al 2015 referentes a las metaheurísticas aplicadas en la solución del problema de 
JSS. A partir de toda la información recopilada se hizo un estudio comparativo que 
permitió describir las ventajas a la hora de aplicar técnicas de inteligencia artificial 
como Búsqueda Tabú y Algoritmos Genéticos (puros e híbridos) en los problemas 
de Job Shop Scheduling. 
 
2. RESULTADOS Y DISCUSIÓN 
 
1. Características de los Algoritmos Genéticos Aplicados al Problema 
de JSS, Resultados Computacionales Obtenidos y Ventajas 
 
Los Algoritmos Genéticos generan resultados eficientes en problemas de 
programación de tareas. En la tabla 1 se muestran las aplicaciones recientes de 
estos algoritmos en la solución del problemadel JSS y en la tabla 2 sus ventajas 
en cuanto a calidad de solución; tiempos computacionales; software; equipos de 
cómputo y lenguajes de programación empleados. 
 
Tabla 1. 
 
Descripción detallada de investigaciones de Algoritmos Genéticos aplicados 
al problema de JSS. 
CARACTERÍSTICAS DEL ALGORITMO Y DEL 
PROBLEMA 
AUTOR(ES) 
1. Representación del problema: Utilizan 4 
representaciones: (1) basada en operaciones; (2) 
basada en trabajos; (3) basada en lista de preferencia 
y (4) basada en reglas de prioridad. 
2. Población inicial: Generada aleatoriamente. 
3. Método de Selección de los progenitores: 
Aleatorio. 
(Ponnambalam et al, 
2001) 
4. Tamaño de la Población: 10 
5. Cantidad de puntos de cruzamiento: 4 puntos. 
6. Longitud del cromosoma: Dinámica de 
acuerdo a cada instancia. 
7. Cruce: Probabilidad 0.8; basado en el operador: 
cruce de orden generalizado GPX (Generalized-
Order-Crossover) de (Mattfeld, 1996). 
8. Mutación: Probabilidad 0.05; basada en ordenes 
o pedidos BOM (Based-Order-Mutation) de (Mattfeld, 
1996), la mutación altera el orden absoluto de las 
operaciones en la permutación, modificando la 
posición de las operaciones. 
9. Criterio de parada: Cuando el número de 
iteraciones alcanza el valor de 1000. 
10. Criterio a optimizar: Minimizar el Makespan. 
11. Instancias Testeadas (n × m): 20 instancias 
(ABZ; MT; YN; LA; ORB) obtenidas de la biblioteca de 
OR-Library (Beasley, 1990). 
12. Representación del problema: Se modifica la 
representación basada en operaciones tradicional en 
un Sistema Análogo que representa la utilización de 
una máquina en un tipo de unidad por un conductor 
de 10hm, considerando que cada segmento del 
cromosoma se utiliza para cada nivel de operaciones. 
El objetivo del sistema análogo es organizar los 
conductores de una manera que produzca la 
resistencia equivalente más pequeña. Esto a su vez 
constituye una nueva medida para la función de 
aptitud del algoritmo genético. 
13. Población inicial: Generada aleatoriamente. 
14. Método de Selección de los progenitores: 
(Al-Hakim, 2001) 
Aleatorio. 
15. Cantidad de puntos de cruzamiento: 1 punto. 
16. Longitud del cromosoma: Dinámica de 
acuerdo a cada instancia. 
17. Cruce: 2 Operadores: (1) un punto de cruce y (2) 
cruce diagonal. 
18. Mutación: 4 Operadores: (1) Selección de dos 
genes de un segmento y el intercambio de ellos; (2) 
Selección de dos segmentos del cromosoma y el 
intercambio de ellos; (3) Selección de un segmento y 
la inversión de las preferencias de los trabajos de ese 
segmento y (4) Teniendo en cuenta todo el 
cromosoma y la inversión de la estructura del gen 
para el cromosoma. 
19. Criterio a optimizar: Minimizar el Makespan. 
20. Instancias Testeadas (n × m): 40 instancias de 
5x5 a 20x50 
21. Representación del problema: Se construyen 3 
representaciones basadas en (1) la secuencia de 
trabajo; (2) la distribución de la máquina y (3) en el 
diagrama de Gantt. 
22. Población inicial: Generada aleatoriamente. 
23. Método de Selección de los progenitores: 
Aleatorio. 
24. Tamaño de la Población: 50 
25. Cantidad de puntos de cruzamiento: 1 punto. 
26. Longitud del cromosoma: 12. 
27. Cruce: 2 tipos de cruce basados en la secuencia 
de trabajo y la distribución de la máquina. 
28. Mutación: Probabilidad 0.2; se selecciona una 
operación al azar y uno de los padres. 
(Li, y Chen, 2010) 
29. Criterio de parada: Cuando el número de 
iteraciones alcanza al valor de 50. 
30. Criterio a optimizar: Minimizar el Makespan. 
31. Instancias Testeadas (n × m):1 instancia de 
8x5 
32. Representación del problema: Utilizan 3: (1) 
representación basada en operaciones y deducción 
del Schedule; (2) representación basada en trabajos y 
deducción del Schedule; (3) representación basada 
en la operación precedente y deducción del 
Schedule. 
33. Población inicial: Generada aleatoriamente. 
34. Método de Selección de los progenitores: Se 
utiliza el método de la Rueda de la Ruleta (Roulette-
wheel). 
35. Tamaño de la Población: 10 
36. Cantidad de puntos de cruzamiento: 2 puntos. 
37. Longitud del cromosoma: 12. 
38. Cruce: Probabilidad 0.8; basado en el operador: 
recombinación de bordes EX (edge-recombination). 
39. Mutación: Probabilidad 0.05; basada en ordenes 
o pedidos BOM (Based-Order-Mutation) de (Mattfeld, 
1996). 
40. Criterio de parada: Cuando el número de 
iteraciones alcanza al valor de 1000. 
41. Criterio a optimizar: Minimizar el Makespan. 
42. Instancias Testeadas (n × m): 24 instancias 
(ABZ; ORB; MT; LA; SWV; YN) obtenidas de la 
biblioteca de OR-Library (Beasley, 1990). 
(Amirthagadeswaran 
y Arunachalam, 
2006) 
43. Representación del problema: Representación 
en tres dimensiones 3DGA donde cada cromosoma 
(Wang et al, 2009) 
está formado por un número de m matrices (n×n) 
cuadradas, cada (n×n) es llamada matriz job–job. 
44. Población inicial: Generada aleatoriamente. 
45. Método de Selección de los 
progenitores:Aleatorio. 
46. Cantidad de puntos de cruzamiento: múltiples 
puntos. 
47. Longitud del cromosoma: Dinámica de 
acuerdo a cada instancia. 
48. Cruce: Basado en una unión de operadores de 
cruce tiene dos cromosomas de los padres y crea dos 
cromosomas del hijo en tres pasos. 
49. Mutación: El operador de mutación lleva dos 
cromosomas de los padres y crea dos cromosomas 
hijos, dos subgrupos de trabajos son elegidos al azar 
sin trabajos duplicados. 
50. Criterio a optimizar: Minimizar el Makespan. 
51. Instancias Testeadas (n × m): 5 instancias 
(SWV) obtenidas de la biblioteca de OR-Library 
(Beasley, 1990). 
52. Representación del problema: Representación 
basada en lista de preferencia y diagrama de Gantt. 
53. Población inicial: Generada aleatoriamente. 
54. Método de Selección de los progenitores: Se 
utiliza el método del Torneo (Tournamnet). 
55. Tamaño de la Población: 200 
56. Longitud del cromosoma: Dinámica de 
acuerdo a cada instancia. 
57. Criterio de parada: Cuando el número de 
iteraciones alcanza al valor de 500. 
58. Criterio a optimizar: Minimizar el Makespan. 
(Lestan, 2009) 
59. Instancias Testeadas (n × m): 2 instancias de 
10x10 y 20x5. 
60. Representación del problema: Representación 
basada en operaciones. 
61. Población inicial: Generada aleatoriamente. 
62. Método de Selección de los progenitores: Se 
utiliza el método de la Rueda de la Ruleta (Roulette-
wheel). 
63. Tamaño de la Población: 10 
64. Cantidad de puntos de cruzamiento: 4 puntos. 
65. Longitud del cromosoma: 12 
66. Cruce: Probabilidad 0.8; basado en los 
operadores: cruce de orden generalizado GPX 
(Generalized-Order-Crossover) de (Mattfeld, 1996) y 
operador de inversión INV. 
67. Mutación: Probabilidad 0.05; basada en ordenes 
o pedidos BOM (Based-Order-Mutation) de (Mattfeld, 
1996). 
68. Criterio de parada: Cuando el número de de 
iteraciones alcanza al valor de 1000. 
69. Criterio a optimizar: Minimizar el Makespan. 
70. Instancias Testeadas (n × m): 20 instancias 
(ABZ; MT; YN; LA; ORB) obtenidas de la biblioteca de 
OR-Library (Beasley, 1990). 
(Amirthagadeswaran 
y Arunachalam, 
2007) 
Fuente: Elaboración Propia. 
Tabla 2. 
 Ventajas en calidad de solución; tiempos computacionales; software; 
equipos de cómputo y lenguajes de programación utilizados en la solución 
del JSSP con Algoritmos Genéticos. 
AUTOR (ES) 
SOFTWARE Y 
LENGUAJE DE 
PROGRAMACIÓN 
VENTAJAS Y DESCRIPCIÓN 
(Ponnambalam et al, 
2001) 
Software: No 
especificado 
Lenguaje: C++ 
Resultados computacionales: El 
makespan mínimo fue de 1243s 
obtenido utilizando la representación 
basada en la lista de preferencia, 
pero el mejor tiempo computacional 
lo obtuvo la representación basada 
en operaciones; al final de los test la 
mejor representación que cumplió 
con tiempo computacional razonable 
y makespan mínimo fue la basada 
en trabajos. 
Tiempo computacional: con las 4 
representacionesutilizadas se 
obtuvieron resultados diferentes 
tiempos: basada en operaciones 7s; 
en trabajos 17s, en lista de 
preferencia 17s y en reglas de 
prioridad 9s. 
Equipo de cómputo: computador de 
corte industrial con procesador 
INTEL CeleronTM referencia CPU 
MMX a 266 MHz y RAM de 32 MB. 
Características del Lenguaje: 
Programación de bajo nivel (nivel 
bit) compatible; eficiente; con 
extensibilidad de modificadores y de 
operadores; instrucciones seguras; 
gestión automática de memoria; 
orientado a componentes y a 
objetos; sencillo; lenguaje 
estructurado e implementación de 
apuntadores; versátil, potente y 
general entre otras. 
(Al-Hakim, 2001) 
Software: No 
especificado 
Lenguaje: No 
especificado 
Resultados computacionales: Los 
resultados computacionales en 
términos de tiempo y calidad de 
solución, muestran la eficiencia de 
algoritmo en comparación con otros 
algoritmos. 
(Li, y Chen, 2010) 
Software: No 
especificado 
Lenguaje: No 
especificado 
Resultados computacionales: El 
resultado computacional muestra 
que GA puede obtener una mejor 
solución en comparación con 
trabajos similares, se validaron el 
minfitness=56.8354 y el 
meanfitness=56.8354 frente a la 
solución resultando estos válidos. 
(Amirthagadeswaran 
y Arunachalam, 2006) 
Software: No 
especificado 
Lenguaje: C++ 
Resultados computacionales: En la 
primera representación basada en 
operaciones y deducción del 
Schedule el makespan es 1212; en 
la segunda representación basada 
en trabajos y deducción del 
Schedule el makespan es 1251; en 
la tercera representación propuesta 
y deducción del Schedule el 
makespan es 1076. 
Tiempo computacional: El tiempo 
computacional empleado por la 
primera representación es1.37s; la 
segunda 0.44 y la tercera 0.38s. 
Equipo de cómputo: Usaron una 
CPU con procesador Intel Pentium 
IV A 1.8 GHz, 128 MB RAM. 
Características del Lenguaje: 
Programación de bajo nivel (nivel 
bit) compatible; eficiente; con 
extensibilidad de modificadores y de 
operadores; instrucciones seguras; 
gestión automática de memoria; 
orientado a componentes y a 
objetos; sencillo; lenguaje 
estructurado e implementación de 
apuntadores; versátil, potente y 
general entre otras. 
(Wang et al, 2009) 
Software: Microsoft 
Visual C++ 6.0 
Lenguaje: C++ 
Resultados computacionales: A 
pesar de la complejidad de la 
representación codificada en 3 
dimensiones, se generaron buenos 
resultados computacionales y de 
criterio a optimizar. 
Equipo de cómputo: ordenador 
personal con procesador Intel 
Pentium 2,66 GHz. 
Características del Software: 
Adaptabilidad; soporta la 
abstracción, la encapsulación, el 
poliformismo (presencia de 2 o más 
variables heredables) y la 
reutilización del código. 
Características del Lenguaje: 
Programación de bajo nivel (nivel 
bit) compatible; eficiente; con 
extensibilidad de modificadores y de 
operadores; instrucciones seguras; 
gestión automática de memoria; 
orientado a componentes y a 
objetos; sencillo; lenguaje 
estructurado e implementación de 
apuntadores; versátil, potente y 
general entre otras. 
(Lestan et al, 2009) 
Software: No 
especificado 
Lenguaje: LISP 
Resultados computacionales: El 
algoritmo propuesto fue ejecutado 
en un tiempo razonable y se obtuvo 
un makespan muy bueno en 
comparación con resultados 
arrojados por otros algoritmos. 
Características del Lenguaje: "List 
Processing" (Proceso de Listas). Las 
listas encadenadas son una de las 
estructuras de datos importantes de 
LISP, y el código fuente de LISP en 
sí mismo está compuesto de listas. 
Como resultado, los programas 
LISP pueden manipular el código 
fuente como una estructura de 
datos, dando lugar a los macro 
sistemas que permiten a los 
programadores crear una nueva 
sintaxis de lenguajes de 
programación de dominio específico 
empotrados en LISP. 
(Amirthagadeswaran 
y Arunachalam, 2007) 
Software: No 
especificado 
Lenguaje: C 
Resultados computacionales: El 
algoritmo desarrollado para las 
diferentes instancias testeadas 
muestra mejores resultados en 
términos de tiempo computacional y 
calidad de solución con el operador 
INV frente al GPX. 
Tiempo computacional: El tiempo 
con el operador INV fue de 58.5s y 
con el operador GPX 220s. 
Equipo de cómputo: Los 
experimentos con el operador de 
inversión (INV), se llevaron a cabo 
utilizando una CPU MMX con 
procesador Intel Pentium a 200 
MHz, 32 MB de RAM. Y con el 
operador GPX se llevaron a cabo en 
una CPU MMX con procesador Intel 
Celeron a 266 MHz, 32 MB de RAM. 
Características del Lenguaje: 
Programación de bajo nivel (nivel 
bit) compatible; posee un conjunto 
completo de instrucciones de 
control; trabaja con librerías de 
funciones; los datos son tratados 
directamente por el hardware de 
números, caracteres y direcciones 
de los computadores; lenguaje muy 
flexible que permite programar con 
múltiples estilos; sistema de tipos 
que impide operaciones sin sentido; 
acceso a memoria de bajo nivel 
mediante el uso de punteros e 
interrupciones al procesador con 
uniones. 
Fuente: Elaboración Propia. 
 
1. Características de los Algoritmos de Búsqueda TabúAplicados 
al Problema de JSS, Resultados Computacionales Obtenidos y Ventajas. 
 
Los algoritmos de Búsqueda Tabú son métodos de trayectoria que 
usualmente permiten movimientos hacia peores soluciones para ser capaces de 
escapar de óptimos locales o soluciones de baja calidad (Birattari et al, 2001). En 
la tabla 3 se muestran las aplicaciones recientes de estos algoritmos en la 
solución del problema del JSS y en la tabla 4 sus ventajas en cuanto a calidad de 
solución; tiempos computacionales; software; equipos de cómputo y lenguajes de 
programación utilizados. 
 
Tabla 3. 
 
Descripción detallada de investigaciones de algoritmos de Búsqueda Tabú 
empleados en el problema de JSS. 
 
CARACTERÍSTICAS DE ALGORITMO Y DEL PROBLEMA AUTOR(ES) 
71. Representación del problema: modelo de 
permutación y gráfico. 
72. Solución inicial: obtenida con el algoritmo INSA 
equipado con acelerador presentado en (Nowicki y 
Smutnicki, 2001). 
73. Estructuras de vecindario: estructura N (π) basada 
en (Taillard, 1994) y (Van Laarhoven et al, 1992). 
74. Evaluación del Movimiento: Cada movimiento en el 
vecindario se evalúa con exactitud. 
75. Lista tabú: la longitud de la lista tabú es 5 y el criterio 
que acepta el movimiento es aspiración. 
76. Estrategia de memoria largo plazo: re-
encadenamiento de trayectorias (path relinking). 
77. Criterio de parada: cuando el número de de 
iteraciones o el número de movimientos desmejorados 
alcanza al valor 5000. 
78. Criterio a optimizar: Minimizar el Makespan 
79. Instancias Testeadas (n × m): 15 ×15, 20×15, 
20×20, 30×15, 30×20, 50×15, 50×20 and 100×20 
(Nowicki y 
Smutnicki, 
2005) 
80. Algoritmo implementado: i-TSAB 
81. Representación del problema: gráfico disyuntivo. 
82. Solución inicial: obtenida por la regla de despacho 
SPT. 
83. Estructuras de vecindario: 6 estructuras [NS1-NS2 
(Błażewicz et al, 1996); NS3-NS4 (Dell'Amico y Trubian, 
1993); NS5 (Nowicki y Smutnicki, 1996); NS6 (Balas y 
Vazacopoulos, 1998)] siendo NS6 la mejor. 
84. Evaluación del Movimiento: Cada movimiento en el 
vecindario se evalúa con exactitud. 
85. Lista tabú: la longitud de la lista tabú es 12 y el 
criterio que acepta el movimiento es aspiración. Memoria 
de corto plazo. 
86. Criterio de parada: cuando el número de de 
iteraciones o el número de movimientos desmejorados 
alcanza al valor 3000. 
87. Criterio a optimizar: Minimizar el Makespan 
88. Instancias Testeadas (n × m): 72 (FT, LA, ABZ, 
SWV y YN). 
(Zhang et al, 
2006) 
89. Representación del problema: gráfico disyuntivo. 
90. Solución inicial: obtenida por las regla de despacho: 
MDD (Baker y Kanet, 1983); MOD (Baker y Kanet, 1983) y 
(Baker,1984); CR+SPT y S/RPT+SPT (Anderson y 
Nyirenda, 1990). 
91. Estructuras de vecindario: 2 estructuras [Ne1: todas 
las soluciones obtenidas por la inversión de arcos en todos 
los caminos críticos] y [Ne2: basado en (Dell'Amico y 
Trubian, 1993). 
92. Regla de restricción tabú: un movimiento es tabú si 
su inversa se almacena en la lista tabú. 
(Amaral y 
Rigão, 2000) 
93. Tenencia Tabú: el número de iteraciones que un 
movimiento sigue siendo tabú se selecciona de un 
intervalo; U[min, máx.], donde; U representa una 
distribución uniforme entre los números enteros min. y 
máx. 
94. Movimiento: inversión de un solo arco disyuntivo en 
la ruta crítica de un determinado puesto de trabajo. 
95. Estrategia de memoria largo plazo: diversificación e 
intensificación. 
96. Criterio de parada: cuando el número de iteraciones 
o el número de movimientos desmejorados alcanza al valor 
250. 
97. Criterio a optimizar: Minimizar la Tardanza 
98. Instancias Testeadas (n × m): 20 generadas 
aleatoriamente con parámetros basados en (Taillard, 
1994); (Van Laarhoven et al, 1992) y (Adams et al, 1998). 
99. Representación del problema: representación 
basada en operaciones. 
100. Solución inicial: obtenida aleatoriamente. 
101. Estructuras de vecindario: V*(x1) es un método de 
intercambio de pares adyacentes se utiliza para generar 
los vecindarios. 
102. Regla de restricción tabú: La regla considerada para 
la tenencia de tabú es una regla estática en la que la 
tenencia tabú t = √n donde n es una medida de la 
dimensión problema. 
103. Tenencia Tabú: El período de tenencia de tabú es el 
número de movimientos posteriores durante el cual el 
último par de soluciones debe ser prohibido. 
104. Criterio de parada: cuando el número de de 
iteraciones o el número de movimientos desmejorados 
(Ponnambalam 
et al, 2000) 
alcanza al valor 100. 
105. Criterio a optimizar: Minimizar el Makespan. 
106. Instancias Testeadas (n × m): 25 basadas en 
(Jawahar et al, 1998) y OR-Library. 
107. Representación del problema: representación 
basada en operaciones. 
108. Solución inicial: obtenida por las regla de despacho: 
SPT. 
109. Estructuras de vecindario: se genera sólo una ruta 
crítica, basado en la estrategia de first-last. 
110. Lista tabú: la longitud de la lista tabú es dinámica. 
111. Criterio de parada: cuando el número de de 
iteraciones o el número de movimientos desmejorados 
alcanza al valor 5000. 
112. Criterio a optimizar: Minimizar el Makespan. 
113. Instancias Testeadas (n × m): 30 donde 29 son de 
(6x6; 10x5; 15x5; 20x5; 10x10) basadas en OR-Library y 
una de 6x6 del caso de estudio. 
(Velmurugan y 
Selladurai, 
2007) 
Fuente: Elaboración Propia. 
 
Tabla 4. 
 
Ventajas en Calidad de Solución; Tiempos Computacionales; Software; 
Equipos de Cómputo y Lenguajes de Programación Utilizados en la Solución 
del JSSP don Algoritmos de Búsqueda Tabú. 
 
AUTOR (ES) 
SOFTWARE Y 
LENGUAJE DE 
PROGRAMACIÓN 
VENTAJAS Y DESCRIPCIÓN 
Nowicki y 
Smutnicki, 2005) 
Software: Borland 
Delphi 7 
Lenguaje: Object 
Pascal 
Resultados computacionales: El 
algoritmo propuesto posee, sin 
precedentes hasta ahora, la precisión, 
que puede obtenerse en un tiempo 
rápido en un PC, y fue confirmado 
después de una amplia cantidad de 
pruebas en el ordenador. 
Tiempo computacional: En los 
experimentos, el tiempo de ejecución se 
redujo 8 veces para instancias con n = 
15, m = 15, 11.8 veces para los casos 
con n = 20, m = 20 y 13.6 veces para los 
casos con n = 30, m = 20. Se corrieron 
aproximadamente 2 a 5 millones de 
iteraciones en un tiempo de 25 y 47 
segundos. 
Equipo de cómputo: PC de corte 
industrial con procesador Pentium III 900 
MHz 
Características del Software: soporta la 
abstracción y la encapsulación; 
compilador altamente optimizado que 
genera un código directamente 
ejecutable; gestión y administración de 
Base de Datos. 
Características del Lenguaje: 
programación orientada a objetos; 
encapsulación; manejo estructurado de 
excepciones; programación activada por 
eventos; manejo de la herencia simple; 
emula las características de los 
lenguajes de bajo nivel. 
(Zhang et al, 
2007) 
Software: Visual Basic 
6.0 
Lenguaje: VC ++ 
Resultados computacionales: el 
algoritmo aplicado domina a diferentes 
aplicaciones, en términos de calidad de 
la solución y rendimiento 
computacional.| 
Tiempo computacional: 1235 segundos 
aprox. con 5 millones de iteraciones. 
Equipo de cómputo: ordenador personal 
Pentium IV1.8G. 
Características del Software: 
adaptabilidad; soporta la abstracción, la 
encapsulación, el poliformismo y la 
reutilización del código. 
Características del Lenguaje: 
Programación de bajo nivel (nivel bit) 
compatible; eficiente; con extensibilidad 
de modificadores y de operadores; 
instrucciones seguras; gestión 
automática de memoria; orientado a 
componentes y a objetos; sencillo; 
lenguaje estructurado e implementación 
de apuntadores; versátil, potente y 
general, entre otras. 
(Amaral y Rigão, 
2000) 
Software: No 
especificado 
Lenguaje: C 
Resultados computacionales: 2422.53 
segundos del tiempo habitual de 
ejecución del algoritmo exacto (PEM con 
el software CPLEX) fue reducido a 22.55 
segundos con el nuevo algoritmo 
basado en búsqueda tabú. 
Tiempo computacional: 22.55 segundos 
aprox. con 250 iteraciones. 
Equipo de cómputo: CPU de 50 MHz 
Texas Instrument microSPARC (sun4m) 
(1soldered), Memoria de 24 MB (max 96 
MB - 6 x 4 or 16 MB 72 pins parity 
SIMMs). 
Características del Lenguaje: 
Programación de bajo nivel (nivel bit) 
compatible; posee un conjunto completo 
de instrucciones de control; trabaja con 
librerías de funciones; los datos son 
tratados directamente por el hardware 
de números, caracteres y direcciones de 
los computadores; lenguaje muy flexible 
que permite programar con múltiples 
estilos; sistema de tipos que impide 
operaciones sin sentido; acceso a 
memoria de bajo nivel mediante el uso 
de punteros y Interrupciones al 
procesador con uniones. 
(Ponnambalam et 
al, 2000) 
Software: No 
especificado 
Lenguaje: C 
Resultados computacionales: De 25 
problemas testeados 6 tienen un mejor 
rendimiento computacional con el 
algoritmo de TS. Para los problemas 
pendientes de los resultados de 
búsqueda tabú están muy cerca del 
rendimiento y calidad de algoritmos 
genéticos y recocido simulado. 
Equipo de cómputo: Computador de 
corte industrial HCL-HP Pentium, 16 MB 
RAM, 100 MHz 
Características del Lenguaje: 
Programación de bajo nivel (nivel bit) 
compatible; posee un conjunto completo 
de instrucciones de control; trabaja con 
librerías de funciones; los datos son 
tratados directamente por el hardware 
de números, caracteres y direcciones de 
los computadores; lenguaje muy flexible 
que permite programar con múltiples 
estilos; sistema de tipos que impide 
operaciones sin sentido; acceso a 
memoria de bajo nivel mediante el uso 
de punteros e interrupciones al 
procesador con uniones. 
(Velmurugan y 
Selladurai, 2007) 
Software: No 
especificado 
Resultados computacionales: Se 
obtuvieron resultados computacionales 
en tiempos razonables, es algoritmo 
Lenguaje: C++ propuesto obtuvo óptimos resultados en 
el problema de jssp presente en una 
industria que manufactura partes de 
automóviles. 
Equipo de cómputo: Computador de 
corte industrial; plataforma Linux; AMD 
ATHLON 2600+; 2GHz y 512 de RAM. 
Características del Lenguaje: 
Programación de bajo nivel (nivel bit) 
compatible; eficiente; con extensibilidad 
de modificadores y de operadores; 
instrucciones seguras; gestión 
automática de memoria; orientado a 
componentes y a objetos; sencillo; 
lenguaje estructurado e implementación 
de apuntadores; versátil, potente y 
general entre otras. 
Fuente: Elaboración Propia. 
 
1. Características de los algoritmos híbridosentre Algoritmos 
Genéticos y Búsqueda Tabú Aplicados en la Solución del Problema de JSS y 
sus Ventajas de Implementación. 
 
Los de los algoritmos híbridos entre Algoritmos Genéticos y Búsqueda Tabú 
ofrecen ventajas mayores al complementarse. Las primeras dos décadas de 
investigación sobre metaheurísticas se caracterizaron por la aplicación de 
metaheurísticas más estándar. Sin embargo, en los últimos años se ha hecho 
evidente que la concentración en una sola metaheurística es muy restrictiva. Una 
metaheurística híbrida puede proporcionar un comportamiento más eficiente y una 
mayor flexibilidad, cuando se trata de problemas del mundo real y de gran escala 
(Talbi, 2002), (Blum y Roli, 2008), (Blum et al, 2011). 
 
En la tabla 5 se muestran las aplicaciones recientes de estos algoritmos 
híbridos en la solución del problema del JSS y en la tabla 6 sus ventajas en cuanto 
a calidad de solución; tiempos computacionales; software; equipos de cómputo y 
lenguajes de programación empleados. 
 
 
Tabla 5. 
 
Descripción detallada de investigaciones sobre algoritmos híbridos entre 
Algoritmos Genéticos y Búsqueda Tabú Aplicada en la Solución del 
Problema de JSS. 
 
CARACTERÍSTICAS DE ALGORITMO Y DEL PROBLEMA AUTOR(ES) 
FASE 1 
114. Representación del problema: Diagrama de Gantt. 
115. Población inicial: Generada Aleatoriamente. 
116. Estructuras de vecindario: Estructura basada en la 
estructura propuesta por (Nowicki y Smutnicki, 1996). 
117. Lista tabú: la longitud de la lista tabú es de 6 a 36 y 
el criterio que acepta el movimiento es aspiración. 
 
FASE 2 
118. Representación del cromosoma: Basada en 
operaciones. 
119. Población inicial: Generada en la fase 1 con TS. 
120. Tamaño de la Población: 30 a 200. 
(Meeran y 
Morshed, 2014) 
121. Método de Selección de los progenitores: Se 
utiliza la estrategia Elitista. 
122. Cantidad de puntos de cruzamiento: Múltiples 
Puntos. 
123. Longitud del cromosoma: de acuerdo a cada 
instancia. 
124. Cruce: Probabilidad 0.7 a 0.8. 
125. Mutación: Probabilidad 0.01 a 0.10. 
126. Criterio de parada: Cuando el número de de 
iteraciones alcanza al valor de 20 a 100. 
127. Criterios a optimizar: Minimizar el makespan y la 
tardanza máxima. 
128. Instancias Testeadas (n×m): 43 instancias (LA; FT; 
ABZ; ORB) obtenidas de la biblioteca de OR-Library 
(Beasley, 1990). 
129. Algoritmo 1: GA basado en NSGA-II ver (Deb et al, 
2002). 
FASE 1 
130. Algoritmo 2: GA basado en NSGA-II (Deb et al, 
2002) combinado con Búsqueda Tabú basada en TSA 
(Dauzère y Paulli, 1997). 
131. Representación del problema: Grafico disyuntivo. 
132. Población inicial: Generada con el método Greedy 
basado en la regla SLACK (las operaciones se asignan a 
las máquinas y luego se genera una solución factible al 
JSSP-General). 
133. Estructuras de vecindario: vecindario NS para cada 
operación crítica y para cada movimiento factible se 
genera un vecino. (Dauzère y Paulli, 1997). 
134. Lista tabú: la longitud de la lista tabú es [10; 30; 50; 
(Vilcot y Billaut, 
2008) 
70; 100] y el criterio que acepta el movimiento es 
aspiración. 
 
FASE 2 
135. Representación del cromosoma: código binario. 
136. Población inicial: Generada en la fase 1 con TS. 
137. Tamaño de la Población: [100; 300; 500] 
138. Método de Selección de los progenitores: Se 
utiliza el método del Torneo Binario (Binary Tournamnet). 
139. Cantidad de puntos de cruzamiento: Un Punto. 
140. Longitud del cromosoma: de acuerdo a cada 
instancia. 
141. Cruce: Probabilidad 0.9; utilizaron el operador: cruce 
de simulación binaria (SBX). 
142. Mutación: Probabilidad 0.5; utilizaron operadores de 
mutación bit a bit y polinomial (Deb y Agrawal, 1994). 
143. Criterio de parada: Cuando el número de de 
iteraciones alcanza al valor de 1000. 
144. Criterios a optimizar: Minimizar el makespan y la 
tardanza máxima. 
145. Instancias Testeadas (n×m): 8 instancias (LA: 5x10; 
5x15; 15x20; 10x10; 10x15; 10x20; 10x30; 15x15) 
obtenidas de la biblioteca de OR-Library (Beasley, 1990). 
FASE 1 
146. Representación del problema: Grafico disyuntivo y 
Diagrama de Gantt. 
147. Población inicial: heurística de corte medio 
148. Estructuras de vecindario genético: 4 basadas en 
(Nowicki y Smutnicki, 1996). 
149. Lista tabú y estado tabú de movimiento: la longitud 
(Meeran y 
Morshed, 2012) 
de la lista tabú es de 6 a 36 y el criterio que acepta el 
movimiento es aspiración. 
FASE 2 
150. Representación del cromosoma: basada en (Gen et 
al, 1994) y (Cheng et al, 1996) codifica una solución como 
una secuencia ordenada de trabajo/operaciones, donde 
cada gen es una sola operación. 
151. Población inicial: Generada en la fase 1 con TS. 
152. Tamaño de la Población: [30 a 200]. 
153. Cantidad de puntos de cruzamiento: Múltiples 
puntos. 
154. Longitud del cromosoma:16 
155. Cruce: Probabilidad 0.7 a 0.8; 
156. Mutación: Probabilidad 0.01 a 0.10; 
157. Criterio de parada: Cuando el número de de 
iteraciones alcanza al valor de 100 y el criterio que acepta 
el movimiento es aspiración. 
158. Criterios a optimizar: Minimizar el makespan 
159. Instancias Testeadas (n×m): 51instancias de la 
Literatura de OR-Libraty (Beasley, 1990) y 3 instancias 
reales de empresas productoras de parabrisas del 
automóvil y de fabricación de acero, donde el JSSP es de 
8x8; 6x6; 6x6. 
FASE 1 
160. Representación del problema: Grafico disyuntivo y 
diagrama de Gantt. 
161. Población inicial: Generada Aleatoriamente. 
162. Representación del cromosoma: basada en (Gen et 
al, 1994) y (Cheng et al, 1996) codifica una solución como 
una secuencia ordenada de trabajo/operaciones, donde 
(Thamilselvan y 
Balasubramanie, 
2012) 
cada gen es una sola operación. 
163. Lista tabú: la longitud de la lista tabú es dinámica 
aumentar la exploración del espacio de búsqueda 
(Thamilselvan y Balasubramanie, 2012), el criterio que 
acepta el movimiento es aspiración. 
164. Criterio de parada: Cuando el número de iteraciones 
alcanza al valor de 4000. 
165. Cantidad de puntos de cruzamiento: Múltiples 
puntos. 
166. Longitud del cromosoma: 12 
167. Cruce: Probabilidad 0.6 a 1.0; operador de cruce 
basado en una estrategia cambio de cruce de una 
subsecuencia no ordenada (USXX); donde los hijos 
heredan de los padres subsecuencias en cada máquina en 
la medida de lo posible. 
168. Mutación: basado en el mecanismo de reubicación 
(Thamilselvan y Balasubramanie, 2012). 
169. Criterios a optimizar: Minimizar el makespan 
170. Instancias Testeadas (n×m):4 instancias de 5x5; 
5x10; 10x5; 5x10. 
FASE 1 
171. Algoritmo: GA + TS − 
172. Representación del problema: Grafico disyuntivo 
(Roy y Sussmann, 1964). 
173. Representación del cromosoma: se basa en 
permutaciones con repetición propuesto por (Bierwirth 
1995). 
174. Estructuras de vecindario: Estructura basada en 
(González et al, 2008) y (González et al, 2009). 
175. Método de Selección de los progenitores: Se 
(González et al, 
2010) 
utiliza el método del Torneo (Tournamnet). 
176. Cruce: Probabilidad 1.0; basado en el operador de 
cruce de órdenes de trabajo (JOX) descrito por (Bierwirth 
1995). 
177. Mutación: El JOX operador puede cambiar 
cualquiera de las dos operaciones que requieren la misma 
máquina este es un efecto implícito de mutación. Por esta 
razón no se utiliza ningún operador de mutación explícito 
178. Criterios a optimizar: Minimizar el Tiempo Total de 
Flujo. 
179. Instancias Testeadas (n×m): 53 instancias (LA; 
ORB; ABZ; FT; obtenidas de la biblioteca de OR-Library 
(Beasley, 1990). 
FASE 1 
180. Algoritmo: GA+TS 
181. Representación del problema: Grafico disyuntivo. 
182. Población inicial: Generada Aleatoriamente. 
183. Estructuras de vecindario: Estructura basada en 
(González et al, 2008). 
184. Lista tabú y estado tabú de movimiento: la longitud 
de la lista tabú es dinámica basada en (Dell'Amico y 
Trubian,1993), y el criterio que acepta el movimiento es 
aspiración. 
185. Representación del cromosoma: se basa en 
permutaciones con repetición propuesto por (Bierwirth 
1995). 
186. Cruce: Probabilidad 1.0; basado en el operador de 
cruce de órdenes de trabajo (JOX) descrito por (Bierwirth 
1995). 
187. Mutación: El JOX operador puede cambiar 
(González et al, 
2009) 
cualquiera de las dos operaciones que requieren la misma 
máquina este es un efecto implícito de mutación. Por esta 
razón no se utiliza ningún operador de mutación explícito 
188. Criterio de parada: La búsqueda tabú se detiene tras 
la realización de un número determinado de iteraciones 
MAXGLOBALITER, o cuando la pila de soluciones élite se 
vacía y devuelve la mejor solución alcanzada hasta ese 
momento. 
189. Criterios a optimizar: Minimizar el makespan 
190. Instancias Testeadas (n×m): Instancias de (Brucker 
y Thiele, 1996); (Vela et al, 2010) y (Applegate y Cook, 
1991). 
FASE 1 
191. Algoritmo: GTS 
192. Representación del problema: Grafico disyuntivo. 
193. Población inicial: Generada Aleatoriamente. 
194. Criterio de Terminación: se detiene después de un 
número fijo de generaciones consecutivas sin mejora 
frente a la mejor solución en la población. 
195. Método de Selección de los progenitores: Se 
utiliza el método de la clasificación (Ranking). 
196. Cantidad de puntos de cruzamiento: Un Punto. 
197. Cruce: Probabilidad xxx; operador de cruce MSX 
(Merge and Split Recombination) fusionar y dividir la 
recombinación, consiste en conseguir dos hijos 
complementarios mediante la combinación de las 
características de precedencia de sus padres tratando de 
minimizar la pérdida de la diversidad. 
 
FASE 2 
(Moraglio et al, 
2005) 
198. Población inicial: Generada en la fase 1 con GA. 
199. Estructuras de vecindario: Estructura basada en la 
estructura propuesta por (Nowicki y Smutnicki, 1996). 
200. Lista tabú y estado tabú de movimiento: consiste 
en una cola FIFO de movimientos de longitud fija. La 
longitud de la lista tabú es el tamaño promedio de la zona 
más un valor aleatorio. 
201. Estrategia de Búsqueda: Dado que el tamaño de un 
vecindario es bastante pequeño usan la estrategia de 
búsqueda del vecino más empinado. 
202. Criterio de parada: se detiene después de un 
número fijo de pasos sin mejora. 
203. Criterios a optimizar: Minimizar el makespan 
204. Instancias Testeadas (n×m): las instancias de (LA; 
FT; SWV) obtenidas de la biblioteca de OR-Library 
(Beasley, 1990). 
Fuente: Elaboración Propia. 
 
Tabla 6. 
Ventajas en Calidad de Solución; Tiempos Computacionales; Software; 
Equipos de Cómputo y Lenguajes de Programación utilizados en la 
Solución del JSSP con Algoritmos Híbridos entre Algoritmos Genéticos y 
Búsqueda Tabú. 
AUTOR (ES) 
SOFTWARE Y 
LENGUAJE DE 
PROGRAMACIÓN 
VENTAJAS Y DESCRIPCIÓN 
(Meeran y 
Morshed, 2014) 
Software: Visual Basic 
6.0 
Resultados computacionales: 40 de las 
43 instancias testeadas fueron resueltas 
Lenguaje: C ++ de forma óptima con el algoritmo 
propuesto a un costo computacional 
razonable. 
Tiempo computacional: testeando las 
diferentes instancias emplearon un 
tiempo entre 0.10 segundos y 60 
minutos. 
Equipo de cómputo: Equipo con 
procesador Pentium III a 1 GHz con 
128MB de RAM. 
Características del Lenguaje: 
Programación de bajo nivel (nivel bit) 
compatible; eficiente; con extensibilidad 
de modificadores y de operadores; 
instrucciones seguras; gestión 
automática de memoria; orientado a 
componentes y a objetos; sencillo; 
lenguaje estructurado e implementación 
de apuntadores; versátil, potente y 
general entre otras. 
(Vilcot y Billaut, 
2008) 
Software: Direct 
Planning 
Lenguaje: No 
especificado 
Resultados computacionales: Los 
resultados factibles en tiempos de 
cálculo y eficiencia en la solución se 
obtuvieron con el algoritmo hibrido de 
GA y TS. 
Tiempo computacional: GA basado en 
NSGA-II los criterios óptimos fueron 
obtenidos en 10 minutos y con el 
algoritmo GA+TS el tiempo fue de 0.75 
segundos. 
Equipo de cómputo: Computador de 
corte industrial con procesador Pentium 
IV a 2.8 GHz con 512 Mb de RAM. 
Características del Software: es intuitivo 
y se puede utilizar en una estación de 
trabajo autónomo o en una red, y está 
disponible de acuerdo a dos ejes: la 
planificación y sus representaciones 
gráficas, y la programación. Diseñado 
específicamente para modelar la 
programación de horarios en pequeñas 
y medianas industrias. Permite 
personalizar los datos, desde un 
sistema de información (ERP, CAPM) 
de forma automática. 
(Thamilselvan y 
Balasubramanie, 
2012) 
Software: No 
especificado 
Lenguaje: C++ 
Resultados computacionales: el 
algoritmo se probó en 52 problemas de 
referencia que existen en la literatura y 
encontró soluciones óptimas para 39 de 
estos problemas y logro un ARE 
(Average Relative Error) Promedio de 
error relativo de 1,56%. 
Equipo de cómputo: Equipo con 
plataforma de Windows con procesador 
Intel Pentium E5800, a 3.2 GHz y 2GB 
RAM. 
Características del Lenguaje: 
Programación de bajo nivel (nivel bit) 
compatible; eficiente; con extensibilidad 
de modificadores y de operadores; 
instrucciones seguras; gestión 
automática de memoria; orientado a 
componentes y a objetos; sencillo; 
lenguaje estructurado e implementación 
de apuntadores; versátil, potente y 
general entre otras. 
(Zhang et al, 
2013) 
Software: No 
especificado 
Lenguaje: C++ 
Resultados computacionales: El método 
propuesto tiene un tiempo de CPU 
requerido. Sin embargo, se puede 
mejorar la eficiencia y la estabilidad del 
sistema de programación de manera 
significativa. El tiempo de CPU 
requerido es el valor medio de cada 
frecuencia de Schedule. 
Equipo de cómputo: computador con 
procesador Intel-Core2-Duo a 2.0 GHz 
y 2.00GB de RAM. 
Características del Lenguaje: 
Programación de bajo nivel (nivel bit) 
compatible; eficiente; con extensibilidad 
de modificadores y de operadores; 
instrucciones seguras; gestión 
automática de memoria; orientado a 
componentes y a objetos; sencillo; 
lenguaje estructurado e implementación 
de apuntadores; versátil, potente y 
general entre otras. 
(González et al, 
2010) 
Software: No 
especificado 
Lenguaje: No 
especificado 
Resultados computacionales: El tiempo 
computacional es razonable en cada 
una de las instancias testeadas, aunque 
presenta mayor complejidad de 
programación el JSSP con criterio 
minimización del tiempo total de flujo 
que con el convencional makespan. 
Equipo de cómputo: Los algoritmos de 
la versión A* de (Sierra 2009) fue 
corrida en Ubuntu V8 con procesador 
Intel Core2 Duo a 2,13GHz con 7,6Gb 
de RAM, LSRW fue corrido en Windows 
XP con procesador Intel Core2 Duo a 
2,13GHz con 3Gb de RAM y 
GA+TS− fue corrido en Windows XP 
con procesador Intel Core2 Duo a 
2.66GHz con 2Gb de RAM. 
(González et al, 
2009) 
Software: No 
especificado 
Lenguaje: C, utilizado 
en el algoritmo (SB-
GLS) 
Resultados computacionales: (GA-TS) 
supera en tiempo computacional y 
calidad de solución a (SB-GLS) y (GA-
LS). 
Equipo de cómputo: El algoritmo (SB-
GLS) fue corrido en un computador 
Lenguaje: C++, 
utilizado en los 
algoritmos (GA-LS) y 
(GA-TS) 
Sun-Ultra-60 con procesador Ultra-
SPARC-II a 360MHz; (GA-LS) y (GA-
TS) son corridos en un computador con 
procesador Pentium IV (1.7GHz) e Intel 
Core2 Duo (2.6GHz) respectivamente. 
Características del Lenguaje C: 
Programación de bajo nivel (nivel bit) 
compatible; posee un conjunto completo 
de instrucciones de control; trabaja con 
librerías de funciones; los datos son 
tratados directamente por el hardware 
de números, caracteres y direcciones 
de los computadores; lenguaje muy 
flexible que permite programar con 
múltiples estilos; sistema de tipos que 
impide operaciones sin sentido;acceso 
a memoria de bajo nivel mediante el 
uso de punteros y Interrupciones al 
procesador con uniones. 
Características del Lenguaje C++: 
Programación de bajo nivel (nivel bit) 
compatible; eficiente; con extensibilidad 
de modificadores y de operadores; 
instrucciones seguras; gestión 
automática de memoria; orientado a 
componentes y a objetos; sencillo; 
lenguaje estructurado e implementación 
de apuntadores; versátil, potente y 
general entre otras. 
(Moraglio et al, 
2005) 
Software: No 
especificado 
Lenguaje: No 
especificado 
Resultados computacionales: GTS 
supero en términos de computacionales 
y de criterio de optimización a SAGen. 
Equipo de cómputo: Utilizaron una 
estación Sparc5 a (110Mhz) para el 
GTS y para SAGen una estación con 
procesador Pentium a 120/166Mhz. 
Fuente: Elaboración Propia. 
 
205. CONCLUSIONES 
 
1. Las ventajas en calidad de solución y los tiempos computacionales que 
ofrecen las metaheurísticas en el problema de JSS, aumentan cuando se 
emplean instancias pequeñas y los equipos de cómputo son robustos. 
2. El estudio muestra que la mayoría de los métodos híbridos funcionan mejor 
que el algoritmo individual porque se ayudan mutuamente para escapar de 
la región de búsqueda local y acelerar hacia la convergencia, mediante la 
adopción de fortalezas y la abolición de debilidades. 
3. Esta investigación evidencio que el software no es un problema a la hora de 
implementar un algoritmo, puesto que este debe adecuarse a un lenguaje 
de programación robusto, eficiente, compatible, de bajo nivel, versátil, 
potente, con gestión automática de memoria entre otras características de 
los lenguajes fuertes. Otro aspecto importante es el equipo de cómputo 
dado que a medida que aumenta la complejidad del problema es necesario 
tener también mayor capacidad en memoria y procesador, los autores de 
los artículos estudiados en su mayoría recomiendan equipos acordes a la 
complejidad del problema. 
 
 
 
Referencias 
 
Adams, J., Balas, E., y Zawack, D. (1988). The shifting bottleneck procedure for 
job shop scheduling. Management science, 34(3), 391-401. 
Al-Hakim, L. (2001). An analogue genetic algorithm for solving job shop scheduling 
problems.International Journal of Production Research, 39(7), 1537-1548. 
Amaral A., V., y Rigão S., C. (2000). Tabu search for minimizing total tardiness in a 
job shop.International Journal of Production Economics, 63(2), 131-140. 
Amirthagadeswaran, K. S., y Arunachalam, V. P. (2006). Improved solutions for job 
shop scheduling problems through genetic algorithm with a different method 
of schedule deduction.The International Journal of Advanced Manufacturing 
Technology, 28(5-6), 532-540. 
Amirthagadeswaran, K. S., y Arunachalam, V. P. (2007). Enhancement of 
performance of genetic algorithm for job shop scheduling problems through 
inversion operator.The International Journal of Advanced Manufacturing 
Technology, 32(7-8), 780-786. 
Anderson, E. J., y Nyirenda, J. C. (1990). Two new rules to minimize tardiness in a 
job shop.The International Journal of Production Research, 28(12), 2277-
2292. 
Baker, K. R. (1984). Sequencing rules and due-date assignments in a job 
shop.Management science, 30(9), 1093-1104. 
Baker, K. R., y Kanet, J. J. (1983). Job shop scheduling with modified due dates. 
Journal of Operations Management, 4(1), 11-22. 
Balas, E., y Vazacopoulos, A. (1998). Guided local search with shifting bottleneck 
for job shop scheduling.Management science, 44(2), 262-275. 
Beasley, J. E. (1990). OR-Library: Distributing test problems by electronic mail. 
Journal of the operational research society, 1069-1072. Disponible en: 
http://www.brunel.ac.uk/~mastjjb/jeb/info.html. 
Bierwirth, C. (1995). "A generalized permutation approach to job-shop scheduling 
with genetic algorithms".Or Spektrum Nº 17, pp: 87-92. 
Birattari, M., Paquete, L., Strutzle, T., y Varrentrapp, K. (2001). Classification of 
Metaheuristics and Design of Experiments for the Analysis of Components 
Tech. Rep. AIDA-01-05. 
Blum, C., Puchinger, J., Raidl, G. R., y Roli, A. 2011. Hybrid metaheuristics in 
combinatorial optimization: A survey.Applied Soft Computing.11(6), 4135-
4151. 
Blum, C., y Roli, A. (2008). Hybrid metaheuristics: an introduction. In Hybrid 
Metaheuristics (pp. 1-30).Springer Berlin Heidelberg. 
Cheng, R., Gen, M., y Tsujimura, Y. (1996). A tutorial survey of job-shop 
scheduling problems using genetic algorithms—I. Computers & Industrial 
Engineering, 30(4), 983-997. 
Cheung, R., Gen, M., y Tsujimura, Y. (1996).A tutorial survey of job-shop 
scheduling problems using genetic algorithms—I.Computers and Industrial 
Engineering, 30(4), 983-997. 
Dauzère-Pérès, S., y Paulli, J. (1997). An integrated approach for modeling and 
solving the general multiprocessor job-shop scheduling problem using tabu 
search.Annals of Operations Research, 70, 281-306. 
Deb, K., Pratap, A., Agarwal, S., y Meyarivan, T. A. M. T. (2002). A fast and elitist 
multiobjective genetic algorithm: NSGA-II. Evolutionary Computation.IEEE 
Transactions on, 6(2), 182-197. 
Deb, K., y Agrawal, R. B. (1994). Simulated binary crossover for continuous search 
space.Complex Systems, 9(3), 1-15. 
Dell'Amico, M., y Trubian, M. (1993). Applying tabu search to the job-shop 
scheduling problem.Annals of Operations Research, 41(3), 231-252. 
Duarte Muñoz, A., Pantrigo Fernández, J. J., y Gallego Carrillo, M. (2007). 
Metaheurísticas (Vol. 22). Librería-Editorial Dykinson. 
French, S. (1982). Sequencing and scheduling: an introduction to the mathematics 
of the job-shop. Ellis Horwood Ltd, Publisher.(Jain y Meeran, 1999). 
Gen, M., Tsujimura, Y., y Kubota, E. (1994). Solving job-shop scheduling problems 
by genetic algorithm.In Systems, Man, and Cybernetics, 1994.Humans, 
Information and Technology.1994 IEEE International Conference on (Vol. 2, 
pp. 1577-1582).IEEE. 
Glover, F. (1989). Tabu search-part I. ORSA Journal on Computing, 1:190-206. 
Glover, F. y Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers, 
Boston, Hardbound. 
González, M. A., Vela, C. R., Sierra, M. R., y Varela, R. (2010). Tabu search and 
genetic algorithm for scheduling with total flow time minimization. In 
Proceedings of the workshop on constraint satisfaction techniques for 
planning and scheduling problems (COPLAS), Freiburg, Germany (pp. 33-
41). 
González, M. A., Vela, C. R., Sierra, M. R., y Varela, R. (2010). Tabu search and 
genetic algorithm for scheduling with total flow time minimization.In 
Proceedings of the workshop on constraint satisfaction techniques for 
planning and scheduling problems (COPLAS), Freiburg, Germany (pp. 33-
41). 
González, M. A., Vela, C. R., y Varela, R. (2009). Genetic algorithm combined with 
tabu search for the job shop scheduling problem with setup times. In Methods 
and Models in Artificial and Natural Computation.A Homage to Professor 
Mira’s Scientific Legacy (pp. 265-274). Springer Berlin Heidelberg. 
Holland, J. H. (1975). Adaptation in natural and artificial systems: an introductory 
analysis with applications to biology, control, and artificial intelligence. U 
Michigan Press. 
Jawahar, N., Aravindan, P., y Ponnambalam, S. G. (1998). A genetic algorithm for 
scheduling flexible manufacturing systems.The International Journal of 
Advanced Manufacturing Technology, 14(8), 588-607. 
Lestan, Z., Brezocnik, M., Buchmeister, B., Brezovnik, S., y Balic, J. (2009). 
Solving the job-shop scheduling problem with a simple genetic algorithm.Int J 
Simul Model, 8(4), 197-205. 
Li, Y., y Chen, Y. (2010). A genetic algorithm for job-shop scheduling.Journal of 
software, 5(3), 269-274. 
Mattfeld, D. C., (1996).Evolutionary Search and the Job Shop: Investigations on 
Genetic Algorithms for Production Scheduling (Heidelberg, Germany: 
Physica-Verlag). 
Meeran, S., y Morshed, M. S. (2012). A hybrid genetic tabu search algorithmfor 
solving job shop scheduling problems: a case study. Journal of intelligent 
manufacturing, 23(4), 1063-1078. 
Meeran, S., y Morshed, M. S. (2014). Evaluation of a hybrid genetic tabu search 
framework on job shop scheduling benchmark problems.International Journal 
of Production Research, 1-19. 
Moraglio, A., Ten Eikelder, H., y Tadei, R. (2005). Genetic local search for job shop 
scheduling problem.Tech. Rpt. CSM-435, Dept. of Comput.Sci., Univ. of 
Essex. 
Nowicki, E., y Smutnicki, C. (1996). A fast taboo search algorithm for the job shop 
problem.Management science, 42(6), 797-813. 
Nowicki, E., y Smutnicki, C. (2001). New ideas in TS for job-shop 
scheduling.Preprint, 50, 2001. 
Nowicki, E., y Smutnicki, C. 2005. An advanced tabu search algorithm for the job 
shop problem.Journal of Scheduling, 8(2), 145-159. 
Ponnambalam, S. G., Aravindan, P., & Rao, P. S. (2001).Comparative evaluation 
of genetic algorithms for job-shop scheduling.Production Planning & Control, 
12(6), 560-574. 
Ponnambalam, S. G., Aravindan, P., y Rajesh, S. V. (2000). A tabu search 
algorithm for job shop scheduling. The International Journal of Advanced 
Manufacturing Technology, 16(10), 765-771. 
Roy, B., y Sussmann, B. (1964). Les problemes d’ordonnancement avec 
contraintes disjonctives. Note ds, 9. 
Taillard, E. D. (1994). Parallel taboo search techniques for the job shop scheduling 
problem. ORSA journal on Computing, 6(2), 108-117. 
Talbi, E. G. (2002).A taxonomy of hybrid metaheuristics.Journal of heuristics, 8(5), 
541-564. 
Thamilselvan, R., y Balasubramanie, D. P. (2009). Integrating genetic algorithm, 
tabu search approach for job shop scheduling.arXiv preprint arXiv:0906.5070. 
Thamilselvan, R., y Balasubramanie, P. (2012). Integration of genetic algorithm 
with tabu search for job shop scheduling with unordered subsequence 
exchange crossover.Journal of Computer Science, 8(5). 
Van Laarhoven, P. J., Aarts, E. H., y Lenstra, J. K. (1992). Job shop scheduling by 
simulated annealing.Operations research, 40(1), 113-125. 
Velmurugan, P. S., y Selladurai, V. (2007). A Tabu Search algorithm for job shop 
scheduling problem with industrial scheduling case study.International 
Journal of Soft Computing, 2(4), 531-537. 
Vilcot, G., y Billaut, J. C. (2008). A tabu search and a genetic algorithm for solving 
a bicriteria general job shop scheduling problem.European Journal of 
Operational Research, 190(2), 398-411. 
Wang, Y. M., Yin, H. L., y Wang, J. (2009). Genetic algorithm with new encoding 
scheme for job shop scheduling.The International Journal of Advanced 
Manufacturing Technology, 44(9-10), 977-984. 
Zhang, C., Li, P., Guan, Z., y Rao, Y. (2007). A tabu search algorithm with a new 
neighborhood structure for the job shop scheduling problem.Computers & 
Operations Research, 34(11), 3229-3242. 
Zhang, L., Gao, L., y Li, X. (2013). A hybrid genetic algorithm and tabu search for a 
multi-objective dynamic job shop scheduling problem. International Journal of 
Production Research, 51(12), 3516-3531.