Efficient heuristic approaches to transform job shops into flow shops

Abstract

In this paper, we address the problem of transforming a job shop layout into a flow shop with the objective of minimizing the length of the resulting flow line. Since this problem is NP-hard, we focus our attention on developing high quality approximate solutions. We start by reviewing existing heuristics for the problem as well as some heuristics developed for the Shortest Common Supersequence problem, a well-known stringology problem similar to the one under consideration. We then present a new decomposition approach for the problem that allows the application of local search techniques. We have embedded this approach into a tabu search procedure that is shown to be effective in subsequent computational experiments. Finally, we provide best-so-far solutions for classical job shop problem instances, so they can be used as benchmark instances for further research.