Theory Flashcards
Strategic Supply Chain Model ?
Production Capacity is a VARIABLE:
- Binary: building/closing of a production site/line
- Continuous: what capacity to install
Usually Multi-Site: consideration for transportation between production site/depots/customers
Product Model: use one Generic (tons, pounds, square meter)
Strategic Supply Chain questions ?
- Where should I build a production line ?
- Should I start serving clients in Asia ?
- How to structure my transportation/distribution network ?
Tactical Supply Chain Model ?
- Time: Multi-periods, days to months
- Given demand to be satisfied, and/or sales with maximum amount and price
- Production Capacity is given (including set-up/start-up/change-over costs
- Main decision is lot-size/production mix
- Possibly multi-level: some products are produced as input to others
Tactical Supply Chain questions ?
- What mix should I produce in each factory during next month ?
- Which contract should I use ?
- When should I plan the maintenance of my units ?
- What is the aggregate production plan to communicate to the plant manager ?
- What is the expected capacity usage/service level over the next months ?
- What is the expected lot size for the next month ?
Operational Supply Chain Model ?
- Time: Days to continuous
- Given demand to be satisfied
- Each production lines with its specificities is modelled
- Close to scheduling problem with:
- precedence constraints
- changeover time
- Product model: SKU Decision variable:
- machine assignment
- lot-size
- detailed production/transportation schedule
Operation Supply Chain questions ?
- What is the schedule for each production line at each moment for the next day ?
- In which order should the tasks be performed ?
- What is the precise routing of each vehicle in my transportation fleet ?
- And what should each individual vehicle carry ?
- What will be exactly the state of my stock at the end of the day ?
What is a graph ?
A graph is defined by:
- a set of Nodes (V)
- a set of Edges (E) with E included in V x V = a set of pairs (i, j) of nodes i, j included in V
What is a directed graph or digraph ?
A digraph is defined by:
- a set of Nodes (V)
- a set of Arcs (A) with A included in V x V = a set of ordered pairs (i, j) of nodes i, j included in A
What is the purpose of a graph ?
A graph is an abstraction used to model connections (edges, arcs) between agents (nodes).
A generic Strategic Supply Chain Model
SETS:
- S # set of suppliers
- P # set of production sites
- D # set of distribution center
- C # set of customers
VARIABLES:
- up, ud : quantity of goods annually handled by the corresponding site/center
- yp, yd : binary variable indicating if the corresponding site/center is open
- fsp, fpd, fdc : flow of goods between the corresponding entities
- wsp, wpd, wdc : corresponding binary variables indicating if the arc is open
PARAMETERS:
- Dc : demand at the customer site
CONSTRAINTS:
- Demand satisfaction: Σdfdc >= Dc for all c
- Flow Conservation & Capacity at Distribution and Production Site
How to estimate fixed costs ?
We have to compute the NPV of the investment.
How to extend to Multi-Item case ?
The typical case is when several product families share a common facility, therefore share the fixed cost.
For the model: just add an index set I and indices i for all variables and constraints (representing the different products).
How to extend to Multi-Periods case ?
Add set T for periods and associate index t to all variables & constraints.
Standard Capacitated dynamic lot-sizing model LS-C
- Discrete time horizon: set of periods indexed by t in (1..n)
- Demand Dt >= 0 for each period
- Production Capacity Ct for each period
- Production cost in period t is composed of two components
- a fixed cost ft
- a variable cost vt
- Holding costs ha only one variable component ht
- The objective is to decide the production level in each period in order to minimize production and holding costs while satisfying all customer demand on time
The model
Variables:
- xt >= 0: production in period t, with t in (1..n)
- st >= 0: stock at the end of period t, with t in (0..n-1)
- yt = {0, 1}: is one if there is a setup in period t (in this case production xt may be positive, but setup cost is incurred), and 0 if not
Lot-Sizing: network model
What if we can only produce in full batches?
We obtained this model by fixing the LS model with
xt = Ct* yt
► Just allow yt to be integer instead of binary.
What are the 3 types of capacity and how to model them ?
- C: varying capacity: capacity is different in each period
- CC: constant capacity: capacity is the same in each period
- U: Uncapacitated: capacity is so big that it is never binding
NB:
- lot-syzing problems with varying capacity are NP-Hard !
- lot-sizing problems with constant capacity or uncapacitated are polynomially solvable
- but uncapacitated problems are easier than capacitated ones
What is Backlogging ?
Service level is usually an important criterion/constraint in production environment, you want to:
- minimize cost, but still reaching a minimum service level
- otherwise it’s just less costly to produce nothing
Until now we’ve always assumed 100% service level (all demand is always satisfied on time. But sometimes, 99% service level might be acceptable and save a lot.
Therefore, backlogging is the satisfaction of the demand, but not necessarily on time, with some penalty.
The backlog at the end of period t is the amount of gods produced after t to satisfy some demand in t or before.
Lot-Sizing with Backlogging: Network model
What is the lead time?
In some applications, time periods are small so that if production of product i is started in period t, then it is only available for (own or external) consumption at time t + tlead.
If there is only one single item, if suffices to shift the demand earlier by t(lead) periods.
How to model Lead Time ?
What is Startup cost ?
Setup cost in incurred in each period where there is positive production. There is a start up cost in period t if there is no setup in period t-1 and there is a setup in period t.
What is a shutdown ?
There is a shutdown in period t if there is a setup in period t-1 and no setup in period t.
Suppose we have several products that share a common production line, how do we model the constraint ?
Joint Capacity Constraints
The most basic constraint is: sum xi,t <= C for all t.
The total quantity on the line is limited by a given capacity C.
This stands true as long as:
- x(i, t) represents items differing by colour only.
- sum xi,t <= Ct *for all t.
- For some reasons the production capacity can vary from one period to the next
- different number of shifts
- each period has different number of working days
What if the products are different ant the production rate of each product is different?
We will express the capacity in minutes/hours/days to have a unit that is common to all items/products.
Thus, we have
sum æi * xi, t <= Ct for all t.
where æi is the amount of time necessary to produce one unit of item i and Ct is the amount of production time in period t.
What is “Complete Enumeration” ?
A continuous problem has an infinite number of solutions.
A binary/integer problem has only a finite number of solutions. Therefore, we can just check all possible solutions ?
Definition: for each combination of values for the binary/integer variables, compute the best choice for the continuous variables (linear program). Among those that are feasible, choose the solution that gives the best objective.
2 binary variables ? 4 possibilities
4 binary variables ? 16 possibilities
— > OK by hand
10 binary variables ? 1024 possibilities
— > OK with a computer
100 … 402 million centuries
► This is the combinatorial explosion.
What should we do when solving MILP ?
We want to solve general (hard) Mixed-Integer Linear Programs, but we can only solve easier problems:
- Linear Programs
- Some specific problems (shortest path, network flow, spanning tree, etc)
► So that we need to transform the original problem into an easier problem that we can solve !
What is a relaxation?
The optimization problem X is a relaxation of the optimization program Y if
- The feasible region of X is larger than the feasible region of Y
- For maximization problems the objective function of X is larger than that of Y for all solutions feasible in Y (for minimization problems, smaller).
What are the two types of relaxations ?
- The Linear Programming Relaxation (or LP relaxation) of an MILP is obtained by just dropping the integrality requirements
- no modification of the objective function
- it transforms any MILP into a LP
- The Lagrangean relaxation is obtained by replacing “complicating constraints” by a penalty in the objective.
What two bounds can we obtain after relaxation ?
The optimal solution value of a relaxation gives a upper bound on the optimal solution value of the original maximization problem (and a lower bound fo minimization problem).
What if after you solve the relaxation you see that the relaxation is infeasible ?
Then the original problem is infeasible as well, as any feasible solution of the original problem is also feasible in the relaxation.
What if you solve the relaxation and you obtain an optimal solution, that is feasible in the original problem and for which the relaxed objective function is the same as the original function ?
Then you have solved the original problem ! Indeed there cannot be a better solution of the original problem, otherwise it would be a better solution of the relaxed problem as well.
What is Branch-and-Bound ?
B and B solves the relaxation of a series of problems where some variables are fixed.
The goal is to
- find the optimal solution
- prove that any other feasible solution in not better than the optimal solution
- and to do this by solving as few problems as possible
During the course of the algorithm, we keep in memory the best solution found so far, the “incumbent solution” and its value.
How does Branch-and-Bound work ?
How to do the Branch and Bound Algorithm ?
- INITIALIZATION: Make the only active partial solution the one with all discrete variables free, and initialize solution index t < = 0. If any feasible solution are known for the model, also choose the best as incumbent solution x* with objective value v*. Otherwise, set v* to - INFINITY if the model maximizes and v* to + INFINITY if it minimizes.
- STOPPING: If active partial solutions remain, select one as x(t), and proceed to RELAXATION. Otherwise, stop. If there is an incumbent solution x*, it is optimal, and if not, the model is infeasible.
-
RELAXATION: Attempt to solve the linear programming relaxation of the candidate problem corresponding to x(t).
4.
What are Joint Stock Constraints?
Similarly to production of different products can share production line (capacity), stocks might use the same resource: wareouse.
gammai represents the space taken by one unit of item i.
A specific case of joint stock constraints
A somewhat different situation is with silos, which are typical of liquid or gaseous) products, each silo can only hold one type of product at the same time.
