Two machine flow shop with blocking have been studied for about 50 years. The most famous solution is about converting it into a TSP problem. Is there other approach to get optimal solutions for this solution.
It is NP-hard, so you won't find anything significantly better. Johnson's rule for the case of makespan without blocking can build up a huge buffer (see reference below) so it is not going to give you a good heuristic.
Ramudhin, A., Bartholdi, J. J. III, Calvin, J. M., Vande Vate, J. H. and Weiss, G., "A Probabilistic Analysis of 2-Machine Flowshops", Operations Research, 44 No. 6, pp. 899-908, 1996.
it is NP-hard problem so the exact solution for large and medium sale problem are not reachable.
Yes, TSP is NP-hard, BUT the best algorithm to date, Concorde, can solve problems with up to 84900 cities to optimality (using super-computers), but problems less than, say 2000 cities can be solved in a reasonable time. Furthermore: CONCORDE IS OPENSOURCE, you can download it from: http://www.math.uwaterloo.ca/tsp/index.html
Best Regards Thomas
- Badges
- Science topic