Este documento está motivado por, pero no limitado a, la tarea de programar trabajos organizados en flujos de trabajo en una rejilla computacional. Debido a la naturaleza dinámica de la computación en rejilla, se requiere replanificación más o menos permanente para que solo haya un tiempo muy limitado disponible para idear un plan revisado. Para cumplir con los requisitos tanto de los usuarios como de los propietarios de recursos, se necesita una optimización multiobjetivo que comprenda y. Este documento resume nuestro trabajo de los últimos seis años en este campo, y reporta nuevos resultados obtenidos mediante la combinación de heurísticas y búsqueda evolutiva en un Algoritmo Memético adaptativo. Mostraremos cómo diferentes heurísticas contribuyen a resolver escenarios de replanificación variables e investigaremos la pregunta de la carga de trabajo máxima manejable para una rejilla de tamaño creciente comenzando con una carga de 200 trabajos y 20 recursos hasta 7000 trabajos y 700 recursos. Además, se estudia el efecto de cuatro buscadores locales diferentes incorporados en la búsqueda evolutiva. También informaremos brevemente sobre enfoques que fallaron dentro del breve marco de tiempo dado para la planificación.