I had some troubles implementing Lawler's algorithm but thanks to SO and a bounty of 200 reputation I finally managed to write a working implementation:

http://stackoverflow.com/questions/2466928/lawlers-algorithm-implementation-assistance

I feel like I'm using too many variables and loops there though so I am trying to refactor the code. It should be simpler and shorter yet remain readable.

Does it make sense to make a class for this? Any advice or even help with refactoring this piece of code is welcomed:

<?php

/*
 * @name Lawler's algorithm PHP implementation
 * @desc This algorithm calculates an optimal schedule of jobs to be
 *       processed on a single machine (in reversed order) while taking
 *       into consideration any precedence constraints.
 * @author Richard Knop
 *
 */

$jobs = array(1 => array('processingTime' => 2,
                         'dueDate'        => 3),
              2 => array('processingTime' => 3,
                         'dueDate'        => 15),
              3 => array('processingTime' => 4,
                         'dueDate'        => 9),
              4 => array('processingTime' => 3,
                         'dueDate'        => 16),
              5 => array('processingTime' => 5,
                         'dueDate'        => 12),
              6 => array('processingTime' => 7,
                         'dueDate'        => 20),
              7 => array('processingTime' => 5,
                         'dueDate'        => 27),
              8 => array('processingTime' => 6,
                         'dueDate'        => 40),
              9 => array('processingTime' => 3,
                         'dueDate'        => 10));
// precedence constrainst, i.e job 2 must be completed before job 5 etc
$successors = array(2=>5,
                    7=>9);
$n = count($jobs);
$optimalSchedule = array();

for ($i = $n; $i >= 1; $i--) {

    // jobs not required to precede any other job
    $arr = array();
    foreach ($jobs as $k => $v) {

        if (false === array_key_exists($k, $successors)) {
            $arr[] = $k;
        }

    }

    // calculate total processing time
    $totalProcessingTime = 0;
    foreach ($jobs as $k => $v) {
        if (true === array_key_exists($k, $arr)) {
            $totalProcessingTime += $v['processingTime'];
        }
    }

    // find the job that will go to the end of the optimal schedule array
    $min = null;
    $x = 0;
    $lastKey = null;
    foreach($arr as $k) {
        $x = $totalProcessingTime - $jobs[$k]['dueDate'];
        if (null === $min || $x < $min) {
            $min = $x;
            $lastKey = $k;
        }
    }

    // add the job to the optimal schedule array
    $optimalSchedule[$lastKey] = $jobs[$lastKey];
    // remove job from the jobs array
    unset($jobs[$lastKey]);
    // remove precedence constraint from the successors array if needed
    if (true === in_array($lastKey, $successors)) {
        foreach ($successors as $k => $v) {
            if ($lastKey === $v) {
                unset($successors[$k]);
            }
        }
    }

}

// reverse the optimal schedule array and preserve keys
$optimalSchedule = array_reverse($optimalSchedule, true);

// add tardiness to the array
$i = 0;
foreach ($optimalSchedule as $k => $v) {
    $optimalSchedule[$k]['tardiness'] = 0;
    $j = 0;
    foreach ($optimalSchedule as $k2 => $v2) {
        if ($j <= $i) {
            $optimalSchedule[$k]['tardiness'] += $v2['processingTime'];
        }
        $j++;
    }
    $i++;
}

echo '<pre>';
print_r($optimalSchedule);
echo '</pre>';