On transforming job-shops into flow-shops

In this paper the problem of transforming a job-shop environment into a flow-shop is addressed, where scheduling issues are simpler and pull production control systems might be easily applied. A linear programming model employing machine investment minimization as objective function is proposed. For the special case where all machines have the same costs, a branch and bound approach is developed. Both exact approaches prove to be suitable only for small problem instances. For those cases where the exact approaches are not suitable, a local search procedure based in filtered beam search is proposed. The procedure shows how to reach an optimal solution for most of the instances where optimal data are available. For bigger problem instances, the local search procedure outperforms the results obtained by a filtered-beam-search version of the branch and bound algorithm in shorter CPU times.