Note—Operations Sequencing in Discrete Parts Manufacturing
提出一种算法，用于高效排序数控机床加工离散零件时的切割操作。先建模为整数规划，再通过拉格朗日松弛转化为二分网络上的最小割问题，用最大流算法得到紧下界，再用贪心启发式生成可行解，最后用分支定界找到最优解。
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.