ES2155678T5 - Asignacion de recursos. - Google Patents

Abstract

Dispositivo para asignación de tareas destinado a asignar recursos a tareas, estando adaptado el dispositivo de asignación de tareas para comunicarse con los terminales asociados a dichos recursos, comprendiendo dicho dispositivo para asignación de tareas:<br /><br />- unos medios de entrada para proporcionar información relativa a las tareas a asignar y los recursos disponibles para llevar a cabo las tareas,<br /><br />- unos medios de generación de planificaciones para asignar los recursos a las tareas, generando de ese modo, para cada recurso, una planificación inicial,<br /><br />- un sistema de almacenamiento para almacenar las planificaciones iniciales y las planificaciones iniciales modificadas, estando almacenadas cada una de dichas planificaciones en forma de una pluralidad de tareas que se debe utilizar para determinar una secuencia de tareas que debe llevar a cabo un recurso,<br /><br />- unos medios de actualización para recibir, desde los medios de entrada, información actualizada relativa a las tareas y recursos, caracterizado porque comprende unos medios de modificación dispuestos para acceder al sistema de almacenamiento para modificar la planificación inicial de por lo menos un primer recurso, en respuesta a dicha información actualizada, y para almacenar dicha planificación inicial modificada en el sistema de almacenamiento, de manera que pueden llevarse a cabo cambios en las planificaciones iniciales, en respuesta a dicha información actualizada, independientemente de los medios de generación de planificaciones.

Description

Asignación de recursos.

La presente invención se refiere a un procedimiento para optimizar la asignación de una pluralidad de recursos a una pluralidad de tareas, y a un dispositivo para llevar a cabo dicho procedimiento. La presente invención es particularmente adecuada para su utilización en situaciones en las que la disponibilidad de recursos, y las tareas a efectuar, cambian dinámicamente. Un ejemplo de una de dichas situaciones es la asignación de tareas a personal de campo como, por ejemplo, conductores de ambulancias o de taxis, personal de asistencia en carretera para vehículos o personal de campo de mantenimiento para un sistema distribuido como, por ejemplo, un sistema de suministro de electricidad o agua o una red de telecomunicaciones.

En dichas situaciones, la carga de trabajo es muy variable y volátil, y las tareas deben ser asignadas en tiempo real, puesto que los tiempos de respuesta necesarios son del orden de la duración de las propias tareas, y mucho más cortos que la jornada laboral de un técnico. Las propias duraciones de las tareas individuales son muy variables y a menudo impredecibles, lo que incide en la disponibilidad de recursos para dichas tareas que están a la espera de ser asignadas.

Un sistema de la técnica anterior, descrito en la solicitud de patente internacional nº WO95/26535, da a conocer un sistema en el que, para cada recurso, se calcula la hora a la que éste estará disponible. A cada tarea se le asigna una función dependiente del tiempo, que de ahora en adelante se denominará "función de coste". Esta función de coste es una medida de las consecuencias de asignar un recurso a la tarea, en un momento dado. Por ejemplo, si no se puede asignar un recurso dentro del plazo indicado y garantizado a un cliente, tal vez deba pagarse una compensación al cliente. Otros de los factores de esta función son el tiempo de desplazamiento para llegar hasta una tarea o regresar de ésta, o para ir de una tarea a otra, y el tiempo de inactividad (en el que se incurre si un recurso no puede llevar a cabo la siguiente tarea asignada, inmediatamente después de que el recurso quede disponible para efectuarla, por ejemplo, antes de obtener acceso a las dependencias, o antes de que una tarea precedente de una secuencia haya sido llevada a cabo). Para cada combinación de tareas con recursos puede determinarse un coste previsto. Este coste es la suma de los valores de las funciones dependientes del tiempo para cada tarea, en el momento en que el recurso que le ha sido asignado queda disponible para llevarla a cabo. A continuación, se determina la combinación que proporciona el menor coste global.

En la patente mencionada anteriormente, se dan a conocer características adicionales que aseguran que no se asignen combinaciones de tareas/recursos incompatibles, y que reducen la complejidad del cálculo decidiendo el orden de prioridad de las tareas y los recursos. La planificación de asignaciones puede mantenerse actualizada ejecutando el programa de forma periódica (por ejemplo, cada cinco minutos) o a petición (por ejemplo, cuando un técnico solicita una nueva tarea o cuando se añade una petición de nueva tarea al sistema).

Este sistema requiere una gran cantidad de potencia de procesado debido a que toda la planificación de asignaciones se construye empezando desde cero cada vez que se ejecuta el programa. Dicha disposición es posible cuando los propios criterios de asignación son relativamente simples, aún cuando puedan estar involucrados muchos elementos individuales (tareas y recursos). El problema resulta más intratable cuando existen relaciones complejas entre las tareas o el personal implicado. Por ejemplo, para algunas tareas tal vez sea necesario que dos o más personas se hallen en lugares diferentes al mismo tiempo, para determinar la integridad de una conexión entre las dos ubicaciones. En otras circunstancias, puede ser necesario llevar a cabo las tareas en una secuencia indicada, y tal vez sea necesario personal diferente para llevarlas a cabo.

Debido a que el sistema de la técnica anterior se ejecuta en tiempo real, el tiempo disponible para ejecutar el programa es limitado y, por este motivo, sólo se puede planificar por adelantado una tarea, o como mucho unas cuantas tareas. Esto puede tener por resultado una planificación que sea subóptima a más largo plazo, en particular, si conlleva tareas que ocuparán una gran proporción del día, o incluso varios días, puesto que la disponibilidad de recursos a más largo plazo no puede ser tenida en cuenta fácilmente en dicho sistema.

Otro de los problemas de este procedimiento en tiempo real es que cuando existe una tarea de alta prioridad y ésta puede ser llevada a cabo por varios técnicos, el procedimiento en tiempo real de la técnica anterior descrito anteriormente planifica dicha tarea como siguiente tarea para un técnico individual concreto. La selección normalmente tendrá en cuenta los técnicos que se hallen más cerca de la situación geográfica de la tarea, y los que se prevea que terminen antes su presente tarea. No obstante, si el técnico seleccionado va retrasado respecto de su tarea actual, comprometiendo la hora señalada para su siguiente tarea, no podrá asignarse dicha tarea a otros técnicos que estén disponibles, a menos que vuelva a ejecutarse todo el procedimiento de planificación. Hasta que esto ocurra, la tarea permanece planificada para el primer técnico.

Un planteamiento alternativo, que se encarga sin problemas de las interrelaciones complejas y las tareas a largo plazo, es la creación de una planificación para un día completo (o más). Esto puede llevarse a cabo de forma muy estricta, asignando a ésta una gran cantidad de tiempo de máquina (por ejemplo, toda la noche). No obstante, el resultado no se puede adaptar con facilidad a las circunstancias cambiantes, debido simplemente, en primer lugar, a la gran cantidad de tiempo de máquina dedicado a prepararlo.

\newpage

G J Garwood y A C Robinson proponen, en el documento "Work Management System" ("Sistema de Gestión de Trabajo") del British Telecommunications Engineering Journal, Vol. 10, octubre de 1991, ejecutar dos sistemas diferentes, uno según cada uno de los dos planteamientos anteriores: un sistema en "tiempo real", para ocuparse de casos relativamente sencillos pero urgentes que son adecuados para la planificación en tiempo real, y un sistema de "creación de planificaciones" para casos más complejos pero menos urgentes, que son más adecuados para un procedimiento de planificación complejo pero mucho más lento. No obstante, esto presenta una serie de inconvenientes. En primer lugar, debe tomarse una decisión inicial en cuanto a qué recursos y qué tareas deben asignarse a cada sistema. Los recursos no pueden ir de acá para allá entre sistemas (por ejemplo, para llevar a cabo una tarea a corto plazo en un sistema e intercalarla entre dos tareas más largas del otro sistema). Puede proporcionarse un enlace entre los dos sistemas, de manera que si una de las planificaciones complejas falla por un motivo imprevisto, los recursos que no puedan llevar a cabo la planificación compleja original y las tareas que no puedan llevarse a cabo en dicha planificación se transfieran al sistema de planificación en tiempo real. No obstante, el sistema de planificación en tiempo real no está configurado para ocuparse fácilmente de dichas tareas. En particular, el planificador en tiempo real está obligado a considerar sólo las tareas cuya hora señalada sea inminente, puesto que la necesidad de responder de forma rápida impide supervisar cualquier otra tarea.

La invención se dirige a un dispositivo para asignación de tareas según la reivindicación 1.

La invención se dirige asimismo a un procedimiento correspondiente según la reivindicación 12.

En esta disposición, existe una cooperación más estrecha entre los dos procedimientos básicos que la prevista en las disposiciones de la técnica anterior. La planificación inicial se crea a partir de tareas que, por algún motivo, son difíciles de asignar. Esta planificación se completa, o modifica, a continuación, utilizando información actualizada.

Preferentemente, las planificaciones iniciales se generan de forma periódica, y las planificaciones iniciales generadas de esta forma se modifican en respuesta a la recepción de datos mientras tiene lugar dicha generación periódica de las planificaciones iniciales. El usuario puede seleccionar esta periodicidad para adecuarla a sus propias necesidades. Si las planificaciones se generan con relativa frecuencia, el usuario puede ejecutar un procedimiento en el que predomine el procedimiento de generación inicial, y de ese modo asegurará que la planificación inicial actual esté actualizada, siendo modificadas sólo unas cuantas planificaciones mediante nuevos datos, entre las ejecuciones del procedimiento de generación. Como alternativa, si las planificaciones se generan con menos frecuencia, predominará el procedimiento de modificación (porque se habrán modificado más planificaciones desde la última ejecución del procedimiento de generación), pero éste proporcionará más tiempo entre actualizaciones para generar una solución más rigurosa.

Además, el usuario puede seleccionar cuánto procesado llevará a cabo cada procedimiento. Cuanto más trabajo efectúe el procedimiento inicial, más rigurosa será la planificación generada. No obstante, esto también requiere más tiempo de procesado, durante el cual la planificación que se está generando va quedando obsoleta ya que van llegando nuevos datos de entrada. El procedimiento de modificación puede suspenderse durante la generación periódica de las planificaciones iniciales, siendo utilizada la información actualizada para modificar las planificaciones iniciales una vez finalizada su generación. Como alternativa, el procedimiento de modificación puede continuar durante la generación de las planificaciones iniciales, siendo las planificaciones modificadas de este modo introducidas como modificaciones para las planificaciones iniciales una vez finalizada su generación.

Si se recibe un elemento de datos de actualización importante, lo que determinaría que las planificaciones existentes, o las que se estén generando en ese momento, fueran redundantes, el procedimiento de generación de planificaciones podría iniciarse en un momento que no fuera el determinado por la periodicidad a la que se ha hecho referencia anteriormente.

En una disposición preferida, la función de generación de planificaciones comprende una primera etapa determinista para planificar tareas seleccionadas, y una segunda etapa de optimización para planificar el resto de tareas, y está caracterizada porque la segunda etapa trata las tareas planificadas por la primera etapa como si fueran fijas. En la forma de realización preferida, la segunda etapa funciona según un procedimiento estocástico.

Preferentemente, se seleccionan grupos de tareas asociadas que conciernen a más de un recurso o que forman una secuencia de tareas, para ser planificadas por la primera etapa determinista.

Esta arquitectura permite llevar a cabo la planificación en varias etapas, siendo tratadas las tareas más cambiantes, pero más fáciles de asignar, de forma diferente a las tareas que son más difíciles de asignar, pero que están menos sujetas a cambios. El sistema está preparado de forma adecuada para generar periódicamente planificaciones optimizadas, efectuando el procedimiento de modificación cambios a corto plazo mientras se lleva a cabo la generación de dichas planificaciones. Esto proporciona al procedimiento de generación de planificaciones más tiempo para generar cada planificación, permitiendo generar a éste una solución más óptima, y/o utilizar más datos (p.ej. con más anticipación) que en caso de que su tiempo de ejecución estuviera limitado, debido a la necesidad de efectuar un seguimiento en tiempo real de los cambios a corto plazo.

La arquitectura descrita es modular, de modo que cada una de las etapas individuales de generación y modificación de planificaciones puede adaptarse o sustituirse independientemente de las otras.

Debe sobrentenderse que los términos "determinista" y "estocástico" de esta memoria pretenden diferenciar los diferentes procedimientos de funcionamiento de las dos etapas. La etapa determinista funciona según las reglas de asignación introducidas en el sistema por la persona que lo utiliza, basándose en la experiencia, para generar una planificación parcial. Esta planificación parcial es una solución óptima determinada de forma rigurosa para planificar las tareas seleccionadas a incluir dentro de la misma. La etapa de optimización añade después otras tareas, que son relativamente fáciles de planificar, a la planificación parcial, para generar una planificación completa, pero en general no óptima y, a continuación, busca mejoras a esta solución no óptima, aunque con la limitación de no poder cambiar las partes de la solución generada por la etapa determinista. En la forma de realización descrita, el procedimiento de optimización es un procedimiento de reasociación simulada. Este procedimiento constituye un ejemplo de técnica de búsqueda estocástica, es decir, una técnica de búsqueda que utiliza un procedimiento aleatorio restringido; o sea, un procedimiento con un elemento de aleatoriedad con límites o ponderaciones para concentrar la búsqueda en las áreas con más probabilidades de proporcionar una solución, y evitarla por completo en las áreas que se percibe que tienen menos probabilidades. Estas técnicas son útiles para hallar soluciones casi óptimas cuando el "espacio de soluciones" en el que debe efectuarse la búsqueda tiene características generales conocidas, de modo que el procedimiento puede ser guiado hacia las mejores áreas para efectuar la búsqueda. Pueden utilizarse otras técnicas estocásticas como, por ejemplo, las técnicas de "Escalada", "Búsqueda Tabú" y "Algoritmo Genético", o efectuarse búsquedas sistemáticas exhaustivas, en circunstancias adecuadas, tal como se describirá más adelante. Los medios de generación de planificaciones también pueden comprender una tercera etapa de postoptimización, en la que las planificaciones creadas por la etapa de optimización se analizan para determinar si hay alguna planificación individual que requiera una mayor optimización, y dichas planificaciones se introducen en otra iteración de la etapa de optimización para una mayor optimización, siendo tratadas las planificaciones no determinadas de ese modo como si fueran fijas por la otra iteración de la etapa de optimización.

El procedimiento de modificación de planificaciones puede comprender una pluralidad de etapas de selección, en cada una de las cuales se evalúa la pluralidad de tareas que están a la espera de ser efectuadas, para determinar si hay alguna tarea de una prioridad dada adecuada disponible que pueda ser llevada a cabo por el primer recurso (habitualmente, uno que se haya presentado y solicite una nueva tarea), y dicha tarea se asigna al primer recurso si éste se determina, estando destinadas cada una de las etapas de selección a determinar tareas por orden de prioridad decreciente, de modo que las tareas de alta prioridad se asignan con preferencia sobre las tareas de prioridad más baja, tanto si están como si no están en la planificación inicial optimizada para el recurso. Por lo menos una de las etapas de selección puede determinar en primer lugar si la planificación inicial optimizada del recurso incluye alguna tarea de la prioridad dada que sea realizable, y seleccionar dicha tarea si está presente, o si la planificación inicial optimizada del recurso no contiene dicha tarea, determinar si existe alguna tarea de esa prioridad que no haya sido planificada, y seleccionar dicha tarea si está presente.

En esta memoria, el término "tarea planificada" significa la tarea que en ese momento tiene asignado provisionalmente un recurso. Esta tarea puede ser finalmente asignada a otro recurso al ser revisada la planificación. Como se ha indicado anteriormente, los sistemas de la técnica anterior asignan con antelación las tareas a recursos específicos, excluyendo cualquier otro recurso adecuado que, llegado el momento, queda disponible en primer lugar y le es asignada otra tarea factible. En el sistema de la presente invención, aunque puede planificarse una tarea de alta prioridad para un técnico indicado inicialmente, podrá asignarse dicha tarea a otro técnico de situación y aptitudes adecuadas para llevar a cabo la tarea si la solicita primero, si esto supone un beneficio neto para las planificaciones. La planificación original para el segundo técnico es pues suspendida, y cada una de las tareas de esa planificación quedará excluida de la planificación hasta que sea solicitada por un técnico adecuado. Éste puede ser el primer técnico, si sus aptitudes técnicas y situación geográfica son adecuadas, y si llama antes de que la tarea sea asignada a otro técnico. También podría ser el segundo técnico (es decir, el técnico para el cual fue planificada originalmente la tarea) si, una vez que ha finalizado la primera tarea, todavía tiene tiempo para llevar a cabo la tarea planificada en un principio. No obstante, la tarea suele asignarse a un tercer técnico, cuya propia planificación será interrumpida a su vez.

Para evitar que las interrupciones en las planificaciones proliferen de forma incontrolada, el sistema puede estar preparado para limitar los cambios a un grupo seleccionado de recursos y tareas. Éstos pueden ser los recursos que tengan características relacionadas como, por ejemplo, parecidas situaciones geográficas actuales, y/u hora de finalización estimada de la tarea actual, y/o aptitudes, y/o tipos de tareas que actualmente tienen planificadas. Una modificación en las planificaciones limitadas al área del "espacio de soluciones" (la matriz multidimensional conceptual de recursos, tareas, tiempo, situación, etc.) representada por dichos recursos asegura que cualquier cambio en las planificaciones se propagará de forma relativamente lenta a través del espacio de soluciones, siendo por lo tanto poco probable que ocasione un fracaso total de la planificación. En particular, si no se permite interrumpir determinadas tareas que se han determinado que son difíciles de asignar, se asegurará la existencia de "islas de estabilidad" en el espacio de soluciones, que tenderán a reducir la velocidad a la que dichas interrupciones se propagan por el espacio de soluciones.

Pueden añadirse otras tareas a la pluralidad de tareas que será considerada por el procedimiento de modificación de planificaciones, después de la generación de las planificaciones iniciales, permitiendo de ese modo al sistema asignar tareas urgentes en una escala temporal más corta que la de la generación de las planificaciones iniciales.

Según un tercer aspecto, se proporciona un dispositivo ordenador para asignar una pluralidad de tareas a una pluralidad de recursos, comprendiendo dicho dispositivo ordenador una unidad central de procesado, una memoria, un dispositivo de entrada y un dispositivo de salida, conteniendo dicha memoria un programa para controlar el ordenador y estando destinada a almacenar una planificación inicial, basándose en la disponibilidad prevista de recursos, prioridades de tareas e idoneidad de las tareas para los recursos, y lleva a cabo las siguientes etapas:

cuando un recurso queda disponible, evaluar la pluralidad de tareas en espera de ser efectuadas, para determinar si está disponible alguna tarea de alta prioridad adecuada para ser llevada a cabo por el recurso, y asignarla al recurso;

si no hay ninguna de dichas tareas disponible para ser llevada a cabo por el recurso, evaluar la siguiente tarea de la planificación inicial optimizada del recurso para determinar si puede ser llevada a cabo, y asignarla al recurso en caso de que pueda ser llevada a cabo;

si dicha siguiente tarea no está disponible para ser llevada a cabo por el recurso, asignar al recurso una tarea de prioridad más baja de la pluralidad de tareas.

A continuación, se describirá una forma de realización de la presente invención, sólo a título de ejemplo, en relación con los dibujos adjuntos, en los que:

La Figura 1 muestra una disposición general de un sistema que incluye un ordenador X, configurado para funcionar según la presente invención;

La Figura 2 muestra los componentes del ordenador X de la Figura 1.

La Figura 3 es un diagrama de bloques funcionales de un sistema de generación de planificaciones iniciales para generar una planificación inicial optimizada de forma provisional, asignando recursos a las tareas. Los dos componentes principales son una etapa de "preplanificador" determinista 30 y una etapa de "subsistema de optimización" estocástica 31.

La Figura 4 es un diagrama de bloques funcionales de un subsistema de modificación de planificaciones 40 para asignar recursos a las tareas en tiempo real a medida que los recursos quedan disponibles, utilizando la planificación inicial optimizada generada por el sistema de generación de planificaciones de la Figura 3.

La Figura 5 es un diagrama de flujo que ilustra el funcionamiento del preplanificador 30 de la Figura 3.

Las Figuras 6, 7, 8 y 9 ilustran la variación en el tiempo del coste de asignación de una tarea, para cinco situaciones diferentes.

La Figura 10 es un diagrama de flujo que ilustra el funcionamiento del subsistema de optimización 31 de la Figura 3.

La Figura 11 es una ilustración del procedimiento de reasociación simulada utilizado por el subsistema de optimización 31.

Las Figuras 12, 13 y 14 son diagramas de flujo que ilustran el procedimiento mediante el cual las tareas son asignadas a los técnicos por el sistema de asignación de la Figura 4, basándose en la planificación inicial optimizada generada por el sistema de la Figura 3, y modificaciones en tiempo real a dicha planificación.

Las Figuras 15, 16 y 17 ilustran tres modalidades de funcionamiento del sistema de la presente invención.

En relación con la Figura 1, se muestra un sistema de telecomunicaciones, representado por un bloque N, que es supervisado por un sistema de supervisión de fallos FMC. El sistema de supervisión de fallos FMC detecta fallos en la red que requieren atención, y también recibe entradas de un operador humano, p.ej. para planificar el mantenimiento previsto, para generar peticiones de tareas J1, J2, J3, J4, J5, J6, J7 a llevar a cabo por el personal técnico de campo T1, T2, T3. Las peticiones de tareas se introducen en un sistema de asignación de recursos que comprende un aparato que adopta la forma de un ordenador X para asignar recursos a las tareas, que puede comunicarse a través de la red de telecomunicaciones N con los terminales portátiles H1, H2, H3, según las necesidades. Como se representa en la Figura 1, el terminal H1 actualmente está comunicándose con el ordenador X a través de una conexión C. Los terminales portátiles pueden ser del modelo Husky FS/2 fabricado por Husky Computers Ltd de Coventry, Inglaterra, aunque pueden utilizarse otros equipos adecuados.

En una situación real, existirán muchos técnicos (habitualmente, algunos centenares) y tareas. Una mano de obra constituida por cien técnicos suele poder llevar a cabo seiscientas tareas por día. Por consiguiente, en un día típico se añadirán aproximadamente 600 tareas al sistema, y se eliminarán 600 tareas una vez finalizadas. Para todas las nuevas tareas, y una proporción de las terminadas, es necesario efectuar cambios en el programa del día. Por lo tanto, aunque la planificación de cada técnico individual sólo cambia algunas veces al día, en la planificación global, se efectúan dos cambios cada minuto por término medio, durante una jornada laboral de 8 horas. Naturalmente, esta cifra oculta una fluctuación considerable ya que, por ejemplo, al principio de la jornada laboral se producen un gran número de entradas, ya que entonces se detectan y comunican los fallos que se han producido durante toda la noche.

A efectos ilustrativos, el presente ejemplo sólo tiene tres técnicos T1, T2 y T3 que están provistos de los terminales H1, H2 y H3, respectivamente. Actualmente, los técnicos están ocupados con las tareas J1, J2 y J3, y existen otras cuatro tareas J4, J5, J6 y J7 en espera de ser atendidas. Los técnicos T1, T2 y T3 pueden utilizar sus terminales H1, H2 y H3 para indicar la finalización de una tarea y para recibir instrucciones del ordenador X para efectuar la siguiente tarea.

A efectos ilustrativos, los tres técnicos T1, T2 y T3 pueden considerarse que forman parte del personal de campo para llevar a cabo tareas en la red de telecomunicaciones N. No obstante, no es necesario que el sistema a supervisar sea un sistema de telecomunicaciones, pudiendo éste hallarse bastante alejado del sistema de telecomunicaciones a través del cual los terminales se comunican con el ordenador X.

Los componentes básicos del ordenador X se muestran en la Figura 2. Éstos comprenden un teclado 21, una unidad central de procesado (CPU) 22, una unidad de visualización (VDU) 23, una memoria 24 y una puerta de entrada/salida 25. Los datos y programas para controlar el ordenador X están almacenados en memoria 24. La puerta de entrada/salida 25 conecta el ordenador con el sistema de telecomunicaciones que proporciona los enlaces de comunicación entre el ordenador X y los terminales portátiles H1, H2 y H3. El ordenador X también puede revisar las alarmas de un sistema de supervisión de fallos asociado a la red de telecomunicaciones.

El ordenador X está provisto de un programa principal para asignar los técnicos a las tareas. El programa principal está dividido en un grupo de rutinas. Más adelante, se proporcionan más detalles acerca de las estructuras generales del programa, las rutinas individuales y el procedimiento utilizado por el programa para asignar técnicos a las tareas.

En la Figura 1, el técnico T1 ha finalizado la tarea J1 y entra en contacto con el ordenador X, con ayuda de su terminal H1 y el enlace de comunicación C, para obtener instrucciones para su siguiente tarea. El problema es determinar cuál de las tareas J4, J5, J6, J7 debe indicarse al técnico T1 que debe efectuar. El procedimiento utilizado por el programa principal del ordenador X tiene en cuenta:

- si el técnico puede llevar a cabo cada tarea individual;

- el tiempo que emplearía el técnico para desplazarse hasta la situación de cada tarea;

- el tiempo que emplearía el técnico para llevar a cabo cada tarea;

- la importancia relativa de cada tarea, determinada por ejemplo por el número de clientes afectados y cualquier sanción económica en la que se incurriría si la tarea no se llevara a cabo dentro de un período de tiempo indicado, o si no se llevara a cabo nunca; y

- la disponibilidad de los otros técnicos T2, T3.

La disponibilidad de estos otros técnicos depende de las horas a las que estarán disponibles, que a su vez depende de las duraciones de sus tareas actuales, y las horas a las que los técnicos las empezaron, así como el tiempo de desplazamiento necesario para llegar a la situación de la tarea desde sus situaciones actuales.

El tiempo que llevará la tarea está sujeto a cierta incertidumbre, puesto que en muchos casos las tareas conllevan la investigación y rectificación de un problema detectado. Hasta que el problema no haya sido investigado, el tiempo que llevará su rectificación sólo podrá ser calculado con un margen de error bastante grande. Existen también otros factores variables como, por ejemplo, las circunstancias locales de cada tarea, que dificultan las mediciones precisas. El procedimiento utilizado por el programa del ordenador X calcula inicialmente una planificación provisional para cada técnico, pero permite cambios en estas planificaciones si un técnico comunica la finalización de la tarea antes de lo esperado, o no puede hacerlo a la hora calculada, o si se solicitan nuevas tareas una vez que la planificación provisional ha sido creada.

El procedimiento calcula una "función de coste" dependiente del tiempo para cada tarea. Ésta tiene en cuenta la sanción por incumplimiento del horario acordado. La sanción puede ser un coste monetario real si debe pagarse una compensación a un cliente por incumplimiento de un horario, o un coste "virtual", p.ej., el daño a la reputación de una empresa. La sanción es una propiedad dependiente del tiempo. En el caso más simple, la función es cero si se cumple el horario acordado, y un valor fijo en caso contrario. En casos más complejos, por ejemplo, en los que la compensación a pagar varía según la importancia del retraso, puede ser una función dependiente del tiempo algo más compleja. Planificar una tarea para antes de su hora señalada tiene un valor de contingencia (la reducción del coste proyectado de la tarea ocasionada por la reducción de la probabilidad de incumplimiento); es decir, si el técnico se retrasa en route, o emplea más tiempo del esperado para efectuar la tarea, todavía podrá finalizar la tarea antes de la hora señalada, justificándose, por consiguiente, ese coste más bajo si la tarea no está planificada muy cerca de su hora señalada.

A continuación, para cada asignación posible de un técnico a una tarea, se calcula un "coste técnico/tarea", es decir, el coste de asignar una tarea dada a un técnico dado. Este coste tiene en cuenta el coste del incumplimiento de la tarea (que es el mismo para todos los técnicos) y la probabilidad de que se incumpla la tarea (que varía de un técnico a otro). Esta probabilidad depende de la hora de finalización proyectada de la tarea actual del técnico, la cantidad de tiempo de desplazamiento necesaria para llegar hasta la nueva tarea, la duración estimada de la nueva tarea y la hora señalada antes de la cual debe haberse realizado la tarea. Estos factores determinan un margen, que es la cantidad de tiempo en que pueden sobrepasarse los otros factores sin rebasar la hora señalada o, si es negativo, la cantidad de tiempo en que se rebasa la hora señalada.

Asimismo, pueden tenerse en cuenta otros factores como, por ejemplo, la cantidad de tiempo no productivo necesario para que un técnico concreto lleve a cabo la tarea (p.ej. el tiempo empleado en desplazamientos, o en espera de obtener acceso a la ubicación si se ha concertado una hora de cita del tipo "no antes de" - es decir, si la tarea debe finalizar después de una hora indicada). Debe observarse que estos costes son cálculos aproximados. En ciertas circunstancias, el coste puede hallarse en una escala decreciente, dependiendo de la hora a la que la tarea se lleva a cabo realmente. No obstante, en muchos casos, el coste real de asignar la tarea de hecho sólo puede tomar uno de dos valores, el valor del cumplimiento (coste negativo) o el coste del incumplimiento, pero, en el momento de la asignación se desconoce cuál de estos valores tomará, puesto que circunstancias imprevistas pueden impedir que el técnico llegue a tiempo (o no llegue), o pueden impedir que lleve a cabo la tarea a tiempo, o que no la lleve a cabo, si de hecho logra llegar. Existen otros factores como, por ejemplo, la capacidad del técnico para llevar a cabo la tarea (teniendo en cuenta aptitudes, equipo y permisos de acceso disponibles para cada persona), que también deben tenerse en cuenta. Para estos factores, la probabilidad de que se incumpla la tarea sólo puede tomar los valores cero (si el técnico tiene las aptitudes adecuadas, etc.) o 1 (en caso contrario). También pueden ponerse de manifiesto las preferencias por determinados tipos de trabajo, p.ej. si un técnico particular desea ganar experiencia en una técnica concreta, mediante valores intermedios.

Es necesario reducir a una unidad de medición común estos diversos factores. Resultará beneficioso que todos los factores puedan ser medidos en unidades equivalentes de tiempo de desplazamiento. El coste de permitir que se incumpla una tarea puede calcularse como el equivalente a la cantidad de tiempo de desplazamiento no productivo que sería razonable que un técnico dedicara a impedir que se produjera este incumplimiento. Como alternativa, puede utilizarse un valor financiero equivalente. Por ejemplo, si debe pagarse una compensación económica determinada a un cliente por no cumplir con la hora concertada, puede establecerse que el precio del tiempo no productivo y el precio del tiempo que se está dispuesto a emplear en evitar pagar dicha compensación tengan valores equivalentes.

El procedimiento determina la combinación de técnicos y tareas para la cual el total de los valores de "coste técnico/tarea" es mínimo. También debe considerarse el coste de no asignar una tarea. Esto se lleva a cabo incluyendo un técnico no existente o "ficticio". Si todo permanece igual, pero existen más tareas que recursos para llevarlas a cabo, la tarea de prioridad más baja se planificará para el técnico ficticio. Por ejemplo, como siguiente tarea a llevar a cabo, el técnico T1 puede tener planificada actualmente la tarea J5, el técnico T2 la tarea J7, y el técnico T3 la tarea J6. La tarea J4 podría planificarse como tarea posterior para uno de estos técnicos si queda suficiente tiempo en su planificación después de la hora de finalización proyectada de las tareas que tiene planificadas para llevar a cabo; o en caso contrario, ésta se planifica para el técnico ficticio. Cuando el técnico T1 solicita instrucciones, el ordenador X evalúa la planificación actual y asigna una tarea al técnico T1, proporcionándole instrucciones a través del enlace de comunicaciones C. Normalmente, la tarea asignada será la tarea planificada (en este caso J5), pero si se solicita una nueva tarea (no representada) de prioridad superior a la de la tarea J5, o si el técnico T1 indica que ha finalizado la tarea T1 antes de lo esperado o no puede finalizar la tarea a la hora prevista, podrá asignarse al técnico una tarea distinta, posiblemente una de las tareas J4, J6 y J7, para asegurar que las tareas de prioridad más alta todavía puedan efectuarse a tiempo. A los técnicos T2 y T3 no se les da ninguna instrucción en esta etapa, puesto que todavía no han finalizado sus tareas actuales. La planificación de las tareas J6 y J7 a los técnicos T2 y T3 es provisional, pudiendo ser cambiada, en particular si una de dichas tareas se asigna al técnico T1, o si se introduce una tarea de alta prioridad con poca antelación.

Se conocen diversos algoritmos de análisis de costes para asignar tareas a recursos como, por ejemplo, el denominado "algoritmo húngaro" descrito en un documento de 1955 por H W Kuhn, "The Hungarian Method for the Assignment Problem" ("El método húngaro para el problema de asignación") (Naval Research Logistics Quarterly, vol. 2, páginas 83-97) y perfeccionado por M B Wright, en el documento "Speeding Up the Hungarian Algorithm" ("Cómo agilizar el algoritmo húngaro"), Computer Operations Research, vol. 17, nº 1, páginas 95-96 (1990). No obstante, la utilización de estos algoritmos en situaciones reales no es fácil, en particular, para las tareas interrelacionadas. Además, estos algoritmos no pueden planificar con antelación más de una tarea, y la solución óptima tal vez requiera considerar más tareas que la siguiente inmediata.

El programa para controlar el ordenador X tiene dos elementos principales. El primero de ellos es un sistema de programa de construcción de recorridos fuera de línea ilustrado de forma general en la Figura 3, y el segundo es un sistema de modificación de planificaciones en tiempo real en línea ilustrado de forma general en la Figura 4. Estos dos sistemas se ejecutan independientemente, pero la salida del sistema fuera de línea se utiliza como punto de partida para el funcionamiento del sistema en línea (de tiempo real). Cada sistema suele ser un ordenador, controlado por un programa adecuado. Habitualmente, ambos sistemas se ejecutan a la vez; el sistema de tiempo real 40, controlando la asignación actual de técnicos a tareas, mientras el sistema de generación de planificaciones 30, 31 prepara los datos para la siguiente ejecución del sistema de tiempo real 40. A continuación, se describirá de forma detallada cada uno de los sistemas.

\newpage

La Figura 3 muestra la disposición general del sistema fuera de línea para generar la planificación inicial optimizada. Este sistema funciona utilizando datos estables, para preparar una planificación inicial que el sistema de tiempo real puede utilizar luego como base para su propio funcionamiento a medida que progresa la situación. La planificación inicial de optimización puede prepararse utilizando un procedimiento riguroso, pero comparativamente lento, puesto que no necesita reaccionar a cambios de sus datos. Por ejemplo, la planificación inicial de optimización puede prepararse durante la noche, y quedar preparada para el inicio de la jornada laboral.

El sistema ilustrado en la Figura 3 para la generación de la planificación inicial tiene dos elementos centrales; en concreto, un preplanificador determinista (basado en reglas) 30 y un subsistema de optimización 31. El preplanificador 30 obtiene los datos referentes a los recursos a asignar, y las tareas a las que éstos deben asignarse, de las entradas 33 y 34, respectivamente. Estos datos se someten a cierto preprocesado en las respectivas entradas 33, 34 antes de ser introducidos en el preplanificador 30. El preplanificador 30 tiene información acerca de los técnicos disponibles (entrada 33) e información acerca de las tareas que debe planificar (entrada 34). Asimismo, necesita un archivo de configuración que contiene valores paramétricos.

La función del preplanificador es crear los puntos fijos de la planificación de cada técnico, planificando tantas tareas como sea posible de las que le son proporcionadas para satisfacer las limitaciones impuestas por una memoria de reglas 35. Esto dará por resultado un "recorrido" de tareas para cada técnico. Estos recorridos serán probablemente recorridos parciales, es decir, recorridos con cierto tiempo de inactividad, puesto que las tareas planificadas por el preplanificador 30 son sólo un subconjunto de todas las tareas disponibles. Además, el preplanificador 30 establece la "siguiente hora disponible" (normalmente, la hora a la que el técnico debe empezar a trabajar), las pausas, las ausencias planificadas y el evento "fin de día" (la hora a la que el técnico tiene planificado dejar de trabajar) en los recorridos de cada técnico.

Una vez ha terminado el preplanificador, los resultados obtenidos se pasan al subsistema de optimización 31. El subsistema de optimización 31 recibe una planificación parcial del preplanificador 30 y los datos relativos a los recursos a asignar y las tareas todavía no asignadas por el preplanificador 30, desde las entradas 33 y 34, respectivamente, y genera una planificación inicial optimizada para pasarla a una memoria 32.Tanto el preplanificador 30 como el subsistema de optimización 31 siguen ciertas normas, como se describirá. Las reglas pueden ser seleccionadas o modificadas por las personas que utilizan el sistema a través de las respectivas entradas 35 y 36. Las personas que utilizan el sistema también controlan las entradas a los preprocesadores 33, 34 para actualizar información acerca de los técnicos y las tareas.

Como se describirá, el subsistema de optimización 31 genera una planificación provisional de asignaciones, situando inicialmente otras tareas alrededor y entre los eventos fijos (incluyendo las tareas de difícil planificación) establecidos por el preplanificador, y luego, utilizando un procedimiento estocástico para reasignar estas otras tareas entre los diferentes técnicos hasta que se consigue una planificación óptima.

El funcionamiento del sistema de generación de planificaciones puede mejorarse interrumpiendo periódicamente el funcionamiento de la etapa de optimización 31, y ejecutando una etapa de postoptimización 39. Esta etapa de postoptimización utiliza ciertos criterios basados en reglas para evaluar la planificación creada hasta el momento, determinando las partes que parecen ser próximas a óptimas, añadiendo éstas a la planificación parcial fija generada por la etapa de preplanificación 30, y luego ejecutando de nuevo el subsistema de optimización 31. Esto conduce al subsistema de optimización 31 a concentrarse en la mejora de las partes de la planificación que el postoptimizador 39 determina como menos óptimas. Esta etapa puede repetirse varias veces.

La planificación provisional generada finalmente por el sistema de generación de planificaciones 30, 31 se utiliza a continuación para programar el modificador de tiempo real 40 ilustrado de forma esquemática en la Figura 4, que está programado para asignar tareas a técnicos según la planificación provisional, pero que es capaz de desviarse de la planificación provisional si las circunstancias de tiempo real, que difieren de las previstas en la planificación provisional, lo exigen.

La Figura 4 muestra, en forma de diagrama de bloques, las características principales del modificador en tiempo real 40. El registro de estados de la planificación 42, el registro de estados del técnico 43 y el registro de lista de trabajos 44 proporcionan una entrada a un procesador de asignaciones 47, que a su vez puede actualizarlos. Los registros 42, 43, 44 reciben sus datos iniciales desde la memoria de planificaciones 32 y los preprocesadores 33, 34, respectivamente. La entrada de parámetros 41 permite al operador establecer diversas ponderaciones y otros valores utilizados por el sistema.

El registro de estados del técnico 43 y el registro de lista de trabajos 44 también pueden actualizarse a partir de otras fuentes externas; las interfaces de los técnicos T1, etc. y las interfaces de la red 45, 46, respectivamente.

El procesador de asignaciones 47 utiliza la información de estado actual de los registros para generar una asignación para un técnico cuando se pone en línea para solicitar instrucciones. La asignación resultante se pasa a una unidad de generación de instrucciones 48, que genera instrucciones relativas a la tarea recién asignada, y cualquier actividad asociada, para su transmisión al técnico T.

\newpage

A continuación, se describirán en detalle los procedimientos llevados a cabo por el preplanificador 30, el subsistema de optimización 31 y el modificador en tiempo real 40, en relación con las Figuras 5 a 9 (preplanificador), las Figuras 10 y 11 (subsistema de optimización) y las Figuras 12 a 14 (modificador de tiempo real).

El procedimiento de planificación llevado a cabo por el preplanificador 30 se ilustra en forma de diagrama de flujo en la Figura 5. Antes de asignar las tareas a los técnicos, el preprocesador 34 aplica un determinado preprocesado de los datos, que incluye calcular la primera hora y la última hora de inicio de las tareas. Esta información se utiliza cuando se trata de añadir tareas a los recorridos. El preprocesador de recursos 33 fija en los recorridos la siguiente hora disponible, las pausas, las ausencias y el evento "fin de día" del técnico.

La siguiente hora disponible del técnico abarca no sólo la situación en la que el programa se ejecuta, por ejemplo, durante toda la noche y el técnico todavía no ha empezado su jornada laboral, sino también la situación en la que se solicita al técnico, que ya se encuentra trabajando, que calcule la hora a la que acabará su actividad actual (p.ej. cuando terminará la tarea que le ocupa o cuando regresará al trabajo después de una ausencia autorizada). En el último caso, el preplanificador 30 calculará la siguiente hora disponible del técnico, utilizando información acerca de la duración esperada de la actividad actual, más un cálculo del tiempo de desplazamiento que puede conllevar. En el caso del inicio del día, se supone que todos los técnicos empiezan a trabajar a la hora planificada para presentarse al trabajo.

Los datos de recursos incluyen información necesaria para planificar pausas, por ejemplo, para las comidas. Estas pausas son normalmente de una duración determinada, pero sus horas de inicio (y, por lo tanto, de fin) son flexibles dentro de una ventana especificada para adaptarse a los requisitos del trabajo, y sus situaciones no han sido previamente acordadas. Para cada técnico, se almacena información acerca de la primera hora de inicio de una pausa, la última hora de inicio de ésta y su duración. El preplanificador 30 fijará inicialmente cada pausa en la primera hora de inicio posible.

Los datos de recursos también incluyen información necesaria para planificar ausencias del trabajo. Éstas pueden ser necesarias para llevar a cabo otras tareas no controladas por el planificador como, por ejemplo, sesiones de formación, reuniones de personal, etc., así como ausencias autorizadas no relativas al trabajo como, por ejemplo, citas médicas. Estas ausencias normalmente tienen horas de inicio y fin fijas, y asimismo pueden tener situaciones de inicio y fin especificadas. (Estas ubicaciones pueden ser diferentes si la ausencia implica desplazamiento, por ejemplo, para llevar equipo a reparar, o para recoger provisiones.) Para cada técnico, se almacena información acerca de las horas y situaciones de cualquiera de dichas ausencias planificadas. Debe observarse que debido a que una ausencia puede tener una situación asociada, el desplazamiento con origen y destino en ésta deberá tenerse en cuenta al planificar.

Al preplanificador también se le proporciona información acerca de los datos de fin de día de cada técnico (incluyendo las horas extraordinarias planificadas). El preprocesado situará el punto de fin de día o de "vuelta a casa" de tal modo que el día del técnico finalice a la hora correcta. Llegado este momento, se habrán creado los puntos fijos básicos de la planificación de cada técnico.

En cualquier momento, existirá una pequeña parte del total de tareas disponibles para asignar que serán más difíciles de planificar, y de situar dentro o entre los recorridos, que la mayoría de tareas. Habitualmente, estas tareas estarán sometidas a restricciones más severas que las otras. El preplanificador planifica estas tareas para dejar disponible la máxima cantidad de flexibilidad para las subsiguientes etapas de planificación. Una tarea planificada por el preplanificador no será pasada a otro técnico como parte del procesado de búsqueda llevado a cabo por el subsistema de optimización.

La entrada 33 pasa al preplanificador 30 información acerca de las tareas que cada técnico es capaz de llevar a cabo.

El preprocesador de tareas 34 selecciona el subconjunto de tareas que deben ser planificadas por el preplanificador 30 (es decir, la lista de tareas consideradas difíciles de planificar), y pasa estas tareas al preplanificador 30. Estas tareas incluyen:

a. Tareas que requieren más de una persona en una sola posición.

b. Tareas que requieren más de una persona, pero en diferentes situaciones.

c. Tareas que deben asignarse en su totalidad al mismo técnico en un orden predeterminado.

d. Tareas que tienen una duración superior a un valor predeterminado.

e. Tareas que el usuario ha solicitado que sean asignadas a un técnico específico. Esta categoría puede incluir tareas que han sido planificadas en una ejecución previa del planificador, si el usuario decide que éstas no deben ser pasadas a otro técnico en una posterior ejecución. Por ejemplo, puede ocurrir que el equipo especializado necesario para llevar a cabo una de dichas tareas ya haya sido pasado al técnico.

Cualquier tarea que no haya sido seleccionada para el preprocesado se pasa directamente al subsistema de optimización 31.

El procedimiento determinista llevado a cabo por el preplanificador 30 se muestra en la Figura 5. Las tareas seleccionadas se clasifican primero por orden de prioridad (etapa 51) y luego se planifican en dicho orden. El orden de prioridad puede ser seleccionado por el usuario, utilizando la entrada de reglas 35. El orden de clasificación habitual será:

1. primera hora de inicio de las tareas (las primeras horas, al principio; a las tareas que no tienen hora de inicio planificada o cuya primera hora ya ha pasado se les da la hora actual).

2. puntuación de importancia (en primera lugar, la más alta) - puede determinarse de conformidad con factores como, por ejemplo, el número de clientes afectados, si la tarea es crucial para la seguridad, sanciones económicas, etc.

3. número de técnicos necesarios (en primer lugar, el más elevado).

4. hora de llegada señalada (la primera hora, al principio), es decir, la hora antes de la cual el técnico debe haber empezado la tarea para satisfacer una hora concertada o una garantía de servicio. Ésta puede tener en cuenta la duración calculada de la tarea si existe el compromiso de finalizar la tarea antes de una hora dada (es decir, hora de llegada = hora de finalización - duración de la tarea).

5. duración (en primer lugar, la más larga).

6. número de técnicos capaces de llevar a cabo la tarea (primero el número más pequeño).

Por lo tanto, en un momento dado cualquiera, se dará prioridad a las tareas que puedan llevarse a cabo de inmediato y, dentro de esta categoría, a las tareas que tengan la puntuación de importancia más alta.

Para cada tarea a planificar, la lista de técnicos que puedan llevarla a cabo será almacenada por orden de prioridad (etapa 52). Este orden de prioridad tiene en cuenta factores como

a. si el técnico tiene las aptitudes necesarias para cada tarea,

b. si el técnico tiene alguna autorización de seguridad necesaria para obtener acceso,

c. si la tarea se halla dentro del área de trabajo preferida del técnico,

d. éxito/fracaso (calcula si la tarea, una vez que ha sido asignada al técnico como siguiente tarea de su recorrido después del resto de tareas presentes en ese momento en su recorrido, todavía cumpliría su compromiso principal. Un éxito es una tarea que satisface su compromiso principal; en cambio, un fracaso es una tarea que no lo hace).

e. margen de éxito (medida de la hora de llegada esperada menos la hora de llegada señalada (para horas acordadas que requieren una respuesta antes de un plazo predeterminado), o la hora de finalización calculada menos la hora de finalización señalada (para otras tareas). Reduciendo al mínimo este margen, se asegura que las tareas de prioridad más baja que todavía no han sido asignadas no sean excluidas, debido a que se estén llevando a cabo tareas de prioridad más alta antes de lo necesario.

f. número de aptitudes que posee el técnico (primero, el más bajo, para asegurar que los técnicos más versátiles no se asignen a una tarea que podría haber sido llevada a cabo por un técnico menos versátil).

g. tiempo de desplazamiento (tiempo que podría emplear el técnico en llegar hasta la tarea. Si el técnico ya tiene tareas o actividades en su recorrido, entonces el desplazamiento tendrá lugar desde la última posición hasta la tarea. Si la tarea es la primera del día, entonces el desplazamiento se medirá desde la situación inicial del técnico).

A continuación, el preplanificador 30 intenta planificar las tareas para los técnicos. En primer lugar, trata de añadir la primera tarea al final del recorrido parcial de cada técnico, por turnos (etapa 53), utilizando la lista ordenada de técnicos y empezando por el primero (etapa 54). Si la posición es válida (etapa 55), entonces se planifica la tarea para ese técnico (56). Esta colocación de tareas en el recorrido del técnico tiene en cuenta el tiempo necesario para desplazarse entre las situaciones. Por lo tanto, si el recorrido parcial existente de un técnico termina a la hora T, la asignación de tarea siguiente se intenta a la hora T + t, siendo "t" el tiempo de desplazamiento entre las dos tareas. El valor de t será diferente para cada combinación de técnico y tarea.

Si la tarea no puede añadirse al final del recorrido del primer técnico, el procedimiento se repite para otros técnicos (etapa 57). Si la tarea no puede añadirse al final del recorrido de cualquier técnico, entonces se intenta con la penúltima posición (es decir, la inmediatamente anterior a la última tarea existente en la planificación), de forma alternativa para cada técnico (etapa 58). Nuevamente, si se halla una posición válida, la tarea se planifica. Este procedimiento continúa hasta que se planifica la tarea (etapa 56) o hasta que se haya intentado con todas las posiciones del recorrido de cada uno de los técnicos, sin hallarse ninguna posición válida.

\newpage

Si se produce esta última situación (etapa 59), el preplanificador retrocede en su búsqueda (etapa 510), intentando planificar de nuevo la última tarea añadida a la planificación, suprimiéndola de su posición actual y continuando la búsqueda desde dicho punto hasta que halla otra posición válida, utilizando las mismas reglas que antes. A continuación la búsqueda continúa, retrocediendo cuando es necesario, hasta que se planifica la tarea (etapa 56). Este procedimiento se va repitiendo hasta que todas las tareas están planificadas o hasta que resulta imposible planificar la siguiente tarea (etapa 512) o hasta que se sobrepasa un tiempo de ejecución predeterminado.

Cuando resulta imposible planificar la siguiente tarea, la salida del preplanificador 30 es el recorrido creado hasta ese momento que planifica el mayor número de tareas. Debe observarse que este recorrido no es necesariamente el último en haberse creado, puesto que la búsqueda de retroceso puede haber liberado más recorridos de los que permitía asignar.

Si el tiempo de ejecución es limitado, el planificador puede estar preparado para efectuar un solo intento de planificar cada tarea, utilizando el técnico más preferido para dicha tarea, como se ilustra mediante la línea de puntos (513) en la Figura 5.

En el caso de una tarea que requiere más de una persona (que se trata como un grupo de tareas conectadas para los objetivos de este procedimiento), la planificación de las tareas determina la alineación de sus tiempos de inicio. En algunos casos, esto puede ocasionar que un técnico tenga cierto tiempo inactivo.

El preplanificador utiliza las horas extraordinarias como corresponda dentro de los límites determinados por el límite de horas extraordinarias de cada técnico individual. Estos límites se introducen en el preplanificador en la entrada 33 e incluyen horas extraordinarias planificadas, horario flexible previsto y otras variaciones permitidas de las horas de trabajo. Si la tarea puede ser terminada dentro de las horas extraordinarias permitidas de un técnico, entonces ésta puede ser planificada por el preplanificador. No obstante, si la tarea va a rebasar el límite de horas extraordinarias de un técnico, ésta no se planificará a menos que pueda dividirse, siendo la proporción de la tarea que puede finalizarse antes del fin del día con horas extraordinarias mayor que un valor mínimo predeterminado. En estas circunstancias, se planifica la finalización de la primera parte de la tarea para el fin de día planificado.

El marcador de fin de día para cada técnico, que ha sido colocado por el preprocesador, se cambia de sitio si se ha planificado una tarea que requerirá horas extraordinarias no planificadas. La nueva posición del marcador de fin de día será la de la hora de lo que se produzca en último lugar: la finalización de la tarea que requiere horas extraordinarias no planificadas o bien la comunicación por parte del técnico de que ha terminado de trabajar.

Es posible que las ausencias incluyan los desplazamientos del técnico (p.ej. cuando va a una reunión de personal o regresa de la misma). Dicho desplazamiento se tiene en cuenta cuando se determina la hora de llegada esperada del técnico para una tarea, y su hora esperada de finalización de una tarea.

El preplanificador 30 descrito anteriormente sólo se utiliza para planificar las tareas más difíciles de colocar. Si la función de preplanificación se utilizara para planificar todo el programa de trabajos, el tiempo de ejecución necesario haría que la planificación fuera inutilizable para cuando fuera creada, debido a las nuevas entradas efectuadas en el sistema durante el tiempo de ejecución. No es eficaz dedicar excesivo tiempo de procesado del ordenador a crear una solución perfecta, cuando es probable que dicha solución sea modificada a consecuencia de circunstancias de tiempo real. Para las tareas que son más fáciles de planificar, es muy probable que existan numerosas soluciones aceptables, aunque no óptimas, siendo preferible obtener una solución casi óptima en un tiempo limitado, en vez de crear la solución perfecta en un tiempo muy superior. Se conocen varias técnicas estocásticas dentro de la técnica para generar soluciones casi óptimas a problemas de varias dimensiones como, por ejemplo, el problema indicado aquí. Varias de éstas se describen en el artículo "Stochastic Techniques for Resource Management" ("Técnicas estocásticas para gestión de recursos") de Brind, Muller y Prosser, en BT Technology Journal, volumen 13, nº 1 (enero de 1995). En particular, este artículo describe las técnicas conocidas como "Escalada", "Reasociación simulada", "Búsqueda Tabú" y "Algoritmos Genéticos".

En la técnica de escalada, se selecciona una solución aleatoria al problema, luego se evalúan soluciones "cercanas" que difieren en pequeña medida de la solución original, y finalmente se selecciona el valor situado junto al valor óptimo. Este procedimiento se repite tantas veces como sea necesario. Un problema que plantean las soluciones de la técnica de escalada es que el procedimiento puede quedar "atrapado"en un valor óptimo local del espacio de soluciones.

La técnica de reasociación simulada funciona de forma parecida a la de escalada salvo porque permite a su vez algunos cambios a soluciones menos óptimas. Se ha dispuesto que dicha capacidad disminuya a medida que avanza el procedimiento, de modo que el procedimiento puede librarse de un óptimo local, aunque es menos probable que vuelva a éste.

El procedimiento de búsqueda de tabú compara el valor de un punto de partida seleccionado aleatoriamente, con varias posibles soluciones de las inmediaciones del punto de partida. Entonces, se selecciona el punto con el valor óptimo (que puede ser el punto de partida), y el procedimiento se repite utilizando este punto óptimo como nuevo punto de partida. La disposición determina que una solución que ya ha sido rechazada no pueda ser tenida en consideración en posteriores ciclos. Puesto que el espacio de soluciones locales es sometido a una búsqueda exhaustiva, el sistema busca por necesidad posibles soluciones en otros lugares, hasta hallar finalmente una solución más óptima. Por consiguiente, el procedimiento se librará al fin y al cabo de cualquier mínimo local del espacio de soluciones.

La técnica de algoritmos genéticos prueba combinaciones de las soluciones óptimas halladas hasta ese momento, con el intento de determinar una solución que sea superior a cualquiera de las soluciones "progenitoras" individuales.

También pueden utilizarse técnicas sistemáticas. Estas técnicas exploran cada una de las posibles permutaciones de tareas (aunque los grupos de permutaciones pueden ser eliminados de forma conjunta), para asegurar de ese modo que se hallará la solución óptima. Sin embargo, en un tiempo limitado, las técnicas estocásticas por lo general hallarán una solución casi óptima en un tiempo mucho más corto.

Como se ha descrito en el artículo al que se ha hecho referencia, la elección de qué técnica es la más adecuada para una circunstancia particular depende de la naturaleza del problema. En términos de velocidad de funcionamiento y de resolución en relación con problemas tanto de exceso como de escasez de recursos, la técnica de reasociación simulada es la preferida por la presente forma de realización de la presente invención, aunque debe sobrentenderse que no quedan excluidas del alcance de las reivindicaciones otras técnicas de optimización alternativas.

A continuación, se describirá el subsistema de optimización 31 de la presente forma de realización. Como se representa en la Figura 3, el subsistema de optimización 31 tiene tres entradas. En primer lugar, existe una entrada para un conjunto de recorridos destinados para los técnicos que están disponibles, creados por el preplanificador determinista 30. (En una disposición alternativa, el preplanificador determinista 30 puede ser omitido y los recorridos incluyen sólo puntos fijos establecidos por el preplanificador 33.) Esta entrada puede utilizarse también para los recorridos generados por el postoptimizador 39 en una disposición iterativa. En segundo lugar, existe una entrada para la información de los técnicos disponibles, 37. En tercer lugar, existe una entrada para la información de las tareas no planificadas, 38 (es decir, las no seleccionadas por el preplanificador 34 para ser planificadas por el preplanificador 30).

Antes de empezar el trabajo, el subsistema de optimización 31 somete los datos a cierto preprocesado. Esto incluye calcular la primera y la última hora a la que puede empezar una tarea. Esta información es utilizada por el subsistema de optimización cuando trata de aumentar los recorridos. Además, el preprocesado fija las actividades, las pausas, las ausencias y el evento de fin de día de cada recorrido. El subsistema de optimización requiere diversos valores paramétricos, programados por una entrada 36.

La función del subsistema de optimización 31 es crear un conjunto de recorridos para los técnicos que reduzca al mínimo la función de coste objetivo. Los recorridos definitivos se crean efectuando los cambios de uno en uno en la planificación actual, utilizando una sola operación matemática de modificación. El subsistema de optimización pasa la información de los recorridos creados a una memoria 32, desde donde pueden ser recuperados por el sistema de modificación de tiempo real 40.

Debe observarse que ninguna de las tareas planificadas por el preplanificador 30 puede ser pasada por el subsistema de optimización 31 a otro técnico o al estado no planificado (técnico ficticio). No obstante, el subsistema de optimización 31 podrá cambiar estas tareas de sitio dentro de sus ventanas temporales e insertar tareas antes, entre y después de las mismas. Es posible que el recorrido final creado por el subsistema de optimización tenga tareas, que en un principio fueron incluidas por el preplanificador, en un orden modificado (p.ej. si el preplanificador 30 al ordenar dos tareas coloca la tarea B después de la A, es posible que el subsistema de optimización 31 inserte otras tareas entre éstas, hecho que puede dar por resultado la generación de un nuevo horario para una o ambas de las tareas, siempre que se sigan cumpliendo las diversas restricciones de ambas tareas y que se mantenga el orden de éstas).

A continuación, se proporcionará información detallada acerca de la metodología de "reasociación simulada". Esta metodología presenta cuatro elementos:

- función objetiva

- operador de modificación

- régimen de enfriado; y

- regla de interrupción.

A continuación, se describirá cada uno de estos cuatro elementos, empezando por la función objetiva. Ésta proporciona una valoración objetiva de cuál de las dos soluciones del problema que se está tratando es la mejor, y si un cambio que se está considerando mejora la solución o la empeora. La función se evalúa a través de todas las tareas del sistema, tanto si las tareas están planificadas como si no lo están, y sin tener en cuenta si el preplanificador o el simulador de reasociación incluyeron la tarea en el recorrido. Puede considerarse que la función objetiva está constituida por los siguientes cuatro componentes:

- una sanción por desplazamiento;

- una sanción por horas extraordinarias;

- una sanción por discriminación de aptitud;

- el coste de asignación - es decir, una medida del riesgo y del coste del incumplimiento o un valor de contingencia.

Estos cuatro componentes se aplican a todas las tareas, salvo a las tareas "de relleno" de baja prioridad. Estas tareas de relleno se tratan como un caso especial y, reciben un coste que es proporcional a la cantidad de desplazamiento relacionado sólo.

La sanción por desplazamiento se determina multiplicando el coste por unidad de tiempo y el tiempo de desplazamiento calculado. Por consiguiente, cuánto más largo sea el tiempo de desplazamiento calculado relativo a una asignación, más alto será el coste.

La sanción por horas extraordinarias funciona de idéntica forma: el coste de cada minuto de trabajo extraordinario se multiplica por la cantidad de horas extraordinarias utilizadas. Nuevamente, cuántas más horas extraordinarias se empleen, más alto será el coste de la asignación.

La sanción por discriminación de aptitud añade un coste adicional a la función objetiva si la aptitud necesaria para que el técnico lleve a cabo la tarea no es una aptitud hacia la cual el usuario desea desviar la planificación (suele ser una aptitud fuera de lo común, y por ello, si es posible, los técnicos que la poseen no son asignados preferentemente a las tareas que no la requieren).

El efecto global de estos tres costes es asegurar que el simulador de reasociación trate de reducir al mínimo el desplazamiento, las asignaciones que no reflejan la discriminación de aptitud necesaria y las horas extraordinarias empleadas.

El coste de asignación es una función del tipo de tarea, del coste de importancia de la tarea y de si la situación de la tarea permite su cumplimiento en un plazo límite definido. En general, con este tipo de función, cuánto antes se termina la tarea más se reduce el coste de asignación. La función se calcula, para las tareas en las que existe una hora de llegada señalada, calculando la diferencia entre la hora de llegada esperada y la hora de llegada señalada, y para las tareas en las que existe una hora de finalización señalada, calculando la diferencia entre la hora de finalización esperada y la hora de finalización señalada.

Estos términos se modifican para proporcionar a la función las dos importantes propiedades siguientes. En primer lugar, se define la propiedad "P" como la relación de la diferencia entre la hora esperada de cumplimiento de la hora señalada y la hora señalada y el tiempo máximo en que la hora esperada puede exceder de la hora señalada. Por ejemplo, una tarea para la cual debe concertarse una hora en el período entre 10,30 h y 13 h, en la que la hora de llegada esperada es 11,30 h, tiene un valor de P que es 11,30 h menos 13 h (-90 minutos) divido por 10,30 h menos 13 h(es decir, -150 minutos), o sea, -90/-150 = 0,6, siendo dicho valor igual al de una tarea que debe finalizar antes de las 17 h y que se espera, a las 12 del mediodía, que realmente finalice antes de las 14 h. En ambos casos, se cumple con la hora señalada, habiéndose utilizado el 40% de la ventana disponible (quedando un 60%) y siendo la única diferencia el coste de asignación, que sólo depende del coste de importancia de asignar cada una de las tareas.

En segundo lugar, el coste de retrasar una tarea situada cerca del punto de incumplimiento deberá ser mayor que el coste de adelantar, la misma cantidad de tiempo, una tarea parecida que todavía está muy lejos de la hora de incumplimiento. Por ejemplo, si existen dos tareas con una hora acordada de 17 h, una de las cuales se esperaba que finalizara a las 16,50 h y la otra, a las 12,00 del mediodía, entonces, un desplazamiento que determine que la primera tarea se adelante cinco minutos y que la segunda tarea se retrase cinco minutos reducirá el coste total de planificación. Por lo tanto, los desplazamientos que retrasan una tarea que ya se halla cerca de la hora de incumplimiento sólo mejorarán la función objetiva si el retraso trae consigo algún beneficio mucho mayor.

La única diferencia entre el coste de asignar las diferentes tareas al inicio de sus respectivas ventanas es debida a las diferencias que puedan existir en las puntuaciones de importancia de las tareas. Esto significa que la importancia relativa de las dos tareas, indicadas por las puntuaciones de importancia, no están distorsionadas.

Para reproducir esta segunda propiedad de la función objetiva, se introduce el término (1+P/2) x P en los costes para todas las tareas que cumplen con su hora señalada primaria. Este término significa que el coste de asignación aumenta a medida que la tarea se acerca a su hora señalada primaria; en un principio aumenta un poco por cada minuto de retraso, pero a medida que se aproxima la hora señalada esta velocidad aumenta. Cuando el coste se representa gráficamente frente a la diferencia entre la hora esperada y la hora señalada, se obtiene por resultado una curva como la ilustrada en los ejemplos representados en las Figuras 6 a 9, que se describirán más adelante.

Algunas tareas deben haberse realizado a una hora acordada fija, p.ej. una hora acordada con un cliente. Otras tareas tienen una hora de respuesta señalada. Para las tareas que no tienen una hora acordada, el coste de asignación aumenta todavía más si la tarea ocupa, dentro del recorrido, una posición que determinará el incumplimiento de su hora señalada primaria (es decir, la hora de respuesta garantizada). También puede existir una hora acordada secundaria, más allá de la cual deberán pagarse compensaciones al cliente. Las sanciones de coste fijo están calculadas para asegurar que el número de tareas que incumplen dichas horas señaladas se reduzca al mínimo. Sin estos costes, el coste de asignar dos tareas idénticas sin hora acordada, una de las cuales no cumple por una hora su hora señalada, y la otra lo cumple con dos horas de antelación, será mejor que el de cumplir cada una de las dos tareas con 15 minutos de antelación. Como es obvio, la última situación es preferible en términos comerciales. Con sanciones fijas, es posible ajustar el coste para que la solución comercial deseada sea la que tenga el menor coste.

Para las horas concertadas que quedan por planificar al final del procedimiento de creación de recorridos, el coste de asignación viene determinado por un coste fijo, ponderado por un coste de importancia de asignación. El coste de las tareas sin hora acordada que quedan por planificar se calcula basándose en la hora de finalización supuesta al final del período de planificación y sumando la duración de la tarea. Este coste se calcula para asegurar que el coste de añadir una tarea a una planificación sea siempre inferior al coste de dejarla sin planificar.

El coste de importancia de asignar una tarea se basa en una puntuación de importancia (IMP) modificada por dos parámetros: el multiplicador de puntuación de importancia (IMU) y el índice de puntuación de importancia (IEX). Este coste se calcula efectuando IMU^{IEX} x IMP. Si tanto IMU como IEX se establecen en 1 (o IEX = 0), entonces el coste es simplemente la puntuación de importancia de la tarea. Los valores de IMU e IEX mayores que 1 aumentan el coste diferencial de asignar tareas con una alta puntuación de importancia en comparación con las de baja
puntuación.

En la función objetiva, se calcula el coste de las tareas de relleno, utilizando un coste de cero para cada tarea planificada y un coste de 1 para cada tarea no planificada. Esta regla tiene como objetivo asegurar que siempre será más económico planificar una tarea de relleno en vez de dejarla sin planificar, pero que nunca valdrá la pena retrasar una tarea más importante para poder planificar una tarea de relleno.

La función objetiva utiliza los siguientes parámetros:

- ETT (Tiempo de desplazamiento estimado en minutos: por lo general, el tiempo estimado para que el técnico se desplace de una tarea a la siguiente).

- FTF (Etiqueta de tarea incumplida: = 1 si la tarea no cumple la hora acordada, 0 en caso contrario).

- FSP (Sanción por incumplimiento de hora acordada secundaria).

- SCT (Hora acordada secundaria: una hora, posterior a la hora de finalización señalada, a la que la sanción de coste tiene un cambio escalonado).

- TSS (Hora a la que se inicia la ejecución del sistema de búsqueda).

- ETA (Hora de llegada estimada: es la hora a la que se calcula que el técnico llegará al lugar suponiendo que todas las duraciones de desplazamiento y de las tareas sean exactas y que cada tarea se planifique justo cuando termina la anterior. No obstante, si este cálculo determina que la tarea se lleve a cabo antes del inicio de la ventana temporal asignada, ETA se calcula como el inicio exacto de la ventana temporal de la tarea. Una ventana temporal de tarea se define como el tiempo comprendido entre la primera hora de inicio (EST) y la última hora de inicio de la tarea
(LST)).

- TAT (hora de llegada señalada: proporcionada por el preprocesador de tareas 34. Para una tarea con hora concertada, ésta será el final del intervalo de tiempo acordado).

- UOT (Cantidad de horas extraordinarias no planificadas en minutos: la cantidad de tiempo después del fin de día planificado del técnico necesario para llevar a cabo la planificación).

- ETC (Hora de finalización calculada: la hora a la que se espera que el técnico finalice la tarea. Para las tareas planificadas, se obtiene sumando ETA y la duración de la propia tarea. Para las tareas no planificadas, se calcula sumando la hora final planificada y la duración de la tarea. El valor es específico para el técnico, puesto que los técnicos tienen diferentes ritmos de trabajo, como se indica en el preprocesador de técnicos 33).

- TCT (Hora de finalización señalada: un campo proporcionado para tareas que no tienen una hora concertada. Si se produce incumplimiento de la hora de finalización señalada, se incurrirá en una sanción económica pero la tarea no se incumplirá).

- FSF (Etiqueta de incumplimiento de hora señalada secundaria: se establece en 1 si la tarea incumple su hora señalada secundaria, y en cero en caso contrario).

- SBF (Etiqueta de sanción por discriminación de aptitud: se establece en el valor de preferencia de aptitud del técnico para la tarea planificada, menos 1). Por ejemplo, si una tarea que requiere una aptitud concreta se asigna a un técnico que tiene una preferencia 3 para dicha aptitud, la SBF se establece en 2).

\newpage

- BTF (Etiqueta de hora comercial: se establece en 1 si la hora de llegada esperada del técnico es anterior a una primera hora de interrupción o posterior a una última hora de interrupción, es decir, se halla fuera de la ventana para llevar a cabo dicha tarea, o se establece en 0 en caso contrario. La hora de llegada esperada se determina como la hora a la que el técnico llegará al lugar, suponiendo que tanto las duraciones de desplazamiento como las de las tareas sean exactas y que cada tarea se asigne justo cuando finaliza la anterior o, si ésta sitúa la tarea fuera de su ventana temporal, se establece en una hora de llegada del técnico situada al inicio de la ventana temporal de la
tarea).

- ETP (Sanción por desplazamiento calculado: este parámetro toma un valor mayor o igual a cero, y se utiliza para calcular la contribución a la función objetiva para el desplazamiento asociado con cada tarea. La contribución de desplazamiento se determina multiplicando ETP por ETT. El valor por omisión del parámetro es cero).

- OTP (Sanción por horas extraordinarias no planificadas: este parámetro toma un valor mayor o igual a cero, y se utiliza para calcular la contribución a la función objetiva que llevará a cabo cada asignación de tarea que requiere horas extraordinarias no planificadas. El valor por omisión es cero).

- UAP (Sanción por hora concertada no asignada: este parámetro toma un valor mayor o igual a cero, y se utiliza para calcular la contribución a la función objetiva para las horas concertadas que no se asignan. El valor por omisión vuelve a ser cero).

- FTP (Sanción por tarea incumplida: toma un valor mayor o igual a cero, y representa el valor que se utilizará para calcular la contribución a la función no objetiva para tareas sin hora concertada. El valor por omisión es cero).

- SBP (Sanción por discriminación de aptitud: toma un valor mayor o igual a cero, y representa el valor a añadir a la función objetiva para cada asignación de tarea que no refleja la discriminación de aptitud deseada; es decir, cuando la etiqueta de discriminación de aptitud (SBF) se establece en 1. El valor por omisión del parámetro es cero).

- ATC (Constante de tipo de llegada: un entero mayor que cero que representa el período de tiempo durante el cual el coste de asignar una tarea incumplida de "tipo llegada" - es decir, una tarea en la que el compromiso es llegar al lugar a una hora determinada, a diferencia de otras en las que el compromiso es finalizar la tarea - se duplica).

- ITP (Sanción por desplazamiento de tarea de relleno: toma un valor mayor o igual a cero y representa un valor que se utilizará para calcular la contribución a la función objetiva para el desplazamiento asociado a cada tarea de relleno asignada. La contribución de desplazamiento se calcula multiplicando ITP por ETT (tiempo de desplazamiento calculado). El valor por omisión del parámetro es cero).

- MIT (Desplazamiento máximo de tarea de relleno: toma un valor mayor o igual a cero, y representa la cantidad de desplazamiento por encima de la cual el coste de asignar una tarea de relleno es exactamente igual al coste de no asignarla. Cuánto más alto sea el valor, más lejos podrá viajar el técnico hasta dicha tarea de relleno).

- BTP (Sanción por hora comercial: toma un valor mayor o igual a cero, y representa un valor que se utilizará para calcular la contribución a la función objetiva para la asignación de una tarea sin hora concertada en la que la hora de llegada calculada del técnico al lugar no se halla dentro de un período indicado. Las asignaciones que incurren en esta sanción tienen establecida la etiqueta de hora comercial (BTF) en 1. El valor por omisión del parámetro es
cero).

Debe observarse que todas las horas se expresan en minutos, siendo las horas de reloj establecidas en cero = medianoche; p.ej. las doce del mediodía del día 1 se representa como 720; las 16,40 h como 1000; 9:20 h del día 2 como 2000, etc. Las horas que no pertenecen a la jornada laboral normal no se sustraen. A título de ejemplo, en este caso, una jornada laboral se define como el período de tiempo comprendido entre las 8 h y las 17 h, de lunes a sábado). Una tarea con una TAT (hora de llegada señalada) a las 17 h del miércoles y una ETA (hora de llegada calculada) a las 8,01 del jueves da por resultado una última llegada de ETA - TAT = +901 minutos, no de + 1 minuto. (Un valor positivo indica una última llegada).

Se supone que una tarea con una ETA (hora de llegada calculada) después de las 17 h, sin sustraer las horas no laborables, terminará a las 8 h del siguiente día laborable; en el presente sistema no se lleva a cabo dicha suposición. Por ejemplo, una tarea con una ETA (hora de llegada calculada) a las 17,17 h del sábado (día laborable) y una TAT (hora de llegada señalada) a las 8,12 del lunes, dará por resultado, una vez sustraído el tiempo inactivo, el valor ETA - TAT = - 12 (es decir, la tarea se ha completado justo a tiempo); en vez del valor correcto de - 2335. (Estos valores son negativos, puesto que son valores de llegada antes de la hora señalada).

La función objetiva a reducir al mínimo es determinada por las diez siguientes ecuaciones, dependiendo del tipo de tarea relacionada.

\newpage

Ecuación 1

Para tareas con hora concertada asignadas, la contribución a la función objetiva es:

(1 \ + \ P/2) \ x \ P \ x \ (IMU^{IEX} \ x \ IMP) + (ETP \ x \ ETT) + (OTP \ x \ UOT) + (SBP \ x \ SBF)

en la que, si la hora actual es igual o superior a la hora de apertura del intervalo:

P = (ETA - TAT)/(TAT - TSS) \hskip1cm [si \ TAT = TSS, \ entonces \ P = 0]

o, si el intervalo todavía no se ha abierto:

P = min \{1, \ (ETA - TAT)/duración \ del \ intervalo \ de \ tiempo \ concertado \ en \ minutos\}

(P toma el valor inferior de los dos valores separados por la coma)

\vskip1.000000\baselineskip

Ecuación 2

Para tareas de tipo llegada asignada, en las que ETA menos TAT es inferior o igual a cero, la contribución a la función objetiva es:

(1 \ + \ P/2) \ x \ P \ x \ (IMU^{IEX} \ x \ IMP) \ + \ (ETP \ x \ ETT) \ + \ (OTP \ x \ UOT) \ + \ (SBP \ x \ SBF)

en la que P = (ETA - TAT)/(TAT - TSS)

\hskip1cm

[si TAT = TSS, entonces P = 0]

\vskip1.000000\baselineskip

Ecuación 3

Para tareas de tipo llegada asignada, en las que ETA - TAT es mayor que cero, la contribución a la función objetiva es:

(P \ + \ FTP) \ x \ (IMU^{IEX} \ x \ IMP) \ + \ (ETP \ x \ ETT) \ + \ (OTP \ x \ UOT) \ + \ (SBP \ x \ SBF)

en la que P = (ETA - TAT)/ATC

\vskip1.000000\baselineskip

Ecuación 4

Para horas concertadas desasignadas y tareas de tipo llegada la contribución es:

(IMU^{IEX} \ x \ IMP) \ x \ UAP

\vskip1.000000\baselineskip

Ecuación 5

Para tareas con horas concertadas asignadas en las que ETC - TCT es inferior o igual a cero la contribución es:

(1 \ + \ P/2) \ x \ P \ x \ IMU^{IEX} \ x \ IMP) \ + \ (ETP \ x \ ETT) \ + \ (OTP \ x \ UOT) \ + \ (SBP \ x \ SBF) \ + \ (BTP \ x \ BTF)

en la que P = (ETC - TCT)/(TCT - TSS)

\vskip1.000000\baselineskip

Ecuación 6

Para tareas con horas concertadas de asignación en las que ETC - TCT es mayor que cero, pero en las que no se ha sobrepasado el límite de hora concertada secundaria, la contribución es:

(P \ + \ FTP) \ x \ (IMU^{IEX} \ x \ IMP) \ + \ (ETP \ x \ ETT) \ + \ (OTP \ x \ UOT) \ + \ (SBP \ x \ SBF) \ + \ (BTP \ x \ BTF)

en la que P = (ETC - TCT) / (SCT - TCT)

\newpage

Ecuación 7

Para tareas con horas concertadas asignadas en las que ETC - TCT es mayor que cero y en las que se sobrepasa el límite de hora concertada secundaria, la contribución es:

(P \ + \ FSP \ + \ FTP) \ x \ (IMU^{IEX} \ x \ IMP) \ + \ (ETP \ x \ ETT) \ + \ (OTP \ x \ UOT) \ + \ (SBP \ x \ SBF) \ + \ (BTP \ x \ BTF)

en la que P = (ETC - TCT) / (SCT - TCT)

\vskip1.000000\baselineskip

Ecuación 8

Para tareas con horas concertadas no asignadas la contribución será:

\{(ETC - TCT) / (SCT - TCT) \ + \ (FTP \ x \ FTF) \ + \ (FSP \ x \ FSF)\} \ x \ (IMU^{IEX} \ x \ IMP)

\vskip1.000000\baselineskip

Ecuación 9

Para tareas de relleno asignadas la contribución es:

ETT \ x \ ITP

\vskip1.000000\baselineskip

Ecuación 10

Para tareas de relleno no asignadas la contribución es:

MIT \ x \ ITP

Debe observarse que no se planificará ninguna hora concertada cuyo incumplimiento se prevea (es decir, si el técnico llega al lugar después del final del intervalo concertado). Además, si la hora concertada que se planifica es una hora que permite que el técnico pueda llegar antes de que se inicie el intervalo concertado, entonces se supone, en cambio, que el técnico llegará en el preciso momento en que se inicia el intervalo.

En las Figuras 6 a 9, se ilustra el coste de asignación para una serie de tipos diferentes de tareas y situaciones. Éstas muestran cómo varía el coste de asignación de una tarea según la variación de la hora de llegada o la hora de finalización de una tarea. En todos los casos, IEX e IMU se establecen en 1.

La Figura 6 ilustra la situación para una tarea con hora concertada dentro de un "intervalo de tiempo" indicado. Esta tarea está concertada para el período entre 8 h y 10,30 h (480 a 630 minutos, después de medianoche) y, por lo tanto, las únicas horas de llegada válidas se hallan dentro de este rango. Si la hora de llegada es exactamente las 8 h, se generará un coste de menos 0,5 veces la puntuación de importancia de la tarea, mientras que si la hora de llegada es exactamente las 10,30 h se obtendrá una puntuación de cero. En caso de que la tarea quede sin asignar, y por lo tanto sin ser llevada a cabo, se incurrirá en una puntuación de sanción de UAP x IMP. Se establece UAP en un valor positivo, de manera que el coste de asignar una hora concertada siempre será inferior al coste de no asignarla.

La Figura 7 muestra una situación parecida a la de la Figura 6, salvo porque el intervalo ya se ha iniciado y la hora actual es 9,40 h (580 minutos después de medianoche) de modo que sólo quedan 50 minutos antes del final del intervalo. La forma de la curva es la misma, pero los valores del eje del tiempo se han comprimido.

La Figura 8 muestra una tarea sin hora concertada, pero con el compromiso de finalización antes de una hora indicada (17,30 h: 1050 minutos). El parámetro FTP se establece en 1, dando por resultado un cambio escalonado del coste después de la hora señalada de compromiso, siendo el tamaño del escalón igual a la puntuación de importancia (es decir, 50). El parámetro FSP se establece en 2, dando por resultado otro cambio escalonado del coste del doble de la puntuación de importancia (es decir, 100) después de una segunda hora de compromiso secundario (en este caso la hora de sanción; 2040 minutos, es decir, 10 h del día 2).

La Figura 9 muestra cómo el coste de asignación varía con el tiempo para una tarea con una hora de llegada señalada y una puntuación de importancia de 900. En esta Figura, la hora de llegada señalada es las 12 del mediodía (720 minutos) y el valor del parámetro FTP es 0,1. Esto da por resultado un cambio escalonado de 90 (es decir, de 0,1 veces la puntuación de importancia de 900) cuando la tarea sobrepasa las 12 del mediodía.

\newpage

Se crea una planificación inicial tomando la planificación parcial generada por el preplanificador 30 y asignando de forma arbitraria más tareas a los técnicos. Esta planificación inicial es modificada a continuación por el subsistema de optimización 31. Este procedimiento se ilustra en el diagrama de flujo de la Figura 10. El procedimiento incluye cuatro etapas 1001, 1002, 1005, 1016 que requieren la generación de un número aleatorio. A cada tarea y técnico se le asigna un número aleatorio.

El procedimiento se inicia calculando el coste de la planificación original (etapa 1000). A continuación, se utiliza un generador de números aleatorios para seleccionar una de las tareas. Con la excepción de las tareas preasignadas, descritas anteriormente, cada tarea tiene la misma probabilidad de ser seleccionada, tanto si actualmente se halla en una planificación como si no. Una vez seleccionada una tarea, el procedimiento continúa de una forma que depende de si la tarea seleccionada ya está presente en un recorrido.

También se selecciona aleatoriamente un técnico factible (es decir, un técnico que pueda llevar a cabo la tarea según determina el preprocesador 33), utilizando un procedimiento análogo al utilizado para seleccionar una tarea. Se selecciona un número (etapa 1002) del rango de 1 a N + 1, siendo N el número de técnicos factibles; sin embargo, se excluye de la selección el número que corresponde al técnico para el que se ha planificado actualmente la tarea seleccionada. El número N + 1 representa un técnico "ficticio". La asignación de una tarea al técnico ficticio constituye la desasignación de la tarea para las finalidades de la función objetiva. Debe observarse que la probabilidad de planificar una tarea para el técnico ficticio es 1/N, y por lo tanto, ésta disminuye a medida que aumenta el número de técnicos en el sistema. Si la tarea no está planificada, entonces el técnico que se excluye de la selección es el ficticio.

Si la tarea no es para el técnico ficticio (etapa 1003), ni para una hora concertada (etapa 1004), se selecciona una posición aleatoria en el recorrido del técnico seleccionado (utilizando también esta vez el procedimiento de números aleatorios; etapa 1005) y se examina la posición para ver si la tarea puede ajustarse a esta (1006). Para que sea posible introducir la tarea en el recorrido, el espacio de tiempo debe ser suficientemente grande como para incluir la tarea o, en caso contrario, debe ser posible retrasar todas las tareas posteriores para crear un espacio de tiempo suficientemente grande como para insertar la tarea (1007).

Si la tarea tiene una hora concertada (etapa 1004), entonces se examinan todas las posiciones posibles del recorrido (etapas 1008 a 1010) hasta que se halla una posición válida (etapa 1009). La validez de cada posición se determina (etapa 1009) en relación con el intervalo de tiempo concertado de la tarea; por ejemplo, una tarea con hora concertada en un intervalo de tarde no es válida para una posición del recorrido que termina a las 9,30 h. Si se han probado todas las posiciones y ninguna es válida (etapa 1010), la tarea se rechaza (etapa 1018) y se selecciona una nueva (etapa 1001). Si se halla una posición válida, se examina como se ha descrito anteriormente en relación con las tareas sin hora concertada, para determinar si la tarea puede ajustarse a ésta (etapas 1006 y 1007). Debe observarse que una tarea que tenga una hora concertada no se planificará en una posición que determinaría que el técnico llegara fuera de una ventana temporal definida por la hora de inicio del intervalo concertado (menos un margen permitido), y la hora final concertada. Si la finalización calculada de la tarea anterior permite llegar al técnico antes de esta ventana, entonces se supone que el técnico incurrirá en tiempo inactivo. Cuando se determina si la inserción puede llevarse a cabo, se tienen en cuenta los desplazamientos con origen y destino en una tarea insertada en una planificación.

Si es posible la inserción (etapa 1006), la tarea se inserta en la planificación del técnico (etapa 1012) y se calcula el coste de la planificación revisada (etapa 1013). A continuación, el coste de la planificación revisada se compara con el mejor valor existente (etapa 1014). Cualquier movimiento que reduzca la función objetiva, o la mantenga inalterada, se acepta de forma automática (etapa 1015). Esto se parece al procedimiento de "escalada" mencionado anteriormente, puesto que sólo se aceptan los movimientos en una dirección particular (hacia el óptimo). No obstante, en un procedimiento de reasociación simulada, los movimientos que aumentan el valor de la función objetiva también se aceptan, con una probabilidad p definida por el "régimen de enfriamiento", que se describirá en breve. Se genera un número aleatorio R del rango de cero a 1 (etapa 1016), y si es menor o igual a la probabilidad p (etapa 1017), entonces el movimiento se acepta (etapa 1015).

Si se acepta el movimiento, el valor resultante de la función objetiva se compara con el mejor valor obtenido anteriormente (etapa 1019). Si es mejor que el mejor valor anterior, la solución se salva como nuevo "mejor valor" (etapa 1020) para futuras comparaciones. Cualquier cambio puede ser rechazado (etapa 1018) ya sea en esta etapa final, o debido a que la tarea no puede ser insertada en la planificación (etapa 1007 ó 1009).

A continuación, el procedimiento se repite para otra tarea (etapa 1001), utilizando ya sea la planificación revisada si el cambio fue aceptado (etapa 1015), o la planificación anterior si el cambio fue rechazado (etapa 1018). Debe observarse que un movimiento que es aceptado en la etapa 1015 se utiliza como base para la siguiente iteración, tanto si es como si no es una mejora del "mejor valor" (etapas 1019/1020).

Desasignar una tarea (es decir, planificarla para el técnico ficticio) siempre aumenta la función objetiva, pero dicha desasignación se acepta con probabilidad p, y por lo tanto permite la posibilidad, en la siguiente iteración del procedimiento, de volver a planificar una tarea de reposición para el técnico al que se le quitó la tarea. Debe observarse que no existe ninguna limitación de aptitud, tiempo o de otro tipo en la asignación de una tarea al técnico ficticio - dicha asignación siempre es factible, pero siempre incrementa la función objetiva.

\newpage

La probabilidad p de aceptar un movimiento que determina un incremento del valor de la función objetiva es proporcionada por la fórmula p = exp(-delta/temperatura).

La "temperatura" es un concepto que controla el número de movimientos llevados a cabo que incrementan el valor de la función objetiva. Cuánto más alto sea el valor de la temperatura, más movimientos que incrementen el valor de la función objetiva serán aceptados. Durante la búsqueda, el valor de la temperatura se reduce gradualmente, de modo que en puntos posteriores de la búsqueda se aceptan menos de dichos movimientos. Delta es la diferencia entre el valor de la función objetiva tras el cambio y el valor antes del cambio. Al cabo de un número dado de movimientos a una temperatura dada, el valor se reduce. La reducción se produce multiplicando la temperatura por un valor predeterminado. Todos los movimientos, ya sean válidos, no válidos, rechazados o aceptados, se incluyen en este recuento.

En la Figura 11, se ilustra la relación entre delta, la temperatura y la probabilidad de aceptar un movimiento que empeora el valor de la función objetiva (es decir, lo hace mayor). Esta figura muestra las dos características clave del régimen de enfriado. En primer lugar, muestra cómo la probabilidad de aceptar un movimiento que empeora el valor de la función objetiva disminuye a medida que aumenta la magnitud de delta, y en segundo lugar, cómo la probabilidad disminuye con la reducción de la temperatura.

Puede establecerse que el simulador de reasociación se detenga, ya sea después de una hora predeterminada, o bien después de que se hayan utilizado un número predeterminado de temperaturas. La planificación (un grupo de recorridos) que debe pasarse al gestor de planificaciones es la que proporciona el valor más bajo de la función objetiva (es decir, el valor que ha sido almacenado como el mejor hallado hasta ese momento; etapa 1020) a la hora a la que se detuvo el procedimiento.

El subsistema de optimización 31 utiliza las horas extraordinarias según proceda dentro de límites determinados por la disponibilidad de los límites individuales de horas extraordinarias; estos límites son pasados al subsistema 31 por el preprocesador 33. Si la tarea puede terminarse dentro de las horas extraordinarias permitidas de un técnico, entonces puede ser planificada por el subsistema de optimización. No obstante, si la tarea va a rebasar el límite de horas extraordinarias de un técnico, entonces sólo se planifica si puede dividirse en dos o más subtareas, y si la proporción de la tarea que puede terminarse antes del fin de día planificado es mayor que un mínimo predeterminado. En estas circunstancias, la tarea se divide y la primera parte de la misma se planifica para que termine en el fin de día planificado. No se incluirá ninguna tarea dividida que se espere que requiera horas extraordinarias no planificadas.

Durante el transcurso del día, el subsistema de optimización 31 se ejecuta a intervalos regulares. En cada ocasión en que se ejecuta, el procedimiento puede empezar desde un principio a tratar de planificar todas las tareas que no han sido planificadas por el preplanificador 30. Como alternativa, el subsistema 31 puede ejecutarse, reutilizando, como punto de partida, los recorridos generados en su ejecución anterior. En esta modalidad, el subsistema de optimización 31 construye su posición de partida de la siguiente forma. Se comprueba la disponibilidad de cada técnico del conjunto de recorridos anterior (es decir, se comprueba si todavía se halla en la lista de técnicos proporcionada por el preprocesador de técnicos 33). Para los técnicos que todavía están disponibles, todas las tareas incluidas por el preplanificador 30 son escritas en el recorrido. A continuación, se revisan los recorridos anteriores, en el orden en que las tareas habían de haberse llevado a cabo, y todas las tareas que puedan añadirse al recorrido actual (es decir, después de que todavía son asignaciones válidas) se añaden al final del nuevo recorrido (es decir, tras cualquier tarea incluida por el preplanificador). Las tareas que dejan de ser válidas (p.ej. las que ya han sido asignadas) se omiten del nuevo recorrido. Una vez creado un recorrido inicial de este modo, el subsistema de optimización busca mejores soluciones de la forma descrita anteriormente.

El procedimiento puede ser interrumpido de forma periódica para determinar la mejor planificación hasta el momento analizada por un postoptimizador 39. Éste utiliza un planteamiento basado en reglas para determinar planificaciones individuales que parecen aproximarse a una planificación óptima, es decir, planificaciones que incluyen sólo pequeñas cantidades de tiempo inactivo o tiempo de desplazamiento, y que no conllevan un itinerario que doble sobre sí mismo. Dichas planificaciones son reconocidas como fijas, y el procedimiento de optimización se reanuda. Esto asegura que el procedimiento de optimización se concentre en las partes de la planificación global en las que es más probable hallar mejoras, restringiendo la búsqueda a las áreas del "espacio de soluciones".

Al cabo de un tiempo de ejecución adecuado, se crea un último conjunto de planificaciones para técnicos que, a continuación, se pasa al modificador de planificaciones de tiempo real 40. Mientras el modificador en tiempo real se está ejecutando, utilizando esta planificación, el generador de planificaciones 30,31 puede reanudar su funcionamiento para generar una nueva planificación utilizando datos actualizados.

En las Figuras 12, 13 y 14, se muestra en forma de diagrama de flujo el funcionamiento del modificador de tiempo real 40 (Figura 4). En el diagrama de flujo de la Figura 4, se muestran las características principales del optimizador de tiempo real 40. El registro de estados de planificación 42 almacena el estado actual de las planificaciones que son proporcionadas inicialmente, por medio de la memoria de planificaciones 32, desde el subsistema de optimización 31 (véase la Figura 3). El registro de estado del técnico 43 y el registro de lista de trabajos 44 almacenan de forma parecida datos relativos a los técnicos y tareas, respectivamente, que se obtienen en un principio desde los respectivos preprocesadores 33, 34. Estos tres registros pueden actualizarse, como se indicará más adelante. Una entrada de parámetros 41 permite al operador establecer las diversas ponderaciones y otros valores utilizados por el
sistema.

El registro de estado del técnico 43 puede actualizarse mediante las entradas de los propios técnicos T1, etc., en particular para indicar si el estado de un técnico está en línea o fuera de línea. La fuente de registros de trabajo también puede actualizarse por medio de una interfaz manual (un terminal de ordenador) 45, que permite al operador añadir nuevas tareas a la reserva de trabajos durante una ejecución del asignador de tiempo real, p.ej. en respuesta a un cliente ha indicado la existencia de un fallo. También pueden proporcionarse entradas automáticas, conectadas a monitores de fallos, dentro de la red 46.

Los registros 42, 43, 44 proporcionan entradas a un procesador de asignaciones 47, que utiliza la información de estado actual de los registros de una forma que se describirá en relación con las Figuras 12, 13 y 14 para generar una asignación para un técnico T en cuanto se ponga en línea para solicitar instrucciones. La asignación resultante se pasa a una unidad de generación de instrucciones 48, que transmite instrucciones relativas a la tarea recién asignada, y cualquier actividad asociada, al técnico T. El procesador de asignaciones 47 también transmite información de actualización al registro de estados del técnico 43, en relación con la ubicación actual del técnico, próxima hora de llamada esperada, etc. El procesador de asignaciones 47 también transmite información de actualización al registro de lista de trabajos 44, en particular, para suprimir la tarea que acaba de ser asignada. Asimismo, el procesador de asignaciones transmite información de actualización al registro de estados de planificación, en particular, para modificar las planificaciones provisionales de cualquier otro técnico afectado por la asignación que se acaba de efectuar.

El modificador 40 es gestionado de una forma que permite tener en cuenta los cambios producidos desde que se generaron las planificaciones en un primer momento o en el momento más adecuado. Dichos cambios pueden originarse cuando los técnicos solicitan nuevas tareas antes o después de lo esperado, cuando se solicitan ausencias a corto plazo, cuando se efectúan cambios en una tarea planificada (p.ej. al modificar la hora concertada), cuando se introducen nuevas tareas en el sistema o cuando se efectúan cambios en las reglas de planificación y de asignación como, por ejemplo, cambios en los tiempos de desplazamiento para tener en cuenta condiciones climáticas o de tráfico adversas. El objetivo de esto es asegurar que cuando el técnico solicite una tarea, la tarea que de hecho se asigna sea la tarea más adecuada disponible para dicho técnico en el momento en que se procesa la petición, sea o no la tarea planificada en un principio. Para facilitar la comprensión, las reglas de asignación y optimización que se describirán vienen respaldadas por una serie de diagramas de flujo, representados en las Figuras 12 a 14. En la Figura 12, el número de referencia 13 remite al diagrama de flujo representado en la Figura 13, que funciona como subrutina que se activa durante el procedimiento ilustrado en el diagrama de flujo de la Figura 12. Del mismo modo, el procedimiento de la Figura 14 tiene lugar como una subrutina en diversas etapas de las Figuras 12 y 13.

En varias de las reglas, aparecen los términos que se definen a continuación para mayor comodidad.

"Inexacta": estado de planificación de una actividad (p.ej. tarea, ausencia, pausa) que está planificada para un técnico pero que todavía no está asignada al mismo, y para la cual la información en la que se basa la planificación ha dejado de ser válida. Esto puede ocurrir cuando se asigna a un técnico una tarea que no se halla en la planificación original del técnico, o cuando una tarea que originalmente se halla en la planificación del técnico se asigna a otro técnico.

"Pendiente": estado de planificación de una actividad (p.ej. tarea, ausencia, pausa) que está planificada para un técnico pero que todavía no está asignada al mismo, y para la cual la información en la que se basa la planificación se supone que todavía es válida (es decir, no se ha marcado como "inexacta").

A continuación, se describirán en líneas generales los procedimientos ilustrados en las Figuras 12 a 14.

La Figura 12 muestra el procedimiento para determinar qué instrucción debe darse a un técnico que acaba de presentarse (etapa 1200). La instrucción (1211 a 1215) habitualmente será llevar a cabo una tarea (1213), pero también pueden proporcionarse otras instrucciones como, por ejemplo, ausentarse (p.ej. para asistir a una reunión o sesión de formación, 1211).

La Figura 13 es el procedimiento mediante el cual se selecciona una tarea adecuada.

En ambos procedimientos de las Figuras 12 y 13, se utiliza una subrutina que determina si es factible o no que el técnico lleve a cabo una tarea dada. Este procedimiento se ilustra en la Figura 14.

La Figura 12 ilustra el procedimiento para determinar la asignación de una tarea para un técnico en línea. Al presentarse un técnico (etapa 1200), el sistema consulta la planificación para determinar la siguiente actividad para el técnico (1201). Si la siguiente actividad planificada es el "fin de día (EOD)" (es decir, si al técnico ya no le queda ninguna actividad planificada para el resto del día), el sistema avanza hasta el procedimiento 13 para tratar de hallar una tarea adecuada para el técnico. Si existe alguna actividad planificada antes de la actividad de "fin de día" (resultado negativo para la etapa 1201), se efectúa un procedimiento de "comprobación de ausencia de preselección" (etapas 1202 a 1207). En primer lugar, el sistema comprueba la planificación del técnico para determinar si hay alguna ausencia planificada para el técnico (etapa 1202). Si no existe ninguna de dichas ausencias, entonces se busca una tarea posterior para el técnico utilizando el procedimiento 13 que se describirá a continuación.

Si existe por lo menos una ausencia, entonces el sistema comprueba si se espera que la siguiente ausencia empiece dentro de un tiempo predeterminado a partir de la hora actual (etapa 1203). En caso afirmativo, se efectúa una comprobación para establecer si el fin de la ausencia planificado se hallará dentro de un período durante el cual debe efectuarse una pausa (etapa 1204). Si ello no es así, se indica al técnico que se ausente, p.ej. para asistir a una reunión (etapa 1211), y que comunique su regreso para recibir nuevas instrucciones. La base de datos se actualiza (etapa 1216) registrando el inicio del período de ausencia, la siguiente hora de contacto del técnico se actualiza y pasa a ser el final planificado de la ausencia y la situación del técnico se actualiza y pasa a ser la de la ausencia.

Si el técnico todavía no ha efectuado ninguna pausa y tiene planificado el fin de su ausencia después de la última hora antes de la cual debe empezar la pausa, entonces se ordena al técnico que continúe su ausencia y que efectúe la pausa antes de su siguiente contacto con el sistema (etapa 1212). La planificación del técnico se actualiza para incluir la duración de la pausa y de la ausencia y la duración del desplazamiento calculado hasta la ubicación de ausencia, y para registrar que en ese momento se inicia una pausa (1216).

Volviendo a la etapa 1203, si no se espera que empiece todavía la siguiente ausencia, el sistema asigna la mejor tarea que puede efectuarse antes del inicio previsto de la ausencia (etapas 1205 a 1210). Las pertinentes reglas se describen a continuación.

La etapa 1205 determina si la siguiente actividad planificada es la ausencia (es decir, si no se ha planificado ninguna tarea antes de la ausencia planificada). En caso afirmativo, el procedimiento busca una tarea, utilizando un procedimiento que se describirá más adelante en relación con la Figura 13. No obstante, si se ha planificado una tarea antes de la ausencia, entonces se ejecuta una prueba de factibilidad (etapa 1206) que se describirá más adelante en relación con la Figura 14. Si la tarea planificada sigue siendo factible en el tiempo que queda antes de que deba efectuarse la pausa, de acuerdo con la comprobación efectuada en la etapa 1206, entonces se evalúa si la ausencia planificada aún puede llevarse a cabo después de la tarea (etapa 1207). Si la tarea supera ambas pruebas (etapas 1206, 1207), entonces se asigna al técnico, que recibe instrucciones para llevarla a cabo (etapa 1213). No obstante, si la tarea planificada no supera cualquiera de las pruebas, es decir, no puede llevarse a cabo antes de la hora prevista para la ausencia o una pausa planificada, se determina una tarea alternativa utilizando el procedimiento de la Figura 13.

A continuación, se describirá el procedimiento de asignar técnicos a tareas, ilustrado en la Figura 13. Este procedimiento es uno de los principales puntos de partida de los sistemas anteriores. En dichos sistemas anteriores, si un técnico tiene una planificación predeterminada, siempre le será asignada la siguiente tarea de la planificación, si es posible, o en caso contrario, se le asignará una tarea que ya se halla en el sistema pero que todavía no ha sido planificada para otro técnico. En dichas disposiciones, una tarea nueva para el sistema desde la última actualización regular del sistema de planificación no será asignada hasta la siguiente actualización regular. El procedimiento descrito aquí permite la optimización de la planificación en lo que respecta a un técnico dado, cada vez que se presenta para una nueva tarea, tanto si se presenta según lo planificado como si no, y tanto si una tarea que puede llevarse a cabo ya está planificada para ser llevada a cabo por dicho técnico como si no, y tiene en cuenta en dicha optimización incluso las tareas que han sido añadidas al sistema desde la última revisión de planificación. Esto proporciona más tiempo entre reconstrucciones de la totalidad de la planificación y, por lo tanto, permite emplear más tiempo en cada ejecución de reconstrucción.

La asignación de una tarea a un técnico que no sea el técnico planificado para llevar a cabo dicha tarea, sólo modificará la planificación con respecto a dicho técnico y, si la tarea fue planificada en un principio para otro técnico, con respecto a ese otro técnico. Con regularidad, durante el día, se crea una nueva planificación. La frecuencia a la que ésta se lleva a cabo debe seleccionarse de acuerdo con la velocidad a la que los cambios tienen lugar, de manera que la planificación anterior no se vea totalmente perturbada por cambios en línea antes de que la nueva tarea esté disponible. No obstante, cuanto más tiempo pueda proporcionarse para la generación de cada nueva planificación, más óptimas serán las soluciones que puedan generarse.

En lo posible, la planificación inicial utilizada en la primera iteración de la etapa de optimización 31 será la planificación actual, generada por el optimizador de tiempo real 40 en el ciclo anterior, subordinado a cualquier punto fijo nuevo añadido por la etapa determinista 30.

La información de las tareas que todavía no han sido asignadas (tanto si están planificadas provisionalmente para la asignación como si no lo están) está almacenada en la base de datos de "lista de trabajos" 44. Cuando se considera un técnico para asignarlo a una tarea, se determinan los siguientes factores para utilizarlos en las diversas comprobaciones de rectificación y optimización que se efectúan:

a. La situación desde la cual se estima que el técnico va a desplazarse para acudir a la tarea en cuestión, que se considera que es la situación en la que se halla la tarea actual del técnico, o su situación de inicio de día si todavía no le ha sido asignada ninguna tarea.

b. La hora de inicio de asignación (es decir, la hora actual o la de inicio de la jornada laboral del técnico, sea cual sea la última de éstas).

c. El tiempo que queda de las horas laborables del técnico, incluyendo las horas extraordinarias planificadas.

d. La situación en la que el técnico debe finalizar su período de trabajo, que puede ser su domicilio o la situación de una ausencia planificada.

e. Una situación de trabajo preferida y un radio de desplazamiento alrededor de ésta. Las tareas situadas fuera de este radio no se asignarán al técnico.

f. Una unidad de movilidad, que se adapta para evitar que se emplee un tiempo excesivo de desplazamiento de una tarea a otra.

Como se ilustra en la Figura 13, en una primera etapa (1301), se efectúa una comprobación para determinar si existe alguna tarea planificada para el técnico. Si existe alguna tarea, el procedimiento utiliza a continuación una prueba 1302 (la subrutina de la Figura 14) para comprobar si la tarea todavía podría efectuarse si se asignara al técnico. Tal vez sea imposible para el técnico llevar a cabo la tarea planificada, debido a cambios no planificados, en particular, si el técnico se presenta más temprano o más tarde de lo planificado. La tarea podrá llevarse a cabo si se cumplen todas las condiciones siguientes:

a. El técnico tiene suficiente tiempo para llevar a cabo la tarea dentro de sus horas laborables planificadas o, si la tarea queda dividida por el fin de día (indicado mediante horas de inicio y fin planificadas en diferentes fechas), la proporción de la duración esperada de la tarea que el técnico podrá terminar antes del fin de las horas laborables planificadas es superior a un mínimo predeterminado.

b. La tarea cumple los requisitos para la gestión de pausas (véase la Figura 14).

c. Si la tarea debe llevarse a cabo entre horas determinadas, la hora de llegada esperada del técnico al lugar se halla dentro de este período.

d. La tarea todavía no ha sido asignada a un técnico diferente.

Si la siguiente tarea de la planificación del técnico no supera todas las comprobaciones anteriores, entonces se considera que la tarea no es factible, en caso contrario, se considera que es factible.

Tanto si existe una tarea factible como si no en la planificación provisional del técnico, el sistema trata en consecuencia de mejorar la planificación provisional ejecutando una serie de pruebas. Estas pruebas se indican en la Figura 13 como pruebas 1303, 1304, 1306 (si existe una tarea factible, es decir, si el resultado de las pruebas 1301 y 1302 es positivo) o como pruebas 1304A, 1306A y 1309 (si no existe ninguna tarea planificada que actualmente sea factible, es decir, si el resultado de la prueba 1301 o la prueba 1302 es negativo). Este procedimiento está preparado para que cuando exista una tarea planificada factible, la planificación sólo sea alterada si existe la posibilidad de obtener una mejora importante en la calidad del servicio.

En primer lugar, si se ha determinado que existe una tarea factible, se efectúa una prueba para determinar (etapa 1303) si la tarea planificada lleva la etiqueta de gran importancia o de difícil asignación. En tal caso, se asigna al técnico que no está siendo sometido a otra optimización (resultado 1308).

En los demás casos (es decir, cuando en la planificación no existe ninguna tarea factible que lleve una de dichas etiquetas), el procedimiento investiga (etapas 1304/1304A) si existe alguna tarea en las lista de trabajos 44, que lleve la etiqueta de muy importante y cuya hora acordada se halle muy próxima, que todavía no haya sido planificada. Esto puede ser debido a varias razones; por ejemplo, porque es una nueva tarea o una tarea perdida de otra planificación.

Para reasignar una tarea al técnico que actualmente está en línea, deben cumplirse las cuatro condiciones descritas en relación con la etapa 1302, y además las siguientes:

e. la tarea no ha sido "planificada en firme" para el técnico planificado (si lo hubiera) por el preplanificador 30;

f. el técnico que se está considerando tiene las aptitudes y permisos necesarios para llevar a cabo la tarea;

g. la situación de la tarea se halla dentro de los límites geográficos del técnico,

h. la tarea se halla dentro de un período predeterminado de su hora señalada,

i. la tarea puede llevarse a cabo antes de la siguiente tarea fijada del técnico.

Todas las tareas seleccionadas de este modo se ordenan en la siguiente secuencia;

1. Cualquier tarea expresamente preplanificada para el técnico en línea.

2. Tiempo de desplazamiento hasta la tarea (por orden creciente).

3. Preferencias de aptitudes.

4. Prioridad (por orden decreciente)

5. Tiempo hasta hora acordada.

El tiempo de desplazamiento puede calcularse desde una situación a otra situación utilizando cualquier sistema de navegación de rutas conocido, teniendo en cuenta factores como el tipo de carreteras, hora del día, etc. Cuando una tarea está planificada pero la tarea anterior a ésta todavía no lo está, se utiliza un factor de tiempo de desplazamiento característico de las tareas del área general. Si la tarea está marcada como "inexacta", o si se está llevando a cabo una operación de rectificación en la planificación, entonces deberá volverse a calcular el tiempo de desplazamiento, puesto que el cálculo para la entrada planificada dejará de ser correcto.

La primera tarea de la lista resultante que cumpla los criterios anteriores y los criterios de gestión de pausas se selecciona para su asignación al técnico en línea (etapa 1305). Si no se halla dicha tarea, se efectúa otra prueba (etapa 1306/1306A) en la que se determina si existe alguna tarea que cumpla las siguientes condiciones:

- es de prioridad más alta que la tarea planificada para el técnico en línea (si la hubiera),

- todavía no ha sido considerada en la etapa 1304/1304A,

- se ha planificado para otro técnico,

- el técnico en línea puede acudir antes que el otro técnico planificado.

Todas las tareas que cumplan estas condiciones serán evaluadas. Se utilizan las mismas pruebas, salvo porque el requisito de que la tarea esté cerca de su hora señalada (prueba "i" anterior) se sustituye por el requisito de que sólo es necesario considerar las tareas de prioridad más alta que la tarea planificada (si la hubiera). Si se halla una tarea adecuada, se asigna al técnico, con preferencia a la tarea planificada, si la hubiera (etapa 1307).

Si ni la prueba 1304 ni la 1306 proporcionan una tarea más adecuada, entonces se asigna la tarea planificada (etapa 1308). No obstante, si se obtiene un resultado negativo en ambas pruebas 1304A y 1306A (es decir, las pruebas equivalentes cuando la planificación ya se ha desajustado), no habrá ninguna tarea planificada que pueda asignarse. En su lugar, el técnico recibe la orden de entrar en contacto con su supervisor para obtener instrucciones (etapa 1309).

Cuando se seleccionan tareas en las etapas 1304, 1304A, 1306, 1306A, se requiere una prueba para asegurar que la tarea puede llevarse a cabo dentro de su hora concertada (si la hubiera). Además, debe tenerse en cuenta si también debe darse la orden al técnico de efectuar una pausa antes de que vuelva a entrar en contacto con el sistema de control. Asimismo, es necesario llevar a cabo una prueba para evaluar la factibilidad de las tareas planificadas (etapas 1302 y 1206). La prueba se ilustra en la Figura 14. Este procedimiento tiene tres objetivos. En primer lugar, asegura que las pausas se efectúen dentro de las ventanas temporales adjudicadas. En segundo lugar, si una tarea no puede ser planificada de forma inmediata, puede asignarse una pausa para permitir que esta tarea pueda ser planificada después de la pausa. Por ejemplo, la llegada para la hora concertada puede producirse demasiado temprano a menos que se efectúe primero una pausa. Esto está supeditado a la concesión a dicho técnico del permiso para efectuar una pausa en ese momento. En tercer lugar, este procedimiento rechaza cualquier tarea de hora concertada si el período dentro del cual se producirá el incumplimiento de la hora concertada no coincide con la hora a la que el técnico llegaría a la situación si ésta le fuera asignada.

La primera prueba llevada a cabo en este procedimiento (1401) determina si necesita tenerse en cuenta una pausa. Si ya se han efectuado todas las pausas planificadas, la tarea que se está considerando es factible, a menos que el técnico no pueda llegar a la situación de la tarea dentro del intervalo de tiempo concertado, si lo hubiera. Por lo tanto, el sistema comprueba en primer lugar si la tarea tiene un intervalo de tiempo concertado (etapa 1402) y en tal caso, si el técnico puede llegar dentro de ese intervalo de tiempo (es decir, ni demasiado pronto, lo que generaría tiempo inactivo, ni demasiado tarde: etapas 1403 y 1404). Si el técnico puede llegar dentro del intervalo de tiempo concertado, o si no existe ningún intervalo de tiempo concertado, la tarea es factible (1410). Si no puede llegar dentro del intervalo de tiempo concertado, la tarea no es factible (1413).

Si al técnico todavía le queda una pausa por efectuar, entonces existen cuatro posibles resultados para la prueba (1410 a 1413 en la Figura 14). La tarea puede ser no factible (1413) o factible; siendo necesario tal vez, en este último caso, planificar una pausa antes (1412) o durante (1411) la tarea, o ninguna (1410) si la tarea puede terminarse antes de que deba efectuarse la pausa.

Si el técnico todavía no ha efectuado ninguna pausa, entonces la prueba de la etapa 1401 proporciona un resultado positivo. En este caso, la siguiente prueba vuelve a comprobar si la tarea tiene una hora concertada (etapa 1402A). En caso afirmativo, entonces se comprueba si el técnico llegará demasiado pronto para la hora concertada (etapa 1403A). Si el técnico no va a llegar demasiado pronto, se efectúa una prueba para averiguar si el técnico llegará después del final del intervalo de tiempo concertado (etapa 1404A). Estas tres pruebas son en esencia las mismas que las de las etapas 1402, 1403 y 1404, descritas anteriormente, pero conducen a diferentes resultados. Si el resultado de la prueba 1404A es positivo (en otras palabras, si el técnico no puede llegar antes del final del intervalo de tiempo concertado) la tarea no es factible para el técnico (resultado 1413), y entonces debe serle asignada otra tarea. Si el técnico no va a llegar ni demasiado pronto ni demasiado tarde (los resultados de las pruebas 1403A y 1404A son negativos), entonces se lleva a cabo una prueba (etapa 1405) para averiguar si la tarea puede terminarse antes de la última hora a la que puede iniciarse la pausa. Si el resultado de esta prueba es positivo, entonces la tarea es factible, y no se requiere ninguna orden de pausa (resultado 1410). No obstante, si la tarea no puede terminarse antes de la última hora a la que debe efectuarse una pausa (el resultado de la prueba 1405 es negativo), entonces se efectúa la siguiente prueba (etapa 1406), para determinar si todavía es demasiado temprano para que el técnico efectúe la pausa de inmediato. Si el resultado de la prueba es positivo, entonces la tarea es factible, pero la pausa debe efectuarse durante la tarea (resultado 1411), debido a que el resultado de la prueba 1405 fue negativo, y, por lo tanto, la tarea no puede terminarse antes de que acabe el período dentro del cual debe efectuarse la pausa. No obstante, si ya se ha iniciado el intervalo de tiempo dentro del cual debe efectuarse la pausa (prueba 1406 negativa), se efectúa otra prueba (etapa 1408) para determinar si el técnico (en caso de que éste tuviera que efectuar la pausa de inmediato) todavía podría empezar la tarea antes del fin del intervalo de tiempo concertado. Si el resultado es positivo (es decir, la tarea es factible si la pausa se efectúa antes de la misma), se ordena al técnico que efectúe la pausa y luego lleve a cabo la tarea (resultado 1412). Sin embargo, si la respuesta a la prueba 1408 es negativa, entonces la tarea no es factible (resultado 1413). Esto es debido a que la pausa no puede terminar antes de la última hora antes de la cual la tarea debe iniciarse, y viceversa.

Si el resultado de la prueba 1403a (¿llegará el técnico demasiado temprano para la hora concertada?) es positivo, entonces se ejecutará la prueba 1406a (análoga a la prueba 1406). No obstante, en este caso, si el intervalo de tiempo de la pausa y el intervalo de tiempo concertado no se han iniciado (1406a es positivo), entonces la tarea no es factible (resultado 1413). Si el intervalo de tiempo de la pausa ya se ha iniciado (1406a negativo), entonces se lleva a cabo otra prueba 1407 para determinar si, al final de la pausa del técnico, el intervalo de tiempo concertado ya se habrá iniciado. Si ello no es así, entonces, de nuevo, la tarea no es factible en ese momento (resultado 1413). Esto no significa que el técnico no pueda llevar a cabo la tarea, sino simplemente que ésta no puede ser su siguiente tarea. La siguiente prueba, 1408, es la misma que la de la situación anterior. Mediante esta prueba se determina si, cuando se efectúa la pausa, la tarea puede empezar antes del final del intervalo de tiempo concertado. El resultado de esta prueba será o bien que la tarea es factible y que la pausa debe efectuarse antes que la tarea (resultado 1412), o bien que la tarea no es factible, debiéndose concertar otra tarea (resultado 1413).

Finalmente, si el resultado de la prueba 1402a es negativo (es decir, la tarea no tiene una hora concertada) se lleva a cabo una prueba 1405a, análoga a la prueba 1405, para determinar si la tarea puede terminar antes del fin del intervalo de tiempo dentro del cual debe efectuarse la pausa. Si el resultado es positivo, entonces la tarea es factible y no se requieren instrucciones para la pausa (resultado 1410); en caso contrario, se efectúa otra prueba (1409) para determinar si el técnico llegará a la tarea antes del inicio del intervalo de tiempo de la pausa. Si esto no es así (el resultado 1409 es negativo), entonces se ordena al técnico que efectúe la pausa antes de iniciar la tarea (resultado 1412). De lo contrario, se ordena al técnico que efectúe la pausa durante la tarea (resultado 1411).

Volviendo a la Figura 12, en la etapa 1208, si mediante el procedimiento de la Figura 13 se halla una tarea adecuada (resultados 1305, 1307, 1308), esta tarea se asigna al técnico (etapa 1213), junto con cualquier otra instrucción generada en la prueba de factibilidad (Figura 14) como, por ejemplo, efectuar una pausa planificada antes de la tarea (1412) o durante la tarea (1411). Sin embargo, si no se halla ninguna tarea válida (resultado 1309), entonces se efectúa una prueba para averiguar si puede efectuarse una pausa (etapa 1209). Si no hay ninguna pausa planificada, el técnico no tiene trabajo y se le ordena que entre en contacto con el supervisor para obtener instrucciones (etapa 1214), ya sea para ser autorizado para terminar el trabajo del día o bien para esperar nuevas instrucciones, por ejemplo, en caso de que se introduzca una nueva tarea o que ésta entre en su ventana concertada.

Si puede efectuarse una pausa (etapa 1209), entonces se efectúa una prueba (etapa 1210) para averiguar si en caso de que haya una ausencia planificada que todavía no deba empezar, dicha ausencia podría efectuarse inmediatamente después de la pausa. En esta prueba, se determina si para cuando haya terminado el período de pausa, habrá empezado la ausencia. (Debe observarse que si la ausencia ya ha empezado, el resultado de la prueba 1203 habrá sido negativo, por consiguiente, en lugar de la prueba 1210, se habrá efectuado la prueba 1204.) Dependiendo del resultado de esta prueba (etapa 1210), el técnico recibe la orden de efectuar sólo la pausa (etapa 1215), permaneciendo la ausencia en su planificación para ser efectuada más adelante; o de efectuar la ausencia y la pausa a la vez (etapa 1212). Si no hay ninguna ausencia planificada (el resultado de la prueba 1202 es negativo), entonces la respuesta a la pregunta de la etapa 1210 será por supuesto siempre negativa y, por este motivo, el resultado 1212 no es pertinente.

Una vez que se ha asignado una tarea, con o sin pausa (resultados 1211, 1212, 1213 ó 1215), o se ha tomado la decisión de que no puede asignarse (etapa 1214) ninguna tarea ni otra actividad como, por ejemplo, una ausencia o pausa, entonces se dan al técnico las instrucciones que correspondan. Las instrucciones son generadas por una unidad de generación de mensajes 48. Ésta puede generar una pantalla de asignación para su utilización por la persona expedidora, para proporcionar las instrucciones al técnico T, o puede transmitir un mensaje de datos directamente al microteléfono del técnico (p.ej, H1) a través del enlace de comunicaciones C. La información de planificación revisada se almacena en las bases de datos 42, 43, 44 (etapa 1216). Para el registro del técnico 43, esta información indica la situación actual del técnico y la hora de finalización prevista (es decir, la hora a la que se espera que el técnico vuelva a ponerse en línea para solicitar nuevas instrucciones). En general, esta hora será la suma del tiempo de desplazamiento hasta la nueva tarea, la duración esperada de la tarea y la duración de todas las ausencias y pausas que se hayan asignado.

\newpage

Asimismo, se actualizará la planificación 42. Si la tarea asignada fue la que se planificó para el técnico que estaba en línea, entonces simplemente se suprime esta entrada por haber sido asignada. Si luego se planifica otra tarea para el técnico, y dicha tarea asignada procede de la planificación de otro técnico, entonces esa entrada debe suprimirse de la planificación de otro técnico. El resto de entradas de la planificación de ese técnico se etiquetan como "inexactas", puesto que se planifican partiendo del supuesto de que el técnico efectuará primero la tarea que actualmente ha sido asignada a otro. Del mismo modo, todas las entradas del resto de la planificación del técnico en línea también se marcan como inexactas por la misma razón. Cualquier tarea etiquetada como "inexacta" se considera que ya no está planificada, porque no se sabe con exactitud si el técnico planificado en un principio todavía podrá llevarla a cabo. Al seleccionar tareas para asignarlas a otros técnicos, puede darse a las entradas "inexactas" una prioridad más alta que a las tareas etiquetadas como "pendientes", puesto que existe un mayor riesgo de incumplimiento en las primeras si éstas no son asignadas.

Las entradas al sistema como, por ejemplo, las nuevas tareas a añadir a las planificaciones o los técnicos que comunican la finalización de las tareas, que tienen lugar mientras se lleva a cabo el procedimiento de generación de planificaciones iniciales de las Figuras 5 a 10, harán que la planificación inicial sea parcialmente incorrecta para cuando se haya creado la planificación. Las Figuras 15, 16 y 17 son líneas horarias que ilustran tres procedimientos para tratar dichas entradas.

En estas tres Figuras, dichas entradas se indican mediante las referencias 1, 1a, y las salidas como, por ejemplo, las instrucciones para los técnicos en respuesta a dichas entradas, mediante las referencias 2, 2a. El procedimiento de generación de planificaciones iniciales se indica mediante las referencias 3 y 3a, y el procedimiento de modificación de planificaciones, mediante las referencias 4 y 4a. Se observará que, en general, los dos procedimientos 3 y 4 tienen lugar en paralelo, proporcionando el procedimiento de generación de planificaciones iniciales 3 una entrada para el siguiente ciclo del procedimiento de modificación 4a.

En cada caso, las entradas 1 que se producen mientras el procedimiento de generación inicial no está funcionando se procesan según el procedimiento de modificación de planificaciones 4, y se generan todas las salidas necesarias 2. Las entradas se proporcionan también a la siguiente ejecución del generador de planificaciones iniciales 3.

En la Figura 15, el procedimiento de modificación de planificaciones 4 se suspende durante el procedimiento de generación de planificaciones iniciales 3. Las entradas 1a que se producen mientras se está ejecutando el procedimiento de generación inicial 3 no se procesan de inmediato según el procedimiento de modificación actual 4, sino que se almacenan en una memoria tampón 5 hasta que haya finalizado el procedimiento 3, y luego se procesan según el procedimiento de modificación 4a basándose en la nueva planificación inicial, proporcionando una salida 2a.

Como alternativa, en la Figura 16, se genera una salida 2a de forma inmediata, al recibir una entrada 1a, utilizando el procedimiento de modificación 4 que utiliza los datos existentes, pero la entrada 1a también es almacenada en memoria tampón para proporcionar una entrada al nuevo procedimiento de modificación 4a una vez terminada la planificación inicial 3. Esto tiene la ventaja de proporcionar una respuesta rápida 2, mientras que la disposición de la Figura 15 tiene la ventaja de utilizar una planificación inicial más reciente para generar la respuesta 2a. La selección de una u otra disposición depende del retardo aceptable entre una entrada 1a y una salida 2a.

Si se proporcionan datos 1b que exigen una considerable modificación de la planificación inicial, hecho que determina que las soluciones 3, 4 generadas utilizando la planificación inicial existente dejen de ser válidas, el procedimiento de modificación de planificaciones 4 y el procedimiento de generación de planificaciones iniciales 3 se suspenden (si se están ejecutando en ese momento), y el procedimiento de generación de planificaciones iniciales vuelve a iniciarse (3a) con los nuevos datos. Las entradas 2a recibidas durante la ejecución del procedimiento reiniciado 3a se almacenan en memoria tampón (5) hasta que se genera la nueva planificación.

Claims (26)

1. Dispositivo para asignación de tareas destinado a asignar recursos a tareas, estando adaptado el dispositivo de asignación de tareas para comunicarse con los terminales asociados a dichos recursos, comprendiendo dicho dispositivo para asignación de tareas:

unos medios de entrada para proporcionar información relativa a las tareas a asignar y los recursos disponibles para llevar a cabo las tareas,

unos medios de generación de planificaciones para asignar los recursos a las tareas, generando de ese modo, para cada recurso, una planificación inicial,

un sistema de almacenamiento para almacenar las planificaciones iniciales y las planificaciones iniciales modificadas, estando almacenadas cada una de dichas planificaciones en forma de una pluralidad de tareas que se debe utilizar para determinar una secuencia de tareas que debe llevar a cabo un recurso,

unos medios de actualización para recibir, desde los medios de entrada, información actualizada relativa a las tareas y recursos, caracterizado porque comprende

unos medios de modificación dispuestos para acceder al sistema de almacenamiento para modificar la planificación inicial de por lo menos un primer recurso, en respuesta a dicha información actualizada, y para almacenar dicha planificación inicial modificada en el sistema de almacenamiento, de manera que pueden llevarse a cabo cambios en las planificaciones iniciales, en respuesta a dicha información actualizada, independientemente de los medios de generación de planificaciones.

2. Dispositivo según la reivindicación 1, en el que los medios de generación están destinados a generar periódicamente planificaciones iniciales según los datos recibidos por los medios de entrada, y los medios de modificación están destinados a efectuar cambios a las planificaciones iniciales, en respuesta a la recepción de datos entre dicha generación periódica de las planificaciones iniciales.

3. Dispositivo según la reivindicación 1, en el que los medios de generación de planificaciones comprenden:

una primera etapa determinista (30);

unos medios para seleccionar tareas que deben ser planificadas por la primera etapa;

y una segunda etapa de optimización (31) para planificar el resto de tareas;

caracterizado porque la segunda etapa incluye unos medios para tratar como fijas las tareas planificadas por la primera etapa.

4. Dispositivo según la reivindicación 3, en el que los medios para seleccionar tareas a planificar por la primera etapa están destinados a seleccionar grupos de tareas asociadas que conciernen a más de uno de los recursos, o a crear una secuencia de tareas.

5. Dispositivo según la reivindicación 3 ó 4, en el que la segunda etapa funciona según un procedimiento estocástico.

6. Dispositivo según la reivindicación 5, en el que el procedimiento estocástico es un procedimiento de reasociación simulada.

7. Dispositivo según la reivindicación 3, 4, 5 ó 6, en el que los medios de generación de planificaciones comprenden una tercera etapa de postoptimización (39), que comprende medios para analizar las planificaciones creadas por la segunda etapa, medios para determinar las planificaciones que necesitan optimizarse más y medios para introducir dichas planificaciones en otra iteración de la segunda etapa para ser más optimizadas, teniendo la otra iteración de la segunda etapa medios para tratar las planificaciones que no se ha determinado que sean fijas.

8. Dispositivo según cualquiera de las reivindicaciones anteriores, en el que los medios de modificación de planificaciones comprenden una pluralidad de medios de selección, cada uno de los cuales se utiliza para evaluar de forma alternativa la pluralidad de tareas en espera de ser efectuadas, para determinar si está disponible una tarea de una prioridad dada adecuada para ser llevada a cabo por el primer recurso, y asignar dicha tarea al primer recurso, estando destinados los medios de selección a determinar tareas cuya prioridad decrece secuencialmente, de manera que en vez de las tareas de prioridad más baja se asignan preferentemente las tareas de alta prioridad de la planificación inicial optimizada para el primer recurso.

9. Dispositivo según la reivindicación 8, en el que por lo menos uno de los medios de selección comprende primeros medios de evaluación para determinar si la planificación inicial optimizada del primer recurso incluye una tarea de la prioridad dada, y seleccionar dicha tarea si está presente, y segundos medios de evaluación que pueden utilizarse si la planificación inicial optimizada del primer recurso no contiene dicha tarea, para determinar si existe alguna tarea que no haya sido planificada y, en tal caso, seleccionarla.

10. Dispositivo según cualquiera de las reivindicaciones anteriores, en el que los medios de modificación de planificaciones comprenden unos medios para determinar los recursos que tienen características relacionadas con las del primer recurso, y destinados a modificar sólo las planificaciones de los recursos que tengan dichas características, en respuesta a la información actualizada.

11. Dispositivo según cualquiera de las reivindicaciones anteriores, en el que además comprende medios (45, 46) para añadir, después de la generación de la planificación inicial optimizada, otras tareas y/o recursos a la pluralidad de tareas y/o recursos a planificar.

12. Procedimiento para asignar una pluralidad de recursos a una pluralidad de tareas, comprendiendo el procedimiento la utilización de un ordenador, y estando adaptado el ordenador para comunicarse con los terminales asociados a los recursos, estando dispuesto dicho ordenador para llevar a cabo las etapas siguientes:

proporcionar información inicial relativa a las tareas a asignar y los recursos disponibles para llevar a cabo las tareas,

generar, para cada recurso, una planificación inicial para asignar los recursos a las tareas, estando almacenada cada una de dichas planificaciones iniciales en forma de una pluralidad de tareas que se debe utilizar para determinar una secuencia de tareas que debe llevar a cabo un recurso;

almacenar las planificaciones iniciales generadas en un sistema de almacenamiento;

proporcionar información actualizada relativa a las tareas y a los recursos:

acceder al sistema de almacenamiento para modificar la planificación inicial de por lo menos un primer recurso en respuesta a dicha información actualizada,

almacenar dicha planificación inicial en el sistema de almacenamiento,

de manera que pueden efectuarse cambios en las planificaciones iniciales, en respuesta a dicha información actualizada, independientemente del procedimiento de generación de las planificaciones iniciales.

13. Procedimiento según la reivindicación 12, en el que las planificaciones iniciales se generan de forma periódica, y las planificaciones iniciales generadas de este modo se modifican en respuesta a la recepción de datos entre dicha generación periódica de las planificaciones iniciales.

14. Procedimiento según la reivindicación 13, en el que durante la generación periódica de las planificaciones iniciales se suspende el procedimiento de modificación, siendo retenida la información actualizada hasta que se generan las nuevas planificaciones iniciales, y luego utilizada para modificar las planificaciones iniciales cuando la generación de las mismas ha finalizado.

15. Procedimiento según la reivindicación 13, en el que durante la generación de las planificaciones iniciales el procedimiento de modificación continúa, siendo las planificaciones modificadas de esta forma introducidas como modificaciones de las planificaciones iniciales cuando la generación de las mismas ha finalizado.

16. Procedimiento según la reivindicación 12, 13, 14 ó 15, en el que el procedimiento de generación de planificaciones se inicia si se ha recibido un elemento de datos de actualización importante.

17. Procedimiento según la reivindicación 12, 13, 14, 15 ó 16, en el que la función de generación de planificaciones comprende una primera etapa determinista (30) para planificar tareas seleccionadas, y una segunda etapa de optimización (31) para planificar el resto de tareas, y porque la segunda etapa trata como fijas las tareas planificadas por la primera etapa.

18. Procedimiento según la reivindicación 17, en el que se seleccionan grupos de tareas asociadas que conciernen a más de uno de los recursos o que forman una secuencia de tareas, para ser planificadas por la primera etapa determinista.

19. Procedimiento según la reivindicación 17 ó 18, en el que la segunda etapa funciona según un procedimiento estocástico.

20. Procedimiento según la reivindicación 19, en el que el procedimiento estocástico es un procedimiento de reasociación simulada.

\newpage

21. Procedimiento según la reivindicación 17, 18, 19 ó 20, en el que la función de generación de planificaciones comprende una tercera etapa de postoptimización (39) en la que las planificaciones creadas por la segunda etapa son analizadas para determinar las planificaciones que necesitan ser más optimizadas, y dichas planificaciones son introducidas en otra iteración de la segunda etapa para ser más optimizadas, tratando la otra iteración de la segunda etapa como fijas las planificaciones que no se ha determinado que lo son.

22. Procedimiento según cualquiera de las reivindicaciones 12 a 21, en el que el procedimiento de modificación de planificaciones comprende una pluralidad de etapas de selección, en cada una de las cuales se evalúa la pluralidad de tareas en espera de ser llevadas a cabo, para determinar si está disponible una tarea de una prioridad dada adecuada para ser llevada a cabo por el primer recurso, y en caso afirmativo, asignar dicha tarea al primer recurso, estando destinadas cada una de las etapas de selección a determinar tareas cuya prioridad decrece secuencialmente, de modo que se asigna preferentemente una tarea de alta prioridad en vez de una de menor prioridad, tanto si la tarea de alta prioridad se halla en la planificación inicial optimizada para el primer recurso, como si no.

23. Procedimiento según la reivindicación 22, en el que por lo menos una de las etapas de selección determina primero si la planificación inicial optimizada del recurso incluye una tarea de la prioridad dada, y selecciona dicha tarea si está presente o, si la planificación inicial optimizada del recurso no contiene dicha tarea, determina si existe alguna tarea que no haya sido planificada, y selecciona dicha tarea si está presente.

24. Procedimiento según cualquiera de las reivindicaciones 12 a 22, en el que la función de modificación de planificaciones indica los recursos que tienen características relacionadas con las del primer recurso, y modifica sólo las planificaciones de los recursos que tienen dichas características.

25. Procedimiento según cualquiera de las reivindicaciones 12 a 23, en el que pueden añadirse otras tareas a la pluralidad de tareas a efectuar después de la generación de la planificación inicial optimizada.

26. Ordenador para asignar una pluralidad de tareas a una pluralidad de recursos, comprendiendo dicho ordenador una unidad central de procesado (22), una memoria (24), un dispositivo de entrada (21) y un dispositivo de salida (23), conteniendo dicha memoria un programa para controlar el ordenador y estando destinada a almacenar una planificación inicial, basándose en la disponibilidad prevista de recursos, prioridades de tareas e idoneidad de las tareas para los recursos, caracterizado porque lleva a cabo las siguientes funciones:

cuando un recurso queda disponible, evaluar la pluralidad de tareas en espera de ser efectuadas, para determinar si está disponible alguna tarea de alta prioridad adecuada para ser llevada a cabo por el recurso, y asignarla al recurso;

si no hay ninguna de dichas tareas disponible para ser llevada a cabo por el recurso, evaluar la siguiente tarea de la planificación inicial optimizada del recurso para determinar si puede ser llevada a cabo, y asignarla al recurso en caso de que pueda ser llevada a cabo;

si dicha siguiente tarea no está disponible para ser llevada a cabo por el recurso, asignar al recurso una tarea de prioridad más baja de la pluralidad de tareas.