A framework of using linear programming for manufacturing scheduling

It has been shown that the Lagrangian relaxation approach can be used successfully to develop pragmatic manufacturing scheduling strategies. To apply it to real world situations, it is important to develop an efficient algorithm to solve its associated nondifferentiable dual problem. In this paper, we present a framework to address this issue. By converting the dual problem into an equivalent linear programming (LP) problem, we can use numerous existing LP methods to solve it. Based upon the LP problem, we can also develop families of algorithms for the original dual problem. We present among numerous choices a method of using the LP framework to develop families of algorithms to find an optimal solution of the dual problem. Numerical examples are given to illustrate the potential of the algorithm by comparing it with a subgradient algorithm. An efficient initialization algorithm is also presented, and its implication discussed