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>';
