Редактировать: Очевидно, эта проблема немного отличается от той, которую я помню, потому что, как показывает @han, этот алгоритм не является оптимальным, просто приближением (хотя есть гарантия того, что «makepan» из этого алгоритма не более 4/3 * оптимальный вариант в целом и 11/9 * оптимальный для 3 машин.).
Ссылка @han предоставлена связанная с the multiprocessor scheduling article, что в точности эквивалентно этой проблеме. В статье говорится, что проблема на самом деле NP-hard. Это означает, что для вычисления оптимального ответа нет алгоритма полиномиального времени (тем более, что мы имеем здесь O(n log n)).
Вы можете просто использовать жадный алгоритм: перейти через список и назначить задание, которое занимает самый длинный в машине, которая в настоящее время имеет наименьшую работу, возложенную на нее.
В качестве примера рассмотрим только наличие c(5,3,6,1,2) в качестве вашей части времени производства. Сначала вы сортируете это в порядке убывания: c(6,5,3,2,1), а затем пройдите через него (в порядке), назначая задачи.
Step: 1 2 3 4 5
Machine 1: 6 6 6 6 6
Machine 2: - 5 5 5 5,1
Machine 3: - - 3 3,2 3,2
Так машина 1 делает часть, которая занимает 6 минут, машина 2 делает те, которые занимают 1 и 5 минут и машина 3 делает тот, который принимает 3 и 2.
Вы можете видеть, что в шаг 4, машина с наименьшим общим временем - это машина 3, поэтому мы назначили ей 2.
Из памяти этот алгоритм фактически оптимален; хотя у меня нет ссылки на эту претензию. Я также не знаю, можете ли вы адаптировать его, чтобы получить все возможные оптимальные результаты.
Если определить функцию, которая принимает одно задание и список машин с их текущей работы, вы можете использовать Reduce назначить все рабочие места. Единственное назначение работы может выглядеть примерно так:
assign.job <- function(machines, job) {
which.machines <- which.min(lapply(machines, sum))
machines[[which.machines]] <- c(machines[[which.machines]], job)
machines
}
(я не люблю machines[[which.machines]] линию ... Я уверен, что есть лучший способ изменить список по заданному индексу.)
а то задание может быть как:
allocate <- function(num.machines, job.times) {
machines <- lapply(1:num.machines, function(...) c())
Reduce(assign.job,
sort(job.times, decreasing=TRUE),
machines)
}
(я не люблю строку, начинающуюся machines <-: Я уверен, что есть аккуратнее способ создания списка длина n, но я не могу найти его.)
На вашем примере, это дает:
> allocate(3,ItemTime)
[[1]]
[1] 84 58 46 45 8 3 # total time: 244
[[2]]
[1] 84 55 55 21 16 8 5 # total time: 244
[[3]]
[1] 75 65 48 28 12 11 3 # total time: 242
Последний шаг является разработка которой работа соответствует тому времени: это может быть сделано, работая в обратном направлении после назначения раз (это может быть сделано примерно в линейном время, так как существует относительно простое сопоставление от времени до работы и наоборот) или путем изменения allocate и assign.job для отслеживания индексов заданий (если вы собираетесь это сделать, то функция order будет более полезной чем sort, а также использовать фреймы данных вместо векторов, чтобы хранить времена в одном столбце и индексы в другом).
(Следует отметить, что это решение несколько раз быстрее, чем другие, так как другой ответ, используя более высокий приведенные алгоритмы, которые возможно не избыточны для этой проблемы ... «возможно», потому что я м еще не 100% уверен, что этот алгоритм является оптимальным.)
Я думаю, что эта проблема имеет больше (и другую) структуру для любой проблемы с рюкзаком, поэтому мне было бы интересно, если бы вы могли подробнее рассказать о сходствах. :) – huon
Да, @dbaupp. В этом конкретном случае легко сказать, что решение {243, 243, 244} или {242, 244, 244}, если оно существует, является оптимальным. Поэтому можно было бы решить «проблему с несколькими рюкзаками» (как определено здесь: http://en.wikipedia.org/wiki/List_of_knapsack_problems) для каждого из этих двух наборов весов. Если одна из двух проблем имеет решение, в котором три машины полностью загружены, то мы нашли оптимальное решение исходной задачи. Опять же, это «вариант» ... – flodel
@dbaupp, меня заинтриговало ваше утверждение о том, что жадный подход оптимален. Сначала я думал «нет!», Но поскольку я не могу найти встречный пример, я все больше убеждаюсь, что вы правы. Если это так, я убил муравья с кувалдой! – flodel