解决R中的任务计划或装箱优化 [英] Solving task scheduling or bin-packing optimizations in R

问题描述

我有一个优化问题.这是关于包含20个零件的产品(生产顺序无关紧要).我有3台可以生产全部20个零件的类似机器.

I have an optimisation issue. It's about a product that contains 20 parts (the order of producing doesn't matter). I've got 3 similar machine that can produce all 20 parts.

我用分钟表示了20个零件(即，制作第一部分需要3分钟，制作第二部分需要75分钟，依此类推)

I've got the 20 parts represented in minutes (ie. it takes 3min to produce the first part and 75min to produce the second part, etc)

ItemTime<-c(3,75,55,12,45,55,11,8,21,16,65,28,84,3,58,46,5,84,8,48)

所以要生产1种产品需要730分钟.

So to produce 1 product it takes 730 min.

sum(ItemTime)

目标是通过将优质商品分配给三台机器来最大程度地减少一种产品的产量.

The aim is to minimise the production of one product by allocating the good item to the three machines.

sum(ItemTime/3)

所以实际上我需要接近243.333分钟(730/3)

So actually I need to be as close as 243.333 min (730/3)

可能性是巨大的3 ^ 20

The amount of possibility is huge 3^20

我想有很多不同的最佳解决方案.我希望R给我所有人.我不需要只知道需要1号机器2号和3号机器的总时间:我还需要知道要分配给1号机器，2号机器和3号机器的物品.

I guess there are many different optimal solutions. I would like that R give me all of them. I don't need only to know total time that will need machine 1 2 and 3 : I also need to know which items to give to machine 1, to machine 2 and to manchine 3.

或者，如果时间太长，我想选择一个尽可能不重复的样本...

Alternatively, if it's too long I would like to choose a sample without repetition that is as reasonable as possible...

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

Can I solve my issue with R language?

推荐答案

我相信您的问题是多重背包问题(MKP)的近似变体，它是先验的，而不是小菜一碟...

I believe your problem is a close variant of the Multiple Knapsack Problem (MKP) which is, a priori, not a piece of cake...

但是，您的尺寸很小，可以通过混合整数编程(MIP)来解决问题.我用Rglpk在下面解决了；求解器花了大约四分钟的时间.如果您足够幸运地可以使用CPLEX，我强烈建议您使用Rcplex代替，它会吸烟.

However, your dimension is small enough that the problem can be solved as a Mixed-Integer Programming (MIP). I solved it below using Rglpk; it took the solver about four minutes. If you are lucky enough to have access to CPLEX, I would highly recommend you use Rcplex instead, it will smoke it.

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

这篇关于解决R中的任务计划或装箱优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！