Решение задачи планирования или оптимизации упаковки в R
У меня проблема с оптимизацией. Речь идет о продукте, который состоит из 20 частей (порядок производства не имеет значения). У меня есть 3 аналогичных машины, которые могут производить все 20 деталей.
У меня есть 20 частей, представленных в минутах (т. Е. На изготовление первой части уходит 3 минуты, а на создание второй - 75 минут и т. Д.)
ItemTime<-c(3,75,55,12,45,55,11,8,21,16,65,28,84,3,58,46,5,84,8,48)
Таким образом, для производства 1 продукта требуется 730 мин.
sum(ItemTime)
Цель состоит в том, чтобы минимизировать производство одного продукта, распределяя хороший продукт на три машины.
sum(ItemTime/3)
Так что на самом деле мне нужно быть как можно ближе к 243,333 мин (730/3)
Количество возможностей огромно 3^20
Я думаю, что есть много разных оптимальных решений. Я хотел бы, чтобы R дал мне все из них. Мне не нужно только знать общее время, которое потребуется машине 1, 2 и 3: мне также нужно знать, какие предметы отдать машине 1, машине 2 и манчине 3.
В качестве альтернативы, если это слишком долго, я бы хотел выбрать образец без повторений, который был бы максимально разумным...
Могу ли я решить мою проблему с помощью языка R?
3 ответа
Я полагаю, что ваша проблема - это близкий вариант проблемы множественных ранцев (MKP), которая априори, а не кусок пирога...
Тем не менее, ваше измерение достаточно мало, чтобы проблему можно было решить как смешанное целочисленное программирование (MIP). Я решил это ниже, используя Rglpk; Решатель занял около четырех минут. Если вам повезло иметь доступ к CPLEX, я настоятельно рекомендую вам использовать Rcplex вместо этого это будет курить это.
ItemTime<-c(3,75,55,12,45,55,11,8,21,16,65,28,84,3,58,46,5,84,8,48)
N <- length(ItemTime)
M <- 3
Постановка проблемы:
# variables are in this order:
# z: slack variable for the max of (s1, s2, s3)
# s1: sum of times for machine 1
# s2: sum of times for machine 2
# s3: sum of times for machine 3
# a1-a20: booleans for assignment to machine1
# b1-b20: booleans for assignment to machine1
# c1-c20: booleans for assignment to machine1
obj <- c(1, rep(0, 3 + 3*N))
mat <- rbind(
c(1, -1, 0, 0, rep(0, M*N)), # z >= s1
c(1, 0, -1, 0, rep(0, M*N)), # z >= s2
c(1, 0, 0, -1, rep(0, M*N)), # z >= s3
c(0, -1, 0, 0, ItemTime, rep(0, N), rep(0, N)), # s1 = ...
c(0, 0, -1, 0, rep(0, N), ItemTime, rep(0, N)), # s2 = ...
c(0, 0, 0, -1, rep(0, N), rep(0, N), ItemTime), # s3 = ...
cbind(matrix(0, N, 4), diag(N), diag(N), diag(N)) # a_i + b_i + c_i = 1
)
dir <- c( ">=", ">=", ">=", "==", "==", "==" , rep("==", N))
rhs <- c(rep(0, 2*M), rep(1, N))
types <- c(rep("C", 1+M), rep("B", M*N))
Теперь давайте решим это:
Rglpk_solve_LP(obj, mat, dir, rhs, types, max=FALSE, verbose=TRUE)
# GLPK Simplex Optimizer, v4.47
# INTEGER OPTIMAL SOLUTION FOUND
# $optimum
# [1] 244
#
# $solution
# [1] 244 243 243 244 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0
# [31] 1 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1
# [61] 0 0 0 1
#
# $status
# [1] 0
Редактировать: Очевидно, что эта проблема немного отличается от той, которую я помню, потому что, как показывает @han, этот алгоритм не является оптимальным, просто приблизительным (хотя есть гарантия, что "время выполнения" этого алгоритма никогда не превышает 4/3 * оптимальный рабочий диапазон в целом и 11/9 * оптимальный для 3 машин.).
Ссылка @han предоставила ссылку на статью о многопроцессорном планировании, что в точности соответствует этой проблеме. В статье говорится, что проблема на самом деле NP-сложная. Это означает, что нет алгоритма полиномиального времени для вычисления оптимального ответа (намного меньше, чем 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% в этом алгоритм оптимален.)
Как отмечено в других ответах, это связано с проблемой упаковки бункера. Простой алгоритм упаковки бинов уже реализован в пакете BBmisc; мы можем применить эту существующую функцию здесь для простого и быстрого решения:
library(BBmisc)
binlimit <- 3 # specify how many bins
binsize <- ceiling(sum(ItemTime)/binlimit) # calculate the minimum possible bin size (244)
binPack(ItemTime, binsize) # pack the bins
[1] 3 1 2 3 3 2 2 3 3 3 2 3 1 3 2 3 3 1 3 3
В этом случае он мгновенно создает оптимальное решение, используя 3 контейнера. Мы можем подтвердить размеры бункера решения:
library(dplyr)
df <- data.frame(ItemTime, bins)
df %>% group_by(bins) %>% summarise (time = sum(ItemTime))
bins time
1 1 243
2 2 244
3 3 243
Если binPack создает исходное решение с использованием слишком большого числа бинов, его можно поместить в цикл for, который увеличивает размер бина и возвращает решение, только когда на выходе не более 3 бинов binPack,
Интересно, что binPack возвращает решение с теми же размерами бинов, что и в ответе Флоделя выше, но с разными назначениями в бинах 2 и 3:
ItemTime Rglpk binPack
1 3 3 3
2 75 1 1
3 55 2 2
4 12 2 3
5 45 3 3
6 55 3 2
7 11 2 2
8 8 2 3
9 21 2 3
10 16 3 3
11 65 2 2
12 28 3 3
13 84 1 1
14 3 3 3
15 58 2 2
16 46 3 3
17 5 2 3
18 84 1 1
19 8 2 3
20 48 3 3
В то время как binPack обеспечивает быстрый и простой способ решения этой проблемы, его описание отмечает, что этот алгоритм прост и может не вернуть оптимальное решение:
Преобразует числовые элементы в x в группы с суммой, меньшей или равной емкости. Используется очень простой жадный алгоритм, который на самом деле не оптимизирован по скорости. Это удобная функция для меньших векторов, а не конкурентный решатель для реальной проблемы возврата. Если элемент x превышает емкость, выдается ошибка.