title: Lawler's Algorithm Implementation Assistance
body: <p>UPDATE2:</p>
  
  <p>I think I got it now:</p>
  
  <pre><code>&lt;?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 =&gt; array('processingTime' =&gt; 2,
                           'dueDate'        =&gt; 3),
                2 =&gt; array('processingTime' =&gt; 3,
                           'dueDate'        =&gt; 15),
                3 =&gt; array('processingTime' =&gt; 4,
                           'dueDate'        =&gt; 9),
                4 =&gt; array('processingTime' =&gt; 3,
                           'dueDate'        =&gt; 16),
                5 =&gt; array('processingTime' =&gt; 5,
                           'dueDate'        =&gt; 12),
                6 =&gt; array('processingTime' =&gt; 7,
                           'dueDate'        =&gt; 20),
                7 =&gt; array('processingTime' =&gt; 5,
                           'dueDate'        =&gt; 27),
                8 =&gt; array('processingTime' =&gt; 6,
                           'dueDate'        =&gt; 40),
                9 =&gt; array('processingTime' =&gt; 3,
                           'dueDate'        =&gt; 10));
  // precedence constrainst, i.e job 2 must be completed before job 5 etc
  $successors = array(2=&gt;5,
                      7=&gt;9);
  $n = count($jobs);
  $optimalSchedule = array();
  
  for ($i = $n; $i &gt;= 1; $i--) {
  
      // jobs not required to precede any other job
      $arr = array();
      foreach ($jobs as $k =&gt; $v) {
  
          if (false === array_key_exists($k, $successors)) {
              $arr[] = $k;
          }
  
      }
  
      // calculate total processing time
      $totalProcessingTime = 0;
      foreach ($jobs as $k =&gt; $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 &lt; $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 =&gt; $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 =&gt; $v) {
      $optimalSchedule[$k]['tardiness'] = 0;
      $j = 0;
      foreach ($optimalSchedule as $k2 =&gt; $v2) {
          if ($j &lt;= $i) {
              $optimalSchedule[$k]['tardiness'] += $v2['processingTime'];
          }
          $j++;
      }
      $i++;
  }
  
  echo '&lt;pre&gt;';
  print_r($optimalSchedule);
  echo '&lt;/pre&gt;';
  </code></pre>
  
  <p>UPDATE:</p>
  
  <p>So here are some more sources with the explanation of Lawler's algorithm I found:</p>
  
  <ul>
  <li><a href="http://www.google.com/books?id=aSiBs6PDm9AC&amp;pg=PA166&amp;dq=lawler%27s+algorithm+code&amp;lr=&amp;hl=sk&amp;cd=4#v=onepage&amp;q=&amp;f=false" rel="nofollow noreferrer">Source 1</a></li>
  <li><a href="http://www.google.com/books?id=Dw5e12aB7owC&amp;pg=PA360&amp;dq=lawler+algorithm+scheduling&amp;lr=&amp;hl=sk&amp;cd=1#v=onepage&amp;q=lawler%20algorithm%20scheduling&amp;f=false" rel="nofollow noreferrer">Source 2</a></li>
  <li><a href="http://www.google.com/books?id=iDtxXdSW5DgC&amp;pg=PA428&amp;dq=lawler%27s+algorithm+code&amp;lr=&amp;hl=sk&amp;cd=119#v=onepage&amp;q=&amp;f=false" rel="nofollow noreferrer">Source 3</a> (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)</li>
  </ul>
  
  <hr>
  
  <p>Here is my implemenation of Lawler's algorithm in PHP (I know... but I'm used to it):</p>
  
  <pre><code>&lt;?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 &gt;= 1; $i--) {
  
      $x = 0;
      $max = 0;
  
      // loop through all jobs
      for ($j = 0; $j &lt; $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 &lt; $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);
  </code></pre>
  
  <p>Now the above returns an optimal schedule like this:</p>
  
  <pre><code>Array
  (
      [0] =&gt; 1
      [1] =&gt; 1
      [2] =&gt; 1
      [3] =&gt; 3
      [4] =&gt; 2
      [5] =&gt; 6
  )
  </code></pre>
  
  <p>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 <a href="http://www.google.com/books?id=aSiBs6PDm9AC&amp;pg=PA166&amp;dq=lawler%27s+algorithm+code&amp;lr=&amp;hl=sk&amp;cd=4#v=onepage&amp;q=&amp;f=false" rel="nofollow noreferrer">this</a> source to implement it.</p>
  
  <p>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).</p>
  
  <p>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.</p>
  
  <p>Yes, this is a homework, if it wasn't obvious.</p>
  
  <p>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.</p>