Un Algoritmo Memético basado en PSO para la programación de producción en una fábrica de flujo continuo.Bo Liu, Ling Wang, y Yi-Hui Jin

Resumen: Este artículo propone un algoritmo memético (MA) eficiente, basado en la optimización de enjambre de partículas (particle swarm optimization - PSO) para el problema de la permutación de la programación de producción en una fábrica de flujo continuo (PFSSP) con el objetivo de reducir al mínimo el tiempo máximo de realización, el cual es un problema típico de tiempo polinomial (NP) no determinista y de optimización combinatorial compleja. En el algoritmo memético basado en PSO (PSOMA) propuesto, tanto los operadores de búsqueda PSO como algunos operadores especiales de búsqueda local están diseñados para equilibrar la exploración y la capacidad de explotación. En particular, el PSOMA aplica el mecanismo evolutivo de búsqueda PSO, que se caracteriza por mejoras individuales, cooperación de población y competencia para llevar a cabo una exploración efectiva. Por otra parte, el PSOMA utiliza varias búsquedas locales de adaptación para realizar la explotación. Primero, para hacer que se adecue PSO a resolver PFSSP, una regla de valor de orden-alineado basada en una representación de clave aleatoria es presentada para convertir los valores de posición continua de partículas a permutaciones de trabajo. Segundo, para generar un enjambre inicial con cierta calidad y diversidad, la famosa heurística Nawaz-Enscore-Ham (NEH) se incorpora en la inicialización de población. Tercero, para equilibrar las capacidades de exploración y explotación, después de la operación estándar de búsqueda PSO una técnica nueva de búsqueda local llamada inserción NEH_1 se aplica probabilísticamente a algunas buenas partículas seleccionadas mediante el uso de un mecanismo de rueda de ruleta con una probabilidad específica. Cuarto, para enriquecer los comportamientos de búsqueda y evitar la convergencia prematura, una búsqueda local de recocido simulado (simulated annealing - SA) con múltiples vecindades diferentes se ha diseñado e incorporado en el PSOMA. Mientras tanto, una estrategia efectiva de aprendizaje adaptativa meta-Lamarckiana se emplea para decidir qué vecindad se utilizará en la búsqueda local SA. Por último, para mejorar aún más la capacidad de explotación, una búsqueda local por parejas se aplica después de la búsqueda SA. Los resultados de la simulación basados en pruebas comparativas demuestran la eficacia de PSOMA. Además, los efectos de algunos parámetros de optimización de rendimiento también son discutidos.

Términos Clave

Aprendizaje adaptativo meta-lamarckiano, algoritmo memético (MA), optimización de enjambre de partículas (PSO), permutación de programación de producción en una fábrica de flujo continuo.

INTRODUCCION

La programación de la producción juega un papel clave en los sistemas de fabricación de una empresa para mantener la posición competitiva en los mercados que cambian rápidamente. Para tener en cuenta este factor, es importante desarrollar tecnologías y enfoques avanzados de fabricación y programación que sean eficaces y eficientes. El problema de la programación de producción de fabrica de flujo continuo (FSSP) es una clase de problema ampliamente estudiado, basado en ideas recogidas de la ingeniería, que en la actualidad representa casi una cuarta parte de los sistemas de producción: líneas de montaje e instalaciones de servicios de información, y que se ha ganado la reputación de ser difícil de resolver. Como una simplificación de la FSSP, la permutación FSSP (PFSSP), es decir, que la secuencia de procesamiento de todos los trabajos es la misma para todas las máquinas, el reducir al mínimo el tiempo de realización máximo (es decir, el makespan) es un problema complejo típico, bien estudiado, no determinista y de tiempo polinomial (NP). Debido a su importancia tanto en teoría como en aplicaciones de ingeniería, es importante desarrollar métodos eficaces y eficientes para la PFSSP.

Desde el trabajo pionero de Johnson, la PFSSP ha recibido un trabajo considerable de investigación teórica, computacional y empírica. Para tener en cuenta la dificultad de la PFSSP, una cantidad considerable de técnicas de optimización se han propuesto. Sin embargo, debido a la complejidad de PFSSP, las técnicas de solución exacta, como ramificación y acotamiento (branch and bound), y la programación matemática, sólo son aplicables a problemas de pequeña escala. Por tanto, se han propuesto varias heurísticas, incluyendo heurísticas constructivas, heurísticas de mejoramiento, y sus híbridos (a veces llamados algoritmos meméticos (memetic algorithms - MA)). La heurística constructiva forma un programa viable desde el principio, sobre todo para resolver problemas de programación de dos y de tres máquinas. Sin embargo, las cualidades de la solución de la heurística constructiva, no son satisfactorias, aunque el proceso es muy rápido. Los resultados experimentales mostraron que la heurística Nawaz-Enscore-Ham (NEH) es una de las mejores heurísticas constructivas actuales. La heurística de mejoramiento comienza desde una un conjunto de soluciones generadas por algunos generadores de secuencias y trata de mejorar la solución mediante la aplicación de un conocimiento de problema específico para aproximarse al óptimo "global" o "subóptimo". La heurística de mejoramiento se basa generalmente en metaheurísticas tales como el recocido simulado (SA), algoritmos genéticos (AG), búsqueda tabú (TS), programación evolutiva, y búsqueda por vecindad variable (VNS). Las heurísticas de mejoramiento pueden obtener soluciones

bastante satisfactorias, pero a menudo consumen mucho tiempo y dependientes de parámetros.

Recientemente, las heurísticas híbridas han sido un tema candente en campos como en la informática como en la investigación operacional. Se supone que combinando las características de los diferentes métodos de manera complementaria se puede dar lugar a herramientas de optimización más robustas y eficaces. En particular, es bien sabido que el rendimiento de los algoritmos evolutivos se puede mejorar mediante la combinación de búsquedas locales dependientes del problema. Algoritmos meméticos (MA) pueden ser considerados como la unión de una búsqueda global basada en la población y las mejoras locales que se inspiran en los principios darwinianos de la evolución natural y la noción de Dawkins de Meme, definido como la unidad de evolución cultural que es capaz de mejoras locales. Hasta ahora, los algoritmos meméticos (MA) han obtenido amplia investigación sobre una variedad de problemas tales como el problema del viajante de comercio, el problema de la bipartición de grafos, el problema de asignación cuadrática, las redes móviles, y problemas de programación. En MA’s, diferentes estudios se han centrado en cómo lograr una combinación razonable de búsquedas globales y locales, y en cómo hacer un buen equilibrio entre la exploración y explotación. Recientemente, una arquitectura multiagente metaheurística fue presentada como marco conceptual y práctico para el diseño de MA’s. Tradicionalmente, la mayoría de MA’s se basan en el uso de un único algoritmo evolutivo para exploración a nivel global aproximada y una única búsqueda local para buenas mejoras a nivel local. Algunos estudios recientes sobre la elección de búsquedas locales han demostrado que su elección afecta de manera significativa la eficiencia de la búsqueda. Con el fin de evitar los efectos negativos de la búsqueda local incorrecta, Ong y Keane, acuñaron el término "aprendizaje meta-lamarckiano" para introducir la idea de elección adaptativa de memes múltiples durante una búsqueda de algoritmo memético en el espíritu de aprendizaje lamarckiano y en problemas de optimización continua resueltos satisfactoriamente por el algoritmo memético propuesto con múltiples búsquedas locales. En [29], una clasificación de adaptación de memes en algoritmos meméticos adaptativos fueron presentados sobre la base del mecanismo utilizado y del nivel de conocimiento histórico en los memes empleados, así como en las propiedades de convergencia global de MA’s adaptativos que se analizaron por medio de cadenas finitas de Markov. Además, un estudio realizado en [30] se enfoca en el marco del algoritmo memético sustituto-asistido para problemas computacionalmente costosos y problemas de diseño robusto.

Para un solo objetivo PFSSP, los algoritmos meméticos ya se han investigado en muchos estudios. En [12], un operador de fusión cruzado de múltiples pasos que lleva una búsqueda local fue introducido en algoritmos genéticos. En [16], un híbrido de algoritmo genético fue desarrollado mediante la sustitución de la mutación con recocido simulado y mediante la aplicación de varias operaciones de cruce a las subpoblaciones. En [17], un sistema de colonia de hormigas fue propuesto, el cual fue reforzado con una búsqueda local rápida para dar soluciones de alta calidad. En [18], dos versiones híbridas de algoritmos genéticos

fueron presentadas, es decir, recocido simulado genético y búsqueda local genética, donde las fases de mejoría con recocido simulado, así como la búsqueda local se realizan antes de las operaciones de selección y cruce. En [19], un recocido simulado híbrido se integró con las características tomadas de algoritmos genéticos y las búsquedas locales, que trabajaron sobre una población de programaciones candidatas y generaron nuevas poblaciones mediante la aplicación de esquemas adecuados de pequeña perturbación. Por otra parte, durante el proceso de recocido, un procedimiento reiterativo en escalada fue aplicado estocásticamente a la población. En [20], un algoritmo genético basado en la optimización ordinal fue presentado para asegurar la calidad de la solución encontrada con una reducción de esfuerzo de computación. Además, un algoritmo genético basado en pruebas de hipótesis fue propuesto en [31] para PFSSP estocástico con un tiempo de procesamiento incierto. En cuanto a los problemas de programación multiobjetivo, la hibridación con búsqueda local fue implementada por primera vez en [32] como una búsqueda local genética multiobjetivo (MOGLS), donde se utilizó una función escalar conveniente con pesos aleatorios para la selección de los padres y una búsqueda local para su descendencia. En [25], el antiguo MOGLS [32] fue modificado para elegir sólo individuos buenos como solución inicial para la búsqueda local y la asignación de una dirección de búsqueda local apropiada para cada solución inicial. Mientras tanto la importancia del equilibrio entre la genética y las búsquedas locales fue resaltada.

Recientemente, una nueva técnica evolutiva, la optimización de enjambre de partículas (PSO) [33], se propuso para problemas de optimización continua sin restricciones. Su desarrollo se basa en la observación de comportamientos sociales de los animales tales como la bandada de aves, bancos de pescados, y la teoría del enjambre. Se inicia con una población de soluciones al azar. A cada individuo se le asigna una velocidad al azar de acuerdo a su propia experiencia y a la experiencia de los compañeros de vuelo. Los individuos, llamados partículas, son elevados a través del hiperespacio. PSO tiene algunas características atractivas. Debido a que dispone de memoria, el conocimiento de buenas soluciones es retenido por todas las partículas. Además, dispone de una cooperación constructiva entre partículas y las partículas en el enjambre comparten información entre ellas. El PSO debido a su concepto simple, la fácil aplicación y la convergencia rápida, ha ganado mucha atención y amplias aplicaciones en diferentes campos, principalmente para problemas de optimización continua [34]. Sin embargo, la realización de un PSO simple depende de sus parámetros, y con frecuencia sufre el problema de estar restringido a óptimos locales. Se han llevado a cabo algunos estudios para prevenir la convergencia prematura y para equilibrar las capacidades de exploración y explotación [35]. Además, la mayoría de los trabajos publicados de PSO es para problemas de optimización continua, mientras que hay poca investigación en problemas de optimización combinatoria. Obviamente, el empleo de PSO es un reto para las áreas diferentes de problemas de las que los inventores se centraron originalmente. Según nuestro conocimiento, existen pocas obras publicadas sobre PSO para problemas de programación. Recientemente, un híbrido de PSO [36] sobre la base de VNS fue propuesto para PFSSP. En este articulo, se propondrá un algoritmo memético basado en PSO (PSOMA) para PFSSP. El PSOMA aplica el

mecanismo de búsqueda evolutiva de PSO, que se caracteriza por mejoras individuales, cooperación de la población, y competencia para llevar a cabo una exploración efectiva.

Por otra parte, PSOMA utiliza diferentes búsquedas locales de adaptación para realizar la explotación. Las características de PSOMA se pueden resumir de la siguiente manera. En primer lugar, para hacer el PSO adecuado para resolver PFSSP, una regla de valor de rango ordenado (ranked order value - ROV) basada en la representación de llave aleatoria [37] se presenta para convertir los valores de posición continua de una partícula a una permutación de trabajo. En segundo lugar, la heurística NEH se incorpora a la inicialización aleatoria de PSO para generar una población inicial con cierta calidad y diversidad. En tercer lugar, se propone una nueva búsqueda local llamada inserción NEH_1 y es aplicada probabilísticamente a algunas partículas buenas, seleccionadas mediante mecanismo de rueda de ruleta, con una probabilidad específica para equilibrar las capacidades de exploración y explotación. En cuarto lugar, se ha diseñado e incorporado una búsqueda local SA con múltiples y diferentes vecindades para enriquecer los comportamientos de búsqueda y para evitar la convergencia prematura, y una estrategia efectiva de aprendizaje adaptativa meta-lamarckiana se emplea para decidir qué vecindad se utilizará. Además, una búsqueda local de parejas se aplica después de la búsqueda local SA para mejorar aún más la capacidad de explotación. Resultados de las simulaciones y comparaciones demuestran la eficacia del PSOMA propuesto para PFSSP.El resto del contenido se organiza de la siguiente manera. En las secciones II y III, se introducen PFSSP y PSO. En la Sección IV, el PSOMA se propone después de presentar la representación de una solución, la inicialización de la población, la búsqueda local basada en NEH, la búsqueda local SA basada en combinación con la estrategia de aprendizaje adaptativo meta-lamarckiano, y la búsqueda local basado en parejas. En la sección V, se presentan y analizan los resultados experimentales de las pruebas comparativas, junto con las comparaciones con otras metaheurísticas anteriores. En la Sección VI, se discuten los efectos de algunos parámetros de optimización del rendimiento. Por último, en la Sección VII, terminamos este artículo con algunas conclusiones y sugerencias de posibles trabajos futuros.

II. EL PROBLEMA DE LA PERMUTACIÓN DE LA PROGRAMCIÓN DE PRODUCCIÓN EN UNA FÁBRICA DE FLUJO CONTINUO

El PFSSP puede describirse de la siguiente manera: Cada uno de los trabajos n se procesan de forma secuencial en la maquina 1,. . . , m. Se da el tiempo de procesamiento pi,j, del trabajo i en la máquina j. En cualquier momento, cada máquina puede procesar máximo un trabajo, y cada trabajo puede ser procesado en máximo una máquina. La secuencia en que los trabajos se van a procesar es el mismo para cada máquina. El objetivo es encontrar una secuencia para el procesamiento de los trabajos en las máquinas de modo que un criterio dado sea optimizado. En la literatura, el criterio ampliamente usado es la minimización del tiempo máximo de realización, es decir, el makespan (C max) [9] - [14].Si π = {j1, j2,. . . , jn} denota una permutación de trabajos, y C(ji,k) indica el tiempo de la terminación del trabajo ji en la máquina; entonces, el tiempo de la terminación C (ji,k) se puede calcular de la siguiente manera:

La PFSSP es entonces encontrar la permutación π * en el conjunto de todas las permutaciones Π tales que:

III. OPTIMIZACIÓN DE ENJAMBRE DE PARTÍCULAS

En un sistema PSO, se comienza con la inicialización aleatoria de una población (enjambre) de individuos (partículas) en el espacio de búsqueda y se trabaja sobre el comportamiento social en el enjambre. La posición y la velocidad de la partícula i en el espacio de búsqueda d-dimensional se puede representar como Xi Xi = [xi, 1, 2,. . . , xi, d] y Vi = [vi, 1, vi, 2,. . . , vi, d], respectivamente. Cada partícula tiene su mejor posición propia (pbest) pi = [pi, 1, pi, 2,. . . , pi, d] que corresponde al mejor valor objetivo personal obtenido hasta el momento en el tiempo t. Las mejores partículas globales (gbest) se denotan por Pg, las cuales representa las mejores partículas que se encuentran hasta el momento en el tiempo t, en el enjambre entero. La velocidad nueva de cada partícula se calcula de la siguiente manera:

donde c1 y c2 son los coeficientes de aceleración, w es el factor de inercia, R1 y R2 son dos números aleatorios independientes distribuidos uniformemente en el rango de [0, 1]. Así, la posición de cada partícula se actualiza en cada generación de acuerdo con la siguiente ecuación:

En general, el valor de cada componente en Vi puede ser sujetado al rango [ _vmax, vmax ] para controlar el movimiento excesivo de las partículas fuera del espacio de búsqueda. Entonces, la partícula viaja hacia una nueva posición de acuerdo con (8). Este proceso se repite hasta que un criterio de parada definido por el usuario es alcanzado. El procedimiento estándar de PSO se resume de la siguiente manera.

Paso 1) Iniciar una población de partículas con las posiciones y velocidades al azar, donde cada partícula contiene d variables (es decir, d = n). Paso 2) Evaluar los valores objetivo de todas las partículas, que el pbest de cada partícula y su valor objetivo sea igual a su posición actual y valor objetivo, y dejar que gbest y su valor objetivo sea igual a la posición y el valor objetivo de la mejor partícula inicial. Paso 3) Actualización de la velocidad y la posición de cada partícula de acuerdo con (7) y (8). Paso 4) Evaluar los valores objetivo de todas las partículas. Paso 5) Para cada partícula, comparar su valor actual objetivo con el valor objetivo de su pbest. Si el valor actual es mejor, a continuación, actualizar pbest y su valor objetivo con la posición actual y el valor objetivo. Paso 6) Determinar la mejor de las partículas del enjambre actual con el mejor valor objetivo. Si el valor objetivo es mejor que el valor objetivo de gbest, a continuación, actualizar gbest y su valor objetivo con la posición y el valor objetivo de la partícula más actual. Paso 7) Si un criterio de parada se cumple, entonces obtener el gbest de salida y su valor objetivo, de lo contrario regresar al paso 3).

IV. PSOMA para PFSSP

En esta sección explicaremos en detalle la implementación de PSOMA para PFSSP.

A. Representación de la solución

Por lo general, un esquema de codificación basado en permutación-trabajo [2], ha sido utilizado en muchos trabajos de PFSSP. Sin embargo, debido a los caracteres continuos de la posición de las partículas en PSO, el esquema estándar de codificación de PSO no puede ser adoptado directamente por PFSSP. Por lo tanto, la cuestión más importante en la aplicación de PSO a PFSSP es encontrar un mapeo adecuado entre la secuencia de trabajo y las posiciones de las partículas. En este artículo, una regla ROV basada en la representación clave aleatoria [37] es presenta para convertir la posición continua xi Xi = [xi, 1, 2,. . . , XI, n] de las partículas en PSO a la permutación de trabajos π = {j1, j2,. . . , jn}, por lo tanto el rendimiento de la partícula puede ser evaluado. En particular, la información de posición Xi = [xi, 1, xi, 2,. . . , XI, n] en sí misma no representa una secuencia, considerando que la fila de cada valor de posición de una partícula representa un índice de trabajo para construir una permutación de trabajos. En nuestra regla ROV, el valor más pequeño de posición de una

partícula, es primero seleccionado y luego asignado a un valor de rango de uno. Entonces, el segundo valor más pequeño de posición se escoge y se asigna a un valor de rango de dos. De la misma manera, todos los valores de posición serán manejados para convertir la información de posición de una partícula a una permutación de trabajo. Proporcionamos un ejemplo simple para ilustrar la regla de ROV en Tabla I. En el caso (n = 6), la posición es XI = [0.06, 2.99, 1.86, 3, 73, 2.13, 0.67]. Y debido a que XI,1 = 0.06 es el valor más pequeño de la posición, XI,1 es el primer seleccionado y es asignado a un valor de rango de uno; entonces, XI,6 = 0.67 es seleccionado y asignado a un valor de rango de dos. De forma similar, la regla ROV asigna un valor de rango de tres a seis para XI,3, XI,5, XI,2, y XI,4, respectivamente. Así, basándose en la regla ROV, se obtiene la permutación de trabajo, es decir, π = [1, 5, 3, 6, 4, 2].

TABLA I – REPRESENTACIÓN DE LA INFORMACIÓN DE POSICIÓN Y SU ROV CORRESPONDIENTE (PERMUTACIÓN DE TRABAJO)

TABLA II – BÚSQUEDA LOCAL BASADA EN INTERCAMBIO PARA LA PERMUTACIÓN DE TRABAJO Y EL AJUSTE CORRESPONDIENTE PARA LA INFORMACIÓN DE POSICIÓN

En nuestro PSOMA, varias búsquedas locales no se aplican directamente a la posición de información, sino a la permutación de trabajo. Así, cuando un procedimiento de búsqueda local es completado, la información de posición de la partícula debe ser corregida para garantizar que la permutación que será resultado de la regla ROV para la información de la nueva posición es la misma que la permutación que será el resultado de la búsqueda local. Es decir, al aplicar estas búsquedas locales para la permutación de trabajo, la información

de posición se debe ajustar correspondientemente. Afortunadamente, el ajuste es muy simple debido al mecanismo de la regla ROV. El proceso basado en algunas búsquedas locales sobre la información de posición es la misma que el proceso de permutación. Por ejemplo, en la Tabla II, cuando un operador de intercambio (SWAP) [16] se utiliza como búsqueda local para la permutación de trabajo, obviamente el intercambio del trabajo 5 y del trabajo 6 se corresponde con el intercambio de valores de posición 2.99 y 3.73. En cuanto a otros operadores de búsqueda local, como INVERSA e INSERT [16], el ajuste es similar.

B. Inicialización de la Población

En el PSO estándar, el enjambre inicial se genera a menudo aleatoriamente. Para garantizar una población inicial con cierta calidad y diversidad, la heurística NEH [9] se aplica para generar una solución (es decir, una permutación de trabajos), mientras que el resto de las partículas se inicializan con valores y velocidades aleatorias de posición en cierto intervalo. Puesto que el resultado producido por la heurística NEH es una permutación de trabajos, estas se deben convertir a valores de posición de cierta partícula inicial para realizar las búsquedas basadas en PSO. La conversión se realiza usando la siguiente ecuación:

donde XNEH,j es el valor de posición de la partícula en la dimensión j, SNEH,J es el índice de trabajo en la dimensión j de la permutación dada por la heurística NEH xmax,j y xmin,j son los límites superior e inferior del valor de posición, respectivamente, rand denota un número aleatorio uniformemente distribuido en el intervalo [0, 1], y n representa el número de dimensiones de una posición, el cual es igual al número de trabajos. La Tabla III ofrece un ejemplo de la conversión anterior de permutación de trabajo a información de posición. Obviamente, esta conversión obedece a la regla ROV. Es decir, la permutación se puede obtener de información de posición usando la regla ROV.

TABLA III – CONVERSIÓN DE LA SOLUCIÓN NEH (PERMUTACIÓN DE TRABAJO) PARA LA INFORMACIÓN DE POSICIÓN DE PARTÍCULA

C. Búsqueda PSO-basada

En este artículo, las búsquedas PSO-basadas, es decir, (7) y (8), son aplicadas para la exploración. Es decir, la información de posición de las partículas en el enjambre actual es desarrollada por los operadores de búsqueda PSO-basados. Nótese, que la evolución PSO-basada se realiza en un espacio continuo. Así pues, al evaluar el rendimiento de una partícula, la información de posición se debe convertir a la permutación de trabajo usando la regla antedicha de ROV. Por una parte, PSO proporciona un marco evolutivo paralelo para la optimización de problemas complicados, y es también fácil incorporar búsquedas locales en PSO para desarrollar algoritmos híbridos. En el siguiente contenido, presentaremos algunas búsquedas locales que se incorporen en PSO para proponer un MA PSO-basado.

D. Búsqueda local NEH-Basada

En el MAs, las búsquedas locales son muy importantes para la explotación. Para PFSSP, Aldowaisan y Allahverdi [38] diseñaron una búsqueda local nombrada la inserción NEH_2 para mejorar la calidad de una permutación del trabajo, donde dos trabajos consecutivos son considerados como un bloque e insertados en la secuencia de una manera similar como en NEH. La inserción NEH_2 se describe como sigue.

Paso 1) Dada una secuencia de trabajos π.

Paso 2) k = 1. Seleccione los primeros dos trabajos de π, y los programa para reducir al mínimo el makespan parcial. Seleccione la mejor secuencia como secuencia actual.

Paso 3) Establecer k=k+1. Generar secuencias candidatas mediante la selección de los próximos dos trabajos de π, insertando este k-ésimo bloque de dos trabajos en cada ranura de la secuencia actual, e intercambiando el orden de los dos trabajos dentro del bloque. Entre estos candidatos, seleccionar el mejor con el menor makespan parcial. Establecer el mejor como una secuencia actual.Paso 4) Repita el paso 3) hasta que todos los trabajos en π sean asignados. Si la última asignación es un solo trabajo, tratar este trabajo como bloque.

Inspirado por la inserción NEH_2, proponemos una búsqueda local llamada inserción NEH_1 para soluciones basadas en permutación. Demostraremos la superioridad de NEH_1 sobre NEH_2 en la simulación posterior. El NEH_1 se describe como sigue.

Paso 1) Dada una secuencia de trabajos π.

Paso 2) Se toman los primeros dos trabajos de π, y se evalúan las dos posibles programaciones parciales. Seleccione la mejor secuencia como la secuencia actual.

Paso 3) Tomar el trabajo k,k = 3,…, n, y encontrar la mejor programación poniéndolo en todas las posiciones posibles de k en la secuencia de trabajos que se programen en el momento. La mejor secuencia parcial se selecciona para la siguiente iteración.

Además, en PSOMA, sobre la base de los rendimientos de las soluciones de pbest de todas las partículas en enjambre actual, a la solución pbest de cada partícula se le asigna una probabilidad de ser seleccionada por la técnica apropiada de asignación basada en rangos [39]. Entonces, el mecanismo de rueda de ruleta [39] se utiliza para decidir qué soluciones pbest serán seleccionadas. Posteriormente, las soluciones pbest seleccionadas se llevarán a cabo sobre la inserción NEH_1 o NEH_2 con una probabilidad predefinida pls. Debido al mecanismo de la regla de rueda de ruleta, una buena solución tendrá más posibilidades de explotación. Además, es fácil de controlar el proceso de explotación mediante el ajuste del valor de los pls. Por ejemplo, si pls = 1, el pbest seleccionado debe realizar NEH_1 o NEH_2, mientras que si pls <1, el pbest seleccionado realizará NEH_1 o NEH_2 con cierta probabilidad de pls.

E. Búsqueda local SA-basada combinando la estrategia de aprendizaje Meta-Lamarckiana

En el SA, a partir de un estado inicial, el algoritmo genera aleatoriamente un nuevo estado en la proximidad del estado original, que causa un cambio de ΔE en el valor de la función objetivo. Para problemas de minimización, el nuevo estado se acepta con probabilidad min{1, exp (−ΔE/T)}, donde T es un parámetro de control. El SA proporciona un mecanismo para escapar probabilísticamente de óptimos locales, y el proceso de búsqueda puede ser controlado por la programación de refresco [40].

En este artículo, diseñamos una búsqueda local SA-basada con múltiples vecindades diferentes para enriquecer los comportamientos de búsqueda locales y evitar la convergencia prematura. Por otra parte, la estrategia de aprendizaje meta-lamarckiana adaptativa en [28] es empleada para decidir qué vecindad o proximidad se utilizará.

1) Vecindad en búsqueda local SA-basada: Con el fin de mantener la diversidad de una población y enriquecer los comportamientos de búsqueda local, se utilizaran tres tipos diferentes de vecindades: SWAP, INSERT, e INVERSE.

SWAP: Seleccione aleatoriamente dos elementos distintos de una permutación con n-trabajos e intercámbielos.INSERT: Escoja aleatoriamente dos elementos distintos de una permutación de n-trabajos e inserte el de atrás antes del de adelante.INVERSE: Invertir la sub-secuencia entre dos posiciones aleatorias diferentes de una permutación de n-trabajos.

2) Estrategia de aprendizaje Meta-Lamarckiano adaptativo: Inspirado en la idea de trabajo de ONG y Keane [28], no sólo aplicamos a vecindades múltiples si no también adoptamos una estrategia eficaz de aprendizaje meta-Lamarckiano adaptativo para decidir qué vecindad se elegirá para que la búsqueda local recompense los tiempos de utilización de esas vecindades, dando por resultado una solución mejorada.La estrategia de aprendizaje meta-Lamarckiano adaptativo en nuestro PSOMA se ilustra como sigue. Dividimos la búsqueda SA-basada en una fase de entrenamiento y en una fase

de no entrenamiento. Durante la fase meta-Lamarckiana de entrenamiento, cada búsqueda local SA-basada con diferente vecindad es aplicada para los mismos tiempos, es decir, los n(n-1) pasos (una generación de muestreo de Metrópolis). Entonces, el hallazgo η de cada vecindad es determinado mediante la siguiente ecuación:

donde n denota el número de trabajos, el pf es el valor objetivo de la permutación antigua, y el cf es el valor objetivo de la mejor permutación encontrada por la búsqueda local basada en diferentes vecindades durante los n (n-1) pasos consecutivos. Después de que el hallazgo de cada vecindad sea determinado, la probabilidad de utilización put de cada vecindad se ajusta mediante la siguiente ecuación:

donde el ηi es el valor de hallazgo de la i-ésima vecindad y K es el número total de vecindades. En la fase de no entrenamiento, según la probabilidad de utilización de cada vecindad, una regla de rueda de ruleta [39] se utiliza para decidir qué vecindad se utilizará para la búsqueda local SA-basada. Si se utiliza la i-ésima vecindad, su hallazgo será actualizado por ηi = ηi +Δηi, donde Δηi es el valor de hallazgo de la i-ésima vecindad calculada durante la fase de no entrenamiento (es decir, búsqueda SA-basada sobre la i-ésima vecindad con los n (n-1) pasos consecutivos). Por supuesto, la probabilidad de utilización put de cada vecindad debe ser ajustada nuevamente para la siguiente generación de PSOMA.3) Notas adicionales sobre la búsqueda local SA-Basada: Con una apropiada temperatura inicial que debe de ser lo suficientemente alta para que todos los estados del sistema tengan una probabilidad igual de ser visitados, y al mismo tiempo, esta no debe ser excesivamente alta de modo que muchas búsquedas innecesarias en temperatura alta sean evitadas. En este articulo, e establece una temperatura inicial de prueba y error.

Por otra parte, se aplica una programación de refresco exponencial tk= λtk-1, 0 <λ <1, que a menudo se cree que es una receta de refresco excelente, ya que proporciona un compromiso bastante bueno entre una programación computacionalmente rápida y la capacidad de alcanzar una estado de baja energía [41]. Para proporcionar un buen compromiso entre calidad de la solución y eficiencia de la búsqueda, el paso de proceso de muestreo Metrópolis se establece en n • (n - 1).Además, la búsqueda local anterior SA-basada sólo se aplica a la mejor solución encontrada hasta el momento, es decir, gbest. Por tanto, a una alta temperatura, el algoritmo realiza la exploración con cierta probabilidad de salto, así como la mejora local de gbest, mientras que a una baja temperatura, el algoritmo hace hincapié en la explotación de gbest. Por otro lado, la aplicación de poco esfuerzo computacional se pagará en las búsquedas locales, ya que sólo se aplica a gbest. Después de que la búsqueda local SA-basada es completada, el

gbest de todo el enjambre debe ser actualizado si una solución con una mejor calidad se encuentra durante la búsqueda local.F. Búsqueda local basada en parejasComo proceso de búsqueda complementario, una búsqueda local basada en parejas [38] se emplea para el gbest, cuyo procedimiento se describe como sigue: Se examina cada posible intercambio de parejas de trabajo en la primera posición, con los trabajos en todas las otras posiciones. Siempre que haya una mejora en la función objetivo, los trabajos son intercambiados. Similarmente, se examinan los trabajos en la segunda y las otras subsecuentes posiciones. La búsqueda basada en parejas se puede ver como un proceso de búsqueda detallada de vecindades, así que es aplicada después de la búsqueda local SA-basada para mejorar más halla la capacidad de explotación.

G. Algoritmo Memético PSO-BasadoDe acuerdo con la regla propuesta ROV, la inicialización de la población, la búsqueda local NEH-basada, la búsqueda local SA-basada que combina la estrategia de aprendizaje meta-Lamarckiano adaptativo, y la búsqueda local basada en parejas, se propone un esquema de PSOMA, que se ilustra en figura 1.

Se puede notar que PSOMA no sólo aplica el mecanismo de búsqueda evolutivo PSO basado para llevar a cabo una exploración efectiva de soluciones prometedoras en toda la región, sino que también se aplican búsquedas locales problemas-dependientes para llevar a cabo la explotación para la mejora de solución en las subregiones. Debido a la complejidad de PFSSP, PSOMA aplica diferentes búsquedas locales simultáneamente, incluyendo la inicialización NEH basada en la inserción NEH_1 o NEH_2, búsqueda local SA-basada en combinación de la estrategia de aprendizaje adaptativo meta-lamarckiano, y búsqueda local basada en parejas. Dado que tanto la exploración como la explotación están resaltadas y balanceadas, se espera que se logren buenos resultados para PFSSP. En la siguiente sección, vamos a investigar los rendimientos de PSOMA.

V. PRUEBAS NUMÉRICAS Y COMPARACIONES

A. Instalación ExperimentalPara probar el rendimiento del PSOMA propuesto, se lleva a cabo la simulación computacional con algunos puntos de referencia bien estudiados. En este artículo, 29 problemas que fueron aportados a la biblioteca OR son seleccionados. Los primeros ocho problemas se llaman car1, car2 hasta car8 por Carlier [42]. Los otros 21 problemas se llaman rec01, rec03 hasta rec41 por Reeves [11], quienes los utilizan para comparar el rendimiento de algunas metaheurísticas y que han encontrado que estos problemas son particularmente difíciles. Hasta ahora, estos problemas han sido utilizados como puntos de referencia para el estudio con diferentes métodos por muchos investigadores.En nuestra simulación, el PSOMA está codificado en MATLAB 7.0 (The MathWorks, Inc., 2004), y los experimentos se realizan en un Pentium Mobile IV de 2,2 GHz con 512 MB de RAM. Los siguientes parámetros se utilizan en PSOMA: tamaño de enjambre ps = 20, w = 1.0, c1 = c2 = 2.0, xmin = 0, xmax = 4.0, Vmin = -4,0, vmax = 4.0, pls = 0,1, temperatura inicial T0 = 3.0, tasa de recocido λ = 0.9, y parámetro de parada L = 30. Cada instancia es ejecutada 20 veces de manera independiente por cada algoritmo para la comparación.Para validar la eficacia de cada parte en PSOMA, las variantes de PSOMA son comparadas. Las siguientes abreviaturas representan las variantes consideradas:1) PM_NEH1: PSOMA con NEH_1;2) PM_NEH2: PSOMA con NEH_2 reemplazando NEH_1;3) PM_NONEH: PSOMA sin búsqueda local NEH-basada (También NEH_1 o NEH_2);4) PM_NOSA: PSOMA sin búsqueda local SA-basada;5) PM_NOPAIR: PSOMA sin búsqueda basada en parejas.

B. Resultados y Comparaciones de la Simulación

1) Comparación de PM_NEH1, PM_NEH2 y heurística NEH: Los rendimientos estadísticos de 20 ejecuciones independientes se muestran en la Tabla I, incluyendo el

mejor error relativo a C∗ (BRE), error relativo promedio a C∗ (ARE), el peor error relativo

a C∗ (WRE), y tiempo de ejecución promedio de CPU (Tavg). Debido a que la heurística

NEH es determinista, los valores para el error relativo (RE), C∗ son dados. En la tabla IV,

C∗ es el makespan óptimo o el valor de límite más inferior conocido hasta ahora.

En la tabla IV, puede verse que el PM_NEH1 (es decir, nuestra propuesta PSOMA) proporciona el mejor rendimiento de optimización entre los métodos estudiados casi para todos los puntos de referencia. Por un lado, los óptimos resultados obtenidos por el

PM_NEH1 están cerca de C∗ (es decir, la CCE son valores muy pequeños), lo cual

demuestra la búsqueda efectiva de calidad PSOMA. Por otro lado, los valores ARE y WRE que resultan de PM_NEH1 también son muy pequeños, lo que demuestra la solidez de PSOMA en condiciones iniciales. En comparación con heurística NEH, PM_NEH1 puede obtener resultados mucho mejores, y los valores WRE que resultan de PM_NEH1 y PM_NEH2 (dos variantes de PSOMA) son mejores que RE valores que resultan de la heurística NEH, lo cual demuestra la mejora significativa de PSOMA sobre la famosa heurística NEH.

En comparación con PM_NEH2, los valores BRE, ARE, y WRE que resultan de PM_NEH1 son mejores que los que resulten de PM_NEH2 en la mayoría de los casos, lo que demuestra la eficacia en términos de calidad de búsqueda y robustez de la inserción NEH_1 con respecto a la inserción NEH_2. En cuanto al rendimiento en tiempo computacional, el PSOMA NEH_1-basado es competitivo al PSOMA NEH_2-basado. Por lo tanto, se concluye que NEH_1 es superior a NEH_2 en nuestro PSOMA. 2) Comparación de PM_NEH1, PM_NONEH, PM_NOSA y PM_NOPAIR: demostramos la eficacia de la búsqueda local al comparar PM_NEH1 (PSOMA) con PM_NONEH, PM_NOSA y PM_NOPAIR. Los resultados estadísticos de cada algoritmo con 20 ejecuciones independientes se muestran en la Tabla V. De acuerdo con la tabla V, se ha demostrado que los valores BRE y ARE obtenidos por PM_NEH1 son mucho mejores que los obtenidos con PM_NONEH, PM_NOSA y PM_NOPAIR, los cuales demuestran la efectividad al incorporar búsquedas locales en el PSO. Es decir, la superioridad en términos de la calidad de búsqueda y la robustez de PSO es propietaria de la combinación de la búsqueda global y las búsquedas locales, es decir, el balance de la exploración y la explotación. Dado que elementos de búsqueda local son empleados, el tiempo computacional de PSOMA es mayor que el de algoritmos sin búsqueda local, si bien puede

considerarse como el costo de evitar la convergencia prematura con el fin de lograr un mejor rendimiento en la optimización.

3) Comparación de PSOMA y PSOVNS: para mostrar la eficacia de PSOMA, llevamos a cabo una simulación para comparar nuestro PSOMA con el PSO híbrido basado en VNS (PSOVNS) [36]. En la simulación, los parámetros de PSOVNS son los mismos que los utilizados en [36], mientras que el PSOVNS utiliza el mismo número de evaluación con PSOMA para cada instancia. Los resultados estadísticos de los dos algoritmos se muestran en la Tabla 6.De acuerdo con la Tabla VI, está demostrado que los valores BRE obtenidos por PSOMA son mucho mejores que los obtenidos por PSOVNS en todas las instancias, y los valores ARE y WRE obtenidos por PSOMA son mucho mejores que los obtenidos por PSOVNS casi para todos los casos. Por tanto, se concluye que nuestros métodos de búsqueda local propuestos, especialmente su utilización en sentido híbrido, son más eficaces que la búsqueda local pura VNS-basada [36]. En resumen, nuestro PSOMA es más eficaz que PSOVNS.

4) Comparación de PSOMA y otros métodos populares: Para mostrar la eficacia de PSOMA, realizamos algunas comparaciones con otras meta-heurísticas populares y eficaces como simple GA (SGA), SGA+NEH y GA híbrida (HGA) [16], cuyos resultados son comparables o incluso superiores a las de muchas otras meta-heurísticas en artículos anteriores. La Tabla VII lista los resultados estadísticos de cada algoritmo para resolver los 29 problemas. De los resultados, puede concluirse que nuestro PSOMA es más eficaz que HGA [16].

VI. EFECTOS DE LOS PARÁMETROS

En esta sección, investigaremos los efectos del tamaño del enjambre y la probabilidad de utilización de inserción NEH_1 en el rendimiento de PSOMA.

A. Efecto del tamaño del enjambre ps

Tal como sabemos, el rendimiento de PSO depende enormemente del tamaño del enjambre. Por tanto, debemos investigar el efecto del tamaño del enjambre sobre el rendimiento de

PSOMA. El efecto de ps sobre la calidad de búsqueda y el tiempo computacional cuando se resuelve el problema Rec25 se ilustra en la Tabla VIII.

En la Tabla VIII, puede observarse que, con el aumento de tamaño, el tiempo computacional aumenta, mientras que la calidad de búsqueda varía de acuerdo con una pequeña magnitud. Es decir, el tamaño de enjambre no afecta demasiado la calidad de búsqueda PSOMA. Por tanto, se recomienda adoptar un tamaño de enjambre de 20 para problemas de pequeño y mediano tamaño y se sugiere de manera adecuada aumentar el tamaño de enjambre para problemas de gran tamaño.

B. Efecto de pls

En PSOMA, el parámetro pls determina la probabilidad de usar inserción NEH_1 para la permutación seleccionada pbest. Por tanto, este afecta el elemento de explotación, así como el tiempo computacional. El efecto de pls en la calidad de búsqueda y en el tiempo computacional cuando se resuelva el problema Rec25 se ilustra en la Tabla IX.Se puede apreciar que los rendimientos obtenidos por PSOMA cuando pls = 0 (que significa que la búsqueda local NEH no es utilizada) son peores que los que se obtienen cuando pts >0, lo que demuestra la eficacia de incorporar la búsqueda local NEH-basada en PSOMA. Con el aumento de pls, el tiempo computacional aumenta, y la calidad de búsqueda varía de acuerdo con una pequeña magnitud. Es decir, el pls no afecta demasiado la calidad de búsqueda de PSOMA cuando pls > 0. Por tanto, para un compromiso entre el rendimiento y el tiempo computacional, se recomienda en nuestros estudios que pls=0.1.

VII. CONCLUSIONES E INVESTIGACIONES FUTURAS

En este artículo, mediante la hibridización de la habilidad de búsqueda evolutiva basada en población de PSO con habilidades mejoradas locales de algunas búsquedas locales para equilibrar la exploración y la explotación, un efectivo PSOMA ha sido propuesto para PFSSP con el objetivo de minimizar el makespan. Nuestro trabajo mejorado puede resumirse en los siguientes cinco aspectos. En primer lugar, hacer el PSO apropiado para resolver PFSSP, una regla ROV fue presentada para convertir las posiciones continuas a permutaciones de trabajo. Segundo, la heurística NEH fue incorporada dentro de una inicialización aleatoria para generar una población inicial con cierta calidad y diversidad. Tercero, la inserción NEH_1 fue propuesta y probabilísticamente aplicada a algunas buenas partículas seleccionadas mediante el uso de un mecanismo de rueda de ruleta para equilibrar las habilidades de exploración y explotación. Cuarto, la búsqueda local SA-basada fue diseñada e incorporada en el algoritmo memético para enriquecer los comportamientos de búsqueda y para evitar la convergencia prematura, y una estrategia efectiva de aprendizaje adaptativo meta-Lamarckiano fue empleado para decidir cual vecindad seria usada. Además, una búsqueda local basada en parejas fue aplicada para mejorar la habilidad de explotación. Los resultados de la simulación y la comparación demostraron la superioridad de PSOMA en términos de calidad de búsqueda y robustez. El trabajo futuro es investigar la adaptación de parámetros de PSOMA y desarrollar otros algoritmos meméticos PSO-basados para el problema de la permutación de la programación de producción en una fábrica de flujo continuo y para problemas de programación con múltiples objetivos.

RECONOCIMIENTOS

Los autores agradecen a los editores de esta publicación especial en algoritmos meméticos y a quienes lo han recomendado de manera anónima para sus comentarios constructivos en el cercano manuscrito de este artículo.

REFERENCIAS

[1] H. Stadtler, “Supply chain management and advanced planningbasics, overview and challenges,” Eur. J. Oper. Res., vol. 163, no. 3, pp. 575–588, Jun. 2005.[2] L. Wang, Shop Scheduling with Genetic Algorithms. Beijing, China: Tsinghua Univ. Press, 2003.[3] M. Pinedo, Scheduling: Theory, Algorithms and Systems, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2002.[4] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.[5] S. M. Johnson, “Optimal two- and three- stage production schedules with setup times included,” Nav. Res. Logist. Q., vol. 1, no. 1, pp. 61–68, Mar. 1954.[6] R. Ruiz and C. Maroto, “A comprehensive review and evaluation of permutation flowshop heuristics,” Eur. J. Oper. Res., vol. 165, no. 2, pp. 479–494, Sep. 2005.[7] B. J. Lageweg, J. K. Lenstra, and A. H. G. Rinnooy Kan, “A general bounding scheme for the permutation flow-shop problem,” Oper. Res., vol. 26, no. 1, pp. 53–67, 1978.[8] P. Moscato, “On evolution, search, optimization, genetic algorithms and martial arts: Toward memetic algorithms,” in “Caltech Concurrent Computation Program,” California Inst. Technol., Pasadena, CA, Tech. Rep. 826, 1989.[9] M. Nawaz, E. Enscore, and I. Ham, “A heuristic algorithm for the mmachine, n-job flow-shop sequencing problem,” Omega, vol. 11, no. 1, pp. 91–95, 1983.[10] I. H. Osman and C. N. Potts, “Simulated annealing for permutation flowshop scheduling,” Omega, vol. 17, no. 6, pp. 551–557, 1989.[11] C. R. Reeves, “A genetic algorithm for flowshop sequencing,” Comput. Oper. Res., vol. 22, no. 1, pp. 5–13, Jan. 1995.[12] C. R. Reeves and T. Yamada, “Genetic algorithms, path relinking and the flowshop sequencing problem,” Evol. Comput., vol. 6, no. 1, pp. 45–60, 1998.[13] E. Nowicki and C. Smutnicki, “A fast tabu search algorithm for the permutation flow-shop problem,” Eur. J. Oper. Res., vol. 91, no. 1, pp. 160–175, May 1996.[14] L. Wang and D. Z. Zheng, “A modified evolutionary programming for flow shop scheduling,” Int. J. Adv. Manuf. Technol., vol. 22, no. 7/8, pp. 522–527, Nov. 2003.[15] P. Hansen and N. Mladenovic, “Variable neighborhood search: Principles and applications,” Eur. J. Oper. Res., vol. 130, no. 3, pp. 449–467, May 2001.[16] L. Wang and D. Z. Zheng, “An effective hybrid heuristic for flow shop scheduling,” Int. J. Adv. Manuf. Technol., vol. 21, no. 1, pp. 38–44, 2003.[17] T. Stutzle, “An ant approach to the flow shop problem,” in Proc. 6th Eur. Congr. Intell. Tech. and Soft Comput., Aachen, Germany, 1998, pp. 1560–1564.[18] T. Murata, H. Ishibuchi, and H. Tanaka, “Genetic algorithms for flowshop scheduling problems,” Comput. Ind. Eng., vol. 30, no. 4, pp. 1061–1071, Sep. 1996.[19] A. C. Nearchou, “A novel metaheuristic approach for the flow shop scheduling problem,” Eng. Appl. Artif. Intell., vol. 17, no. 4, pp. 289–300, Apr. 2004.[20] L. Wang, L. Zhang, and D. Z. Zheng, “A class of order-based genetic algorithm for flow shop scheduling,” Int. J. Adv. Manuf. Technol., vol. 22, no. 11/12, pp. 828–835, Dec. 2003.[21] W. E. Hart, N. Krasnogor, and J. E. Smith, Recent Advances in Memetic Algorithms. Heidelberg, Germany: Springer-Verlag, 2004.

[22] P. Merz, “Memetic algorithms for combinatorial optimization problems: fitness landscapes and effective search strategies,” Ph.D. dissertation, Univ. Siegen, Siegen, Germany, 2000.[23] A. Quintero and S. Pierre, “Sequential and multi-population memetic algorithms for assigning cells to switches in mobile networks,” Comput. Netw., vol. 43, no. 3, pp. 247–261, Oct. 2003.[24] P. M. França, A. Mendes, and P. Moscato, “A memetic algorithm for the total tardiness single machine scheduling problem,” Eur. J. Oper. Res., vol. 132, no. 1, pp. 224–242, Jul. 2001.[25] H. Ishibuchi, T. Yoshida, and T. Murata, “Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling,” IEEE Trans. Evol. Comput., vol. 7, no. 2, pp. 204–223, Apr. 2003.[26] M. Milano and A. Roli, “MAGMA: A multiagent architecture for metaheuristics,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 34, no. 2, pp. 925–941, Apr. 2004.[27] N. Krasnogor, “Studies on the theory and design space of memetic algorithms,” Ph.D. dissertation, Univ. West England, Bristol, U.K., 2002.[28] Y. S. Ong and A. J. Keane, “Meta-Lamarckian learning in memetic algorithms,” IEEE Trans. Evol. Comput., vol. 8, no. 2, pp. 99–110, Apr. 2004.[29] Y. S. Ong, M. H. Lim, N. Zhu, and K. W. Wong, “Classification ofadaptive memetic algorithms: A comparative study,” IEEE Trans. Syst., Man, Cybern. B, Cybern., vol. 36, no. 1, pp. 141–152, Feb. 2006.[30] Y. S. Ong, P. B. Nair, and A. J. Keane, “Evolutionary optimization of computationally expensive problems via surrogate modeling,” AIAA J., vol. 41, no. 4, pp. 687–696, 2003.[31] L. Wang, L. Zhang, and D. Z. Zheng, “A class of hypothesis-test based genetic algorithm for flow shop scheduling with stochastic processing time,” Int. J. Adv. Manuf. Technol., vol. 25, no. 11/12, pp. 1157–1163, Jun. 2005.[32] H. Ishibuchi and T. Murata, “A multi-objective genetic local search algorithm and its application to flowshop scheduling,” IEEE Trans. Syst.,Man, Cybern. C, Appl. Rev., vol. 28, no. 3, pp. 392–403, Aug. 1998.[33] J. Kennedy, R. C. Eberhart, and Y. Shi, Swarm Intelligence. San Francisco, CA: Morgan Kaufmann Publishers, 2001.[34] B. Liu, L. Wang, H. Jin, and D. X. Huang, “Advances in particle swarm optimization algorithm,” Control Instruments Chemical Industry, vol. 32, no. 3, pp. 1–6, 2005.[35] B. Liu, L. Wang, Y. H. Jin, F. Tang, and D. X. Huang, “Improved particle swarm optimization combined with chaos,” Chaos, Solitons Fractals, vol. 25, no. 5, pp. 1261–1271, Sep. 2005.[36] M. F. Tasgetiren, M. Sevkli, Y. C. Liang, and G. Gencyilmaz, “Particle swarm optimization algorithm for permutation flowshop sequencing problem,” in Lecture Notes in Computer Science, vol. 3172, M. Dorigo, M. Birattari, and C. Blum, Eds. New York: Springer-Verlag, 2004, pp. 382–389.[37] J. C. Bean, “Genetic algorithms and random keys for sequencing and optimization,” ORSA J. Comput., vol. 6, no. 2, pp. 154–160, 1994.[38] T. Aldowaisan and A. Allahverdi, “New heuristics for no-wait flowshops to minimize makespan,” Comput. Oper. Res., vol. 30, no. 8, pp. 1219–1231, Jul. 2003.[39] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley, 1989.

[40] S. Kirkpatrick, C. D. Gelat, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983.[41] L. Wang and D. Z. Zheng, “An effective hybrid optimization strategy for job-shop scheduling problems,” Comput. Oper. Res., vol. 28, no. 6, pp. 585–596, May 2001.[42] J. Carlier, “Ordonnancements a contraintes disjonctives,” R.A.I.R.O.Recherche Operationelle/Oper. Res., vol. 12, no. 4, pp. 333–351, 1978.