Theory

Question 1

Strategic Supply Chain Model ?

Answer 1

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)

Question 2

Strategic Supply Chain questions ?

Answer 2

• Where should I build a production line ?
• Should I start serving clients in Asia ?
• How to structure my transportation/distribution network ?

Question 3

Tactical Supply Chain Model ?

Answer 3

• 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

Question 4

Tactical Supply Chain questions ?

Answer 4

• 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 ?

Question 5

Operational Supply Chain Model ?

Answer 5

• 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

Question 6

Operation Supply Chain questions ?

Answer 6

• 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 ?

Question 7

What is a graph ?

Answer 7

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

Question 8

What is a directed graph or digraph ?

Answer 8

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

Question 9

What is the purpose of a graph ?

Answer 9

A graph is an abstraction used to model connections (edges, arcs) between agents (nodes).

Question 10

A generic Strategic Supply Chain Model

Answer 10

SETS:

• S # set of suppliers
• P # set of production sites
• D # set of distribution center
• C # set of customers

VARIABLES:

• u_p, u_d : quantity of goods annually handled by the corresponding site/center
• y_p, y_d : binary variable indicating if the corresponding site/center is open
• f_sp, f_pd, f_dc : flow of goods between the corresponding entities
• w_sp, w_pd, w_dc : corresponding binary variables indicating if the arc is open

PARAMETERS:

• D_c : demand at the customer site

CONSTRAINTS:

• Demand satisfaction: Σ_df_dc >= D_c for all c
• Flow Conservation & Capacity at Distribution and Production Site

Question 11

How to estimate fixed costs ?

Answer 11

We have to compute the NPV of the investment.

Question 12

How to extend to Multi-Item case ?

Answer 12

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).

Question 13

How to extend to Multi-Periods case ?

Answer 13

Add set T for periods and associate index t to all variables & constraints.

Question 14

Standard Capacitated dynamic lot-sizing model LS-C

• Discrete time horizon: set of periods indexed by t in (1..n)
• Demand D_t >= 0 for each period
• Production Capacity C_t for each period
• Production cost in period t is composed of two components
  
  • a fixed cost f_t
  • a variable cost v_t
• Holding costs ha only one variable component h_t
• 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

Answer 14

The model

Variables:

• x_t >= 0: production in period t, with t in (1..n)
• s_t >= 0: stock at the end of period t, with t in (0..n-1)
• y_t = {0, 1}: is one if there is a setup in period t (in this case production x_t may be positive, but setup cost is incurred), and 0 if not

Question 15

Lot-Sizing: network model

Answer 15

Question 16

What if we can only produce in full batches?

Answer 16

We obtained this model by fixing the LS model with

x_t = C_t* y_t

► Just allow y_t to be integer instead of binary.

Question 17

What are the 3 types of capacity and how to model them ?

Answer 17

1. C: varying capacity: capacity is different in each period
2. CC: constant capacity: capacity is the same in each period
3. 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

Question 18

What is Backlogging ?

Answer 18

Service level is usually an important criterion/constraint in production environment, you want to:

1. minimize cost, but still reaching a minimum service level
2. 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.

Question 19

Lot-Sizing with Backlogging: Network model

Answer 19

Question 20

What is the lead time?

Answer 20

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 + t_lead.

If there is only one single item, if suffices to shift the demand earlier by t(lead) periods.

Question 21

How to model Lead Time ?

Answer 21

Question 22

What is Startup cost ?

Answer 22

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.

Question 23

What is a shutdown ?

Answer 23

There is a shutdown in period t if there is a setup in period t-1 and no setup in period t.

Question 24

Suppose we have several products that share a common production line, how do we model the constraint ?

Answer 24

Joint Capacity Constraints

The most basic constraint is: sum x_i,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 x_i,t <= C_t *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

Question 25

What if the products are different ant the production rate of each product is different?

Answer 25

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 * x_{i, t} <= C_t for all t.

where æ_i is the amount of time necessary to produce one unit of item i and C_t is the amount of production time in period t.

Question 26

What is “Complete Enumeration” ?

Answer 26

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.

Question 27

What should we do when solving MILP ?

Answer 27

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 !

Question 28

What is a relaxation?

Answer 28

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).

Question 29

What are the two types of relaxations ?

Answer 29

1. 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
2. The Lagrangean relaxation is obtained by replacing “complicating constraints” by a penalty in the objective.

Question 30

What two bounds can we obtain after relaxation ?

Answer 30

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).

Question 31

What if after you solve the relaxation you see that the relaxation is infeasible ?

Answer 31

Then the original problem is infeasible as well, as any feasible solution of the original problem is also feasible in the relaxation.

Question 32

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 ?

Answer 32

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.

Question 33

What is Branch-and-Bound ?

Answer 33

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.

Question 34

How does Branch-and-Bound work ?

Answer 34

Question 35

How to do the Branch and Bound Algorithm ?

Answer 35

1. 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.
2. 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.
3. RELAXATION: Attempt to solve the linear programming relaxation of the candidate problem corresponding to x^(t).
   4.

Question 36

What are Joint Stock Constraints?

Answer 36

Similarly to production of different products can share production line (capacity), stocks might use the same resource: wareouse.

gamma_i represents the space taken by one unit of item i.

Question 37

A specific case of joint stock constraints

Answer 37

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.