Uncapacitated lot sizing problem (ULS)

Catalogue of combinatorial problems · Lot sizing problems · Catalogue (PDF)

Definition 1: Uncapacitated lot sizing problem

Given:

1. a set \(T=\{1,2,\dots,m\}\) of \(m \in \Z_{\ge 1}\) time periods,

2. for each period \(t \in T\), a demand \(d_t \in \Z_{\ge 1}\),

3. for each period \(t \in T\), a setup cost \(sc_t \in \Z_{\ge 0}\), a variable production cost \(vc_t \in \Z_{\ge 0}\) per unit, and a holding cost \(hc_t \in \Z_{\ge 0}\) per unit in stock at the end of period \(t\),

the Uncapacitated Lot-Sizing Problem (ULS) asks to decide how many units to produce in each period, so that, starting with an empty inventory and ending with an empty inventory, the demand of every period is satisfied, and the total cost of setups, production, and holding is minimized.

Assumptions

• We make the following assumptions:

  1. There is a single product, and the stock is empty at the beginning and at the end of the horizon: the ULS is the CLS of a single product without capacities and with no initial stock.

  2. The quantities are integer. With integer data, once the periods with a setup are fixed, what remains is a minimum cost flow problem, which has an integer optimal solution: restricting the quantities to integers does not change the optimal cost.

What the course does on this problem

Technique	Where
Definition	This page
Formulations	Ch. 15 «Formulations of lot sizing problems»
Dynamic programming	Ch. 16 «Principles of dynamic programming»; Ch. 25 «DP for the uncapacitated lot sizing problem»
MIP heuristics	Ch. 33 «MIP heuristics for the classical problems»
Exercises	Exercise 8.4; Exercise 15.6; Ch. 25 (3 exercises)