Geek asks and answers

Solving the problems of planning or optimizing bin packaging in R

I have an optimization problem. This is about a product that contains 20 parts (the order of production does not matter). I have 3 similar machines that can produce all 20 parts.

I have 20 parts presented in minutes (i.e. it takes 3 minutes to create the first part, and 75 minutes to create 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)

Thus, to produce 1 product, it takes 730 minutes.

sum(ItemTime)

The goal is to minimize the production of one product by distributing the goods into three cars.

sum(ItemTime/3)

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

The number of possibilities is huge 3 ^ 20

, . , . , 1 2 3: , 1, 2 manchine 3.

, , , ...

R?

+5
3

, - (MKP), , ...

, (MIP). , Rglpk; . CPLEX, Rcplex , .

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
+11

. , , , , @han, , ( , "makepan" 4/3 * 11/9 * 3 .).

@han , . , NP-hard. , ( , O(n log n), ).

: , , , .

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

, 4 3, 2.

; . , , .

, , , Reduce . :

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

( machines[[which.machines]]... , .)

:

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

( , machines <-: , n, .)

:

> 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

- , : , ( , ) allocate assign.job ( , order , sort, - , - ).

( , , , , ... "", 100%, .)

+8

, . BBmisc; :

library(BBmisc)

binlimit <- 3 # specify how many bins
binsize <- ceiling(sum(ItemTime)/binlimit) # calculate the minimum possible bin size (244)
binPack(ItemTime, binsize) # pack the bins

 [1] 3 1 2 3 3 2 2 3 3 3 2 3 1 3 2 3 3 1 3 3

. :

library(dplyr)
df <- data.frame(ItemTime, bins)
df %>% group_by(bins) %>% summarise (time = sum(ItemTime))

  bins time
1    1  243
2    2  244
3    3  243

binPack , for, binsize , binPack .

, binPack , , , 2 3:

   ItemTime Rglpk binPack
1         3     3       3
2        75     1       1
3        55     2       2
4        12     2       3
5        45     3       3
6        55     3       2
7        11     2       2
8         8     2       3
9        21     2       3
10       16     3       3
11       65     2       2
12       28     3       3
13       84     1       1
14        3     3       3
15       58     2       2
16       46     3       3
17        5     2       3
18       84     1       1
19        8     2       3
20       48     3       3

binPack , , :

Maps numeric elements in x to groups with an amount less than or equal to capacity. It uses a very simple greedy algorithm, which is actually not optimized for speed. This is a handy feature for smaller vectors, not a competitive solver for a real beating problem. If element x exceeds capacity, an error is thrown.

+4
source

More articles:


All Articles