Lawler's Algorithm Implementation Assistance
- by Richard Knop
Here is my implemenation of Lawler's algorithm in PHP (I know... but I'm used to it):
<?php
$jobs = array(1, 2, 3, 4, 5, 6);
$jobsSubset = array(2, 5, 6);
$n = count($jobs);
$processingTimes = array(2, 3, 4, 3, 2, 1);
$dueDates = array(3, 15, 9, 7, 11, 20);
$optimalSchedule = array();
foreach ($jobs as $j) {
$optimalSchedule[] = 0;
}
$dicreasedCardinality = array();
for ($i = $n; $i >= 1; $i--) {
$x = 0;
$max = 0;
// loop through all jobs
for ($j = 0; $j < $i; $j++) {
// ignore if $j already is in the $dicreasedCardinality array
if (false === in_array($j, $dicreasedCardinality)) {
// if the job has no succesor in $jobsSubset
if (false === isset($jobs[$j+1])
|| false === in_array($jobs[$j+1], $jobsSubset)) {
// here I find an array index of a job with the maximum due date
// amongst jobs with no sucessor in $jobsSubset
if ($x < $dueDates[$j]) {
$x = $dueDates[$j];
$max = $j;
}
}
}
}
// move the job at the end of $optimalSchedule
$optimalSchedule[$i-1] = $jobs[$max];
// decrease the cardinality of $jobs
$dicreasedCardinality[] = $max;
}
print_r($optimalSchedule);
Now the above returns an optimal schedule like this:
Array
(
[0] => 1
[1] => 1
[2] => 1
[3] => 3
[4] => 2
[5] => 6
)
Which doesn't seem right to me. The problem might be with my implementation of the algorithm because I am not sure I understand it correctly. I used this source to implement it:
http://www.google.com/books?id=aSiBs6PDm9AC&pg=PA166&dq=lawler%27s+algorithm+code&lr=&hl=sk&cd=4#v=onepage&q=&f=false
The description there is a little confusing. For example, I didn't quite get how is the subset D defined (I guess it is arbitrary).
Could anyone help me out with this? I have been trying to find some sources with simpler explanation of the algorithm but all sources I found were even more complicated (with math proofs and such) so I am stuck with the link above.
Yes, this is a homework, if it wasn't obvious.
I still have few weeks to crack this but I have spent few days already trying to get how exactly this algorithm works with no success so I don't think I will get any brighter during that time.
