Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1999. / Includes bibliographical references (leaves 103-106). / In this thesis, we develop practical solution methods for a supply chain optimization problem: a multi-echelon, un capacitated, time-expanded network of distribution centers and stores, for which we seek the shipping schedule that minimizes total inventory, backlogging, and shipping costs, assuming deterministic, time-varying demand over a fixed time horizon for a single product. Because of fixed ordering and shipping costs, this concave cost network flow problem is in a class of NP-hard network design problems. We develop mathematical programming formulations, heuristic algorithms, and enhanced algorithms using approximate dynamic programming (ADP). We achieve a strong mixed integer programming (MIP) formulation, and fast, reliable algorithms, which can be extended to problems with multiple products. Beginning with a lot-size based formulation, we strengthen the formulation in steps to develop one which is a variation of a node-arc formulation for the network design problem. In addition, we present a path-flow formulation for the single product case and an enhanced network design formulation for the multiple product case. The basic algorithm we develop uses a dynamic lot-size model with backlogging together with a greedy procedure that emulates inventory pull systems. Four related algorithms perform local searches of the basic algorithm's solution or explore alternative solutions using pricing schemes, including a Lagrangian-based heuristic. We show how approximate dynamic programming can be used to solve this supply chain optimization problem as a dynamic control problem using any of the five algorithms. In addition to improving all the algorithms, the ADP enhancement turns the simplest algorithm into one comparable to the more complex ones. Our computational results illustrate that our enhanced network design formulation almost always produces integral solutions and can be used to solve problems of moderate size (3 distribution centers, 30 stores, 30 periods). Our heuristic methods, particularly those enhanced by ADP methods, produce near optimal solutions for truly large scale problems. / by Carl E. Wike. / S.M.
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/9763 |
| Date | January 1999 |
| Creators | Wike, Carl E., 1948- |
| Contributors | Dimitris J. Bertsimas., Massachusetts Institute of Technology. Operations Research Center, Sloan School of Management |
| Publisher | Massachusetts Institute of Technology |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 106 leaves, 5348861 bytes, 5348621 bytes, application/pdf, application/pdf, application/pdf |
| Rights | M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission., http://dspace.mit.edu/handle/1721.1/7582 |
Page generated in 0.0143 seconds