Im sure this can be written in a much simpler way. I feel like I’m using many unnecessary loops and variables Could somebody care to help me refactor this piece of code?
I’m trying to make it shorter and simpler but it should still remain readable:
<?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>';
You could abstract the work out to separate functions, so that the work that’s actually being done is easier to digest.
$jobs = jobsList();
$successors = successorsList();
$schedule = calculateSchedule($jobs, $successors);
echo showSchedule($schedule);
The calculateOptimalSchedule function would be be similar:
function calculateSchedule($jobs, $successors)
{
$schedule = array();
for ($i = 0; $i < count($jobs); $i++) {
$independentJobs = independentJobs($jobs, $successors);
$processingTime = processingTime($jobs, $independentJobs);
$job = findSmallestJob($jobs, $processingTime);
moveJobToSchedule($jobs, $schedule, $job, $successors);
}
$schedule = reverseSchedule($schedule);
$schedule = addTardiness($schedule);
return $schedule;
}
The above code would need you to fill in the function parts, and possibly resolve some other issues (such as, referencing arrays by reference for moveJobToSchedule). It would help improve the understandability of the code.
Thanks. I actually decided to make a class out of that messy code:
<?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
*
*/
class LawlersAlgorithm
{
private $jobs;
private $precedenceConstraints;
private $jobsCount;
private $optimalSchedule = array();
private $jobsWithNoSuccessor; // jobs that are not required to precede any other job
private $totalProcessingTime;
public function __construct(array $jobs,
array $precedenceConstraints)
{
$this->jobs = $jobs;
$this->precedenceConstraints = $precedenceConstraints;
$this->jobsCount = count($jobs);
}
public function computeJobsWithNoSuccessor()
{
$this->jobsWithNoSuccessor = array();
foreach ($this->jobs as $key => $value) {
if (false === array_key_exists($key, $this->precedenceConstraints)) {
$this->jobsWithNoSuccessor[] = $key;
}
}
}
public function computeTotalProcessingTime()
{
$this->totalProcessingTime = 0;
foreach ($this->jobs as $key => $value) {
$this->totalProcessingTime += $value['processingTime'];
}
}
// find the job that will go to the end of the optimal schedule array
public function getLastJobKey()
{
$min = null;
$x = 0;
$lastJobKey = null;
foreach($this->jobsWithNoSuccessor as $key) {
$x = $this->totalProcessingTime - $this->jobs[$key]['dueDate'];
if (null === $min || $x < $min) {
$min = $x;
$lastJobKey = $key;
}
}
return $lastJobKey;
}
private function addTardinessToOptimalSchedule()
{
$i = 0;
foreach ($this->optimalSchedule as $key => $value) {
$this->optimalSchedule[$key]['tardiness'] = 0;
$j = 0;
foreach ($this->optimalSchedule as $k => $v) {
if ($j <= $i) {
$this->optimalSchedule[$key]['tardiness'] += $v['processingTime'];
}
$j++;
}
$i++;
}
}
public function compute()
{
for ($i = $this->jobsCount; $i >= 1; $i--) {
$this->computeJobsWithNoSuccessor();
$this->computeTotalProcessingTime();
$lastJobKey = $this->getLastJobKey();
$this->optimalSchedule[$lastJobKey] = $this->jobs[$lastJobKey];
// unset the job
unset($this->jobs[$lastJobKey]);
// remove precedence constraint if needed
if (true === in_array($lastJobKey, $this->precedenceConstraints)) {
foreach ($this->precedenceConstraints as $key => $value) {
if ($lastJobKey === $value) {
unset($this->precedenceConstraints[$key]);
}
}
}
}
// reverse the optimal schedule array and preserver keys
$this->optimalSchedule = array_reverse($this->optimalSchedule, true);
// add tardiness to the optimal schedule array
$this->addTardinessToOptimalSchedule();
return $this->optimalSchedule;
}
}
$LA = new LawlersAlgorithm(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)),
array(2 => 5,
7 => 9));
echo '<pre>';
print_r($LA->compute());
echo '</pre>';
Great job. That’s the sort of initiative that we like to see around here.
A Job and a JobCollection Object(s) would be a nice addition too. 
Or, if you’re feeling rather adventurous, an iterator for JobCollection that would auto-magically apply your chosen algorithm.