1

ResumenLa creacin de planes temporales de proyectos es una actividad en extremo compleja cuando intervienen cientos de tareas que deben ser dispuestas adecuadamente en una red de proyectos cumpliendo con: 1) las restricciones de secuencialidad, debido a los subproductos requeridos entre las tareas; 2) que la cantidad de recursos utilizados en el emprendimiento de actividades en forma paralela no superen a los disponibles y 3) que el tiempo de ejecucin sea mnimo.

Este trabajo describe una alternativa de solucin que dado un conjunto de tareas encuentre su disposicin adecuada en el tiempo, utilizando algoritmos genticos como herramienta de optimizacin.

En la primera parte del trabajo se discute la problemtica y la importancia de la planificacin de proyectos, los planes temporales y los modelos de red. En la segunda parte se analizan algunos mtodos de optimizacin analticos, exhaustivos y estocsticos. Luego se presenta un modelo de solucin utilizando algoritmos genticos y, por ltimo se plantea una discusin sobre la solucin y se proponen trabajos futuros.

Palabras clavePlanificacin temporal, Modelos de

red, Proyectos, Algoritmos genticos.

I. INTRODUCCIN

os proyectos son esfuerzos temporales emprendidos para crear un producto o servicio nico [2]. Estos han existido desde siempre, as podemos observar que hace

5000 aos atrs, en Egipto ya se emprendan grandes proyectos para la construccin de las pirmides. Hoy, existen emprendimientos como el desarrollo de software, la construccin de aeronaves, buques, represas, etc., [9] que a pesar de las diferencias histricas existentes con el anterior, ambos estn compuestos por cientos e incluso miles de tareas interrelacionadas, siendo an su gestin y direccin actividades difciles de emprender [15]. A su vez, cada vez son ms las organizaciones que orientan sus estructuras al desarrollo de productos o servicios exclusivos, por lo que los proyectos da a da cobran mayor importancia en las actividades de la sociedad.

Un campo en el que los proyectos han cobrado trascendencia es en la Investigacin y Desarrollo (I&D), rea que las empresas han potenciado debido a las nuevas exigencias de innovacin que imponen las sociedades actuales.

El desarrollo de nuevos productos implica creatividad e investigacin, donde la estructura de trabajo ms eficiente para cumplir sus objetivos es la basada en proyectos [9]. As vemos que el emprendimiento de los mismos se transforma en una actividad cotidiana.

En la direccin de proyectos se realizan una gran cantidad de actividades. La mayora son ndole interpersonal (comunicacin), de coordinacin, programacin y planificacin. Un director de proyectos debe estar permanentemente comunicado, ya sea en forma vertical con sus superiores y subordinados; como en forma horizontal, con otros directores, colaboradores, etc.

Otra actividad primordial del director es la planificacin. Todos los emprendimientos deben ser planificados; sin una adecuada planificacin se pierde el rumbo, se diluyen los objetivos y nunca se alcanzan, al menos de forma ptima, las metas planteadas [3].

La planificacin permite controlar la ejecucin del proyecto, facilitando la instauracin de hitos de control, donde son posibles contrastar los resultados esperados con los obtenidos y en caso de discrepancia tomar medidas correctivas antes de que se presenten inconvenientes de mayor envergadura.

La planificacin ha sido y seguir siendo una actividad compleja donde se renen distintas problemticas que necesitan ser resueltas en forma eficiente [2].

En los ltimos aos la cantidad de tcnicas de apoyo a la planificacin han aumentado, pero a su vez en forma casi correlativa a existido un incremento en las dimensiones y complejidades de los proyectos emprendidos en las organizaciones.

La planificacin temporal y los modelos de red

Dentro de la planificacin de proyectos, una actividad que se destaca por su importancia, es la de planificacin temporal, y la distribucin de recursos a cada una de las tareas emprendidas durante el ciclo de vida, teniendo esta actividad, directa relevancia en sus costos y tiempo de culminacin [2][3][9].

Generacin de Planes Temporales de Proyectos Usando Algoritmos Genticos

Carlos Manuel Toledo Instituto Universitario Gastn Dachary

Posadas Misiones Argentina cmtoledo@dachary.edu.ar

L

2

La planificacin temporal es la encargada de elaborar un plan detallado para la ejecucin de todas las tarea, determinando para cada una de estas las fechas de comienzo y fin, y por consiguiente la fecha de culminacin del mismo en su totalidad. Para desempear esta actividad se han creado diferentes herramientas de apoyo, entre las cuales se puede mencionar el mtodo CPM (Critical Path Method) y la tcnica PERT (Program Evaluation and Review Technique), entre otras. [9][12][13] [14]

Estos mtodos son ampliamente utilizados por los encargados de la gestin de proyectos, pero su aplicacin requiere antes la elaboracin del plan de distribucin de las tareas.

Este plan es una red, compuesta por nodos y flechas, donde cada actividad es representada por un nodo o una flecha dependiendo de la notacin utilizada. Las actividades se encuentran enlazadas entre s, con un orden de precedencia que satisface las restricciones impuestas.

Las causas tpicas de estas restricciones son: 1) la inherente secuencialidad que existen entre algunas tareas debido a la necesidad de subproductos elaborados en tareas precedentes. 2) la disponibilidad de recursos necesarios para desempear varias actividades en forma paralela.

Generalmente ambas existen en todos los emprendimientos. La primera de ella es de menor importancia a la hora de armar la red de proyectos. Esto no significa que se tengan que obviar o no incorporarlas, sino que son bien conocidas, o al menos deberan serla, por los especialistas.

En cambio las restricciones inherentes a la disponibilidad de recursos son algo ms complicadas de tratar en forma eficiente, dando este ltimo tipo de restriccin sentido al presente trabajo.

El mayor inconveniente de la planificacin temporal es elaborar planes que cumplan con las restricciones de secuencialidad de las tareas, que no tengan recursos sobreasignados y que adems sean ptimos, es decir que el conjunto de actividades debe ejecutarse en la menor cantidad de tiempo posible, sin importar la cantidad de recursos utilizados, siempre que stos estn dentro de los lmites impuestos por los planificadores.

Otro aspecto que se debe considerar al seleccionar los planes es la homogeneidad del estado de uso de los recursos. Por ejemplo, si se emprende el desarrollo de una aplicacin informtica, se debera dar preferencia al plan que ocupe permanentemente 4 programadores que aquel que en ciertos instantes de tiempo se ocupen diez y en otros instantes necesite nicamente dos.

El objetivo de ste trabajo es plantear una solucin que, dado el conjunto de actividades y restricciones, encuentre una disposicin de actividades ptima, o al menos aceptable dentro de ciertos parmetros fijados.

El trmino aceptable estar condicionado a las exigencias impuestas por las personas encargadas de planificar el proyecto, la cual tendr en cuenta los costos, riesgos, etc. que estn dispuestos a asumir.

II. LA OPTIMIZACIN DE PLANES

Uno de los principales inconvenientes es la generacin de un plan adecuado, compuesto por todas las tareas y sus interrelaciones. Para ello, se necesita una herramienta que encuentre el plan ptimo, o en su defecto un plan aceptable, dentro del espacio de bsqueda compuesto por todos los planes temporales posibles. Existen varias opciones a seguir.

A. Mtodos analticos y exhaustivos

Una solucin clsica radica en plantear una funcin objetivo F, la cual se debe maximizar o minimizar; y un conjunto de funciones, R1, R2, ..., Rn, que representan cada una de las restricciones.

Una vez elaboradas las funciones es posible ocupar un mtodo de optimizacin como el Simplex, la M grande [9][10][12][13][14], los multiplicadores de Lagrange [11], etc. Esta aproximacin tiene el inconveniente de la complejidad, debido a las caractersticas del problema, del planteo de una funcin F a optimizar y un conjunto de funciones R1, R2,..., Rn que se refieran a las restricciones.

Otra alternativa consiste en realizar una bsqueda exhaustiva del conjunto de todos los planes posibles obtenidos al realizar las distintas combinaciones de tareas entre s. En este caso se generan todas las posibles alternativas, combinando todas las tareas. Luego se verifica si cumplen con las restricciones y se eliminan aquellos planes que no cumplan con alguna restriccin. Por ltimo, dentro del conjunto de planes resultantes, se debe encontrar el que se ejecuta en la menor cantidad de tiempo (el ptimo)

El problema de esta aproximacin, es el tamao del espacio de bsqueda. Incluso un proyecto pequeo cuenta con al menos 50 (cincuenta) tareas, si calculamos la cantidades de planes distintos posibles, tenemos 50!= 3.04140932 x1064 planes.

Debido a la gran cantidad de combinaciones posible, hace a esta alternativa prohibitiva en cuanto al tiempo de cmputo y el espacio de almacenamiento necesario para guardar todos los planes generados.

Para ello es necesario ocupar herramientas alternativas que permitan guiar el proceso de bsqueda, acotar el espacio de bsqueda, o bien, no explorarlo en su totalidad.

B. Mtodos heursticos y estocsticos:

Un alternativa se basa en utilizar una heurstica que nos gue durante el proceso de bsqueda del plan ptimo [14]. El inconveniente que plantea esta opcin es la dificultad que

3

presenta el desarrollo de una heurstica eficiente que permita reducir la cantidad de planes a evaluar durante la bsqueda del ptimo.

Otra opcin es utilizar una herramienta similar al mtodo de Montecarlo, generar al azar una gran cantidad de combinaciones y luego elegir entre los planes generados el mejor.

Esta alternativa es eficiente desde el punto de vista computacional, ya que permite generar tantas combinaciones como recursos (equipamiento informtico, tiempo, etc) estamos dispuestos a invertir en la bsqueda.

Si bien, se soluciona el problema sobre la necesidad de cmputo, surge uno ms importante: cmo asegurar que solucin encontrada es la mejor? o bien, cmo saber si la solucin encontrada es lo suficientemente buena?

En mi opinin, el mtodo de Montecarlo contiene excesiva aleatoriedad por lo que no se garantiza la obtencin de un plan aceptable.

Se necesita una alternativa fiable, que permita, al menos empricamente, tener mayor seguridad de que la propuesta que nos brinde sea cuanto menos digna de ejecutarla.

Existe una herramienta de bsqueda basada en la Gentica y la Teora de la Evolucin, denominada Algoritmos Genticos (en adelante AG) [4][6][8][15][20] que nos permite realizar bsquedas eficiente en grandes espacios de soluciones.

Este trabajo pretende encontrar, mediante la utilizacin de AG, planes de proyectos aceptables en cuanto a la duracin total, y cumpliendo todas las restricciones existentes a la hora de la planificacin.

III. ALGORITMOS GENTICOS

A. Introduccin

Los AG se sustentan en los mecanismos de seleccin que utiliza la naturaleza, que de acuerdo a estos, los individuos ms aptos de una poblacin son los que sobreviven a travs del paso del tiempo [21].

Segn Goldberg, un sistema biolgico eficiente desarrolla estrategias exitosas de adaptacin para lograr su supervivencia y propagacin. La Teora de la Evolucin postula que las mejoras en una especie se logran por la evolucin de la misma a lo largo de cientos y miles de generaciones, donde los individuos que sobreviven son los ms aptos y los menos aptos desaparecen [4].

Los AG son algoritmos de bsqueda basados sobre los mecanismos de seleccin natural y gentica natural [4].

La aplicacin de los AG se circunscribe, generalmente, a problemas de optimizacin donde han demostrado ser eficientes y confiables. A pesar de ello, existe numerosos problemas en el que los mismos pueden ser utilizados, siempre y cuando estos presenten ciertas caractersticas:

Problemas que permiten definir una funcin de aptitud, que ser la encargada de decidir cual/es son los individuos que mejor se adaptan a su entorno.

Problemas cuya representacin de los individuos, mediante diferentes estructuras de datos, sea sencilla y eficiente.

Problemas que permitan que sus soluciones puedan codificarse de una forma que resulte relativamente fcil de implementar en un sistema de cmputo. Una ventaja importante que presentan los algoritmos

genticos, con respecto a otras soluciones, es que una vez que se ha definido correctamente la estructura de los individuos y la funcin de aptitud, se puede prescindir del conocimiento dominio del problema, por lo que los principios de las tcnicas aplicadas (mutacin, cruce y seleccin) son los mismos para todo tipo de problemas, convirtindolo en una herramienta verstil y eficiente.

As podemos notar que este conjunto de tcnicas nos pueden brindar soporte a la planificacin de proyectos, debido a que son adecuadas para problemas de optimizacin, especialmente en aquellos en que el espacio de bsqueda no se encuentra acotado, o bien, es demasiado amplio para explorarlos en su totalidad.

En resumen, podemos decir que un AG es una herramienta que nos permite realizar bsquedas por medio de la simulacin de la evolucin de los seres vivos en la naturaleza en un sistema de cmputo, utilizando operadores de mutacin, cruce y seleccin.

B. Terminologa

Cabe aclarar que existe una relacin terminolgica entre los sistemas naturales y artificiales. En un sistema natural los individuos se representan por medio de cromosomas, en cambio, en los AG cada individuo se representa mediante una estructura, la cual contiene a las caractersticas de una posible solucin del problema.

Cuando en un sistema artificial nos referimos a las caractersticas o atributos estamos haciendo referencia a los genes en los cromosomas, los cuales pueden tomar diferentes valores (alelos) y posiciones dentro de cada cromosoma (locus).

C. Operadores utilizados en los algoritmos genticos:

1) Seleccin Elige los individuos ms aptos de una poblacin. Los

individuos seleccionados son los que aportarn sus genes para la prxima generacin. Existen distintas variantes de seleccin. Seleccin por ruleta, por torneo seleccin con control sobre el nmero esperado, seleccin elitista, etc. 2) Cruce (Crossover)

Representa al mecanismo de reproduccin sexual de los sistemas naturales, combinando el material gentico de dos individuos para generar uno nuevo.

4

Es el intercambio gentico entre dos individuos, busca obtener una solucin por medio de dos soluciones parciales.

Toma dos individuos a azar e intercambia parte de su material gentico, formando un nuevo individuo.

El operador de cruza puede generar uno o dos hijos. En algunos casos, por ejemplo en la cruza binomial, uno de ellos es el complemento de su hermano.

Las variantes del cruce son: cruza simple, multipunto y binomial entre las ms conocidas.

3) Mutacin La mutacin en la naturaleza, es poco frecuente, por lo

que en los sistemas artificiales la probabilidad de la misma debera ser pequea; pero existen algunas experiencias prcticas donde la mutacin entre un 25% y 30% ha provocado un aumento en la eficacia del algoritmo. Con valores menores la poblacin se vuelve rpidamente homognea dificultado el arribo a una solucin correcta.

La mutacin nos permite mantener la diversidad de la especie, y su empleo en los algoritmos genticos nos facilita la exploracin de distintas partes del espacio de bsqueda. Por lo tanto, la mutacin permite mantener la variedad en la poblacin de individuos mediante el cambio, al azar, del valor de un gen dentro de un individuo.

Las variantes ms utilizadas de mutacin son: simple y adaptativa por temperatura (ascendente y descendente).

D. Aspectos a considerar en la implementacin de algoritmos genticos

John Holland consider que para que los algoritmos genticos tuviesen xito, al momento de disearse una solucin se deben tener en cuenta los siguientes aspectos: [8] La bsqueda se debe prolongar en el tiempo slo si se

continan realizando avances significativos. Durante la bsqueda se deben explotar posibilidades que

mejoren la aptitud, de lo contrario, se desperdicia una considerable cantidad de esfuerzo.

Siempre se puede estar no explotando posibilidades que contienen la clave para lograr la aptitud ptima.

IV. MODELO GENTICO

A. Estructura de los individuos:

Los AG son altamente flexibles, se pueden aplicar en mltiples situaciones constituyendo una herramienta de bsqueda verstil. La caracterstica que dota a los AG de estas propiedades se debe a que una vez armada la estructura de los individuos y la funcin de aptitud, los mecanismos de seleccin, cruce y mutacin son aplicados de la misma forma o, con modestas modificaciones, a cualquiera problema de bsqueda.

El diseo de los individuos ocupa una de las tareas cruciales a tratar en este trabajo, ya, que de su adecuada eleccin depender la complejidad de las etapas siguientes, e incluso el xito de la solucin.

Antes de comenzar nuestra discusin sobre la estructura de los individuos, debemos definir ciertas convenciones en la notacin. Se define TI(tj) como el instante de tiempo que comienza a ejecutarse la tarea tj, y TC(tj) como el instante de tiempo que culmina la ejecucin de tj. Por ejemplo, una tarea t2 que comienza a ejecutarse en el instante de tiempo 4 y tiene 3 instantes de duracin, se tiene que TI(t2)=4 y TC(t2)=6. Tambin se definen dos conjuntos, T y R, donde T={t1, t2, t3, ..., tn} es el conjunto de todas las actividades que intervienen en el proyecto, y R={titj, tptn,....} el conjunto de todas las restricciones, donde titj implica que ti debe ejecutarse antes de tj. As, s en el conjunto R existe una restriccin titj, necesariamente TC(ti) < TI(tj).

En ste caso particular de la bsqueda, se propone la estructura de los individuos como un arreglo de tamao n, siendo n la cantidad de tareas a planificar, asociando cada tarea a los posiciones (ndices) del arreglo y dnde el contenido del arreglo debe interpretarse por medio de la frase despus de". As, por ejemplo, si la segunda posicin del arreglo contiene el valor 5, se debe interpretar como: la tarea 2 se ejecuta despus de la tarea 5.

Fig. 1. Cromosoma

Generalizando, existen dos situaciones que se pueden

presentar: uno de ellas dada por un conjunto de tareas que se ejecuta en forma secuencial. En este caso, cada una de las tareas involucradas en la secuencia contiene en el arreglo el valor de la tarea predecesora indicada por la restriccin de secuencialidad correspondiente. Por ejemplo, dado un conjunto de tareas T={t1, t2, t3}, y un conjunto de restricciones R={t1t2, t2t3}, se tiene

Fig. 2. Actividades secuenciales. La actividad 3 se ejecuta

despus de la actividad 2 y la actividad 2 se ejecuta luego de la actividad 1

En este caso particular el arreglo contendr en la posicin

1 el valor 0, lo que significa que la tarea 1 se ejecutar al comienzo del proyecto y no es precedida por ninguna otra tarea; la posicin 2, contendr el valor 1 y la posicin 3 contendr el valor 2. Con ello se puede observar que se han

5

representado en forma clara y concisa el conjunto de actividades junto a sus restricciones de secuencialidad.

Fig. 3. Individuo que representa la ejecucin secuencial de las actividades 1, 2 y 3, comenzando la ejecucin de la

actividad 1 al inicio del proyecto

Es conveniente usar este tipo de representacin de las restricciones tanto para representar las restricciones de secuencialidad inherente a la naturaleza de las tareas como el desplazamiento de la fecha de ejecucin de tareas para evitar la sobreasignacin de recursos. Por ejemplo, si se tienen dos actividades (tareas) t1, t2 factibles ejecutarlas en forma paralela, pero ocurre que, la actividad t1 necesita 4 unidades del recurso r1, la actividad t2 necesita 5 unidades del recurso r1 y el equipo cuenta nicamente con 6 unidades de ste recurso, reflejamos la distribucin adecuada de los recursos haciendo que t1 y t2 se ejecuten en forma secuencial, t1t2 o bien t2t1, as, en cada instante de tiempo, se tendr a lo sumo 5 unidades del recurso r1 ocupado.

La segunda situacin se presenta cuando existen varias tareas que se pueden ejecutar en forma paralelas. Por ejemplo, se tienen 3 tareas T={t1, t2, t3}, las cuales se pueden ejecutar en forma simultanea desde el inicio del proyecto, o bien, luego de culminar otra tarea cuya restriccin de secuencialidad prorroga la ejecucin de ste conjunto de tareas T={t1, t2, t3} . Entonces:

Fig. 4. Actividades paralelas. Las actividades 1, 2 y 3, se

ejecutan en forma paralela.

Fig. 5. Individuo que representa la ejecucin paralela de las

actividades 1, 2 y 3 al inicio del proyecto

Si existe una tarea que impida la ejecucin del conjunto T={t1, t2, t3}, se incluye el valor de la tarea precedente en cada una de las posiciones t1, t2, t3 del arreglo en vez del valor 0 que indica el inicio del proyecto.

Esta estructura de individuos permite manejar ambas situaciones y cualquier combinacin vlida de estas.

Por ejemplo, si tenemos un conjunto de actividades T={t1, t2, t3, t3, t4, t5} y un conjunto de restricciones R={t1t2, t1 t3, t1 t4, t3 t5}, dnde la actividad t1 se ejecuta al inicio del proyecto y debe finalizar antes de comenzar la ejecucin de las actividades t2, t3 y t4 (t1, t2 y t3 pueden ejecutarse en forma paralela) y la ejecucin de t5 puede comenzar una vez finalizada t3, se tiene:

Fig. 6. Actividades paralelas y secuenciales.

Fig. 7. Individuo que representa la ejecucin de la

actividad 1, seguida de las actividades 2, 3 y 4 en forma paralela y una vez culminada la actividad 3 comienza la

ejecucin la actividad 5 Otra caracterstica que posee este modelo de cromosoma,

junto con los AG, es la total independencia del dominio del proyecto a planificar. As es posible utilizar esta estructura tanto para planificar el desarrollo de sistemas informticos como la construccin de una aeronave.

B. Funcin aptitud:

Antes de comenzar la discusin sobre la construccin de la funcin aptitud, se debe definir adecuadamente que se propone optimizar. ste problema en particular, como se ha comentado al inicio, radica en: primero, encontrar un plan que tenga el menor tiempo de ejecucin; segundo, que cumpla con todas las restricciones de secuencialidad entre las tareas, impuesta por sus planificadores y tercero, que los recursos de las tareas no se encuentren sobreasignado. Ello indica claramente, que uno de los componentes para la evaluacin de cun apto es un individuo para la supervivencia dentro de una poblacin est dado por el tiempo de ejecucin total del plan. Tambin el cumplimiento de las restricciones y la homogeneidad en el usos de los recursos, son componentes esenciales dentro de la funcin aptitud.

Para el clculo de la duracin de un proyecto se ha expuesto al inicio del trabajo el uso de algunas herramientas

6

como PERT y el mtodo CPM. Ambas brindan una valiosa ayuda a las personas encargadas su planificacin, ya que, adems de calcular el tiempo de culminacin del plan identifican el camino crtico junto con las holguras de cada actividad que compone la red. Se entiende por holgura, a aquella cantidad de tiempo en que pueden atrasarse las actividades en su culminacin, sin modificar el plazo de ejecucin total de proyecto. Se tiene en cuenta que la secuencia de actividades con holguras cero (actividades que no pueden atrasarse sin modificar la fecha de culminacin del proyecto) son las que componen la ruta crtica.

El clculo de las holguras agrega mayor complejidad y por lo tanto mayor tiempo de procesamiento; y su determinacin excede los requisitos necesarios para evaluar la aptitud de los individuos. La rapidez con la que se evalan las aptitudes de los individuos puede ser decisiva para el xito de la solucin. Por consiguiente se ha de elaborar un mecanismo que calcule la aptitud de los individuos sin agregar sobrecargas innecesarias al algoritmo.

El mtodo a utilizar es una modificacin del mtodo CPM, que a diferencia del original, nicamente busca la ruta crtica obviando el clculo de las holguras de las actividades. Para ello se construye un dgrafo que incluya todas las actividades secuenciales y concurrentes. Cada nodo del grafo representa una actividad y el nodo de partida es una tarea ficticia que refleja el inicio del proyecto. Luego se procede a la bsqueda de la secuencia de actividades de mayor duracin dentro del grafo (ruta crtica). Una vez encontrada se establece una correspondencia directa entre la duracin de sta secuencia, con la duracin del proyecto en su totalidad.

Fig 8. Grafo que representa la red de tareas

La segunda caracterstica que debe contemplar la funcin

aptitud es la penalizacin por la violacin de la restricciones de secuencialidad existentes entre las tareas. Una forma sencilla para resolver el inconveniente, es contar la cantidad de violaciones en las restricciones que existen en la solucin planteada. Para ello, se recorre el grafo comenzando desde el inicio de proyecto y calculando el momento en el que comienza a ejecutarse cada actividad.

Para visualizar las situaciones que pueden presentarse, se ocupa una herramienta grfica denominada diagrama de Gantt [11-13] El diagrama de Gantt es una grfica bidimensional, donde en una dimensin representa las tareas y la otra el tiempo de inicio y fin de la ejecucin, y por consiguiente su duracin.

Sean T={tp, tr} el conjunto de actividades y R={tptr} el conjunto de restricciones, pueden surgir 3 escenarios.

1- Que la actividad predecesora culmine luego de haber comenzado la restringida [TI(tp) TI(tr) TC(tp)]. Esto conlleva a superposicin de actividades y con ello una violacin de restriccin.

7

Fig 9. Diagrama de Gantt. La actividad tr comienza su

ejecucin mientras se lleva a cabo la actividad tp.

2- Que la actividad predecesora comience su ejecucin mientras se encuentra ejecutndose la actividad restringida [TI(tr) TI(tp) TC(tr)]

Fig 10. Diagrama de Gantt. La actividad tp comienza su

ejecucin mientras se lleva a cabo la actividad tr.

3- Que la actividad restingida se ejecute antes que la actividad predecesora [TC(tr) < TI(tp)]

Fig 11. Diagrama de Gantt. La actividad tr se ejecuta antes

que comience la actividad tp.

4- Que la actividad restringida comience su ejecucin luego que la actividad predecesora termine [TC(tp) < TI(tr)]

Fig 12. Diagrama de Gantt. Escenario buscado. La actividad

tp se ejecuta antes que comience la actividad tr. Cada vez que se presente una situacin de tipo 1, 2 o 3 se

debe contabilizar una violacin de restriccin. Se debe buscar el escenario 4 en todos los casos que las restricciones

de secuencialidad as lo exijan, caso contrario, se debe identificar la violacin y penalizar el individuo en cuestin.

La tercera caracterstica a tener en cuenta es la homogeneidad en el uso de los recursos. Para ello, se recurre a la estadstica, para valerse de un mtodo de clculo de la dispersin de los datos. Considerando la dispersin como la cantidad de variacin, desperdigamiento o diseminacin en los datos [1].

Un individuo con dispersin pequea hace uso homogneo de los recursos asignados a cada una de sus tareas.

Para conocer el grado de variabilidad se calcula el desvo estndar de la utilizacin de cada uno de los recursos en cada unidad temporal (horas, das, semanas, meses, etc) que planifique el sistema.

Entonces tenemos que la dispersin de los datos es:

Dnde Xi representa cada valor i de utilizacin de

recursos, y X la media. Por ltimo, los problemas de sobreasignacin de recursos.

Para identificar los recursos sobreasignados, verificamos por cada instante de tiempo planificado, las tareas que se ejecutarn, y luego contrastamos la suma de los recursos asignados a cada una de estas con la cantidad de recursos disponibles. En caso que se superen las disponibilidades, se contabiliza como una violacin de sobreasignacin.

Luego de plasmar los diferentes componente de la funcin aptitud se procede a su construccin. Para ello, se pondera cada caractersticas, lo cual permitir, durante la ejecucin, priorizarlas e influir en el proceso de bsqueda y as, obtener una solucin acorde a nuestras necesidades de planificacin, e incluso alterar la velocidad de convergencia del algoritmo. Entonces se tiene que:

Dnde, TEP es el tiempo de ejecucin del plan; REST,

cantidad de violaciones a las restricciones de secuncialidad; HURi, es la homogeneidad en el uso del recurso i, n la cantidad total de recursos, SOBR, la cantidad de sobreasignaciones de recursos y a, b, g y z se corresponden a los pesos asociados al tiempo de ejecucin, el cumplimiento de las restricciones se secuencialidad, el coeficiente de homogeneidad del uso de los recursos y la cantidad de sobreasignaciones, respectivamente.

El problema que presenta la ecuacin anterior es que a menor adaptacin del individuo, mayor valor de aptitud. Para corregir este inconveniente se transforma la ecuacin en:

8

Cmo podemos observar, en nuestra poblacin podrn aparecer individuos (planes) que no cumplen con algunas de las restricciones. Esto se permite debido a varias razones: 1) al partir de una poblacin inicial, cuya generacin es aleatoria, pueden crearse suficiente cantidades de individuos que no cumplan todas las restricciones antes de lograr una poblacin completa para comenzar la simulacin, transformando a la estrategia en un mtodo similar al de Montecarlo. 2) de manera similar ocurre cuando en el transcurso de las generaciones se producen cruzas y mutaciones, pudiendo surgir individuos fallidos, y debido a que se propone un tamao de poblacin fijo, debemos nuevamente recurrir a la generacin aleatoria para completar la bacante. 3) aunque los AG contemplen la pena de muerte, la esencia de la supervivencia de los individuos est dada por el valor de su aptitud y por el mtodo de seleccin utilizado. 4) existen varias razones y experiencias que alientan a conservar el material gentico de individuos subptimos, ya que estos en posteriores generaciones, mediante operaciones de cruza y mutacin, pueden convertirse en buenas soluciones, luego de haber explorado ampliamente el espacio de bsqueda.

C. Operadores:

Se espera la utilizacin de operadores bsicos de AG (cruce, mutacin y seleccin) y algunas variantes avanzadas como ser: variantes de seleccin (por ruleta, por torneo, elitista, etc), de cruce (multipunto y binomial), de mutacin (con temperatura ascendente y descendente).

V. DISCUSIN

A pesar de la validez terica y emprica de los AG [4] estos siguen siendo un mtodo de bsqueda donde la aleatoriedad es su principal componente, y dnde las decisiones tomadas en el diseo del sistema influyen directamente en su eficacia. As existen varias experiencias donde se han tomado decisiones errneas, que al parecer eran insignificantes pero que han llevado al fracaso de la solucin propuesta. Peor an, estas decisiones crticas varan de problema en problema y la nica forma de identificar los parmetros adecuados, es mediante la experiencia emprica con el problema en cuestin y por medio de algunas heursticas generales suscitadas de trabajos anteriores. An existiendo este tipo de inconvenientes, el fundamento de las operaciones ocupadas en los AG (mutacin, cruce y seleccin) no se ven afectadas por el dominio del problema, Los parmetros de funcionamiento (probabilidad porcentaje de cruza, de mutacin, etc.) y otras

consideraciones de ndole general (mtodo de cruce, mutacin y seleccin a utilizar, tamao de la poblacin inicial, poblacin variable o fija, poblacin inicial aleatoria o predeterminada, etc.), brindan la flexibilidad necesaria para probar distintas alternativas de solucin. Estos parmetros y consideraciones son, en la mayora casos, relativamente sencillos de identificar, por lo que una vez desarrollada la solucin se debe someter a una etapa de ajustes y pruebas para identificar los valores que mejor se adecuen a la bsqueda de la solucin propuesta.

Por ello, entre otras razones, se plantean los siguientes interrogantes:

a-Los AG son adecuados para encontrar planes temporales de proyectos?

b-Son eficaces para la planificacin de proyectos? y eficientes?

c-Cmo medir la eficacia del algoritmo? El plan encontrado es ptimo? o al menos, aceptable?

d-Cmo determinar que un plan es lo suficientemente bueno para adoptarlo como solucin?

e-Cul ser la condicin de fin? El algoritmo debe detenerse transcurrida una cierta cantidad de generaciones? o bien o luego que a travs de varias generaciones no se logren cambios significativo? en caso de ser as, Qu es un cambio significativo?

f- Converger a una solucin correcta? Explorar ampliamente el espacio de bsqueda o se concentrar nicamente en una porcin?

Un factor a tener en cuenta, es la complejidad que ha adquirido la funcin aptitud, ya que debido al carcter interactivo del proceso acarrear una sobrecarga importante en el sistema.

VI. TRABAJOS FUTUROS

Se propone como trabajo futuro incluir un amplio marco terico que explique detalladamente las ventajas y desventajas de los distintos mtodos de optimizacin antes expuestos e incluir detalles sobre las teoras y disciplinas que dan fundamento a los AG: teora de la evolucin y la gentica.

Tambin se propone el diseo e implementacin de la solucin y su posterior validacin para as dilucidar los interrogantes antes suscitados.

Se propone la utilizacin de UML [16] como lenguaje de modelado, y el paradigma orientado a objetos junto con una codificacin en C++. La eleccin de UML y el paradigma orientado a objetos radica en sus capacidades grficas y de abstraccin, las cuales permitirn construir un modelo claro y conciso del comportamiento del sistema.

Para la implementacin estima adecuado utilizar las distintas variantes de operadores entre ellos: cruza simple, multipunto, binomial, seleccin elitista, por ruleta y torneo

9

y mutacin por temperatura ascendente. Esta diversidad de operaciones nos permitir probar, durante la etapa de validacin, su eficiencia y eficacia, tanto en forma independiente, como en diferentes combinaciones. Tambin es conveniente la prueba de distintas configuraciones de parmetros, entre ellos: porcentaje de mutaciones, tamao de la poblacin, cantidad de individuos seleccionados en forma elitista, etc.

AGRADECIMIENTOS

Al Ing. Marcelo Karanik, a la Lic. Patricia Vila Torre, y a la Ing. Mara Dekn por sus desinteresadas colaboraciones.

REFERENCIAS

[1] Berenson M.., Levine D. Estadstica para administracin y economa: Conceptos y aplicaciones ISBN 968-422-713-2 Editorial McGraw-Hill Interamericana de Mxico SA de CV Chile 1991.

[2] Proyect Management International PMBOK Gua del Conjunto de Conocimientos de la Administracin de Proyectos www.pmi.org.

[3] Prof. AUS Gustavo Torossi Material de estudio, ctedra Proyectos de Software, Ing. en Informtica, Instituto Universitario Gastn Dachary.

[4] Goldberg, D. E. Genetic Algorithms in Search: Optimization, and Machine Learning ISBN 0-201-15767-5 Addison-Wesley Publishing Company Inc., United State of America 1989.

[5] Coello, C. A. An updated survey of GA-based multiobjective optimization techniques'' ACM Computing Surveys, vol.32.

[6] Coello,C.A.Introduccin a los Algoritmos Genticos [En lnea] Red Cientfica - ISSN: 1597-0223 http://www.redcientifica.com/doc/doc199904260011.html [Consulta: 5 de Febrero del 2005].

[7] Gascn M. http://www.redcientifica.com/doc /doc199904260012.html [En lnea] Red Cientfica ISSN: 1597 0223 [Consulta: 5 de Febrero del 2005].

[8] Holland, J. H. Adaptation in natural and artificial systems - Ann Arbor: The University of Michigan Press 1975.

[9] Solana, R. F. Produccin, su organizacin y administracin en el umbral del tercer milenium, Captulo 17 Editorial Interocenicas Buenos Aires 1994.

[10] Rabuffetti, H. T. Introduccin al Anlisis Matemtico: Clculo 2, Pag 187-192 6ta Edicin Editorial el Ateneo Buenos Aires 2000

[11] Winston W. L. Investigacin de operaciones Captulos 4 y 8 ISBN 970-625-029-8 Grupo Editorial Iberoamerica SA de CV 1994

[12] Taha, H. A. Investigacin de operaciones, 7ma edicin Captulos 1 y 6 ISBN 970 260 4982 Editorial Person Educacin.

[13] Hiller F. S., Lieberman G. J. Investigacin de operaciones, 7ma edicin ISBN 970-10-3486-4 Editorial McGraw-Hill Interamericana Editores SA de CV Mxico 2002.

[14] Winston, P. H Inteligencia artificial, Tercera edicin Editorial Addison Wesley Iberoamericana 1994.

[15] Koontz H., Weihrich H. Administracin: Una perspectiva global - 11 Edicin ISBN 970-103-949-1 Editorial McGraw Hill 2004.

[16] Rumbaugh J., Jacobson I., Booch G. El Lenguaje de Modelado Unificado: Manual de Referencia ISBN 84-7829-037-0 Addison Wesley Longman Inc. Madrid 2000.

[17] Fowler M. UML Gota a gota ISBN 968-444-364-1 Addison Wesley Longman de Mxico, SA de CV Mxico 1999.

[18] De Evolutionibus: Pasado, Presente y Futuro de una Revolucin Cientfica [En lnea] http://www.terra.es/personal/cxc_9747/home.html [Consulta: 17 de Enero de 2006].

[19] Pea Koo, Jimmy Josu Tesis de grado: Desarrollo de un Applet en Java del Micro Algoritmo Gentico Usando Optimizacin Multiobjetivo Universidad Autnoma de Yucatn, Facultad de Matemticas Mrida, Yucatn, Mayo de 2002.

[20] Kury Morales, A; Galaviz Casas, J. Algoritmos Genticos. Centro de Investigacin en Computacin. Mxico 2002.

[21] Darwin Charles El origen de las especies ISBN 847 166 416X Editorial ADAF Edicin 1997.