在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)

生产一个产品需要730分钟。

sum(ItemTime)

目标是通过将优质物品分配给三台机器来最小化生产单个产品的数量。

sum(ItemTime/3)

所以实际上我需要尽可能接近243.333分钟（730/3）

可能性的数量是巨大的，为3^20

我猜有很多不同的最优解。我希望R能把它们全部给我。 我不仅需要知道机器1、2和3需要多长时间：我还需要知道哪些物品要给机器1、机器2和机器3。

或者，如果太长了，我想选择一个没有重复的样本，尽可能合理...

我可以用R语言解决我的问题吗？

- S12000

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

- flodel

---

是的，@dbaupp。在这种特殊情况下，很容易判断{243, 243, 244}或{242, 244, 244}解（如果存在）是最优的。因此，可以为这两组重量分别解决“多重背包问题”（如此处所定义：http://en.wikipedia.org/wiki/List_of_knapsack_problems）。如果其中任何一个问题有一个解，其中三台机器都被完全装载，则我们已经找到了原始问题的最优解。再次强调，这是“变体”... - flodel

@dbaupp，我对你声称贪心算法是最优解感到很好奇。起初，我认为“不可能！”，但由于我似乎找不到反例，我越来越相信你可能是正确的。如果是这样的话，那么我就用大锤杀了一只蚂蚁！ - flodel

啊，好的，我现在理解相似之处了。我也撤回我的说法，即它具有更多的结构：问题的结构较少，因为它是一个纯粹的最小化问题（最小化总时间），没有其他的约束条件。我认为证明贪心算法是最优的可能需要归纳来证明它在每一步都是最优的（显然对于0个任务是最优的，而添加的方法意味着如果前k个任务的解是最优的，则前k + 1个任务的解也是最优的），尽管归纳步骤可能存在一些微妙之处。 - huon

我的最优性声明是基于模糊地记得的维基百科（或其他什么）文章，我似乎无法找到正确的搜索词再次找到它。 - huon

对于解决方案的含义，您可以参考我在问题表述中留下的有关变量的注释。244是您的最终最优时间，243， 243， 244是三个机器的各自所需的时间。接下来的20个值显示第一个机器是否应该生产部件（1）或不生产部件（0），接下来的20个值是第二个机器的，最后的20个值是最后一个机器的。 - flodel

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更有用，并且使用数据框而不是向量，在一个列中存储时间，在另一个列中存储索引）。

（值得注意的是，这种解决方案比其他解决方案快几倍，因为其他答案使用了更高效的算法，这些算法对于此问题来说可能是过度的……“可能”是因为我仍然不能百分之百确定这个算法是最优的。）

- huon

---

你的方法接近于装箱问题的最佳递减算法，但并不是最优解。举个反例，考虑重量为10、6、5、4、3、2的情况。你的算法分配工作如下：(10), (6,3,2)和(5,4)，使跨度达到11。而最优的分配是(10), (6,4)和(5,3,2)，使跨度达到10。 - han

啊，谢谢你指出来！显然我记错了。(我会编辑我的答案以明确这一点。) - huon

@han，与此篇文章链接的装箱问题[https://en.wikipedia.org/wiki/Multiprocessor_scheduling]是完全相同的问题，那里列出的算法正是我上面描述的算法。 - huon

好的，我错过了那个。所以在三台机器的情况下，近似保证为11/9。 - han

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循环中，增加箱子尺寸，并且只有在binPack的输出中不再有超过3个箱子时才返回解决方案。

有趣的是，binPack返回与上述flodel答案相同的箱子大小的解决方案，但是在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 的某个元素超过容量，则会抛出错误。

- Sam Firke