7

我有一个优化问题。这是关于包含 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 语言解决我的问题吗？

4

3 回答 3

13

我相信你的问题是多重背包问题（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
于 2012-05-06T03:45:41.087 回答
8

编辑：显然这个问题与我记得的问题略有不同，因为正如@han 所示，这个算法不是最优的，只是一个近似值（尽管可以保证这个算法的“makespan”永远不会超过 4/3 * 一般最佳制造时间和 11/9 * 最适合 3 台机器。）。

@han 提供的链接链接到多处理器调度文章，正好等价于这个问题。文章告诉我们，这个问题实际上是 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% 确定这个算法是最优的。）

于 2012-05-06T02:54:44.330 回答
6

正如其他答案中所述，这与装箱问题有关。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 个 bin 生成最佳解决方案。我们可以确认解决方案的 bin 大小：

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使用太多 bin 生成初始解决方案，则可以将其放置在增加 binsize 的 for 循环中，并且仅在 的输出中不超过 3 个 bin 时返回解决方案binPack。

有趣的是， binPack 返回的解决方案具有与上述弗洛德尔答案相同的 bin 大小，但在 bin 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 中的数字项映射到总和小于或等于容量的组中。使用了一个非常简单的贪心算法，它并没有真正针对速度进行优化。这是较小向量的便利功能，而不是真正的 binbacking 问题的竞争求解器。如果 x 的元素超出容量，则会引发错误。

于 2015-03-20T13:31:41.967 回答