UPDATE2:
I think I got it now:
<?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>';
UPDATE:
So here are some more sources with the explanation of Lawler's algorithm I found:
- Source 1
- Source 2
- Source 3 (this is a really good source but one crucial page is missing in the preview + this book is not available at amazon or anywhere else bacause it is limited to China - if it were I would have bought it already)
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.
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.