In a given hour, I have a set of tasks that need to be completed and the time it takes for completion of each. This could be, for example:

Assume I have infinite resource/persons to assign to tasks. I am looking to find a method of completing all tasks in the above table, which assigns the least possible persons.

Since the tasks take 2.05 hours to complete in total, if there are no constraints this solution is easy (i.e. ceiling(2.05) = 3, where ceiling() is the ceiling function). However I have a set of constraints which tell me what the permissible combinations of tasks are:

That is, in one hour, a person can only do the above tasks/combinations of tasks and NOT others, e.g. doing E and F in the same hour is impermissible.

Edit: When giving one person a combination of tasks, the amount of time this person contributes toward the completion of each task must add up to at most (less than or equal to) an hour. For example, giving one person A, B, C means they can do x, y, z hrs of A, B, C respectively, where x, y, z are free to choose but subject to the constraint x y z <= 1.

Obviously this complicates the problem and whilst it is easy to solve intuitively I'm not sure if there is an efficient algorithm for this sort of problem, or pre-built functions/packages in R.

Thanks

CodePudding user response：

Assuming that the problem is to select the minimum number of rows from the second data frame such that each task is done once then the first data frame is irrelevant so we can formulate the following integer linear program (known as a set partitioning problem) such that M[i, j] is 1 if the ith task is in the jth row of DF (where DF is shown in Note at end) and x is a 0/1 vector ncol(M) long to be solved for.

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

or in R code

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"

Note

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)