Permutation Flow Shop total time

Question

Consider a matrix M(i, j), which describes the total time for machine i to complete job j and a job sequence S which is the order of execution for the jobs. For example:

Like this:

In this case the total time is 13 for S = j1, j2, j3. I use the following code to get this value:

M = matrix(c(4, 2, 2, 5, 3, 2), ncol = 3)
total = 0

for (i in 2:nrow(M))
  total = total + sum( pmax(M[i, ], M[i - 1, ]) )

print(total)

It outputs 12 and it should be 13. Also, i'm not sure how to incorporate S to this. Any ideas on how to get the correct value? Thanks!

Answer 1

I think this does what you're looking for:

M <- matrix(c(4, 2, 2, 5, 3, 2), ncol = 3)
M2 <- cbind(M, matrix(0, nrow=nrow(M), ncol=nrow(M) - 1))
vec <- seq(len=ncol(M2))
M2.ord <- M2
for(i in 1:nrow(M2)) {
  M2.ord[i, ] <- vec
  vec <- c(tail(vec, 1), head(vec, -1)) + ncol(M2)
}
M2.shift <- matrix(t(M2)[M2.ord], nrow=nrow(M2))
sum(do.call(pmax, split(M2.shift, row(M2.shift))))

The annoying step is creating M2.shift:

     [,1] [,2] [,3] [,4]
[1,]    4    2    3    0
[2,]    0    2    5    2

From that point forward, it's pretty much the logic you used. Note that this assumes we use all steps defined in M.