Solving task scheduling or bin-packing optimizations in R

Question

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.

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)

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)

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

The amount of possibility is huge 3^20

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...

Can I solve my issue with R language?

Answer 1

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

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

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

Now let's solve it:

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