Lawler算法实现协助

Question

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, 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>';

更新：

下面是我发现的对Lawler算法的解释的更多来源：

• 来源1
• 来源2
• 来源3 (这是一个非常好的来源，但预览版中缺少了一个关键的页面。)这本书在亚马逊或其他任何地方都没有，因为它仅限于中国--如果它是我早就买的了。

以下是我在PHP中实现的Lawler算法(我知道.但我已经习惯了)：

<?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是如何定义的(我猜它是任意的)。

有人能帮我解决这个问题吗？我一直试图找到一些对算法有更简单解释的来源，但我发现的所有来源都更加复杂(有数学证明等等)，所以我只能使用上面的链接。

是的，这是一个家庭作业，如果不是显而易见的话。

我还有几周的时间来解决这个问题，但我已经花了几天的时间试图弄清楚这个算法是如何工作的，但没有成功，所以我不认为在这段时间里我会变得更聪明。

Answer 1

根据链接的源代码，Lawler的算法将表单“作业i必须在作业j之前调度”(指定为关系prec)的一组约束作为输入，而这些约束似乎没有出现在代码中。如果您可以按任何顺序安排作业，那么Lawler的算法专门介绍了更简单的最早截止日期优先算法(一行描述:按增加截止日期的顺序排序作业)。

编辑:让我说得更具体些。最初，集合D都是作业。Lawler在D中重复查找带有最新截止日期的作业(D)，但有一个限制，即必须在i之后(即i在D中没有继任者)排定D中的其他作业j，并将i从D中删除。这些作业按反排顺序排定。如果没有优先级约束，那么这就是EDF。