ho n linee di produzione di una catena di montaggio, lunghe uguali.
ogni nodo di indice i delle linee fa la stessa cosa indipendentemente a quale linea appartiene.
la sequenza porta a termine la mia produzione, poso saltare dal nodo di indice j-1 di una linea al nodo di indice j di un'altra. l'importante è che finisco il percorso rispettando l'ordine dei nodi.
quindi ho n linee con s nodi di indice j.
ogni nodo ha un tempo di produzione proprio (2 nodi dello stesso indice ma di linee diverse possono avere tempi diversi).
devo fare un algo che mi calcoli il cammino migliore tra le linee di produzione sommando i tempi per ogni nodo visitato.
in più se passo da una linea ad un altra ho un costo di passaggio, costo che è 0 solo se rimando nella stessa linea (ma non è detto che mi convenga perchè magari il costo di passaggio+il costo di produzione del nodo prossimo di un altra linea è cmq minore)
anche i costi di passaggio sono diversi da nodo a nodo.
ho trovato un algo per le catene di montaggio...ma è studiato per 2 linee.
io ho n possibili linee, mi date una mano?
codice:FASTEST-WAY(a, t, e, x, n) 1 f1[1] ← e1 + a1,1 2 f2[1] ←e2 + a2,1 3 for j ← 2 to n 4 do if f1[j - 1] + a1,j ≤ f2[j - 1] + t2,j-1 + a1,j 5 then f1[j] ← f1[j - 1] + a1, j 6 l1[j] ← 1 7 else f1[j] ← f2[j - 1] + t2,j-1 + a1,j 8 l1[j] ← 2 9 if f2[j - 1] + a2,j ≤ f1[j - 1] + t1,j-1 + a2,j 10 then f2[j] ← f2[j - 1] + a2,j 11 l2[j] ← 2 12 else f2[j] ∞ f1[j - 1] + t1,j-1 + a2,j 13 l2[j] ← 1 14 if f1[n] + x1 ≤ f2[n] + x2 15 then f* = f1[n] + x1 16 l* = 1 17 else f* = f2[n] + x2 18 l* = 2
Originariamente inviata da torpedoblu
