Secuenciación dinámica de sistemas de fabricación flexible mediante aprendizaje automático: análisis de los principales sistemas de secuenciación existentes

Q¨ UESTII´ O,vol. 25, 3, p. 523-549, 2001 SECUENCIACI ´ ON DIN´ AMICA DE SISTEMAS DE FABRICACI ´ ON FLEXIBLE MEDIANTE APRENDIZAJE AUTOM´ ATICO: AN´ ALISIS DE LOS PRINCIPALES SISTEMAS DE SECUENCIACI ´ ON EXISTENTES PAOLO PRIORE  DAVID DE LA FUENTE  JAVIER PUENTE  ALBERTO G ´ OMEZ  Una forma habitual de secuenciar de modo din ´ amico los trabajos en los sistemas de fabricaci´ on es mediante el empleo de reglas de secuenciaci´ on. Sin embargo, el problema que presenta este m´ etodo es que el comportamiento del sistema de fabricaci´ on depender´ a de su estado, y no existe una regla que supere a las dem´ as en todos los posibles estados que puede presentar el sistema de fabricaci´ on. Por lo tanto, ser´ ıa interesante usar en cada momento, la regla m´ as adecuada. Para lograr este objetivo, se pueden utilizar sistemas de secuenciaci´ on que emplean aprendizaje autom´ atico que permiten, analizando el comportamiento previo del sistema de fabricaci´ on (ejemplos de entrenamiento), obtener el conocimiento necesario para determinar la regla de secuenciaci´ on m´ as apropiada en cada instante. En el presente trabajo se realiza una revisi´ on de los principales sistemas de secuenciaci´ on, existentes en la literatura, que utilizan aprendizaje autom´ atico para variar de forma din´ amica la regla de secuenciaci´ on empleada en cada momento. Dynamicscheduling offlexiblemanufacturingsystems throughmachine learning: an analysis of the main scheduling systems Palabras clave: Secuenciaci´on din´amica, aprendizaje autom´atico, sistemas de fabricaci´on flexible, reglas de secuenciaci´on, simulaci´on Clasificaci´ on AMS (MSC 2000): 68T20, 68M20 *Dpto. de Administraci´on de Empresas y Contabilidad. Escuela T´ecnica Superior de Ingenieros Industriales e Inform´aticos de Gij´on. Universidad de Oviedo. –Recibido en diciembre de 1999. –Aceptado en julio de 2001. 523 1. INTRODUCCI ´ ON La secuenciaci´on de trabajos, que forma parte del proceso de control en un sistema de fabricaci´on, es necesaria cuando un conjunto com´un de recursos debe ser compartido, para fabricar una serie de productos duranteel mismo per´ıodode tiempo. El objetivo de la secuenciaci´on es la asignaci´on eficiente de m´aquinas y otros recursos a los trabajos, o a las operaciones contenidas en ´estos, y la determinaci´on del momento en el que cada uno de estos trabajos debe procesarse (Shaw et al., 1992). Los tiempos de procesamiento en los sistemas de fabricaci´on flexible (FMSs1) son casi determin´ısticos puesto que las operaciones son controladaspor ordenadory procesadas, ensumayorparte,por m´aquinasdecontrolnum´erico;asimismo,laspreparacionesentre operacionesconsecutivasest´an automatizadas. Por lo tanto, si no hay perturbacionesen el FMS, se puede predecir el resultado y es suficiente un sistema de secuenciaci´on fijo y«off-line». Sin embargo, debido a la llegada de nuevos trabajos (en ocasiones urgentes), aver´ıas en las m´aquinas y otras perturbaciones, el estado de un FMS puede no ser predecible. Esta naturaleza incierta y din´amica sugiere que un sistema de secuenciaci´on de tipo «off-line»no es el m´as adecuado. Asimismo, los FMSs son m´as sensibles a las perturbaciones que los sistemas de fabricaci´on convencionales puesto que sus componentes est´an m´as sincronizados e integrados y son m´as interdependientes. Por lo tanto, se requiere una respuesta inmediata a los cambios en los estados del FMS, mediante la utilizaci´on de un sistema de secuenciaci´on en tiempo real. Si los estados del FMS cambian de modo din´amico, la secuenciaci´on de trabajos debe hacerse en funci´on del estado actual de ´este (Jeong y Kim, 1998). El resto del art´ıculo est´a organizado de la siguiente forma. En primer lugar, se define el aprendizaje autom´atico y se describen los tipos principales de sistemas de secuenciaci´on de FMSs existentes en la literatura. Posteriormente, para superar el problema que presenta las reglas de secuenciaci´on cuando se emplean de forma est´atica, se definen dos m´etodos para modificar estas reglas de modo din´amico. Uno de ellos est´a basado en la utilizaci´on de un modelo de simulaci´on, mientras que el otro emplea «conocimiento de secuenciaci´on»del sistema de fabricaci´on. A continuaci´on, se realiza una revisi´on de los principales trabajos que utilizan este ´ultimo m´etodo. Finalmente, se especifican una serie de carencias comunesde los sistemas de secuenciaci´on basados en el conocimiento cuya resoluci´on constituye una fuente de futuras l´ıneas de investigaci´on. 1Del ingl´es, Flexible Manufacturing System. 524 2. APRENDIZAJE AUTOM´ ATICO El aprendizaje autom´atico, que pertenece al campo de la inteligencia artificial, permite resolver problemas mediante el empleo del conocimiento obtenido de problemas resueltos en el pasado similares al actual (Michalski et al., 1983). Una representaci´on esquem´atica de lo expuesto anteriormente se muestra en la figura 1. Los tipos principales de algoritmos dentro del aprendizaje autom´atico son las redes neuronales (Bishop, 1995), el aprendizaje inductivo (Quinlan, 1993) y el razonamiento basado en casos (CBR2; Watson, 1997). La diferencia fundamental entre estos tipos de algoritmos radica en la forma en que se almacena el conocimiento. As´ı, en las redes neuronales, el conocimiento se traduce en una serie de pesos y umbrales que poseen las neuronas. En cambio, en el aprendizaje inductivo, el conocimiento se transforma en un ´arbol de decisi´on o un conjunto de reglas. Por ´ultimo, en el CBR, el conocimiento est´a formado por una base de casos compuesta por los problemas resueltos en el pasado. Conocimiento Problemas resueltos en el pasado (ejemplos o casos d e entrenamiento) Algoritmo de aprendizaje automático Nuevo problem a Solución del nuevo problem a Figura 1. Esquema general del problema de aprendizaje. Los casos o problemas resueltos en el pasado (tambi´en denominados ejemplos o casos de entrenamiento)se puedenrepresentarpor tablas atributo-valor,comola quese muestra en la tabla1, dondehay un atributo especialque se denominala clase (lasoluci´on del problema resuelto). Los atributos representan las caracter´ısticas del problema. El objetivo que tiene un algoritmo de aprendizaje autom´atico es tratar de aprender a clasificar nuevos casos, similares a los de entrenamiento, de los que se conocen los valores de todos los atributos excepto la clase. En esta situaci´on, el t´ermino clasificar se utiliza en el sentido m´as literal; es decir, determinar cu´al es la clase de un nuevo caso o ejemplo. 2Del ingl´es, Case-Based Reasoning. 525 Tabla 1. Tabla atributo-valor de los ejemplos de entrenamiento. Ejemplos Atributo 1 Atributo 2  Atributo m Clase Ejemplo 1 A11 A12  A1mC1 Ejemplo 2 A21 A22  A2mC2       Ejemplo n An1An2  Anm Cn 3. SISTEMAS DE SECUENCIACI ´ ON EN LOS FMSs Los sistemas de secuenciaci´on en los FMSs se pueden dividir en las siguientes categor´ıas: 1. Sistemas basados en m´etodos anal´ıticos. 2. Sistemas basados en m´etodos heur´ısticos. 3. Sistemas basados en simulaci´on. 4. Sistemas basados en inteligencia artificial. Los sistemas anal´ıticos formulan el problema de secuenciaci´on de un FMS como un modelo de optimizaci´on con restricciones, en t´erminos de una funci´on objetivo y restricciones expl´ıcitas. Posteriormente, se resuelve el modelo utilizando alguno de los algoritmos de resoluci´on existentes (ver por ejemplo, Han et al., 1989; Hutchison et al., 1989; Kimemia y Gershwin, 1985; Lashkari et al., 1987; Shanker y Rajamarthandan, 1989; Shanker y Tzen, 1985; Stecke, 1983; Wilson, 1989). En general estos problemas son de tipo NP-completo (Garey y Johnson, 1979), por lo que normalmente se proponen algoritmos de tipo heur´ıstico y «off-line»para su resoluci´on (Chen y Yih, 1996; Cho y Wysk, 1993). Asimismo, estos modelos anal´ıticos poseen simplificaciones que no siempre son v´alidas en la pr´actica (de hecho, Basnet y Mize (1994) afirman que algunos modelos son tan singulares que parece que los problemas son ideados para encajar en el modelo y no viceversa) y no son eficientes para problemas de tama˜no razonable. Las dificultades de la aplicaci´on de los sistemas anal´ıticos en los problemas de secuenciaci´on, han propiciado la investigaci´onde m´ultiples heur´ısticas. ´ Estas, suelen tomar la forma de reglas de secuenciaci´on y habitualmente se emplean para secuenciar los trabajos en los sistemas de fabricaci´on de modo din´amico. Estas heur´ısticas ordenan los diversos trabajos que compiten por el uso de una m´aquina dada, mediante diferentes esquemas de prioridad; as´ı, a cada trabajo se le asigna un ´ındice de prioridad y aquel que posea el menor ´ındice se selecciona en primer lugar. 526 Hasta la fecha, muchos investigadores (ver por ejemplo, Baker, 1984; Blackstone et al., 1982; Kim, 1990; Panwalkar y Iskander, 1977; Ramasesh, 1990; Russel et al., 1987; Vepsalainen y Morton, 1987) han evaluado, mediante simulaci´on, el comportamiento de los sistemas de fabricaci´on con diferentes reglas de secuenciaci´on, concluyendoque dicho comportamiento depende de m´ultiples factores como el criterio de eficiencia, la configuraci´on del sistema de fabricaci´on, la carga de trabajo, etc. (Cho y Wysk, 1993). Con la llegada de los FMSs, surgen numerosos estudios que analizan el comportamiento de estos sistemas con las reglas de secuenciaci´on (ver por ejemplo, Choi y Malstrom, 1988; Denzler y Boe, 1987; Egbelu y Tanchoco, 1984; Henneke y Choi, 1990; Montazeri y Van Wassenhove, 1990; Stecke y Solberg, 1981; Tang et al., 1993). Debido al comportamiento variable de los sistemas de fabricaci´on, ser´ıa interesante modificar las reglas de secuenciaci´on din´amicamente, en el momento apropiado, dependiendo de las condiciones del sistema de fabricaci´on. A priori, se espera que este m´etodo sea superior a utilizar una regla de secuenciaci´on de forma constante, por dos razones. En primer lugar, porque es capaz de identificar la mejor regla para un escenario de fabricaci´on determinado. As´ı, debido a esta capacidad de selecci´on, el sistema de fabricaci´on debe comportarse al menos tan bien como con la mejor de las reglas de secuenciaci´on candidatas considerada. En segundo lugar, este m´etodo puede adaptar su selecci´on de forma din´amica a los escenarios cambiantes. Esta adaptabilidad permite secuenciar los trabajos con una eficiencia incluso superior a la de la mejor regla de secuenciaci´on (Shaw et al., 1992). Para modificar de forma din´amica las reglas existen, b´asicamente, dos tipos de sistemas de secuenciaci´on en la literatura. En el primero, la regla se determina, en el momento apropiado, simulando un conjunto de reglas de secuenciaci´on seleccionadas de antemano y eligiendo la mejor (ver por ejemplo, Ishii y Talavage, 1991; Jeong y Kim, 1998; Kim y Kim, 1994; Wu y Wysk, 1989). Los principales inconvenientesque presenta este sistema basado en simulaci´on son los siguientes: 1. El tiempo necesario para realizar las simulaciones con el conjunto de reglas candidatas que puede dificultar la secuenciaci´on en tiempo real. 2. Cambios en el sistema de fabricaci´on muy frecuentes. Dado que la simulaci´on con cada una de las reglas se hace hasta el final del per´ıodo de simulaci´on considerado, puede que no exista coincidencia entre la regla propuestay la realmente necesaria ya que la regla elegida se utiliza durante un per´ıodode tiempo inferioral que se emple´o durante la simulaci´on. 3. No se dispone de mecanismos que eviten modificaciones innecesarias de las reglas de secuenciaci´on ante cambios de tipo transitorio. 4. No se obtiene ning´un tipo de conocimiento acerca del sistema de fabricaci´on. En el segundo tipo de sistema de secuenciaci´on, perteneciente al campo de la inteligencia artificial, se emplea un conjunto de simulaciones previas del sistema de fabricaci´on 527 (ejemplos de entrenamiento) para determinar cu´al es la mejor de las reglas de secuenciaci´on en cada posible estado del sistema de fabricaci´on. Estos casos de entrenamiento se utilizan para entrenar un algoritmode aprendizaje autom´atico, con el objeto de obtener conocimiento acerca del sistema de fabricaci´on. Finalmente, este conocimiento se utiliza para tomar decisiones inteligentes en tiempo real. 4. SISTEMAS DE SECUENCIACI ´ ON BASADOS EN EL CONOCIMIENTO Para que un sistema de secuenciaci´on en tiempo real, que modifique de forma din´amica las reglas de secuenciaci´on, funcione adecuadamente debe cumplir dos caracter´ısticas conflictivas: 1. La selecci´on de reglas debe tener en cuenta una variedad de informaci´on, en tiempo real, acerca del sistema de fabricaci´on. 2. La elecci´on debe realizarse en un corto per´ıodo de tiempo de modo que las operaciones no se retrasen. Una forma de conseguir estas caracter´ısticas es utilizar alguna clase de conocimiento acerca de las relaciones entre el estado del sistema de fabricaci´on y la regla a emplear en ese momento. Por lo tanto, es ´util emplear «conocimiento de secuenciaci´on»del sistema de fabricaci´on para ahorrar tiempo y alcanzar una respuesta r´apida en un entorno que cambia din´amicamente (como es el caso de un FMS). Sin embargo, uno de los problemas m´as dif´ıciles de resolver en un sistema de secuenciaci´on basado en el conocimiento es la adquisici´on de ´este. Para ello, se utilizan algoritmos de aprendizaje autom´atico que reducen el esfuerzo en la determinaci´on del conocimiento necesario para realizar las decisiones de secuenciaci´on. De todas formas, para que este conocimiento sea ´util, es necesario que los ejemplos de entrenamiento y el propio algoritmo de aprendizaje sean los adecuados. Asimismo, para obtener los ejemplos de entrenamiento, son cruciales los atributos seleccionados (Chen y Yih, 1996). Sin embargo, existen, al menos, cuatro razones por las cuales un sistema de secuenciaci´on basado en el conocimiento puede tener un comportamiento inferior a la mejor de las reglas utilizada de forma individual: 1. El conjunto de entrenamiento es un subconjunto del universo de todos los casos posibles. De todos modos, siempre se pueden observar los escenarios en los que el sistema de secuenciaci´on no funcionade forma adecuaday a˜nadirlos como ejemplos de entrenamiento. 2. El comportamiento del sistema de fabricaci´on depende del n´umero y rango de los atributos de control considerados para dise˜nar los ejemplos de entrenamiento. 528 Generador de ejemplos Modelo de simulación Algoritmo de aprendiza je automático E jemplos de entrenamien to y de test FMS C ríti ca E stado del FMS Regla seleccionada C omportamiento d el FMS R efinamiento d el conocimiento C onocimiento d e secuenciación Figura 2. Esquema general de un sistema de secuenciaci´on basado en conocimiento. 3. Una reglapuedeser adecuadaen una simulaci´on duranteun per´ıododetiempolargo, para un conjunto dado de atributos, y no ser apropiada cuando se aplica de modo din´amico. 4. Existen escenarios, o estados del FMS, en los que el sistema de secuenciaci´on no determina la regla adecuada que se debe utilizar. El esquema generalde unsistema de secuenciaci´on basadoen el conocimientose muestra en la figura 2. Las etapas fundamentales de este sistema de secuenciaci´on son las siguientes: 1. Creaci´on de un conjunto de ejemplos de entrenamiento y de test mediante el generador de ejemplos. Para ello, es necesario definir los atributos adecuados que identifiquen el estado del sistema de fabricaci´on. Obviamente, como no es posible tener en cuenta a todos ellos, se deben de elegir los m´as significativos. Los atributos seleccionados se denominan atributos de control siendo los valores utilizados de ´estos, aquellos que se presentan con m´as frecuencia en el sistema de fabricaci´on que se estudia. La clase o soluci´on de cada ejemplo de entrenamiento o de test se obtiene a partir de la regla de secuenciaci´on (o combinaci´on de ellas, si existe m´as de un tipo de decisi´on que se debe tomar) que genere el mejor comportamiento en el sistema de fabricaci´on. Para poder realizar lo anterior, se debe construir un modelo 529 de simulaci´on del sistema de fabricaci´on, y probar para cada conjunto de valores de los atributos de control (ejemplo de entrenamiento o de test) el comportamiento del sistema de fabricaci´on con las diversas reglas de secuenciaci´on que se pretenden utilizar. 2. Determinaci´on del «conocimiento de secuenciaci´on»mediante un algoritmo de aprendizaje autom´atico. 3. Determinaci´on de la regla de secuenciaci´on m´as adecuada (o combinaci´on de ellas, si existe m´as de un tipo de decisi´on), mediante el «conocimiento de secuenciaci´on», dependiendo de los valores que presenten los atributos (estado del sistema de fabricaci´on) en cada momento. 4. Comparaci´on del comportamiento del sistema de fabricaci´on utilizando el «conocimiento de secuenciaci´on»y la mejor reglade secuenciaci´on, o combinaci´onde ellas. Si este segundo m´etodo produce un comportamiento del sistema de fabricaci´on superior, se debe regresar al primer paso para refinar el «conocimiento de secuenciaci´on». A continuaci´on, se analizan diversos sistemas de secuenciaci´on basados en el conocimiento, que modifican de forma din´amica la regla de secuenciaci´on empleada en cada momento. Estos sistemas, seg´un el tipo de algoritmode aprendizajeautom´atico utilizado, se pueden dividir en las siguientes categor´ıas: 1. Sistemas que no utilizan algoritmos de adquisici´on de conocimiento. 2. Sistemas basados en aprendizaje inductivo. 3. Sistemas basados en redes neuronales. 4. Sistemas mixtos. En este caso se utiliza una combinaci´on de distintos tipos de algoritmos de aprendizaje. 4.1. Sistemas de secuenciaci´ on que no utilizan algoritmos de adquisici´ on de conocimiento Thesen y Lei (1986) sugieren un sistema experto para secuenciar robots en un sistema de galvanizado flexible. Los autores realizan un conjunto de simulaciones previas utilizando diversas reglas de secuenciaci´on para estudiar el comportamiento del sistema de fabricaci´on en diversos escenarios, obteniendo, de este modo, 38 ejemplos de entrenamiento. Sin embargo, el conocimiento acerca del sistema de fabricaci´on no se alcanza mediante ning´un procedimiento de adquisici´on autom´atica, sino que se efect´ua de modo manual, inspeccionando directamente los resultados de las simulaciones. Los autores comprueban que el sistema de fabricaci´on aumenta el n´umero de piezas producidas en unos porcentajes que var´ıan entre un 7% y un 30%. 530 Sarin y Salgame (1990) definen un sistema experto para realizar secuenciaci´on de tipo din´amico. El sistema de secuenciaci´on tiene, al comienzo de un per´ıodo de tiempo determinado, una secuencia ordenada de los trabajos que se realizan durante ese per´ıodo y act´ua cuando se produce un cambio. Los cambios se clasifican en diferentes grupos: aver´ıa de una m´aquina, llegada de un trabajo urgente, llegada de un nuevo lote de trabajos, falta de material, absentismo laboral, finalizaci´on de un trabajo en una m´aquina y cambio de turno. El sistema de secuenciaci´on propuesto consta de los siguientes elementos: un «conocimiento de secuenciaci´on», una base de datos global, una interface con el usuario y un bloque de control. El conocimiento est´a dividido en varios grupos, cada uno de los cuales contiene reglas que se encargan de resolver distintos tipos de problemas en funci´on del cambio que ocurra en el sistema de fabricaci´on. Las reglas representan las heur´ısticas de un secuenciador de trabajos humano. La base de datos global contiene informaci´on de los diferentes trabajos y turnos existentes en el momento actual. El grupo de reglas que necesite informaci´on, acude a la base de datos global. Por ´ultimo, el bloque de control,en formade ´arbol(«meta-reglas» o«conocimiento acerca del conocimiento»), elige el grupo de reglas adecuado al nuevo problema que origina el cambio en el sistema de fabricaci´on. Del mismo modo, los autores presentanun sistema de secuenciaci´on integrado que consta de dos m´odulos. El primero, que se apoya en la programaci´on matem´atica, determina una secuencia de trabajos de tipo predictivo como punto inicial de partida. El segundo, el sistema experto, ante cualquier cambio que se produzca, retoma el control para ejecutar una secuenciaci´on din´amica o reactiva en funci´on de la nueva situaci´on. Finalmente, los autores se˜nalan que este sistema de secuenciaci´on integrado a´un no ha sido implementado en un caso real. Chandra y Talavage (1991) presentan un sistema de secuenciaci´on denominado EXPERT, formado por un conjunto de reglas de decisi´on. La informaci´on utilizada en el proceso de decisi´on es el nivel de congesti´on del sistema de fabricaci´on, la preferencia de una pieza por una m´aquina, la criticidad de la pieza (indica la capacidad de la pieza para cumplir sus fechas de entrega) y el objetivo actual del sistema de fabricaci´on. Los autores afirman que, en principio, es interesante el objetivo de maximizar el ritmo de «progreso de trabajo», aunque exista el peligro de que algunos trabajos se retrasen (sobre todo si el sistema es muy utilizado y son muchos los trabajos cr´ıticos). La excesiva preocupaci´on por los trabajos cr´ıticos, puede empeorar todo el sistema; por lo tanto, se elige el objetivodemaximizarel ritmo de «progresode trabajo»comocriterio primario. Por otra parte, los trabajos se dividenen grupos(preferenciaalta, mediana y baja) en lugar de clasificarlos de forma individual. El sistema de secuenciaci´on propuesto elige el trabajo que se asigna a la m´aquina empezando por los de preferencia alta, persiguiendo el objetivo primario y buscando oportunidades para mejorar el secundario (minimizar el n´umero de trabajos retrasados) al mismo tiempo. En determinados casos, se inspeccionan los trabajos disponibles en un futuro cercano. En caso de empate o si no se logra 531 de reglas se determinan, una vez conocida la «clase», las variables de decisi´on que se van a tomar. Sin embargo,nose compara esta metodolog´ıacon ningunaalternativa para comprobar su funcionamiento. Chiu y Yih (1995) sugieren un sistema de secuenciaci´on que utiliza aprendizaje inductivo y algoritmosgen´eticos. ´ Estos ´ultimos se emplean para buscar un conjunto de ejemplos de entrenamientoque posea buena calidad. Para ello, en cada punto de decisi´on, se elige la mejor regla de secuenciaci´on, y ´esta, junto con el estado del sistema de fabricaci´on, forma un caso de entrenamiento. Por otra parte, el algoritmo de aprendizaje puede modificar el ´arbol de decisi´on cuando se presentan nuevos ejemplos, s´olo si el cambio es significativo. Los autores comprueban que el sistema de secuenciaci´on propuesto es superior a utilizar una regla de secuenciaci´on de forma constante. El mayor defecto del sistema de secuenciaci´on presentado es la necesidad de cambiar el «conocimiento de secuenciaci´on»inducido con peque˜nas modificaciones en el sistema de fabricaci´on. Quiroga y Rabelo (1995) resuelven el problema de secuenciaci´on de trabajos en una m´aquina, mediante aprendizaje inductivo (ID3), redes neuronales «backpropagation»y l´ogica «borrosa». Para ello, se utilizan 358casos deentrenamientoy 198de test, siendo el nivel de aciertos superior al 90% en las tres metodolog´ıas. El aprendizaje inductivo ylal´ogica «borrosa»presentan la ventaja de que generan reglas que son inteligibles para el ser humano, cosa que no ocurre con las redes neuronales. Sin embargo, ´estas son las menos sensibles a ruidos o datos incompletos y presentan el mayor porcentaje de aciertos (98.8%). BowdenyBullington(1996)sugierenunsistemadesecuenciaci´ondenominadoGARDS (Genetic Algorithm Rule Discovery System), para determinar estrategias de control utilizando algoritmos gen´eticos. GARDS contiene tres bloques fundamentales: 1. Un modelo de simulaci´on para analizar el comportamiento del sistema de fabricaci´on con las distintas estrategias generadas. 2. Un algoritmo que determina la regla m´as adecuada, dentro de una estrategia o plan, para el estado actual del sistema de fabricaci´on. 3. Un algoritmo gen´etico que intenta, mediante los operadores tradicionales de cruce y mutaci´on, mejorarlos planes iniciales, eligiendoel mejor para el control del sistema de fabricaci´on. El sistema de secuenciaci´on propuesto se prueba en dos configuraciones de distinta complejidad con el objetivo de minimizar el n´umero de trabajos retrasados. Se observa que GARDS mejora el comportamientodel sistema de fabricaci´on con respecto a diversos m´etodos cl´asicos heur´ısticos (por ejemplo, enviar un trabajo a la cola de la m´aquina con menor n´umero de trabajos). Lee et al. (1997) proponenun sistema de secuenciaci´on que tambi´en emplea aprendizaje inductivoy algoritmosgen´eticos. La primerat´ecnica se utiliza, generandoun ´arbol de 538 Tabla 2. Clasificaci´on de las referencias seg´un la metodolog´ıa empleada. Metodolog´ıa Referencias Sistemas basados en m´etodos anal´ıticos Han et al. (1989); Hutchison et al. (1989); Kimemia y Gershwin (1985); Lashkari et al. (1987); Shanker y Rajamarthandan (1989); Shanker y Tzen (1985); Stecke (1983); Wilson (1989). Sistemas basados en m´etodos heur´ısticos Choi y Malstrom (1988); Denzler y Boe (1987); Egbelu y Tanchoco (1984); Henneke y Choi (1990); Montazeri y Van Wassenhove (1990); Stecke y Solberg (1981); Tang et al. (1993) Sistemas basados en simulaci´on Ishii y Talavage (1991); Jeong y Kim (1998); Kim y Kim (1994); Wu yWysk (1989); Sistemas basados en inteligencia artificial Bowden y Bullington (1996); Chandra y Talavage (1991); Chen y Yih (1996); Chiu y Yih (1995); Cho y Wysk (1993); Kim et al. (1998); Lee et al. (1997); Li y She (1994); Min et al. (1998); Nakasuka y Yoshida (1992); Pierreval y Mebarki (1997); Pierreval y Ralambondrainy (1990); Piramuthu et al. (1993); Piramuthu et al. (1994); Quiroga y Rabelo (1995); Rabelo y Alptekin (1989); Sabuncuoglu y Hommertzheim (1992); Sarin y Salgame (1990); Shaw et al. (1992); Sun y Yih (1996); Thesen y Lei (1986); Wu y Wysk (1988) decisi´on medianteC4  5, para seleccionar la regla m´as adecuada que controle el flujo de entrada de trabajos en el sistema de fabricaci´on. Por otra parte, los algoritmos gen´eticos se emplean para seleccionar las reglas de secuenciaci´on m´as apropiadas en cada una de las m´aquinas del sistema de fabricaci´on. Los autores verifican el sistema de secuenciaci´on propuestoen dos sistemas de tipo «job shop»(unode ellos con una m´aquina cuello de botella) utilizando el retraso medio como criterio de comportamiento,y comprueban que supera a la mejor combinaci´on de reglas utilizadas de forma constante, en un porcentaje que var´ıa entre el 20.34%y el 25.28%. Sin embargo,los tiempos requeridos(26 y 168 minutos para el primer y segundo caso, respectivamente) son bastante elevados para que el sistema de secuenciaci´on funcione en tiempo real. Kim et al. (1998) sugieren un sistema de secuenciaci´on, ampliando un trabajo anterior (Min et al., 1998), que emplea redes neuronales «competitivas»y aprendizaje inductivo. Se aplica esta ´ultima t´ecnica, una vez obtenidas las «clases»mediante las redes neuronales, para expresar el conocimiento en forma de ´arbol y reglas de producci´on. Los autores utilizan 99.999 casos de entrenamiento y fijan una red con 100 grupos o «clases». El sistema de secuenciaci´on funciona en tiempo real del mismo modo que el sistema presentado previamentepor los mismos autores (Min et al., 1998). La ´unica diferencia es que la «clase»se identifica mediante las reglas de producci´on obtenidas del programa de aprendizaje inductivoC4  5. Los autores comparan este sistema de secuenciaci´on con otro que solamente utiliza la red neuronal «competitiva», comprobando la 539 Tabla 3. Clasificaci´on de las referencias seg´un el algoritmo de aprendizaje autom´atico empleado. Algoritmo de aprendizaje ´ O autom´atico ´ OReferencias No utiliza Chandra y Talavage (1991); Pierreval y Mebarki (1997); Sabuncuoglu y Hommertzheim (1992); Sarin y Salgame (1990); Thesen y Lei (1986) Aprendizaje inductivo Nakasuka y Yoshida (1992); Pierreval y Ralambondrainy (1990); Piramuthu etal. (1993); Piramuthu et al. (1994); Shawet al. (1992) Redes neuronales Chen y Yih (1996); Min et al. (1998); Sun y Yih (1996) Mixto Bowden y Bullington (1996); Chiu y Yih (1995); Cho y Wysk (1993); Kim et al. (1998); Lee et al. (1997); Li y She (1994); Quiroga y Rabelo (1995); Rabelo y Alptekin (1989); Wu y Wysk (1988) superioridad del primero debido al algoritmo de «podado»de los ´arboles de C4  5 que maneja de forma eficiente el ruido en los datos. Este sistema de secuenciaci´on posee los mismos defectos que el sugerido en Min et al. (1998). A modo de recapitulaci´on, en la tabla 2 se presenta un resumen de las distintas aproximaciones existentes en la literatura, clasificadas seg´un la metodolog´ıa empleada. Por otro lado, en la tabla 3 se muestra una recopilaci´on de los diferentes sistemas de secuenciaci´on existentes que modifican de forma din´amica las reglas de secuenciaci´on, clasificados seg´un el tipo de algoritmo de aprendizaje autom´atico utilizado. 5. LIMITACIONES DE LA LITERATURA EXISTENTE Y L´ INEAS DE INVESTIGACI ´ ON FUTURAS A partir de los sistemas de secuenciaci´on basados en el conocimiento presentados anteriormente, que utilizan algoritmos de aprendizaje autom´atico, se detectan, en general, una serie de carencias o caracter´ısticas deseables comunes. ´ Estas, pueden originar l´ıneas deinvestigaci´onenelcampodelasecuenciaci´ondin´amicade sistemas de fabricaci´on, mediante la modificaci´on de la regla de secuenciaci´on empleada. Estas carencias son las siguientes: 1. Comparaci´on de diversos tipos de algoritmos de aprendizaje autom´atico. En los sistemas de secuenciaci´on presentados en la literatura se utiliza un algoritmo o, en determinados casos, una combinaci´on de ellos. Sin embargo, no existe un estudio comparativoque determine cu´al es el mejor de ellos. Por otra parte, debido a la gran disparidad de los FMSs utilizados en la literatura revisada, no es posible intuir cu´al 540 de los algoritmos presentados es el m´as adecuado para la resoluci´on de este tipo de problemas de secuenciaci´on. 2. Utilizaci´on del CBR en los sistemas de secuenciaci´on. Estos algoritmos poseen una gran eficacia de clasificaci´on, a pesar de su sencillez. Sin embargo, ninguno de los sistemas de secuenciaci´on presentados utiliza CBR; por lo tanto, ser´ıa interesante probar su idoneidad en los problemas de secuenciaci´on. 3. Determinaci´on del n´umero de ejemplos de entrenamiento ´optimo. En ninguno de los sistemas de secuenciaci´on considerados se calcula el n´umero de ejemplos necesario para entrenar el algoritmo de aprendizaje autom´atico de forma ´optima. Por otra parte, tampoco se especifica si los ejemplos de test son iguales, parecidos, o muy distintos de los de entrenamiento. Sin embargo, el error de clasificaci´on del «conocimiento de secuenciaci´on»y, por lo tanto, el comportamiento del sistema de fabricaci´on, depende en gran medida del n´umero de ejemplos de entrenamiento considerado. Por lo tanto, es necesario estudiar el error de clasificaci´on en funci´on del n´umero de ejemplos considerado y elegir un tama˜no adecuado del conjunto de entrenamiento. 4. Selecci´on de un per´ıodo de supervisi´on adecuado. En general, en la literatura existente, no se realiza estudio alguno para determinar el per´ıodo de supervisi´on apropiado para cada criterio de comportamiento. Sin embargo, la frecuencia utilizada para chequear los atributos de control y decidir si se cambian, o no, las reglas de secuenciaci´on, es un tema de vital importancia que determina el comportamiento del sistema de fabricaci´on. 5. Determinaci´on de un mecanismo o filtro que amortig¨ue los estados transitorios. En determinadas ocasiones, el sistema de fabricaci´on alimentado con el «conocimiento de secuenciaci´on»no se comportatal como se esperaba, yes superado porla alternativa de utilizar la mejor combinaci´on de reglas de secuenciaci´on de forma constante. Este fen´omeno se puede explicar por el hecho de que el sistema de secuenciaci´on reacciona de forma precipitada ante cambios en los atributos de control que s´olo son transitorios en el tiempo. Por ello, se propone utilizar filtros de tipo digital que permitan amortiguar estos escenarios transitorios en los atributos de control. En la mayor parte de los trabajos estudiados no se tiene en cuenta este mecanismo y, cuando se considera, no se analizan los diversos tipos de filtros digitales existentes y su relaci´on con el per´ıodo de supervisi´on. 6. Generaci´on de nuevos atributos de control mediante un algoritmo que permita crear atributos que sean combinaci´on de los iniciales. En algunos casos, para seleccionar las reglas de secuenciaci´on m´as adecuadas, es preciso chequear relaciones del tipo: la utilizaci´on de la m´aquina 1 es menor que la de la m´aquina 2. Para poder lograr estas relaciones, ser´ıa necesario definir combinaciones aritm´eticas de los atributos b´asicos iniciales. Sin embargo, a menudo, tales combinaciones no son conocidas de antemano y s´olo se encuentran, en sistemas de fabricaci´on muy sencillos, despu´es de examinar, en detalle, los resultados de simulaci´on. 541 7. Incorporaci´on de un simulador. El comportamiento del sistema de fabricaci´on, podr´ıa mejorar si se incorporase un simulador que determine la mejor regla de entre las que el «conocimiento de secuenciaci´on»considere m´as importantes. En ocasiones, el «conocimiento de secuenciaci´on»determina que ante unos valores dados de los atributos de control existen dos, o m´as, reglas de secuenciaci´on que podr´ıan ser, en principio, adecuadas. En estos casos, en los cuales la decisi´on por parte del «conocimiento de secuenciaci´on»no es clara, la incorporaci´on del simulador ser´ıa bastante ´util. 8. Refinamiento de la base de conocimiento. La base de conocimiento, una vez desarrollada, no es est´atica. Por lo tanto, ser´ıa interesante establecer un procedimiento que modifique el conocimiento autom´aticamente si se producen cambios importantes en el sistema de fabricaci´on. La misi´on principal del m´odulo de refinamiento es descubrir deficiencias en la base de conocimiento y a˜nadir casos de entrenamiento que cubran dichas deficiencias. ´ Estas, se pueden presentar en determinados rangos de valores de los atributos de control. Para solucionar este problema, se requiere «cubrir»estos rangos con nuevos casos de entrenamiento, de forma que el nuevo «conocimiento de secuenciaci´on»obtenido, sea capaz de tratar estas situaciones. 6. CONCLUSIONES En este art´ıculo, se realiza una revisi´on de la literatura existente sobre secuenciaci´on din´amica de FMSs, mediante aprendizaje autom´atico, en la cual se modifica la regla de secuenciaci´on empleada. Al efectuar esta revisi´on, se ha detectado una serie de carencias en los sistemas de secuenciaci´on estudiados. En primer lugar, no se ha encontrado una comparaci´on de los distintos algoritmos de aprendizaje autom´atico existentes para determinar cu´al es el mejor tipo de algoritmo para resolver esta clase de problemas de secuenciaci´on. Asimismo, tampoco se ha utilizado el razonamiento basado en casos como algoritmo de aprendizaje autom´atico, a pesar de su sencillez y gran eficacia de clasificaci´on. Por otro lado, no se ha determinado el n´umero ´optimo de ejemplos de entrenamiento necesario para obtener un «conocimiento de secuenciaci´on»con un error de clasificaci´on peque˜no. Del mismo modo,enlos sistemas de secuenciaci´onestudiados,nose ha considerado,en general, la selecci´on de un per´ıodo de supervisi´on ni la utilizaci´on de filtros que amortig¨uen los estados transitorios del sistema de fabricaci´on. De igual forma, tampoco se ha tenido en cuenta, en la mayor parte de los sistemas de secuenciaci´on estudiados, la incorporaci´on de un generador de nuevos atributos de control y de un simulador que apoye al «conocimiento de secuenciaci´on»cuando ´este no pueda determinar la regla de secuenciaci´on que se debe utilizar. Asimismo, no se han encontrado, en general, m´odulos de refinamiento de la base de conocimiento que permitan modificar el 542 «conocimiento de secuenciaci´on»si se producen cambios importantes en el sistema de fabricaci´on. Por ´ultimo, rese˜nar que ser´ıa interesante, como futuro trabajo, dise˜nar un sistema de secuenciaci´on que incorpore las carencias anteriormente se˜naladas y medir el efecto de cada una de ellas en el comportamiento del sistema de fabricaci´on. 7. REFERENCIAS Baker, K. R. (1984). «Sequencing rules and due-date assignments in a job shop».Management Science, 30, 9, 1093-1103. Basnet, C. Mize, J. H. (1994). «Scheduling and control of flexible manufacturing systems: acriticalreview».InternationalJournalComputerIntegratedManufacturing, 7, 6, 340-355. Bishop, C. M. (1995). Neural Networks for Pattern Recognition. Oxford: Oxford University Press. Blackstone, J. H.; Phillips, D. T. & Hogg, G. L. (1982). «A state-of-the-art survey of dispatching rules for manufacturing job shop operations».International Journal of Production Research, 20, 1, 27-45. Bowden, R. & Bullington, S. F. (1996). «Development of manufacturing control strategies using unsupervised machine learning ».IIE Transactions, 28, 319-331. Chandra, J. & Talavage, J. (1991). «Intelligentdispatchingforflexiblemanufacturing». International Journal of Production Research, 29, 11, 2259-2278. Chen, C. C. & Yih, Y. (1996). «Identifying attributes for knowledge-based development in dynamic scheduling environments».International Journal of Production Research, 34, 6, 1739-1755. Chiu, C. (1994). A learning-based methodology for dynamic scheduling in distributed manufacturing systems, PhD thesis. School of Industrial Engineering, Purdue University, West Lafayette, Indiana. Chiu, C. & Yih, Y. (1995). «A learning-based methodology for dynamic scheduling in distributed manufacturingsystems».International Journal of Production Research, 33, 11, 3217-3232. Cho, H. & Wysk, R. A. (1993). «A robust adaptive scheduler for an intelligent workstation controller».International Journal of Production Research, 31, 4, 771-789. Choi, R. H. &Malstrom, E. M. (1988). «Evaluation of traditional work scheduling rules in a flexible manufacturing system with a physical simulator».Journal of Manufacturing Systems, 7, 1, 33-45. Denzler, D. R. &Boe, W. J. (1987). «Experimental investigationof flexible manufacturing system scheduling rules».International Journal of Production Research, 25, 7, 979-994. Egbelu, P. J. & Tanchoco, J. M. A. (1984). «Characterization of automated guided vehicle dispatching rules».International Journal of Production Research, 22, 3, 359374. 543 Evert, B. (1980). Cluster Analysis. New York: Heinemann. Garey, M. & Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York Freeman. Han, M.; Na, Y. K. & Hogg, G. L. (1989). «Real-time tool control and job dispathing in flexible manufacturing systems».International Journal of Production Research, 27, 1257-1267. Henneke, M. J. & Choi, R. H. (1990). «Evaluation of FMS parameters on overall system performance».Computer Industrial Engineering, 18, 1, 105-110. Hooke, R. & Jeeves, T. A. (1961). «Direct search solution of numerical and statistical problems».Journal of the Association of Computer Machines, 8, 212-229. Hutchison, J.; Leong, K.; Snyder, D. & Ward, F. (1989). «Scheduling for random job shop flexible manufacturing systems».Proceedings of the Third ORSA/TIMS Conference on Flexible Manufacturing Systems, 161-166. Ishii, N. & Talavage, J. (1991). «A transient-based real-time scheduling algorithm in FMS».International Journal of Production Research, 29, 12, 2501-2520. Jeong, K.-C. & Kim, Y.-D. (1998). «A real-time scheduling mechanism for a flexible manufacturingsystem: using simulationanddispatchingrules».InternationalJournal of Production Research, 36, 9, 2609-2626. Kim, Y.-D. (1990). «A comparison of dispatching rules for job shops with multiple identical jobs and alternative routings».International Journal of Production Research, 28, 5, 953-962. Kim, M. H. & Kim, Y.-D. (1994). «Simulation-based real-time scheduling in a flexible manufacturing system».Journal of Manufacturing Systems, 13, 2, 85-93. Kim, C.-O.; Min, H.-S. & Yih, Y. (1998). «Integration of inductive learning and neural networks for multi-objective FMS scheduling».International Journal of Production Research, 36, 9, 2497-2509. Kimemia, J. & Gershwin, S. B. (1985). «Flow optimization in flexible manufacturing systems».International Journal of Production Research, 23, 81-96. Kiran, A. & Alptekin, S. (1989). «A tardiness heuristic for scheduling flexible manufacturing systems».15th Conference on Production Research and Technology: Advances in Manufacturing Systems Integrationand Processes (pp. 559-564),University of California at Berkeley, Berkeley, CA. Lashkari, R. S.; Dutta, S. P. & Padhye, A. M. (1987). «A new formulationof operation allocation problem in flexible manufacturingsystems: mathematical modelling and computational experience».International Journal of Production Research, 25, 1267-1283. Lee, C.-Y.; Piramuthu, S. & Tsai, Y.-K. (1997). «Job shopschedulingwithageneticalgorithm and machine learning».International Journal of Production Research, 35, 4, 1171-1191. Li, D.-C. & She, I.-S. (1994). «Using unsupervised learning technologies to induce scheduling knowledge for FMSs».International Journal of Production Research, 32, 9, 2187-2199. 544 Michalski, R. S.; Carbonell, J. G. & Mitchell, T. M. (1983). MachineLearning. An Artificial Intelligence Approach. Palo Alto, CA: Tioga Press. Min, H.-S.; Yih, Y. & Kim, C.-O. (1998). «A competitive neural network approach to multi-objective FMS scheduling».International Journal of Production Research, 36, 7, 1749-1765. Montazeri, M. & Wassenhove, L. N. V. (1990). «Analysis of scheduling rules for an FMS».International Journal of Production Research, 28, 4, 785-802. Nakasuka, S. & Yoshida, T. (1992). «Dynamic scheduling system utilizing machine learning as a knowledge acquisition tool».International Journal of Production Research, 30, 2, 411-431. Panwalkar, S. S. & Iskander, W. (1977). «A survey of scheduling rules».Operations Research, 23, 5, 961-973. Pierreval, H. & Mebarki, N. (1997). «Dynamic selection of dispatching rules for manufacturing system scheduling».International Journal of Production Research, 35, 6, 1575-1591. Pierreval, H. & Ralambondrainy, H. (1990). «A simulation and learning technique for generatingknowledgeaboutmanufacturingsystemsbehaviour».Journalof theOperational Research Society, 41, 6, 461-474. Piramuthu, S.; Raman, N. & Shaw, M. J. (1994). «Learning-based scheduling in a flexible manufacturing flow line».IEEE Transactions on Engineering Management, 41, 2, 172-182. Piramuthu, S.; Raman, N.; Shaw, M. J. & Park, S.(1993). «Integration of simulation modeling and inductive learning in an adaptive decision support system».Decision Support Systems, 9, 127-142. Quinlan, J. R. (1986). «Induction of decision trees».Machine Learning, 1, 1, 81-106. Reprinted in J. W. Shavlik and T. G. Dietterich (eds.), Readings in Machine Learning. San Mateo, CA: Morgan Kaufmann, 1991. Reprinted in B. G. Buchanan and D. Wilkins (eds.), Readings in Knowledge Acquisition and Learning. San Mateo, CA: Morgan Kaufmann, 1992. Quinlan, J. R. (1993). C4.5: Programsfor MachineLearning. San Mateo, CA: Morgan Kaufmann. Quiroga, L. A. & Rabelo, L. C. (1995). «Learning from examples: a review of machine learning, neural networks and fuzzy logic paradigms».Computers & Industrial Engineering, 29, 561-565. Rabelo, L. C. & Alptekin, S. (1989). «Integrating scheduling and control functions in computer integrated manufacturing using artificial intelligence».Computers & Industrial Engineering, 17, 101-106. Ramasesh, R. (1990). «Dynamic job shop scheduling: a survey of simulation studies». OMEGA: The International Journal of Management Science, 18, 1, 43-57. Russel, R. S.; Dar-El, E. M. & Taylor, B. W. (1987). «A comparative analysis of the COVERT job sequencing rule using various shop performance measures».International Journal of Production Research, 25, 10, 1523-1540. 545 Sabuncuoglu, I. & Hommertzheim, D. L. (1992). «Dynamic dispatching algorithm for scheduling machines and automated guided vehicles in a flexible manufacturing system».International Journal of Production Research, 30, 5, 1059-1079. Sarin, S. C. & Salgame, R. R. (1990). «Developmentof a knowledge-basedsystem for dynamic scheduling».International Journal of Production Research, 28, 8, 14991512. Shanker, K. & Rajamarthandan, S. (1989). «Loading problem in FMS: part movement minimization».Proceedings of the Third ORSA/TIMS Conference on Flexible Manufacturing Systems, 99-104. Shanker, K. & Tzen, Y. J. (1985). «A loadingand dispatchingproblem in a randomflexible manufacturing system».International Journal of Production Research, 23, 579-595. Shaw, M. J.; Park, S. & Raman, N. (1992). «Intelligent scheduling with machine learning capabilities: the induction of scheduling knowledge».IIE Transactions, 24, 2, 156-168. Stecke, K. E. (1983). «Formulation and solution of nonlinear integer production planning problems for flexible manufacturing systems».Management Science, 29, 3, March, 273-288. Stecke, K. E. & Solberg, J. (1981). «Loading and control policies for a flexible manufacturing system».International Journal of Production Research, 19, 5, 481-490. Sun, Y.-L. & Yih, Y. (1996). «An intelligent controller for manufacturing cells».International Journal of Production Research, 34, 8, 2353-2373. Tang, L.-L.; Yih, Y. & Liu, C.-Y. (1993). «A study on decision rules of a scheduling model in an FMS».Computer in Industry, 22, 1-13. Thesen, A. & Lei, L. (1986). «Anexpertsystemforschedulingrobotsinaflexible electroplating system with dynamically changing workloads».Proceedings of the Second ORSA/TIMS Conference on Flexible Manufacturing Systems, (pp. 555-566). Amsterdam: Elsevier Science Publishers. Vepsalainen, A. P. J. & Morton, T. E. (1987). «Priority rules for job shops with weighted tardiness costs».Management Science, 33, 8, 1035-1047. Watson, I. (1997). Applying Case-BasedReasoning: Techniquesfor EnterpriseSystems. San Francisco, CA: Morgan Kaufmann Publishers. Wilson, J. M. (1989). «An alternative formulation of the operation-allocation problem in flexible manufacturing systems».International Journal of Production Research, 27, 1405-1412. Wu, S.-Y. D. & Wysk, R. A. (1988). «Multi-pass expert control system-a control/scheduling structure for flexible manufacturing cells».Journal of Manufacturing Systems, 7, 2, 107-120. Wu, S.-Y. D. & Wysk, R. A. (1989). «Anapplicationofdiscrete-eventsimulationtoonline control and scheduling in flexible manufacturing».International Journal of Production Research, 27, 9, 1603-1623. 546 ENGLISH SUMMARY DYNAMIC SCHEDULING OF FLEXIBLE MANUFACTURING SYSTEMS THROUGH MACHINE LEARNING:AN ANALYSIS OF THE MAIN SCHEDULING SYSTEMS PAOLO PRIORE  DAVID DE LA FUENTE  JAVIER PUENTE  ALBERTO G ´ OMEZ  A common way of dynamically scheduling jobs in a flexible manufacturing system (FMS) is by means of dispatching rules. The drawback of this method is that the performance of the manufacturing system depends on the state the manufacturing system is in at each moment, and no one rule exists that overrules the rest in all the possible states that the manufacturing system may be in. It would therefore be interesting to use the most appropriate dispatching rule at each moment. To achieve this goal, a scheduling system which uses machine learning can be used. By means of this technique, and by analysing the previous performance of the manufacturing system (training examples), knowledge is generated that can be used to decide which is the most appropriate dispatching rule at each moment in time. This paper provides a review of the main scheduling systems that use machine learning to vary the dispatching rule dynamically that have been described in the literature. Keywords: Dynamic Scheduling, Machine Learning, Flexible Manufacturing Systems, Dispatching Rules, Simulation AMS Classification (MSC 2000): *Dpto. de Administraci´on de Empresas y Contabilidad. Escuela T´ecnica Superior de Ingenieros Industriales e Inform´aticos de Gij´on. Universidad de Oviedo. –Received December 1999. –Accepted July 2001. 547