dsf487787 2010-03-17 16:44 采纳率: 100%
浏览 158
已采纳

Lawler的算法实现辅助

UPDATE2:

I think I got it now:

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

UPDATE:

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

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

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
)

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.

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.

展开全部

  • 写回答

1条回答 默认 最新

  • ds34222222 2010-03-20 09:18
    关注

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

    EDIT: 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.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
编辑
预览

报告相同问题?

悬赏问题

  • ¥15 根据历年月数据,用Stata预测未来六个月汇率
  • ¥15 DevEco studio开发工具 真机联调找不到手机设备
  • ¥15 请教前后端分离的问题
  • ¥100 冷钱包突然失效,急寻解决方案
  • ¥15 下载honeyd时报错 configure: error: you need to instal a more recent version of libdnet
  • ¥15 距离软磁铁一定距离的磁感应强度大小怎么求
  • ¥15 霍尔传感器hmc5883l的xyz轴输出和该点的磁感应强度大小的关系是什么
  • ¥15 vscode开发micropython,import模块出现异常
  • ¥20 Excel数据自动录入表单并提交
  • ¥30 silcavo仿真,30分钟,只需要代码