Article ID: | iaor1999107 |
Country: | United Kingdom |
Volume: | 25 |
Issue: | 2 |
Start Page Number: | 159 |
End Page Number: | 168 |
Publication Date: | Feb 1998 |
Journal: | Computers and Operations Research |
Authors: | McKnew Mark A., Cao Qidong |
Keywords: | programming: integer |
Mathematical programming models for manufacturing cell formation problems are primarily integer programming models with the special structure of being ‘multidivision problems’. Lagrangian relaxation has been one of the best decomposition approaches and enabled the solution of problems of practical size. This research develops a partial termination rule for the Lagrangian relaxation algorithm. While the existing algorithm solves all submodels in each iteration, the partial termination rule recognizes early termination of some submodels. This results in a substantial reduction of computation while generating the same solution. The new termination rule is proven mathematically. Thus, its applicability extends beyond the solution of the manufacturing cell formation problem.