Lecture V - Production Planning in Breweries
Applied Optimization with Julia
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
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?
. . .
- \(\mathcal{I}\) - Set of beer types indexed by \(i \in \{1,2,...,|\mathcal{I}|\}\)
- \(\mathcal{T}\) - Set of time periods indexed by \(t \in \{1,2,...,|\mathcal{T}|\}\)
Available Parameters
Question: What are possible parameters?
. . .
- \(a_t\) - Available time on the bottling plant in period \(t\in\mathcal{T}\)
- \(b_i\) - Time used for bottling one unit of beer type \(i\in\mathcal{I}\)
- \(g_i\) - Setup time for beer type \(i\in\mathcal{I}\)
- \(f_i\) - Setup cost of beer type \(i\in\mathcal{I}\)
- \(c_i\) - Inventory holding cost for one unit of beer type \(i\in\mathcal{I}\)
- \(d_{i,t}\) - Demand of beer type \(i\in\mathcal{I}\) in period \(t\in\mathcal{T}\)
Decision Variables?
- Beer types indexed by \(i \in \{1,2,...,|\mathcal{I}|\}\)
- Time periods of the planning horizon indexed by \(t \in \{1,2,...,|\mathcal{T}|\}\)
. . .
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\mathcal{I}\) at the end of \(t\in\mathcal{T}\)
- \(Y_{i,t}\) - 1, if type \(i\in\mathcal{I}\) is bottled in \(t\in\mathcal{T}\), 0 otherwise
- \(X_{i,t}\) - Batch size of type \(i\in\mathcal{I}\) in \(t\in\mathcal{T}\)
Model Formulation
Objective Function?
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?
. . .
- \(W_{i,t}\) - Inventory of type \(i\in\mathcal{I}\) at the end of \(t\in\mathcal{T}\)
- \(Y_{i,t}\) - 1, if type \(i\in\mathcal{I}\) is bottled in \(t\in\mathcal{T}\), 0 otherwise
Objective Function
- \(f_i\) - Setup cost of beer type \(i\in\mathcal{I}\)
- \(c_i\) - Inventory holding cost for one unit of beer type \(i\in\mathcal{I}\)
. . .
\[\text{Minimize} \quad \sum_{i=1}^{\mathcal{I}} \sum_{t=1}^{\mathcal{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?
Consider the current inventory and batch sizes and compute the remaining inventory.
. . .
- \(W_{i,t}\) - Inventory of beer type \(i\in\mathcal{I}\) at the end of period \(t\in\mathcal{T}\)
- \(X_{i,t}\) - Batch size of beer type \(i\in\mathcal{I}\) in \(t\in\mathcal{T}\)
- \(d_{i,t}\) - Demand of beer type \(i\in\mathcal{I}\) in period \(t\in\mathcal{T}\)
. . .
Question: What could the constraint look like?
Demand/Inventory Constraints
\[W_{i,t-1} + X_{i,t} - W_{i,t} = d_{i,t} \quad \forall i\in\mathcal{I},t\in\mathcal{T}|t>1\]
. . .
- \(W_{i,t}\) - Inventory of beer type \(i\in\mathcal{I}\) at the end of period \(t\in\mathcal{T}\)
- \(X_{i,t}\) - Batch size of beer type \(i\in\mathcal{I}\) in \(t\in\mathcal{T}\)
- \(d_{i,t}\) - Demand of beer type \(i\in\mathcal{I}\) in period \(t\in\mathcal{T}\)
. . .
Question: What does \(|t>1\) mean?
Setup Constraints?
Set up beer types where the batch size is \(\geq\) 0.
. . .
- \(Y_{i,t}\) - 1, if beer type \(i\in\mathcal{I}\) is bottled in period \(t\in\mathcal{T}\), 0 otherwise
- \(X_{i,t}\) - Batch size of beer type \(i\in\mathcal{I}\) in \(t\in\mathcal{T}\)
- \(d_{i,t}\) - Demand of beer type \(i\in\mathcal{I}\) in period \(t\in\mathcal{T}\)
. . .
Question: What could the second constraint be?
Setup Constraints
\[X_{i,t} \leq Y_{i,t} \times \sum_{\tau=1}^{\mathcal{T}} d_{i\tau} \quad \forall i\in\mathcal{I},\forall t\in\mathcal{T}\]
. . .
Question: Do you know this type of constraint?
. . .
This type of constraint is called a “Big-M” constraint!
. . .
- M (here \(\sum_{\tau=1}^{\mathcal{T}} d_{i\tau}\)) is a large number
- It is coupled with a binary variable (here \(Y_{i,t}\))
- Like an if-then constraint
Capacity Constraints?
Limit the capacity of the bottling plant per period.
. . .
- \(Y_{i,t}\) - 1, if beer type \(i\in\mathcal{I}\) is bottled in period \(t\in\mathcal{T}\), 0 otherwise
- \(X_{i,t}\) - Batch size of beer type \(i\in\mathcal{I}\) in \(t\in\mathcal{T}\)
- \(a_t\) - Available time on the bottling plant in period \(t\in\mathcal{T}\)
- \(b_i\) - Time used for bottling one unit of beer type \(i\in\mathcal{I}\)
- \(g_i\) - Setup time for beer type \(i\in\mathcal{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}^{\mathcal{I}} (b_i \times X_{i,t} + g_i \times Y_{i,t}) \leq a_t \quad \forall t\in\mathcal{T}\]
. . .
And that’s basically it!
CLSP: Objective Function
\[\text{Minimize} \quad \sum_{i \in \mathcal{I}} \sum_{t \in \mathcal{T}} (c_i \times W_{i,t} + f_i \times Y_{i,t})\]
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} \quad \forall i\in\mathcal{I},t\in\mathcal{T}|t>1\]
\[X_{i,t} \leq Y_{i,t} \times \sum_{\tau \in \mathcal{T}} d_{i,\tau} \quad \forall i\in\mathcal{I},\forall t\in\mathcal{T}\]
\[\sum_{i \in \mathcal{I}} (b_i \times X_{i,t} + g_i \times Y_{i,t}) \leq a_t \quad \forall t\in\mathcal{T}\]
Demand is met, inventory transferred, setup taken care of, and capacity respected.
CLSP: Variable Domains
\[Y_{i,t}\in\{0,1\} \quad \forall i\in\mathcal{I},t\in\mathcal{T}\]
\[W_{i,t}, X_{i,t}\geq 0 \quad \forall i\in\mathcal{I},t\in\mathcal{T}\]
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
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
Heuristics and Optimization
- Multi-level Capacitated Lot-Sizing Problem
- Heuristic fix and optimize approach 1
- Operating cost reduction by 5% and planning effort by 40%
. . .
We now have covered the basics of the CLSP and are ready to start solving some tasks in the upcoming tutorial.
Literature
Literature I
For more interesting literature to learn more about Julia, take a look at the literature list of this course.