Backtracking of jobs in one-dimensional machine location problems

Materials that must be transported upstream in a production line along a linear track are said to backtrack. In this line, management attempts to simplify the workflow of jobs by assigning machines to appropriate locations along the line to minimize backtracking. The problem of assigning M machines to M locations along a linear track to minimize the total backtracking of jobs forms a quadratic assignment problem and is a difficult task; an optimum solution to such a problem with large M is computationally intractable. Therefore, an efficient, depth-first insertion heuristic is used here to improve the solution obtained by a construction heuristic, called multi-pass heuristic. A lower bound to assess the quality, and a measure of backtracking to assess the proximity of a configuration to a generalized flow line are developed in this paper. In addition to computational results, a simulation model is also used to assess the effect of reducing backtracking on overall system performance in a dynamic environment.