劳勒的算法执行援助

劳勒的算法执行援助

关注
发信
关注(28)粉丝(399)

劳勒的算法执行援助

本文介绍了劳勒的算法执行援助的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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

更新：

因此​​，这里有一些更多的来源与劳勒的算法，我找到了解释：

So here are some more sources with the explanation of Lawler's algorithm I found:

  • <一个href="http://www.google.com/books?id=aSiBs6PDm9AC&pg=PA166&dq=lawler%27s+algorithm+$c$c&lr=&hl=sk&cd=4#v=onepage&q=&f=false"相对=nofollow>源1
  • <一个href="http://www.google.com/books?id=Dw5e12aB7owC&pg=PA360&dq=lawler+algorithm+scheduling&lr=&hl=sk&cd=1#v=onepage&q=lawler%20algorithm%20scheduling&f=false"相对=nofollow>来源2
  • <一个href="http://www.google.com/books?id=iDtxXdSW5DgC&pg=PA428&dq=lawler%27s+algorithm+$c$c&lr=&hl=sk&cd=119#v=onepage&q=&f=false"相对=nofollow>来源3 （这是一个很好的来源，但一个关键页面在preVIEW丢失+这本书是不是可以在亚马逊或其他地方bacause它仅限于中国 - 如果它是我早就买了它）
  • Source 1
  • Source 2
  • Source 3 (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)

下面是劳勒的算法我在PHP中实行（我知道......但我已经习惯了）：

Here is my implemenation of Lawler's algorithm in PHP (I know... but I'm used to it):

<?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);

现在上面回报这样一个最优的时间表：

Now the above returns an optimal schedule like this:

Array
(
    [0] => 1
    [1] => 1
    [2] => 1
    [3] => 3
    [4] => 2
    [5] => 6
)

似乎不是我的权利这也。该问题可能与我的实现算法的，因为我不知道我理解正确的话。我用<一个href="http://www.google.com/books?id=aSiBs6PDm9AC&pg=PA166&dq=lawler%27s+algorithm+$c$c&lr=&hl=sk&cd=4#v=onepage&q=&f=false"相对=nofollow>这个的源代码来实现它。

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 this source to implement it.

描述有一点点混乱。例如，我并没有获得是怎么定义的子集D（我猜是任意的）。

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).

任何人都可以帮助我吗？我一直在试图找到与算法的简单解释一些消息来源，但是我发现所有的来源是更加复杂（含数学证明和等），所以我坚持上面的链接。

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.

是的，这是一门功课，如果不是很明显。

Yes, this is a homework, if it wasn't obvious.

我还有几个星期来破解这一点，但我花了几天已经试图让究竟这个算法的工作没有成功，所以我不认为我会得到任何美好的那段时间。

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.

推荐答案

根据您的链接的源代码，劳勒的算法需要输入一个集合的形式工作的制约我必须作业之前安排Ĵ（指定为关系 preC ），这似乎不是刊登在您的code。如果你可以安排工作在任何顺序，那么劳勒的算法，专门为简单的最早时限优先算法（一行说明：为了提高限期就业排序）。

According to your linked source, Lawler's algorithm takes as input a set of constraints of the form "job i must be scheduled before job j" (specified as a relation prec), which seems not to be featured in your code. If you can schedule the jobs in any order, then Lawler's algorithm specializes to the simpler Earliest Deadline First algorithm (one line description: sort the jobs in order of increasing deadline).

编辑：让我更具体。最初设定的 D 是所有作业。劳勒多次找到工作我在 D 与最新的最后期限，受约束没有其他作业在 D Ĵ必须在我（即我没有接班人，在 D ）并删除我从 D 。该工作预计于拆卸相反的顺序。如果没有precedence约束，则这只是EDF

let me be more specific. Initially the set D is all jobs. Lawler repeatedly finds the job i in D with the latest deadline, subject to the constraint that no other job j in D must be scheduled after i (i.e., i has no successors in D), and removes i from D. The jobs are scheduled in reverse order of removal. If there are no precedence constraints, then this is just EDF.

这篇关于劳勒的算法执行援助的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

08-04 23:06
Powered by LMLPHP ©2024 劳勒的算法执行援助 0.071437