XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
TÉCNICAS MULTI-OBJETIVO PARA
RESOLVER PROBLEMAS DE
SECUENCIACIÓN DE OPERACIONES
EN ENTORNOS PRODUCTIVOS
REALES
Mariano Frutos (UNS )
[email protected]
Se presenta, en este trabajo, un algoritmo evolutivo multi-objetivo para
resolver problemas de secuenciación de operaciones en un entorno
productivo Job-Shop. En la actualidad, estos algoritmos son muy
utilizados para resolver este tipo de problemas. La novedad de nuestro
enfoque es la incorporación de un proceso de simulación en la fase
genética del algoritmo, el cual permite evaluar la estabilidad del
proceso productivo. Esta incorporación consiguió filtrar y ordenar las
soluciones, mejorando la calidad de las mismas, logrando, además,
que el algoritmo sea más eficiente en su evolución. Ya que se evaluaron
más de dos objetivos, se analizaron los selectores NSGAII, SPEAII e
IBEA. Se realizaron comparaciones pareadas utilizando los
indicadores Epsilon, Hypervolumen y R2. Observando los resultados
alcanzados, se concluyó que SPEAII mostró más eficiencia que el resto
de los algoritmos. We present here an evolutionary multi-objective
operations sequencing algorithm for Job-Shop environments. While
similar algorithms are already applied to solve those kinds of
problems, in our approach we run a simulation process on the genetic
phase of the algorithm, yielding an evaluation of the stability of the
production process. In this way, by filtering and ordering the solutions,
we improve their quality and make the algorithm more eficient in its
evolution. Since more than two objectives are considered we analize
selectors NSGAII, SPEAII and IBEA. We compare them pairwise using
Epsilon, Hypervolume and R2 indexes. The results yield that SPEAII is
the most efficient of the algorithms considered. Apresenta-se, neste
trabalho, um algoritmo evolutivo multi-objectivo para resolver
problemas de sequenciamento de operações num meio produtivo JobShop. Na actualidade, estes algoritmos são muito utilizados para
resolver este tipo de problemas. A novidade de nosso enfoque é a
incorporação de um processo de simulação na fase genética do
algoritmo, o qual permite avaliar a estabilidade do processo produtivo.
Esta incorporação conseguiu filtrar e ordenar as soluções, melhorando
a qualidade das mesmas, conseguindo, ademais, que o algoritmo seja
mais eficiente em sua evolução. Já que avaliaram-se mais de dois
objectivos, analisaram-se os seletores NSGAII, SPEAII e IBEA.
Realizaram-se comparações pareadas utilizando os indicadores
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
Epsilon, Hypervolumen e R2. Observando os resultados atingidos,
concluiu-se que SPEAII mostrou mais eficiência que o resto dos
algoritmos.
Palavras-chaves: Optimización multi-objetivo, Simulación, Algoritmos
Evolutivos.
2
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
1. Introducción
El Job-Shop Scheduling Problem (JSSP), es uno de los problemas que más aplicación ofrece
dentro del ámbito productivo (ADAMS ET AL., 1998). La resolución del mismo permite
incrementar la eficiencia de los distintos procesos. Es por lo general un problema muy difícil
de resolver. El mismo ha sido clasificado como NP-Hard (ULLMAN, 1975), es decir, no se
ha encontrado un algoritmo polinómico para resolverlo, por lo que el tiempo para encontrar
una solución crece exponencialmente con respecto al tamaño del problema. El JSSP se define
como la asignación de recursos limitados a trabajos que se procesan a lo largo del tiempo y
tiene como finalidad optimizar dicha asignación (CHENG & SMITH, 1997) (ARMENTANO
& SCRICH, 2000) (CHAO-HSIEN & HAN-CHIANG, 2009). Se tiene un conjunto de
máquinas, las cuales deben procesar distintos trabajos (DE GIOVANNI & PEZZELLA,
2010). Cada trabajo se descompone en una serie de operaciones. Se requiere obtener la
programación de cada trabajo determinando para ello los tiempos de inicio de cada una de sus
operaciones (CHINYAO & YULING, (2009). Se supone que al inicio del proceso cada
máquina está disponible y que en cada momento solo puede procesar una operación a la vez.
Además, se conocen las restricciones de precedencia de cada operación, y se supone que
ninguna operación puede ser interrumpida antes de que transcurra su tiempo de
procesamiento. La mayoría de los JSSP involucran la optimización simultánea de dos o más
objetivos, los cuales, generalmente, se encuentran en conflicto entre sí (FRUTOS & TOHMÉ,
2009). Este tipo de problemas se denominan multi-objetivo. Estos, por su naturaleza, suelen
tener múltiples soluciones. Se incluye, en esta sección, algunos conceptos fundamentales
sobre optimización multi-objetivo. En concreto, se define: Problema de Optimización Multiobjetivo, Optimalidad de Pareto, Dominancia de Pareto, Conjunto Óptimo de Pareto y
Frontera de Pareto. En estas definiciones asumimos, sin pérdida de generalidad, la
minimización de todos los objetivos.
a) Problema de Optimización Multi-objetivo: es encontrar un vector x*  [x1* ,..., x*n ]T que
satisfaga la totalidad de las q restricciones de desigualdad ( gi (x)  0, i  1,...,q ) y las p
restricciones de igualdad ( hi (x)  0, i  1,...,p ), minimizando la función vector
f (x)  [f1 (x),...,f k (x)]T , donde x  [x1,..., x n ]T es el vector de variables de decisión. El conjunto de
todos los valores que satisfacen las restricciones define la región de soluciones factibles 
y cualquier punto en x  es una solución factible.
b) Optimalidad de Pareto: un punto x*  es un óptimo de Pareto si para cada x  , hay al
menos una i para el cual fi (x* )  fi (x) . Esta definición dice que x * es un óptimo de Pareto si
no existe ningún vector factible x que mejore algún objetivo sin causar simultáneamente
un empeoramiento en al menos otro objetivo.
c) Dominancia de Pareto: un vector u  [u1,...,u n ]T se dice que domina a otro vector v  [v1,..., vn ]T
(representado por u v ) si y sólo si u es parcialmente menor que v , es decir, i {1,...,k} ,
ui  vi  i {1,...,k}: ui  vi .
d) Conjunto Óptimo de Pareto: para un Problema de Optimización Multi-objetivo dado f (x) ,
el Conjunto Óptimo de Pareto se define como P*  {x    x ' , f (x ' ) f (x)} .
3
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
e) Frontera de Pareto: Para un Problema de Optimización Multi-objetivo dado f (x) y su
Conjunto Óptimo de Pareto P* , la frontera de Pareto se define como FP*  {f (x), x  P*} .
Obtener la Frontera de Pareto para este tipo de problemas es la meta principal de la
optimización multi-objetivo. Dado que la frontera de Pareto puede contener un gran número
de puntos, una buena solución debe contener un número limitado de ellos, localizados lo más
cerca posible de la frontera de Pareto exacta, y distribuidos uniformemente a lo largo de la
misma (CORTÉS RIVERA ET AL., 2003).
El resto del artículo está organizado de la siguiente manera. Inicialmente se proporciona una
descripción general del JSSP y se presentan los objetivos a evaluar. Luego, se establece la
metodología ha utilizar. Seguido a esto, se desarrollan los experimentos y se muestran los
resultados alcanzados. Por último, se presentan las conclusiones y algunos posibles trabajos
futuros.
2. Definición de los objetivos para el JSSP
Como fue mencionado en la sección anterior, el JSSP consiste en organizar la ejecución de
diferentes trabajos. Es decir, se tiene un conjunto finito J de trabajos {J j}nj1 . Estos trabajos
deben ser procesados por un conjunto finito M de máquinas {Mk }km1 . Al procesamiento de una
operación de un trabajo J j en una máquina M k se la denomina Oijk , donde i indica el orden en
que debe ser realizado el conjunto de operaciones {S j}nj1 de un mismo trabajo J j . La operación
Oijk requiere el uso de una máquina M k durante un tiempo ininterrumpido ijk , conocido como
tiempo de procesamiento. El JSSP requiere de un procedimiento que permita afrontar el
secuenciamiento de las distintas operaciones Oijk , orientado por los objetivos a optimizar
(FRUTOS ET AL., 2010).
En este caso, se definieron tres objetivos a evaluar. En primer lugar, se tomó como objetivo la
minimización del tiempo total de procesamiento (Makespan) (1). En segundo lugar, se tomó
como objetivo la minimización del tiempo medio de flujo (Mean Flow Time) (2). Plantear
este objetivo permite disminuir el número de trabajos en proceso. Por último, se plantea
minimizar los efectos que presentan las variaciones en los tiempos de procesamiento de cada
operación Oijk en el Makespan. Para ello se desarrolló un modelo de simulación que nos
brinda información en relación a la distribución de probabilidades que presentará el primer
objetivo analizado (EVANS & OLSON, 1998). Minimizar el desvío estándar ( S ) de esta
distribución de probabilidades garantizará una programación de la producción más estable (3).
j
Min  Cmax

Min  F 
 max(t
iO( j)
kM
k
ij
 ijk )
1
  (t hmj  hmj  t1jk )
n jJ iO( j)
Min  S
j
Cmax
(1)
(2)
(3)
s.t.:
t ijk  0, j  J, i  O( j), k  M
t ijk  t sjh  sjh , if Osjh  Oijk , j  J, i,s  O(j), h,k  M
4
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
k
k
k
t ijk  t sp
 sp
, si Osp
 Oijk , j,p  J, i,s  O(j), k  M
3. Metodología empleada
Debido a sus diversas ventajas, el uso de algoritmos evolutivos se ha vuelto muy popular en
optimización multi-objetivo (COELLO COELLO ET AL., 2002) (CORTÉS RIVERA ET
AL., 2004). Entre los diversos algoritmos evolutivos que se han utilizado, uno de los más
interesantes en su desarrollo y aplicación es el Genetic Algorithm (GA) (GOLDBERG, 1989).
Para este problema se desarrolló un cromosoma cuyos genes representan la secuenciación de
cada operación Oijk , de acuerdo a la prioridad que establezca cada máquina (FRUTOS ET
AL., 2010). La población inicial es conformada por individuos cuyos cromosomas están
constituidos por genes seleccionados de manera aleatoria. Una vez establecido el cromosoma
se procede a la decodificación y evaluación de los individuos. Esta evaluación se lleva a cabo
de acuerdo a los objetivos planteados. Como fue mencionado anteriormente, para el cálculo
del tercer objetivo se utilizará un modelo de simulación el cual se correrá según la
configuración productiva del caso a resolver (EVANS & OLSON, 1998). El análisis de este
objetivo, reordena y filtra soluciones dentro del conjunto de soluciones, lo que mejora el
rendimiento del algoritmo evolutivo. El operador de cruce escogido es el cruce uniforme
(uniform crossover) y el operador de mutación seleccionado establece un intercambio
reciproco de genes del mismo cromosoma (Two-swap) (FRUTOS ET AL., 2010). En el
siguiente punto se determinarán los selectores utilizados en este trabajo. El lay-out del
algoritmo propuesto se muestra en la figura 1.
Set of integer numbers
{0, 1, …, (n!-1)}
Number of Machines
(m)
Set of sequences
{J1J2...Jn-1Jn, J1J2...JnJn-1,…}
Set of integer numbers
{0, 1, …, (m-1)}
Relating sets
0→J 1J2...Jn-1Jn
1→J 1J2...JnJn-1
...
Set of machines
{M1, M2, …, Mm}
Relating sets
0→M1
1→M2
...
Multi-Objective Genetic Algorithm
Simulation
Inicialization Algorithm
Number of Jobs
(n)
Random initialization
Mk→Value
(Chromosomes of
Sequences)
Initial population
↓↑
Individual
↓
Decoding
↓
Fitness
Random initialization
Oi kj →Value
(Chromosomes of
Allocations)
MOGA + Decoding + Fitness
End Algorithm
Figura 1 - Lay-out del algoritmo propuesto.
5
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
4. Experimentos y resultados
Los experimentos fueron desarrollados a través de planteos realizados sobre procesos
productivos reales. Los mismos se describirán de manera general. El primer caso a resolver
(Caso A) se refiere a la elaboración de productos de madera con terminación en laca. El caso
permitió establecer la utilización de 7 máquinas y/o centros de trabajo ( M1 : trozado, M 2 :
cepillado, M3 : corte, M 4 : perfilado, M5 : lijado, M 6 : ensamblado y M 7 : laqueado). Además, el
estudio se centró en la realización de 5 trabajos específicos (Problema 5x7). El segundo caso a
resolver (Caso B) se refiere a la elaboración de productos pre-fabricados de hormigón. A
diferencia con el caso anterior, este posee dos tipos de producción. La primera, la cual posee
mayor prioridad, es la producción estandarizada (vigas, columnas, pórticos, placas alveolares,
bovedillas, casetones, tubos, postes eléctricos, gradas, etc.). En segundo lugar, y objeto de este
estudio, es la producción no estandarizada (fogones, bancos de jardín, fuentes, escaleras, etc.).
Sobre esta última se volcará la aplicación cuya disponibilidad de máquinas y/o centros de
trabajos dependerá de la asignación ya establecida de las mismas a la producción
estandarizada. El caso permite establecer la utilización de 5 máquinas y/o centros de trabajo
( M1 : diseño y armado de los moldes, M 2 : preparación y vertido del mortero, M3 : desmolde y
curado de las piezas, M 4 : ensamble, M5 : acabado). Además, el estudio se centró en la
realización de 7 trabajos (Problema 7x5). El tercer, y último caso a resolver (Caso C) se
refiere a la elaboración de productos de mármol. Este caso también posee dos tipos de
producción, estandarizada (recubrimientos, pisos, escalones, etc.) y no estandarizada
(mesadas de mármol para cocina, lavamanos de baño de mármol, etc.). Sobre esta última se
volcará la aplicación cuya disponibilidad de máquinas y/o centros de trabajos, al igual que la
anterior, dependerá de la asignación ya establecida de las mismas a la producción
estandarizada. El caso permite establecer la utilización de 5 máquinas y/o centros de trabajo
( M1 : corte, M 2 : limado, M3 : agujereado, M 4 : pulido, M5 : ensamblado). Además, el estudio se
centró en la realización de 8 trabajos (Problema 8x5).
Habiendo definido una cantidad adecuada de generaciones para el algoritmo evolutivo y la
configuración productiva para la etapa de la simulación, se trabajó con la herramienta PISA
(BLEULER ET AL., 2003) y se comparó el desempeño global de la etapa evolutiva
intercambiando entre tres selectores: NSGAII (DEB ET AL., 2002), SPEAII (ZITZLER ET
AL., 2002) e IBEA (ZITZLER AND KÜNZLI, 2004). Para los experimentos se tomó α=100,
μ=50 y λ=50. Estos son los parámetros de PISA que corresponden con el número de
individuos (100), el número de padres (50) y de descendientes de la población (50) de una
generación. Estos valores fueron elegidos teniendo en cuenta resultados obtenidos en corridas
preliminares. En el caso del selector IBEA se eligió el indicador Epsilon aditivo y el resto de
los valores de los parámetros se mantuvieron con su valor predefinido en PISA. Muchos
trabajos se enfocan en mejoras marginales sobre estos algoritmos, sacrificando en algunos
casos la simplicidad de diseño de estos algoritmos.
Para el caso de NSGAII, ha sido demostrado en investigaciones previas que se necesita un
tiempo del orden de O(g*N2) teniendo en cuenta una población de tamaño de 2N para el
criterio de dominación. El cálculo de las distancias (DEB ET AL., 2002) que requiere este
algoritmo necesita no menos de O(g*N*logN) por lo que el procedimiento NSGAII completo
es del orden de O(g*N2). La parte más costosa del algoritmo basado en SPEAII (ZITZLER
6
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
ET AL., 2002) es el procedimiento de corte utilizado para preservar la diversidad, el cual
posee un tiempo de ejecución de orden O((N+N’)2*log(N+N’)), donde N es el tamaño de la
población y N’ es el tamaño del archivo donde guarda a los individuos mejores. En el caso de
IBEA (ZITZLER & KÜNZLI, 2004) tiene un orden de complejidad computacional O(N2).
Cada algoritmo fue corrido 20 veces y se tomaron todas las soluciones eliminándose de este
conjunto las dominadas. Los resultados se muestran en las figuras 2, 3 y 4. El valor del tercer
objetivo se establece a partir del diámetro del círculo proyectado sobre el eje de las abscisas o
eje definido para los valores del Makespan. Además, en la tabla 1, se brinda información
sobre el tiempo de procesamiento medio que requirió cada algoritmo.
Figura 2 - Soluciones / Caso A / SPEAII , NSGAII e IBEA .
Figura 3 - Soluciones / Caso B / SPEAII , NSGAII e IBEA .
7
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
Figura 4 - Soluciones / Caso C / SPEAII , NSGAII e IBEA .
Tiempo de Procesamiento Medio (seg.)
Caso A
Caso B
Caso C
NSGAII
5,827
4,602
4,805
IBEA
4,739
4,402
4,705
SPEAII
6,924
5,687
5,898
Tabla 1- Tiempos de Procesamiento Medio / Caso A, Caso B y Caso C.
Para comparar los resultados de los algoritmos y establecer cual es la mejor opción para
resolver el JSSP, varios tests fueron aplicados a las soluciones alcanzadas por los tres
algoritmos. Se aplicaron los indicadores unitarios IH (unary hypervolume indicator), Ie1 (unary
epsilon indicatior) y IR21 (R indicator) sobre el conjunto normalizado generado por PISA (IH,
tabla 2) (Ie1, tabla 3) (IR21, tabla 4).
IH
Caso A
Caso B
Caso C
NSGAII
IBEA
SPEAII
NSGAII
IBEA
SPEAII
NSGAII
IBEA
SPEAII
NSGAII
-
0,54665
0,95125
-
0,50331
0,96989
-
0,31304
0,96761
IBEA
0,45335
-
0,97110
0,49669
-
0,95099
0,68696
-
0,96710
SPEAII
0,04875
0,02890
-
0,03011
0,04901
-
0,03239
0,03290
-
Tabla 2 - IH / Caso A, Caso B y Caso C.
I e1
Caso A
NSGAII
IBEA
Caso B
SPEAII
NSGAII
IBEA
Caso C
SPEAII
NSGAII
IBEA
SPEAII
8
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
NSGAII
-
0,55212
0,96076
-
0,50834
0,97959
-
0,31617
0,97728
IBEA
0,44788
-
0,98081
0,49166
-
0,96050
0,68383
-
0,97677
SPEAII
0,03924
0,01919
-
0,02041
0,03950
-
0,02272
0,02323
-
Tabla 3 - Ie1 / Caso A, Caso B y Caso C.
R2
Caso A
Caso B
Caso C
NSGAII
IBEA
SPEAII
NSGAII
IBEA
SPEAII
NSGAII
IBEA
SPEAII
NSGAII
-
0,54337
0,95010
-
0,49928
0,96213
-
0,31053
0,95987
IBEA
0,45663
-
0,96333
0,50072
-
0,95004
0,68947
-
0,95936
SPEAII
0,04990
0,03667
-
0,03787
0,04996
-
0,04013
0,04064
-
Tabla 4 - R2 / Caso A, Caso B y Caso C.
De acuerdo al análisis realizado, sobre estos problemas (Caso A, Caso B y Caso C), las
diferencias entre los algoritmos NSGAII e IBEA no fueron estadísticamente significativas con
α=0.05 (Overall Significance Level). SPEAII, tuvo diferencias entre NSGAII e IBEA que
fueron estadísticamente significativas con α=0.05 (Overall Significance Level). Con esto se
pudo apreciar que el selector SPEAII es el candidato para resolver de la mejor manera el
JSSP. Uno de los motivos de que NSGAII no mostrara gran eficiencia, fue que al tener el
problema más de 2 objetivos, el operador de crowding no funcionó adecuadamente. Se
muestran en las figuras 5, 6 y 7, programaciones (scheduling) obtenidas con SPEAII.
Caso A: Productos de madera con terminación en laca 5x7
1
2
3
4
5
M1
M2
M3
M4
M5
M6
M7
first day
second day
third day
fourth day
fifth day
first week
Figura 5 - Scheduling / Caso A
9
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
Caso B: Productos pre-fabricados de hormigón 7x5
1
2
3
4
5
6
Unavailable
7
M1
M2
M3
M4
M5
first day
second day
third day
fourth day
fifth day
fourth day
fifth day
first week
M1
M2
M3
M4
M5
first day
second day
third day
second week
Figura 6 - Scheduling / Caso B
Caso C: Productos de mármol 8x5
1
2
3
4
5
6
7
8
Unavailable
M1
M2
M3
M4
M5
first day
second day
third day
fourth day
fifth day
first week
Figura 7 - Scheduling / Caso C
5. Conclusiones
En este trabajo se presentó un Algoritmo Evolutivo Multi-Objetivo (MOEA, Multi-Objective
Evolutionary Algorithms) que fue diseñado específicamente para su uso en el Job-Shop
Scheduling Problem (JSSP). Con la experimentación y análisis realizado se pudo determinar
cual selector (SPEAII, NSGAII e IBEA) brindaba mejores resultados en la evaluación de tres
objetivos. La aplicación requirió una calibración de parámetros, lo que constituye una
referencia para problemas similares. En los tres casos analizados, SPEAII se diferenció de
NSGAII e IBEA. Como parte de trabajos futuros, se está experimentando con otros MOEAs.
Finalmente, estamos interesados en evaluar este procedimiento en otros tipos de
10
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
configuraciones productivas y así verificar si el esquema propuesto realmente produce ahorros
importantes en el procesamiento, sin sacrificar de manera significativa la convergencia.
Agradecimientos
Este trabajo no podría haberse realizado sin el apoyo económico prestado por varias fuentes.
Los autores agradecen al Consejo Nacional de Investigaciones Científicas y Técnicas
(CONICET) por el apoyo brindado y, además, a la Universidad Nacional del Sur por el
subsidio concedido al proyecto PGI 24/J056.
Referencias
ADAMS, J., BALAS, E. & ZAWACK, D. The Shifting Bottleneck Procedure for job shop
scheduling, Management Science. Vol. 34, n. 3, p. 391-401, 1998.
ARMENTANO, V. & SCRICH, C. Taboo search for minimizing total tardiness in a job-shop,
International Journal of Production Economics. Vol. 63, p. 131-140, 2000.
BLEULER, S., LAUMANNS, M., THIELE, L. & ZITZLER, E. PISA, A Platform and
Programming Language Independent Interface for Search Algorithms, In Proceedings of Evolutionary
Multi-Criterion Optimization. p. 494-508, 2003.
CHAO-HSIEN, J. & HAN-CHIANG H. A hybrid genetic algorithm for no-wait job shop cheduling
problems, Expert Systems with Applications. Vol. 36, n. 3, p. 5800–5806, 2009.
CHENG, C. C. & SMITH, S. F. Applyng constraint satisfaction techniques to job shop scheduling,
Annals of Operations Research. Vol. 70, p. 327-357, 1997.
CHINYAO, L. & YULING, Y. Genetic algorithm-based heuristics for an open shop scheduling
problem with setup, processing, and removal times separated, Robotics and Computer-Integrated
Manufacturing. Vol. 25, n. 2, p. 314-322, 2009.
COELLO COELLO, C. A., VAN VELDHUIZEN, D. A. & LAMONT, G. B. Evolutionary
Algorithms for Solving Multi-Objective Problems, Kluwer Academic Publishers, New York, 2002.
CORTÉS RIVERA, D., COELLO COELLO, C. A. & CORTÉS, N. C. Use of an Artificial
Immune System for Job Shop Scheduling, In Proceedings of Second International Conference on
Artificial Immune Systems, Edinburgh, Scotland. Springer-Verlag, Lecture Notes in Computer
Science. Vol. 2787, p. 1-10, 2003.
CORTÉS RIVERA, D., COELLO COELLO, C. A. & CORTÉS, N. C. Job shop scheduling using
the clonal selection principle, In Proceedings of Sixth Int. Conference on Adaptive Computing in
Design and Manufacture (ACDM 2004), Bristol, United Kingdom, 2004.
DE GIOVANNI, L. & PEZZELLA F. An Improved Genetic Algorithm for the Distributed and
Flexible Jobshop Scheduling problem, European Journal of Operational Research. Vol. 200, n. 2, p.
395-408, 2010.
11
XXXIII ENCONTRO NACIONAL DE ENGENHARIA DE PRODUCAO
A Gestão dos Processos de Produção e as Parcerias Globais para o Desenvolvimento Sustentável dos Sistemas Produtivos
Salvador, BA, Brasil, 08 a 11 de outubro de 2013.
DEB, K., PRATAP, A., AGARWAL, S. & MEYARIVAN, T. A Fast and Elitist Multi-objective
Genetic Algorithm: NSGAII, IEEE Transactions on Evolutionary Computation. Vol. 6, n. 2, p. 182197, 2002.
EVANS, J. R. & OLSON, D. L. Introduction to simulation and risk analysis, Editorial Prentice Hall,
New Jersey, 1998.
FRUTOS, M. & TOHMÉ, F. Desarrollo de un procedimiento genético diseñado para programar la
producción en un sistema de manufactura tipo job-shop, In Proceedings of VI Congreso Español sobre
Meta-heurísticas, Algoritmos Evolutivos y Bioinspirados, España. p. 23-30, 2009.
FRUTOS, M., OLIVERA, A. C. & TOHMÉ, F. A Memetic Algorithm based on a NSGAII Scheme
for the Flexible Job-Shop Scheduling Problem, Annals of Operations Research. Vol. 181, p. 745-765,
2010.
GOLDBERG, D. Genetic Algorithms in Search, Optimization, and Machine Learning, Addison
Wesley. 1989.
ULLMAN, J. D. NP-complete scheduling problems. Journal of Computer System sciences. Vol. 10,
p. 384-393, 1975.
ZITZLER, E., LAUMANNS, M. & THIELE, L. SPEAII: Improving the Strength Pareto
Evolutionary Algorithm for Multiobjective Optimization, In Giannakoglou, Tsahalis, Periaux,
Papailiou, and Fogarty (eds), Evolutionary Methods for Design, Optimisations and Control. p. 19-26,
2002.
ZITZLER, E. & KÜNZLI, S. Indicator-Based Selection in Multiobjective Search. In: X. Yao, E. K.
Burke, J. Lozano, J. Smith, J. Merelo Guervós, J. Bullinaria, J. Rowe, P. Tiño, A. Kabán, H-P.
Schwefel (Eds.): PPSN VIII. LNCS (Springer). Vol. 3242, p. 832-842, 2004.
12