Article ID: | iaor19881008 |
Country: | United States |
Volume: | 35 |
Issue: | 2 |
Start Page Number: | 249 |
End Page Number: | 255 |
Publication Date: | Feb 1989 |
Journal: | Management Science |
Authors: | Bard Jonathan F., Feo Thomas A. |
Keywords: | production, programming: integer |
This paper presents an algorithm for efficiently sequencing the cutting operations associated with the manufacture of discrete parts on a CNC machine. The problem is first modeled as an integer program but recast via Lagrangian relaxation as a min-cut problem on a bipartite network. Tight lower bounds are obtained with a max-flow algorithm. The corresponding solution is used as input to a greedy heuristic which generates ‘good’ feasible points. Given nonconvergence, a branch and bound strategy is used to find the optimal solution.