劳勒算法实施协助

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

更新：

所以这里有一些更多的资料来源，其中包含我发现的劳勒算法的解释：

• 来源 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），这似乎没有出现在您的代码中。如果您可以按任何顺序安排作业，那么劳勒算法专门用于更简单的最早截止日期优先算法（一行描述：按照截止日期递增的顺序对作业进行排序）。

编辑：让我更具体一些。最初集合D 是所有作业。 Lawler 反复在 D 中查找截止日期最晚的作业 i，但受限于 D 中没有其他作业 j code> 必须安排在 i 之后（即 i 在 D 中没有后继者），并从其中删除 i D。作业按照与移除相反的顺序进行安排。如果没有优先级约束，那么这就是 EDF。