Lot size problem

From Glossary

Jump to: navigation, search

This is one of the oldest mixed-integer programs in operations research, first presented by Wagner and Whitin in 1958. The problem is to minimize cost while satisfying product demands over (discrete) time. Let LaTeX: y_t be the number of units produced in period LaTeX: t, for LaTeX: t=1,\ldots,T (LaTeX: T is called the planning horizon), and let LaTeX: x_t = 1 if a setup occurs in period LaTeX: t; LaTeX: 0 otherwise. Let LaTeX: D_t be the demand in period LaTeX: t, and let the demand from period LaTeX: i to period LaTeX: j, inclusive, be LaTeX: d_{ij} = \sum_{i \le t \le j} D_t. Then, a MILP formulation is:

LaTeX: \min \left\{ c^T x + d^T y: x \in \{0,1\}^n, \, y \ge 0, 
\sum_{t\le i} y_t \ge d_{li} \mbox{ for } i=1, \ldots,n-1, \,
\sum_{t\le n} y_t = d_{1n}, \,
d_{in} x_i - y_i \ge 0 \mbox{ for } i=1, \ldots,n \right\}.

(This is preferred over the MILP that defines inventory balance equations. Even though they are equivalent, the LP relaxation of the above is sharper.)

Personal tools