Note—Operations Sequencing in Discrete Parts Manufacturing

Management Science · 1989 · Volume 35 · Issue 2

Abstract

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.

Keywords

flexible manufacturing systems, integer programming, Lagrangian relaxation, branch and bound, computer-aided process planning

Enable JavaScript for citation tools and additional paper interactions.