The Multi-Product Dynamic Lot Sizing Problem with Capacity Constraints
Open Access
- Author:
- Bunn, Kevin
- Graduate Program:
- Industrial Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- September 29, 2021
- Committee Members:
- Steven Landry, Program Head/Chair
Jose Ventura, Chair & Dissertation Advisor
Saurabh Bansal, Outside Unit & Field Member
Paul Griffin, Major Field Member
Vittaldas Prabhu, Major Field Member - Keywords:
- Supply Chain
Optimization
Dynamic Programming
Lot Sizing
Lagrangian Relaxation - Abstract:
- This dissertation analyzes approaches for solving two multi-product dynamic lot sizing problems with capacity constraints. In the first problem, orders for two products are placed over a set number of periods in order to meet the demand in each period. The amount that can be ordered is restricted by a capacity. There is a cost for placing an order in each period and inventory can be carried over into future periods for a holding cost. Both the ordering and holding costs in this problem are general concave functions. For this problem we present a dynamic programming approach which can be used to find an optimal solution for this problem with complexity O(T^5 I^2), where T is the number of periods and I is an upper bound on the amount of inventory that can be held at the end of any period for either product. We also present a method to scale this dynamic programming technique to three or more products. For a special case of this problem, where the ordering cost consists of a fixed setup cost plus a cost per unit, and the holding costs are also a cost per unit, we present a modification of the dynamic programming algorithm. This modified algorithm can solve the problem with complexity O(T^3 〖(I_1+c)〗^2), where I_1 is an upper bound on the amount of inventory of product 1 that can be held at the end of any period, and c is the capacity. The second problem is a multi-product dynamic lot sizing problem with capacity constraints, where each product has a fixed batch size. This means that when an order is placed for a given product, it must be for a quantity equal to the batch size. In this case, there is a cost associated with each batch, as well as an inventory holding costs. Multiple orders of the same product may be placed in each period. For this problem we present three solution approaches. The first approach is based on Lagrangian relaxation, the second a genetic algorithm, and the third is a dynamic programming technique. Each of these approaches are implemented in MATLAB, as well as a Mixed-Integer Linear Programming (MILP) solver for three different formulations of the problem, to evaluate the performance of each of the approaches.