UPDATE2:
Думаю, я понял это сейчас:
<?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, ie 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>'; ОБНОВИТЬ:
Итак, вот несколько источников с объяснением алгоритма Лоулера, который я нашел:
Вот моя реализация алгоритма Лоулера в PHP (я знаю … но я к этому привык):
<?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);
Теперь приведенное выше возвращает оптимальное расписание:
Array ( [0] => 1 [1] => 1 [2] => 1 [3] => 3 [4] => 2 [5] => 6 )
Который мне не кажется правильным. Проблема может заключаться в моей реализации алгоритма, потому что я не уверен, что правильно понимаю. Я использовал этот источник для его реализации.
Описание там немного запутанно. Например, я не совсем понял, как определено подмножество D (я предполагаю, что оно произвольно).
Может ли кто-нибудь помочь мне с этим? Я пытался найти некоторые источники с более простым объяснением алгоритма, но все источники, которые я нашел, были еще более сложными (с математическими доказательствами и т. Д.), Поэтому я застрял со ссылкой выше.
Да, это домашнее задание, если это не очевидно.
У меня все еще есть несколько недель, чтобы взломать это, но я потратил несколько дней, пытаясь понять, как именно этот алгоритм работает без успеха, поэтому я не думаю, что за это время я получу ярче.