r - 在 R 中解决任务调度或装箱优化

Question

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

Answer 1

我相信你的问题是多重背包问题(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