7

最適化の問題があります。20個の部品が入った商品のことです（製作順は問いません）。20 個すべての部品を製造できる同様の機械が 3 台あります。

20 パーツを数分で表現しました (つまり、最初のパーツを作成するのに 3 分、2 番目のパーツを作成するのに 75 分かかります)。

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

したがって、1 つの製品を製造するには 730 分かかります。

sum(ItemTime)

3 台の機械に良品を割り付けることで、1 台の製品の生産量を最小化することを目的としています。

sum(ItemTime/3)

したがって、実際には 243.333 分 (730/3) に近づける必要があります。

可能性の量は巨大です 3^20

さまざまな最適解があると思います。私はRがそれらすべてを私にくれることを望みます。マシン 1 2 と 3 を必要とする合計時間を知る必要があるだけでなく、マシン 1、マシン 2、およびマシン 3 にどのアイテムを渡すかを知る必要もあります。

または、長すぎる場合は、できるだけ合理的な繰り返しのないサンプルを選択したいと思います...

R 言語で問題を解決できますか?

4

3 に答える 3

13

あなたの問題は、先験的で簡単なことではない複数のナップザック問題（MKP）の変形であると思います...

ただし、次元が小さいため、混合整数計画法 (MIP) として問題を解決できます。以下を使用して解決しましたRglpk。ソルバーは約 4 分かかりました。幸運にも 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
于 2012-05-06T03:45:41.087 に答える
8

編集：明らかに、この問題は私が覚えている問題とは少し異なります。@ hanが示すように、このアルゴリズムは最適ではなく、単なる近似です（ただし、このアルゴリズムの「メイクスパン」が4/3を超えないことが保証されています） *一般的に最適なメイクスパンおよび11/9*3台のマシンに最適。）

@hanが提供するリンクは、マルチプロセッサスケジューリングの記事にリンクされています。これは、この問題とまったく同じです。この記事によると、問題は実際にはNP困難です。これは、最適な答えを計算するための多項式時間アルゴリズムがないことを意味します（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た。

メモリから、このアルゴリズムは実際に最適です。その主張へのリンクはありませんが。また、可能な限り最適な結果を得るためにそれを適応させることができるかどうかもわかりません。

1つのジョブと、現在のジョブを持つマシンのリストを取得する関数を定義すると、を使用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％確信が持てないためですアルゴリズムが最適です。）

于 2012-05-06T02:54:44.330 に答える
6

他の回答で述べたように、これはビンパッキングの問題に関連しています。シンプルなビン パッキング アルゴリズムは、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

この場合、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 ループに配置してビンサイズをインクリメントし、 の出力に 3 つ以下のビンしかない場合にのみ解を返すことができますbinPack。

興味深いことに、binPack は、上記の flodel の回答と同じビン サイズを持つソリューションを返しますが、ビン 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問題を解決するための迅速かつ簡単な方法を提供しますが、その説明では、このアルゴリズムは単純であり、最適なソリューションを返さない可能性があることに注意してください。

x の数値項目を合計が容量以下のグループにマップします。非常に単純な貪欲なアルゴリズムが使用されますが、これは実際には速度が最適化されていません。これは小さなベクトルの便利な関数であり、実際のビンバッキング問題の競合ソルバーではありません。x の要素が容量を超えると、エラーがスローされます。

于 2015-03-20T13:31:41.967 に答える