在R中解决任务调度或bin-packing优化

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

Answer 2

编辑:显然这个问题与我记忆中的问题略有不同,因为正如@han所示,这个算法不是最优的,只是一个近似值(虽然可以保证这个算法的"完工时间"从不超过4/3*一般的最佳完工时间和3台机器的11/9*最佳.).

@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%肯定这个算法是最优的.)

Answer 3

如其他答案所述，这与垃圾箱包装问题有关。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返回的解决方案具有与上述flodel的答案相同的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的元素超出容量，则会引发错误。