Abstract
A complex machine scheduling problem is studied in this research. It is formulated using the traditional integer programming (IP) technique. However, this formulation appears computationally intractable when the problem size becomes large. The special structure of this problem is exploited through a combination of decomposition, a series of reformulations and constraint generation to tighten the formulation. A new formulation is developed to improve the problem-solving efficiency. This formulation is decomposed into a master problem and subproblem such that a Benders Decomposition approach, which was previously developed to handle problems with such structure, can be applied in this research. Benders Decomposition has been applied to a number of practical problems with impressive results. Most of these problems have one feature in common: the subproblem was formulated as an LP problem. Herein the subproblem for the newly developed formulation is not an LP problem; instead, the variables of the subproblem must be integers to be valid. To take substantial advantage of Benders Decomposition algorithm, an LP approximation to the IP subproblem is developed and employed. The results from experimental runs suggest that the IP subproblem can be generally well approximated and allows the decomposition to be effective. This is one of the major contributions of this research. We have shown that Benders Decomposition approach can also be used in some problems where both the master and subproblem are integer programs. The master problem consumes most of the run time when using Benders Decomposition, thus it is the most critical part in terms of computational efficiency. Four approaches with the potential to improve the problem solving-efficiency of the master problem are analyzed. A designed set of test problems covering a substantial variety of problems typical in industry is used as the test bed. The computational results of the newly proposed formulation, P2, incorporating a heuristic method proposed by McDaniel(1977) indicate that it outperforms the traditional IP formulation by a factor of three when medium-sized problems are solved, and from three to ten for large-sized problems.
Wu, Tai-Hsi (1994). Efficient solution of die casting machine scheduling problem using Benders Decomposition approach. Texas A&M University. Texas A&M University. Libraries. Available electronically from
https : / /hdl .handle .net /1969 .1 /DISSERTATIONS -1552139.