Browse Prior Art Database

Supply chain optimization : formulations and algorithms

IP.com Disclosure Number: IPCOM000128078D
Original Publication Date: 1999-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 5 page(s) / 18K

Publishing Venue

Software Patent Institute

Related People

Wike, Carl E.: AUTHOR [+3]

Related Documents

http://theses.mit.edu:80/Dienst/UI/2.0/Describe/0018.mit.theses/1999-133: URL

Abstract

In this thesis, we develop practical solution methods for a supply chain optimization problem: a multi-echelon, uncapacitated, timeexpanded network of distribution centers and stores, for which we seek the shipping schedule that minimizes total inventory, backlogging, and shipping costs, assuming deterministic, timevarying 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.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 45% of the total text.

Page 1 of 5

 This record is the front matter from a document that appears on a server at MIT and is used through permission from MIT. See http://theses.mit.edu:80/Dienst/UI/2.0/Describe/0018.mit.theses/1999-133 for copyright details and for the full document in image form.

Supply Chain Optimization: Formulations and Algorithms

by

Carl E. Wike
B.S., Applied Mathematics, North Carolina State University Submitted in partial fulfillment of the requirements for the degree of Operations Research
Sloan School of Management

at the Massachusetts Institute of Technology

February 1999
SIGNATURE OF author: [[signature omitted]]

Sloan School of Management August 31, 1998
CERTIFIED BY: [[SIGNATURE OMITTED]]

Dimitris J. Bertsimas Boeing Professor of Operations Research Thesis Supervisor ACCEPTED BY: [[SIGNATURE OMITTED]]

James B. Orlin
E. Pennell Brooks Professor of Operations Research Co-director, Operations Research Center ARCHIVES MASSACHUSETTS INSTITUTE OF TECHNOLOGY LIBRARIES FEB 22 1999

Massachusetts Institute of Technology Page 1 Dec 31, 1999

Page 2 of 5

Supply chain optimization : formulations and algorithms

Supply Chain Optimization: Formulations and Algorithms

by

Carl E. Wike

B.S., Applied Mathematics, North Carolina State University

Submitted to the Sloan School of Management on August 31, 1998, in partial fulfillment of the requirements for the degree of Master of Science in Operations Research

Abstract

In this thesis, we develop practical solution methods for a supply chain optimization problem: a multi-echelon, uncapacitated, timeexpanded network of distribution centers and stores, for which we seek the shipping schedule that minimizes total inventory, backlogging, and shipping costs, assuming deterministic, timevarying 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 nodearc 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 d...