r语言 - 任务分配给尽可能少的人

Question

在给定的一小时内，我有一组需要完成的任务以及完成每项任务所需的时间。这可以是，例如:

tbody> <<tr>BCDEF

任务	完成时间(小时)
	0.2
	0.25
	0.1
	0.5
	0.5
	0.5

假设问题是选择最低的行数从第二个数据帧,每个任务完成一次然后第一个数据帧是无关紧要的,所以我们可以制定以下整数线性规划(称为一组分区问题),M (i, j)是1如果第i个任务的j行DF (DF注意末所示)和x是一个0/1向量ncol (M)需要解决。

minimize 1'x s.t. Mx = 1 and x[j] is in {0,1} for all j

或R代码

library(lpSolve)
s <- strsplit(gsub(" ", "", DF$Task), ",")
names(s) <- seq_along(s)
stk <- stack(s)
M <- table(stk)
res <- lp("min", rep(1, ncol(M)), M, "==", rep(1, nrow(M)), all.bin = TRUE)
res
## Success: the objective function is 3 
res$solution
## [1] 0 0 0 0 1 0 0 0 0 1 0 1
bin2name <- function(x) rownames(M)[x == 1]
apply(M[, res$solution == 1, drop = FALSE], 2, bin2name)
## $`5`
## [1] "E"
##
## $`10`
## [1] "A" "B" "C"
##
## $`12`
##  [1] "D" "F"

注意

Lines <- "Task
A
B
C
D
E
F
A,B
A,C
B,C
A,B,C
D,E
D,F"
DF <- read.table(text = Lines, header = TRUE, strip.white = TRUE)