Risoluzione delle ottimizzazioni della pianificazione delle attività o dell'imballaggio dei contenitori in R

Question

Ho un problema di ottimizzazione. Si tratta di un prodotto che contiene 20 parti (l'ordine di produzione non ha importanza). Ho 3 macchine simili che possono produrre tutte e 20 le parti.

ho le 20 parti rappresentate in minuti (es. Ci vogliono 3 minuti per produrre la prima parte e 75min per produrre la seconda parte, ecc)

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

Quindi, per produrre 1 prodotto ci vogliono 730 min.

sum(ItemTime) 

L'obiettivo è quello di minimizzare la produzione di un prodotto assegnando il buon articolo alle tre macchine.

sum(ItemTime/3) 

Quindi, in realtà ho bisogno di essere il più vicino 243,333 min (730/3)

La quantità di possibilità è enorme 3^20

Credo che ci sono molte soluzioni ottimali differenti. Mi piacerebbe che R mi desse tutti loro. Non ho bisogno di sapere solo il tempo totale necessario per la macchina 1 2 e 3: devo anche sapere quali articoli dare alla macchina 1, alla macchina 2 e alla manchina 3.

In alternativa, se è troppo lungo Vorrei scegliere un campione senza ripetizioni il più ragionevole possibile ...

Posso risolvere il mio problema con il linguaggio R?

Answer 1

credo che il vostro problema è una stretta variante del multiplo Knapsack Problem (MKP) che è, a priori, non è un pezzo di torta ...

Tuttavia, la dimensione è sufficientemente piccola da consentire la risoluzione del problema come programmazione MIP (Mixed-Integer Programming). L'ho risolto sotto usando Rglpk; ha impiegato il risolutore per circa quattro minuti. Se sei abbastanza fortunato da avere accesso a CPLEX, ti consiglio vivamente di usare Rcplex invece, lo fumerà.

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 

formulazione Problema:

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

Ora cerchiamo di risolverlo:

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 

Answer 2

Modifica: Ovviamente questo problema è leggermente diverso da quello che ricordo, perché come mostra @han, questo algoritmo non è ottimale, ma solo un'approssimazione mai più di 4/3 * makepan ottimale in generale e 11/9 * ottimale per 3 macchine.).

Il link @han collegato a the multiprocessor scheduling article, che è esattamente equivalente a questo problema. L'articolo ci dice che il problema è in realtà NP-difficile. Il che significa che non esiste un algoritmo del tempo polinomiale per calcolare la risposta ottimale (molto meno un O(n log n) come abbiamo qui).

---

Si può semplicemente utilizzare un algoritmo greedy: passare attraverso la lista e assegnare il lavoro che prende più tempo per la macchina che attualmente ha il minor lavoro ad esso assegnato.

Ad esempio, considerare solo il c(5,3,6,1,2) come tempi di produzione dei pezzi. Per prima cosa si ordina in ordine decrescente: c(6,5,3,2,1), quindi si passa attraverso di esso (in ordine) l'assegnazione delle attività.

 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 

Così macchina 1 fa la parte che dura 6 minuti, la macchina 2 rende quelli che prendono 1 e 5 minuti e la macchina 3 rende quello che prende 3 e 2.

Si può vedere che in fase 4, la macchina con il tempo totale più breve è la macchina 3 ed è per questo motivo che abbiamo assegnato il 2 ad esso.

Dalla memoria, questo algoritmo è effettivamente ottimale; anche se non ho un link per tale affermazione. Inoltre, non so se è possibile adattarlo per ottenere tutti i possibili risultati ottimali.

---

Se si definisce una funzione che prende un posto di lavoro e un elenco delle macchine con i loro posti di lavoro attuali, è possibile utilizzare Reduce per assegnare tutti i posti di lavoro. Il singolo assegnazione di posti di lavoro potrebbe essere simile:

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

(non mi piace la linea machines[[which.machines]] ... Sono sicuro che ci sia un modo migliore per modificare un elenco in un indice specifico.)

E poi l'assegnazione potrebbe essere come:

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

(non mi piace la riga che inizia machines <-: sono sicuro che ci sia un modo più ordinato di creare una lista di lunghezza n, ma non posso trovalo.)

Sul esempio, questo dà:

> 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 

Il passo finale sta risolvendo quale lavoro corrisponde a quale tempo: questo può essere fatto sia lavorando a ritroso dopo aver assegnato i tempi (questo può essere fatto in circa lineari tempo, dal momento che c'è una mappatura relativamente semplice da tempi a lavoro e vice versa) o modificando allocate e assign.job per tenere traccia degli indici dei lavori (se si sta andando a fare questo allora la funzione order sarà più utile di sort e utilizzando i dataframes anziché i vettori, per memorizzare i tempi in una colonna e gli indici in un'altra).

(Va rilevato che questa soluzione è diverse volte più veloce rispetto agli altri, dal momento che l'altra risposta sta usando algoritmi di potenza superiore, che sono forse non eccessivo per questo problema ... "forse" perché io' m ancora non al 100% sicuro che questo algoritmo è ottimale.)

Answer 3

Come osservato in altre risposte questo è legato al bin packing problem. Un algoritmo di impacchettamento semplice è già implementato nel pacchetto BBmisc; si può applicare questa funzione esistente qui di una soluzione semplice e veloce:

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 

In questo caso, si produce istantaneamente una soluzione ottimale utilizzando 3 scomparti.Possiamo confermare i formati bin della soluzione:

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 

Se binPack produce una soluzione iniziale utilizzando troppi bidoni, può essere collocato in un ciclo for che incrementa il binsize e restituisce solo una soluzione quando non ci sono più di 3 contenitori nell'output di binPack.

È interessante notare che, binPack restituisce una soluzione con gli stessi formati bin come la risposta di flodel sopra, ma con diversi incarichi in contenitori 2 e 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 

Mentre binPack fornisce un modo semplice e veloce per risolvere questo problema, la sua descrizione osserva che questo algoritmo è semplice e non può restituire la soluzione ottimale:

mappe elementi numerici in x in gruppi con somma minore o uguale di capacità. Viene utilizzato un algoritmo molto semplice e avido, che non è in realtà ottimizzato per la velocità. Questa è una funzione di convenienza per i vettori più piccoli , non un risolutore competitivo per il vero problema del binback. Se un elemento di x supera la capacità, viene generato un errore.