我认为,你的问题是多Knapsack 问题(MKP)的一个近似变体,它是一个先验的问题,不是一件ake事。

然而,你的层面很小,这个问题可以作为一个混合分类方案加以解决。 我用<代码>Rglpk将其解决。 如果你能够接触到CPLEX,我会非常建议你使用code>,否则就会吸烟。

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

Problem formulation:

# 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

<>strong>Edit:显然,这个问题与我所记得的问题略有不同,因为正如“@han”所示,这一算法并不理想,只是近似值(尽管有保证,该算法中的“基数”从4/3起降至4/3,* 总的说来最大化,11/9 是3台机器的最佳选择)。

@han提供的链接与,多处理器编程第条,这完全相当于这一问题。 该条款告诉我们,问题实际上是法国的。 哪一种意思是没有综合时间算法来计算最佳答案(如我们在这里所做的那样,减去O(nlog n))。

你们只能使用贪 gr算法:通过该清单,把最长时间的工作分配给目前分配给它的工作最少的机器。

例如,仅考虑将<代码>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分钟。

You can see that in step 4, the machine with the shortest total time is machine 3 so that is why we assigned the 2 to it.

<>记忆中,这一算法实际上是最佳的;尽管我没有这方面的联系。 我也不知道,你是否能够调整,以取得一切可能的最佳结果。

如果你确定需要一份工作的职能和一份现有工作的机器清单,则你可使用rel=“nofollow”。 唯一的工作任务可能包括:

assign.job <- function(machines, job) {
    which.machines <- which.min(lapply(machines, sum))
    machines[[which.machines]] <- c(machines[[which.machines]], job)
    machines
}

allocate <- function(num.machines, job.times) {
    machines <- lapply(1:num.machines, function(...) c())
    Reduce(assign.job,
           sort(job.times, decreasing=TRUE),
           machines)
}

> 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