PrEDA: priorizando tareas para obtener el máximo de beneficio

Hoy traigo a modo de code-kata otro problema resuelto. Se trata de resolver un problema muy muy común en informática, la gestión de tareas.

En este caso, se trata de aplicar la gestión de tareas, o proyectos, con la condición de obtener el máximo de beneficio. Podríamos gestionar las tareas minimizando el tiempo en el sistema, distribuyendo tareas entre varios agentes.. O podríamos aplicarlo a otros ámbitos como la cosecha de cultivos, en donde habría que priorizar en función al tiempo de putrefacción y beneficio, teniendo en cuenta el tiempo necesario para cada cosecha.

Es decir, en este caso, se trata de obtener el orden óptimo de tareas de forma que se maximize el beneficio. Tenemos entonces una duración de cada tarea, un beneficio, y un tiempo de entrega.

Para resolver este problema, la mejor estrategia es la ramificación y poda. No existe una estrategia voraz, ni de divide y vencerás que podamos usar. Tampoco la vuelta atrás es la mejor solución, porque se trata de obtener la solución óptima en el menor tiempo posible. Entonces, tendremos que generar un árbol de posibilidades, un árbol de combinación de tareas. De forma que mientras que generamos el árbol tenemos que tener en cuenta si las nuevas tareas se pueden añadir debido al tiempo de entrega. Llevaremos una estimación mejor y otra peor, de forma que si la ramificación no es posible, o su estimación mejor no mejora el beneficio de la mejor solución obtenida, entonces podamos dicha ramificación. De igual manera llevamos una cota para ir podando.

Generando tareas aleatorias

Primero generamos unas tareas, con beneficio, duración y tiempo de entrega aleatorios..

<?php

define('NUMBER_OF_TASKS', 9);
$GLOBALS['benefits'] = array();
$GLOBALS['durationTime'] = array();
$GLOBALS['deliveryTime'] = array();
$tasksDone = array();
for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) {
    $GLOBALS['benefits'][$i] = rand(1, 9);
    $GLOBALS['durationTime'][$i] = rand(1, 9);
    $GLOBALS['deliveryTime'][$i] = rand(1, 99);
    $tasksDone[$i] = 0;
}

echo 'Initial optimistic estimation: '.optimisticEstimation($tasksDone).PHP_EOL;
echo 'Initial pessimistic estimation: '.pessimisticEstimation($tasksDone).PHP_EOL;

$GLOBALS['cota'] = pessimisticEstimation($tasksDone);
maximizeBenefitsWithTasks($tasksDone, 1);

echo PHP_EOL
    .'BETTER SOLUTION FOUND: '.implode(', ', $GLOBALS['betterSolution']).PHP_EOL
    .'BENEFIT OF SOLUTION: '.benefits($GLOBALS['betterSolution']).PHP_EOL
    .PHP_EOL
    .'Benefits: '.implode(', ', $GLOBALS['benefits']).PHP_EOL
    .'Duration time: '.implode(', ', $GLOBALS['durationTime']).PHP_EOL
    .'Delivery time: '.implode(', ', $GLOBALS['deliveryTime']).PHP_EOL;

También se calcula la estimación pesimista y optimista con la solución vacía. Entonces, lanzamos el proceso inicial de ramificación con una solución vacia: ninguna tarea seleccionada.

Algoritmo principal

function maximizeBenefitsWithTasks($tasksDone, $order)
{
    echo 'BRANCH ==>> maximizeBenefitsWithTasks('
        .implode(', ', $tasksDone).', $order='.$order.', $cota='.$GLOBALS['cota']
        .')'.PHP_EOL;

    for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) {
        if ($tasksDone[$i] == 0) {
            $tasksDone[$i] = $order;
            writeToScreen($tasksDone);

            if (possibleSolution($tasksDone)) {
                echo 'Optimistic estimation: '.optimisticEstimation($tasksDone).PHP_EOL;
                echo 'Pessimistic estimation: '.pessimisticEstimation($tasksDone).PHP_EOL;

                if (benefits($tasksDone) >= $GLOBALS['cota']) {
                    $GLOBALS['cota'] = benefits($tasksDone);
                    $GLOBALS['betterSolution'] = $tasksDone;
                }

                if ($order + 1 <= NUMBER_OF_TASKS) {
                    if (optimisticEstimation($tasksDone) >= $GLOBALS['cota']) {
                        if (pessimisticEstimation($tasksDone) > $GLOBALS['cota']) {
                            $GLOBALS['cota'] = pessimisticEstimation($tasksDone);
                        }
                        maximizeBenefitsWithTasks($tasksDone, $order + 1);
                    } else {
                        echo 'BOUND!!'.PHP_EOL;
                    }
                }
            } else {
                echo 'BOUND!!'.PHP_EOL;
            }

            $tasksDone[$i] = 0;
        }
    }
}

Como indico anteriormente, se trata de ir ramificando las posibilidades. Ramificaremos si y sólo si dicha ramificación tiene unas estimaciones de mejorar la mejor solución encontrada hasta ahora.

El algoritmo original utilizaría un montículo de máximos. Esto convertiría la función en iterativa.

Funciones auxiliares

function writeToScreen($tasksDone)
{
    echo 'Current tasks order ==>> '.implode(', ', $tasksDone).PHP_EOL;
}

// Check if current is a possible solution.
function possibleSolution($tasksDone)
{
    $timeSpent = 0;

    for ($k = 1; $k <= NUMBER_OF_TASKS; ++$k) {
        for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) {
            if ($tasksDone[$i] == $k) {
                if ($timeSpent + $GLOBALS['durationTime'][$i] <= $GLOBALS['deliveryTime'][$i]) {
                    $timeSpent += $GLOBALS['durationTime'][$i];
                } else {
                    return false;
                }
            }
        }
    }

    return true;
}

// Returns benefits of current tasks order.
function benefits($tasksDone)
{
    $benefits = 0;

    for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) {
        if ($tasksDone[$i] != 0) {
            $benefits += $GLOBALS['benefits'][$i];
        }
    }

    return $benefits;
}

// Only those tasks that can be done just after.
function pessimisticEstimation($tasksDone)
{
    $pessimisticEstimation = 0;
    $timeSpent = 0;

    for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) {
        if ($tasksDone[$i] == 0
        and $timeSpent + $GLOBALS['durationTime'][$i] <= $GLOBALS['deliveryTime'][$i]) {
            $pessimisticEstimation += $GLOBALS['benefits'][$i];
            $timeSpent += $GLOBALS['durationTime'][$i];
        }
    }

    return $pessimisticEstimation;
}

// Sum of remain tasks that can be done just after.
function optimisticEstimation($tasksDone)
{
    $optimisticEstimation = 0;
    $timeSpent = 0;

    for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) {
        if ($tasksDone[$i] != 0) {
            $optimisticEstimation += $GLOBALS['benefits'][$i];
            $timeSpent += $GLOBALS['durationTime'][$i];
        }
    }
    for ($i = 0; $i < NUMBER_OF_TASKS; ++$i) {
        if ($tasksDone[$i] == 0
        and $timeSpent + $GLOBALS['durationTime'][$i] <= $GLOBALS['deliveryTime'][$i]) {
            $optimisticEstimation += $GLOBALS['benefits'][$i];
        }
    }

    return $optimisticEstimation;
}

Aquí tienen especial mención la estimación optimista y pesimista. La estimación pesimista sería simplemente el beneficio de intentar añadir sólo una tarea más, si es que es posible, a la posible ramificación actual. La estimación optimista sería poder hacer todas las tareas que restan, si es que su tiempo de entrega es posible cumplirlo, aplicando cada una justo después de la última tarea.

Terminando

Puedes copiar este script en un fichero .php y ejecutarlo. Deberías ver algo parecido a esto: