Skip to content

Lot sizing problems

Part 1 · Combinatorial optimization problems · Chapter 8 · Lecture notes, volume 1 (PDF) · Slides · Exercises: Lot sizing problems

Prerequisites

Objectives

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

  • describe a production plan by its quantities, stocks and setups, and compute its cost;

  • state the capacitated lot sizing problem and name its main variants;

  • decide whether a plan is feasible, and count the feasible setup choices of an instance;

  • build a first plan by hand, merging the demands of consecutive periods;

  • compute a lower bound on the cost from the number of setups that the total demand requires.

8.1 Overview of the family

  • The lot sizing problems share the same data: a set \(T = \{1,2,\dots,m\}\) of \(m\) time periods and, for each period \(t \in T\), a demand \(d_t\), a production capacity and three costs: the setup cost \(sc_t\), the variable production cost \(vc_t\) and the holding cost \(hc_t\).

  • A solution is a production plan: the quantity produced in every period, which determines the stock at the end of each period and the periods with a setup.

  • The objective is to satisfy all the demands at the minimum total cost of setups, production and holding.

A lot sizing problem balances the setup costs, paid in every period with production, against the holding costs of the stock. The members of the family differ in the capacities, in the number of products and in the way the demand and the capacity can be adjusted.

  • The table lists the members of the family, with the section that defines each of them.
Problem Acronym Difference with respect to the CLS Section
capacitated lot sizing problem CLS one product, capacities \(cap_t\) 8.2
uncapacitated lot sizing problem ULS no binding capacity 8.6
several products and setup times MLS products sharing the time of each period 8.6
initial stock LS-SI the initial stock is a decision 8.6
overtime LS-OT extra capacity at a higher cost 8.6
unsatisfied demand LS-UD part of the demand lost at a penalty 8.6

  • Overview

    Overview of the family

    Open

  • 8.2 The capacitated lot sizing problem

    Counting the solutions · A first plan by hand · A combinatorial lower bound

    Open

  • 8.6 Variants

    Several products and setup times · Initial stock · Overtime · Unsatisfied demand · Remarks

    Open

Next: 8.2 The capacitated lot sizing problem

Exercises on this chapter: Lot sizing problems

In depth: what the course does on this problem