Lecture V - Production Planning in Breweries

Applied Optimization with Julia

Author

Dr. Tobias Vlćek

Introduction

Case Study

Large brewery
Brews and sells beverages
Production planning by hand
Planner has a lot of experience
But will retire soon

Challenges

Strong competition
Customer demand is changing
Craft beer gains popularity
Variety of drinks is increasing
Batch sizes are getting smaller

Different costs

Plant can fill multiple types
Time depends on type and batch
Changing type leads to set-up costs for preparation and cleaning
Unsold beer bottles can be stored in a warehouse
This leads to inventory costs

Where is the

challenge?

Problem Structure

Objective

Question: What could be the objective?

Minimize the combined setup and inventory holding cost while satisfying the demand and adhering to the production capacity.

Trade-Off

Question: What is the trade-off?

Larger batches require less setup cost per bottle, but increase the storage cost.

Available Sets

Question: What are sets again?

. . .

Sets are collections of objects.

. . .

Question: What could be the sets here?

. . .

$I$ - Set of beer types indexed by $i \in {1, 2, . . ., | I |}$
$T$ - Set of time periods indexed by $t \in {1, 2, . . ., | T |}$

Available Parameters

Question: What are possible parameters?

. . .

$a_{t}$ - Available time on the bottling plant in period $t \in T$
$b_{i}$ - Time used for bottling one unit of beer type $i \in I$
$g_{i}$ - Setup time for beer type $i \in I$
$f_{i}$ - Setup cost of beer type $i \in I$
$c_{i}$ - Inventory holding cost for one unit of beer type $i \in I$
$d_{i, t}$ - Demand of beer type $i \in I$ in period $t \in T$

Decision Variables?

We have the following sets:

Beer types indexed by $i \in {1, 2, . . ., | I |}$
Time periods of the planning horizon indexed by $t \in {1, 2, . . ., | T |}$

. . .

Our objective is to:

Minimize the combined setup and inventory holding cost while satisfying the demand and adhering to the production capacity.

. . .

Question: What could be our decision variable/s?

Decision Variables

$W_{i, t}$ - Inventory of type $i \in I$ at the end of $t \in T$
$Y_{i, t}$ - 1, if type $i \in I$ is bottled in $t \in T$ , 0 otherwise
$X_{i, t}$ - Batch size of type $i \in I$ in $t \in T$

Model Formulation

Objective Function?

Our objective is to:

Minimize the combined setup and inventory holding cost while satisfying the demand and adhering to the production capacity.

. . .

Question: What could be our objective function?

. . .

We need the following variables:

$W_{i, t}$ - Inventory of type $i \in I$ at the end of $t \in T$
$Y_{i, t}$ - 1, if type $i \in I$ is bottled in $t \in T$ , 0 otherwise

Objective Function

We need the following parameters:

$f_{i}$ - Setup cost of beer type $i \in I$
$c_{i}$ - Inventory holding cost for one unit of beer type $i \in I$

. . .

$Minimize \sum_{i = 1}^{I} \sum_{t = 1}^{T} (c_{i} \times W_{i, t} + f_{i} \times Y_{i, t})$

Constraints

Question: What constraints?

Transfer unused inventory
Fulfill the customer demand
Set up beer types
Calculate the batch size per set-up
Compute remaining inventory
Limit the bottling plant

Demand/Inventory Constraints?

The goal of these constraints is to:

Consider the current inventory and batch sizes and compute the remaining inventory.

. . .

We need the following variables and parameters:

$W_{i, t}$ - Inventory of beer type $i \in I$ at the end of period $t \in T$
$X_{i, t}$ - Batch size of beer type $i \in I$ in $t \in T$
$d_{i, t}$ - Demand of beer type $i \in I$ in period $t \in T$

. . .

Question: What could the constraint look like?

Demand/Inventory Constraints

$W_{i, t - 1} + X_{i, t} - W_{i, t} = d_{i, t} \forall i \in I, t \in T | t > 1$

. . .

Remember, these are the variables and parameters:

$W_{i, t}$ - Inventory of beer type $i \in I$ at the end of period $t \in T$
$X_{i, t}$ - Batch size of beer type $i \in I$ in $t \in T$
$d_{i, t}$ - Demand of beer type $i \in I$ in period $t \in T$

. . .

Question: What does $| t > 1$ mean?

Setup Constraints?

The goal of these constraints is to:

Set up beer types where the batch size is $\geq$ 0.

. . .

We need the following variables and parameters:

$Y_{i, t}$ - 1, if beer type $i \in I$ is bottled in period $t \in T$ , 0 otherwise
$X_{i, t}$ - Batch size of beer type $i \in I$ in $t \in T$
$d_{i, t}$ - Demand of beer type $i \in I$ in period $t \in T$

. . .

Question: What could the second constraint be?

Setup Constraints

$X_{i, t} \leq Y_{i, t} \times \sum_{τ = 1}^{T} d_{i τ} \forall i \in I, \forall t \in T$

. . .

Question: Do you know this type of constraint?

. . .

This type of constraint is called a “Big-M” constraint!

. . .

M (here $\sum_{τ = 1}^{T} d_{i τ}$ ) is a large number
It is coupled with a binary variable (here $Y_{i, t}$ )
Like an if-then constraint

Capacity Constraints?

The goal of these constraints is to:

Limit the capacity of the bottling plant per period.

. . .

We need the following variables and parameters:

$Y_{i, t}$ - 1, if beer type $i \in I$ is bottled in period $t \in T$ , 0 otherwise
$X_{i, t}$ - Batch size of beer type $i \in I$ in $t \in T$
$a_{t}$ - Available time on the bottling plant in period $t \in T$
$b_{i}$ - Time used for bottling one unit of beer type $i \in I$
$g_{i}$ - Setup time for beer type $i \in I$

Capacity Constraints

Question: What could the third constraint be?

It has more variables and parameters when compared to the other constraints but it is easier to understand.

. . .

$\sum_{i = 1}^{I} (b_{i} \times X_{i, t} + g_{i} \times Y_{i, t}) \leq a_{t} \forall t \in T$

. . .

And that’s basically it!

CLSP: Objective Function

$Minimize \sum_{i \in I} \sum_{t \in T} (c_{i} \times W_{i, t} + f_{i} \times Y_{i, t})$

The goal of the objective function is to:

Minimize the combined setup and inventory holding cost while satisfying the demand and adhering to the production capacity.

CLSP: Constraints

$W_{i, t - 1} + X_{i, t} - W_{i, t} = d_{i, t} \forall i \in I, t \in T | t > 1$

$X_{i, t} \leq Y_{i, t} \times \sum_{τ \in T} d_{i, τ} \forall i \in I, \forall t \in T$

$\sum_{i \in I} (b_{i} \times X_{i, t} + g_{i} \times Y_{i, t}) \leq a_{t} \forall t \in T$

Our constraints ensure:

Demand is met, inventory transferred, setup taken care of, and capacity respected.

CLSP: Variable Domains

$Y_{i, t} \in {0, 1} \forall i \in I, t \in T$

$W_{i, t}, X_{i, t} \geq 0 \forall i \in I, t \in T$

The variable domains make sure that:

The binary setup variable is either 0 or 1 and that the inventory and batch size are non-negative.

Model Characteristics

Recap on some Basics

There exist several types of optimization problems:

Linear (LP): Linear constraints and objective function
Mixed-integer (MIP): Linear constraints and objective function, but discrete variable domains
Quadratic (QP): Quadratic constraints and/or objective
Non-linear (NLP): Non-linear constraints and/or objective
And more!

Recap on Solution Algorithms

Simplex algorithm to solve LPs
Branch & Bound to solve MIPs
Outer-Approximation for mixed-integer NLPs
Math-Heuristics (e.g., Fix-and-Optimize, Tabu-Search, …)
Decomposition methods (Lagrange, Benders, …)
Heuristics (greedy, construction method, n-opt, …)
Graph theoretical methods (network flow, shortest path)

Model Characteristics

Questions: On model characteristics

Is the model formulation linear/ non-linear?
What kind of variable domains do we have?
What kind of solver could we use?
Can the Big-M constraint be tightened?

Model Assumptions

Questions: On model assumptions

What assumptions have we made?
What is the problem with the planning horizon?
Any idea how to solve it?

Impact

Can this be

applied?

Scale as a Problem

Solving the problem with commercial solvers is not feasible.

Scale of the Case Study

220 finished products
100 semi-finished products
13 production resources
8 storage resources
3 main production levels
52 weeks planning horizon

Any idea what

could be done?

Heuristics and Optimization

Multi-level Capacitated Lot-Sizing Problem
Heuristic fix and optimize approach ¹
Operating cost reduction by 5% and planning effort by 40%

. . .

And that’s it for todays lecture!

We now have covered the basics of the CLSP and are ready to start solving some tasks in the upcoming tutorial.

Questions?

Literature

Literature I

For more interesting literature to learn more about Julia, take a look at the literature list of this course.

Literature II

Mickein, Markus, Matthes Koch, and Knut Haase. 2022. “A Decision Support System for Brewery Production Planning at Feldschlösschen.” INFORMS Journal on Applied Analytics 52 (2): 158–72.

Footnotes

Mickein, Koch, and Haase (2022)↩︎