Planificación de tareas
Last updated
Last updated
A continuación mostraremos dos problemas relativos a la forma óptima de planificar tareas en una sola máquina.
En el primero, se trata de minimizar el tiempo medio que invierte cada tarea en el sistema.
Y en el segundo, las tareas tienen un plazo fijo de ejecución y cada tarea aporta un beneficio sólo si dicha tarea se acaba antes de llegar su plazo. Se trata pues de obtener el máximo beneficio.
Ambos problemas se pueden resolver empleando algoritmos voraces.
Un único servidor, como por ejemplo, un procesador, un surtidor de gasolina o un cajero de un banco, tiene que atender n clientes que llegan todos juntos al sistema. El tiempo de servicio para cada cliente se conoce de antemano: el cliente requerirá un tiempo ti con 1 ≤ i ≤ n.
El problema de minimización del tiempo de espera consiste en minimizar el tiempo medio invertido por cada cliente en el sistema. Dado que el número n de clientes está predeterminado, esto equivale a minimizar el tiempo total invertido en el sistema por todos los clientes.
En otras palabras, deseamos minimizar (tiempo en el sitema para el cliente i)
Candidatos: los clientes
La solución se puede expresar como una secuencia de decisiones <x1,x2,…,xn> donde x1 es el cliente que se atenderá en primer lugar, x2 es el cliente que se servirá en segundo lugar, … y xn recogerá el cliente que será atendido en último lugar. Como se puede apreciar, todos los candidatos del problema (los clientes) pasan a formar parte de la solución, lo relevante aquí es el orden que ocupan en la solución.
En cada etapa se seleccionará aquel cliente no atendido con menor tiempo de servicio. Supongamos que después de planificar el servicio para los clientes x1 x2…xk se añade al cliente j. El incremento del tiempo T en esta fase es igual a la suma de los tiempos de servicio para los clientes desde el x1 hasta el xk, dado que esto es lo que tiene que esperar el cliente j antes de recibir el servicio, más tj que es el tiempo necesario para servir al cliente j. Para minimizar esto, dado que un algoritmo voraz nunca reconsidera sus decisiones anteriores, lo único que podemos hacer es minimizar tj.
El criterio de selección propuesto hace que todas decisiones sean factibles. La función factible tendrá, por tanto, tratamiento vacío.
Habremos encontrado la solución cuando hayamos seleccionado todos los clientes.
Sea n=3 y t[1..3]={ 5, 10, 3 }
El algoritmo voraz es muy sencillo: en cada paso se añade al final de la planificación al cliente que requiera menor tiempo de servicio de entre los que quedar por atender.
Esta estrategia voraz siempre proporciona la solución óptima para el problema de minimización del tiempo de espera.
Sea un conjunto de n tareas que hay que realizar, cada una de las cuales requiere un tiempo unitario. En cualquier instante t podemos ejecutar únicamente una tarea. La tarea i, 1 ≤ i ≤ n, nos produce un beneficio bi (bi>0) sólo en el caso de que sea ejecutada en un instante anterior a di.
El problema de planificación de tareas con plazo fijo consiste en encontrar una secuencia de realización de las tareas que maximice el beneficio total.
Candidatos: las tareas
La solución se puede expresar como una secuencia de decisiones <x1,x2,…,xk> donde k indica el número de tareas que se realizan dentro de su plazo siendo x1 la tarea que se realiza en primer lugar (del instante 0 al instante 1), x2 es por tanto la tarea que se realiza en segundo lugar y así sucesivamente
En cada etapa del algoritmo se selecciona aquella tarea con mayor beneficio.
La función factible comprobará que la solución parcial ampliada con esa nueva tarea y reordenada con ese orden creciente de plazo, sea una solución parcial ampliada en la que ninguna tarea se ejecute fuera de su plazo.
El bucle voraz ha de tener n iteraciones, tantas como tareas.
Esta estrategia voraz siempre proporciona la solución óptima para el problema de planificación de tareas con plazo fijo.
Podemos utilizar una técnica diferente para calcular si un conjunto de tareas es factible: cuando es el turno de considerar la tarea i, se la incorpora a la secuencia lo más tarde posible siempre que sea antes de su vencimiento
3ª etapa: rechazada la tarea 3
Por ser, en general, simples, a veces se utilizan los algoritmos voraces como heurísticos (algoritmos de aproximación) para obtener soluciones subóptimas (cercanas a las óptimas) cuando esto es suficiente.
Existen problemas donde todos los algoritmos exactos conocidos emplean un tiempo exponencial. Como éstos no son utilizables para ejemplares de gran tamaño, sólo podemos emplear métodos aproximados.
En estos casos, un algoritmo voraz tiene la posibilidad, pero no la certeza, de encontrar la solución óptima.
