로울러의 알고리즘 구현 지원

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

UPDATE : 그래서 여기

내가 발견 로울러의 알고리즘의 설명과 함께 좀 더 소스입니다 :

• Source 1
• Source 2
• Source 3 (이것은 정말 좋은 소식이지만 미리보기에는 하나의 중요한 페이지가 없습니다.이 책은 아마존이나 다른 곳에서는 중국에서만 사용할 수 있습니다 .- 이미 구입했을 경우) 여기

---

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

나는 나에게 맞는 것 같지 않은데. 문제를 제대로 이해하지 못했기 때문에 알고리즘 구현에 문제가있을 수 있습니다. 나는 그것을 구현하기 위해 this 소스를 사용했다.

설명이 약간 혼란 스럽습니다. 예를 들어, 나는 하위 집합 D가 정의 된 방법을 얻지 못했습니다 (나는 그것이 임의적이라고 생각합니다).

누구나 나를 도와 줄 수 있습니까? 나는 알고리즘에 대한 간단한 설명과 함께 몇 가지 소스를 찾으려고 노력했지만, 발견 된 모든 소스는 위와 같은 링크로 인해 더 복잡해졌습니다 (수학 증명 등).

예. 명확하지 않은 경우 숙제입니다.

나는이 문제를 해결하는 데 몇 주일이 걸리지 만,이 알고리즘이 얼마나 성공적으로 작동하는지 이미 알기 위해 며칠을 보냈다. 그래서 나는 그 시간 동안 더 밝아 질 것이라고 생각하지 않는다.

Answer 1

가 연결된 소스에 따르면, 로울러의 알고리즘은 입력으로 형태의 일련의 제약 소요 코드에 등장하지 않는 것, (관계 prec로 지정) "작업 i는 작업 j 전에 예약해야합니다." 어떤 순서로든 작업을 예약 할 수 있다면 Lawler의 알고리즘은보다 간단한 Earliest Deadline First 알고리즘 (한 줄의 설명 : 마감일이 빠른 순서대로 작업 정렬)을 전문으로합니다.

편집 : 좀 더 상세하게하겠습니다. 처음에는 세트 D이 모두 작업입니다. 로울러 반복 D에서 다른 작업 j이 i 후 스케줄되어야합니다 제약에 따라 최신 기한와 D에서 작업 i, 발견 (즉, i는 D에는 후임자가 없습니다), 그리고 D에서 i을 제거합니다. 작업은 제거의 역순으로 스케줄됩니다. 선행 제약 조건이 없으면 이것은 EDF 일뿐입니다.