Skip to content

Formulations of lot sizing problems

Part 2 · Formulations and their properties · Chapter 15 · Lecture notes, volume 2 (PDF) · Slides · Exercises: Lot sizing problems

Prerequisites

Objectives

At the end of this chapter you will be able to:

  • write the big-M formulation of the capacitated lot sizing problem and compute a weak and a strong big-M value;

  • write the shortest-path formulation and interpret its variables as the arcs of a network;

  • represent a production plan as a combination of paths of the network;

  • compare the LP bounds of the formulations on the reference instance;

  • write the ILP model of the uncapacitated lot sizing problem;

  • extend the big-M formulation to several products with setup times, to the initial stock, to overtime and to unsatisfied demand, and compute the strong big-M values of each model.

15.1 Overview of the family

  • The big-\(M\) models of the lot sizing problems use, for every period \(t \in T\), an integer production variable \(x_t\), an integer inventory variable \(s_t\) and a binary setup variable \(y_t\).

  • The flow balancing constraints link the inventories of consecutive periods to the production and to the demand; the setup variables are linked to the production by big-\(M\) constraints.

  • The objective function minimizes the total cost of setups, production and holding. The shortest-path formulation of the CLS replaces the production and inventory variables with the arcs of a network.

The lot sizing models are flow models over the periods, with binary setup variables that switch the production on. The members of the family add products, setup times, an initial stock, overtime or unsatisfied demand to the same balance and big-\(M\) constraints.

  • The table lists the members of the family, with the names of their models and the sections that write them.
Problem Models Formulation Section
CLS \(\mathrm{ILP}_{\mathrm{CLSP}}\) big-\(M\) formulation 15.3
CLS \(\mathrm{MIP}^{\mathrm{SP}}_{\mathrm{CLSP}}\) shortest-path formulation 15.5
ULS \(\mathrm{ILP}_{\mathrm{ULS}}\) big-\(M\), no capacity 15.7
MLS \(\mathrm{ILP}_{\mathrm{CLSP}}^{P}\) big-\(M\), setup times 15.7
LS-SI \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{SI}}\) big-\(M\), initial stock variables 15.7
LS-OT \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{OT}}\) big-\(M\), overtime variables 15.7
LS-UD \(\mathrm{ILP}_{\mathrm{CLSP}}^{\mathrm{UD}}\) big-\(M\), unsatisfied demand variables 15.7

  • Overview

    Overview of the family

    Open

  • 15.2 ILP models for the Capacitated Lot Sizing Problem

    Weak and strong big-M values

    Open

  • 15.7 ILP models for the variants

    Several products and setup times · Initial stock · Overtime · Unsatisfied demand · Typical mistakes

    Open

Next: 15.2 ILP models for the Capacitated Lot Sizing Problem

Exercises on this chapter: Lot sizing problems