PrEDA: minimizando tiempo en el sistema con varios agentes

Continuando con el post anterior, y de nuevo a modo de code-kata, vengo a traer el siguiente paso al algoritmo. Si en el post anterior teníamos cómo minimizar el tiempo en el sistema de varias tareas con un sólo agente, ahora le añadimos la posibilidad de tener varios.

Seguimos teniendo una estrategia voraz para resolver el órden en que se ejecutan las tareas. También voraz para asignar a los agentes dichas tareas, porque se seleccionan las tareas sin tener que volver atrás en la selección. La estrategia de selección es ordenar las tareas por orden creciente de tiempo necesario, y vamos alternando entre los agentes para distribuirles las tareas, distribuyendo también así la carga entre los agentes.

Igual que en la versión anterior, suponemos que todas las tareas tienen el mismo beneficio o importancia, no habría ninguna razón para priorizar tareas de más tiempo. La prioridad la tendrán entonces las tareas de menos tiempo en este caso..

El código

Un poco más elaborado que el anterior:

<?php 

define('NUMBER_OF_TASKS', 30);
define('NUMBER_OF_AGENTS', 3);

$tasksTime = array();

for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) { 
    $tasksTime[$i] = rand(1, 10); 
} 
$totalTimeClientsWaiting = printTasks($tasksTime, $maxTimeWaiting); 
echo 'TIME IN SYSTEM OF TASKS: '.$totalTimeClientsWaiting.' WITH A MAX WAITING TIME OF '.$maxTimeWaiting.PHP_EOL; 

asort($tasksTime); 
echo 'Tasks sorted, asigning to agents..'.PHP_EOL; 

echo 'Asigning to one agent only..'.PHP_EOL; 
$totalTimeClientsWaiting = printTasks($tasksTime, $maxTimeWaiting); 
echo 'TIME IN SYSTEM OF TASKS: '.$totalTimeClientsWaiting.' WITH A MAX WAITING TIME OF '.$maxTimeWaiting.PHP_EOL;

echo 'Asigning to '.NUMBER_OF_AGENTS.' agents..'.PHP_EOL; 
$agentsTasks = array(); 
$ptrAgent = 0; 
foreach ($tasksTime as $task => $time) {
    $agentsTasks[$ptrAgent][$task] = $time;
    ++$ptrAgent;
    if ($ptrAgent == NUMBER_OF_AGENTS) {
        $ptrAgent = 0;
    }
}
$totalTimeWaiting = 0;
foreach ($agentsTasks as $number => $agentTasks) {
    echo 'Tasks for agent number '.$number.PHP_EOL;
    $timeSpent = printTasks($agentTasks, $maxTimeWaiting);
    $totalTimeWaiting = $totalTimeWaiting + $timeSpent;
    echo 'TIME IN SYSTEM OF TASKS: '.$timeSpent.' WITH A MAX WAITING TIME OF '.$maxTimeWaiting.PHP_EOL;
}
echo 'TOTAL TIME IN SYSTEM OF TASKS WITH '.NUMBER_OF_AGENTS.' AGENTS: '.$totalTimeWaiting.PHP_EOL;

function printTasks($tasksTime, &$maxTimeWaiting)
{
    $total = $maxTimeWaiting = 0;
    $tasksRemaining = count($tasksTime);

    echo 'Tasks:  ';
    foreach ($tasksTime as $task => $time) {
        echo str_pad($task, 4, ' ');
        $total = $total + $time * $tasksRemaining;
        $maxTimeWaiting = $maxTimeWaiting + $time;
        --$tasksRemaining;
    }
    echo PHP_EOL.'Time:   ';
    foreach ($tasksTime as $task => $time) {
        echo str_pad($time, 4, ' ');
    }
    echo PHP_EOL;

    return $total;
}

He marcado en negrita las variables principales. Siguiéndolas se puede ver cómo almacenar los tiempos de espera en el sistema de todas las tareas ($total) o el máximo tiempo que espera la última tarea ($maxTimeWaiting). Esta función printTasks simplemente pinta por pantalla calculando estos tiempos. No es necesario ningún cálculo extra porque la estrategia de selección es muy simple: sólo hay que ordenar las tareas por tiempo que consumen y elegir crecientemente en orden de tiempo.

Es curioso ver cómo se reduce considerablemente el tiempo, y se equipara la carga de trabajo entre los agentes. No habiendo así ninguno de los agentes cargado en exceso, ni ninguno de los agentes ocioso.