UPDATE2:
Я думаю, что получил это сейчас:
<code><?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 ' ';
UPDATE:
Итак, вот еще несколько источников с объяснением алгоритма Лоулера, которые я нашел:
- Источник 1
- Источник 2
- Источник 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
)
Что мне не кажется правильным. Проблема может быть связана с моей реализацией алгоритма, потому что я не уверен, что понимаю его правильно. Я использовал этот источник для его реализации.
Описание там немного сбивает с толку. Например, я не совсем понял, как определяется подмножество D (я думаю, оно произвольное).
Может ли кто-нибудь помочь мне с этим? Я пытался найти некоторые источники с более простым объяснением алгоритма, но все источники, которые я нашел, были еще более сложными (с математическими доказательствами и тому подобным), поэтому я застрял по ссылке выше.
Да, это домашнее задание, если оно не было очевидным.
У меня еще есть несколько недель, чтобы разобраться с этим, но я уже потратил несколько дней, пытаясь понять, как именно работает этот алгоритм, но безуспешно, поэтому я не думаю, что за это время я стану ярче.