Monday, April 23, 2012

Longest flow shop

I was trying to demonstrate some simple scheduling models. The permutation flow shop has an obvious first solution: run jobs in the order given in the problem data: job1,job2,job3,…. We compared that with the optimal solution:


The model I presented is fairly simple:


Someone came up with the question: “what would the picture look like for the worst permutation?”.

I think this is actually more difficult to model. We assume in several places that jobs are automatically pushed to the left and if we just start to maximize this won’t work anymore.

Of course just trying all solutions would be feasible in this case. We have 10 jobs so 10! = 3,628,800 permutations (just type 10! in google).