Transcript Consortium de recherche Les @ffaires électroniques pour l

Supply chain and logistic
optimization
Road Map
 Definition and concept of supply chain.
 Primary tool box at strategic level (software).
 Models at strategic level.
 Models at tactical level.
Potential of SCM
• A box of cereal spends, on average, more
than 100 days from factory to sale.
- A car spend around 2 weeks from factory
to dealer.
• National Semiconductor (USA) used air
transportation and closed 6 warehouses,
34% increase in sales and 47% decrease
in delivery lead time.
• Compaq estimates it lost $0.5 billion to $1
billion in sales in 1995 because laptops
were not available when and where
needed.
• When the 1 gig processor was introduced
by AMD (Advanced Micro Devices), the
price of the 800 meg processor dropped
by 30%.
• P&G estimates it saved retail customers
$65 million (in 18 months) by collaboration
resulting in a better match of supply and
demand.
• IBM claims that it lost a major market
share for desktops in 93, for not been able
to purchase enough of a display chip.
• US companies spent $898 B for SC
activities in 98. Out of the above 58% of
SC costs were incurred for transportation
and 38% for inventory.
Advantage of low inventories
• Less time in storage– less deteriorateHigh quality.
• Effective distribution process (Fast
delivery to customers)
• Switching from old technology to new
technology without scraping lot of
products.
• Of course less storage cost.
Gartner Group:
“By 2004 90% of enterprises that fail to
apply
supply-chain
management
technology and processes to increase
their agility will lose their status as
preferred suppliers”.
AMR Research: “The biggest issue
enterprises face today is intelligent
visibility of their supply chains – both
upstream and down”
Why supply chain: A tutorial
Supplier
Retailer
Retailer
Traditional scenario
Demand (Q)= A - B*Z
Assume A = 120
B= 2
Supplier buys a goods at price
X
Sells to retailer at a price
Y
Retailer sells to customer at a price
Z
Retailers profit (R) =
(Z-Y) * (A-B*Z)
Retailers profit (R) =
(Z-Y) * (A-B*Z)
Y=40
Profit
250
200
150
Profit
100
50
Z
60
58
56
54
52
50
48
46
44
42
0
40
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
Demand Profit
40
0
38
38
36
72
34
102
32
128
30
150
28
168
26
182
24
192
22
198
20
200
18
198
16
192
14
182
12
168
10
150
8
128
6
102
4
72
2
38
0
0
Profit
Price
Suppliers profit =
selling cost
Q * (Y-X)
supplier profit
Suppliers profit
250
200
150
Suppliers profit
100
50
Selling price
58
54
50
46
42
38
34
0
30
0
29
56
81
104
125
144
161
176
189
200
209
216
221
224
225
224
221
216
209
200
189
176
161
profit
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
Retailers profit w.r.t. Y
Retailer profit
500
450
400
350
300
250
Retailer profit
200
150
100
50
Y
60
57
54
51
48
45
42
39
36
33
0
30
Profit
selling price (Y) Retailer profit
36
288
37
264.5
38
242
39
220.5
40
200
41
180.5
42
162
43
144.5
44
128
45
112.5
46
98
47
84.5
48
72
49
60.5
50
50
51
40.5
52
32
53
24.5
55
12.5
56
8
57
4.5
58
2
59
0.5
60
0
Combined profit
CP=0.25 (A2 / B -2 . A .X + 2 . B. X. Y – B. Y2)
Supply chain
500
450
400
350
300
250
Supply chain
200
150
100
50
Y
60
57
54
51
48
45
42
39
36
0
33
SC profit
418
409.5
400
389.5
378
365.5
352
337.5
322
305.5
288
269.5
250
229.5
208
185.5
162
137.5
112
85.5
58
29.5
0
30
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
Combined profit
Y
Retailers profit w.r.t. Y
Profit
Profit
500
400
300
200
100
Z (Retail price)
48
46
44
42
40
38
36
0
34
0
58
112
162
208
250
288
322
352
378
400
418
432
442
448
450
448
442
432
418
32
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
30
Selling priceZ
Summery
Traditional scenario
Demand
20 units
Retail price
$ 50.0
Retailer’s profit
$ 200.0
Supplier’s profit $ 200.0
Collaborative scenario
Demand
30 units
Retail price
$ 45.0
Retailer’s profit
$ 225.0
Supplier’s profit $ 225.0
Example
10000
• A Retailer and a
manufacturer.
Demand
Curve
Demand
– Retailer faces
customer demand.
– Retailer orders from
manufacturer.
P=2000-0.22Q
2000
Price
Variable Production Cost=$200
Selling Price=?
Retailer
Manufacturer
Wholesale Price=$900
Example
• Retailer profit=(PR-PM)(1/0.22)(2,000 - PR)
• Manufacturer profit=(PM-CM) (1/0.22)(2,000 PR)
Retailer takes PM=$900
Sets PR=$1450 to maximize (PR -900)
(1/0.22)(2,000 - PR)
Q = (1/0.22)(2,000 – 1,450) = 2,500 units
Retailer Profit = (1,450-900)∙2,500 = $1,375,000
• Manufacturer takes CM=variable cost
Manufacturer profit=(900-200)∙2,500 = $1,750,000
Example: Discount
• Case with $100 discount
New demand
Q = (1/0.22) [2,000 – (PR-Discount)] = (1/0.22)
[2,000 – (1450-100)] = 2954
Retailer Profit = (1,450-900)∙2,955 = $1,625,250
Manufacturer profit=(900-200-100)∙2,955 =
$1,773,000
Wholesale discount
• $100 wholesale discount to retailer
• Retailer takes PM=$800
Sets PR=$1400 to maximize (PR -800)
(1/0.22)(2,000 - PR)
Q = (1/0.22)(2,000 – 1,400) = 2,727 units
Retailer Profit = (1,400-800)∙2,727 = $1,499,850
• Manufacturer takes PR=$800 and
CM=variable cost
• Manufacturer profit=(800-200)∙2,727 =
$1,499,850
Global Optimization
• What happens if both collaborate (SCM)?
Manufacturer sets PR=$1,100 to maximize (PM 200) (1/0.22)(2,000 - PM)
Q = (1/0.22)(2,000 – 1,100) = 4,091 units
Net profit =(1100-200)∙ 4,091 = $3,681,900
Strategy Comparison
Strategy
No discount
Wth ($100) discount
Discount to retailer only
SCM scenario
Retailer Manufacturer
1,370,096
1,750,000
1,625,250
1,773,000
1,499,850
1,499,850
-
Total
3,120,096
3,398,250
2,999,700
3,681,900
Market Requirement
•
•
•
•
•
Low price.
High quality.
Product customization.
Fast delivery.
Fast technology induction.
Strategy: Right product + Right quantity + Right customer + Right time
Cost reduction and value addition at each stage
Sharing information will lead to reducing uncertainty for all
the partners and hence:
- reducing safety stocks,
- reducing lead times,
- improving brand name.
Result
- Value added product/services
- large market segment (Leading brand),
- long lasting supply chain,
- consistent and growing profits,
- Satisfied customer.
It is better to collaborate and co-ordinate to achieve a
win-win situation.
Definition
Supply Chain refers to the distribution channel of
a product, from its sourcing, to its delivery to the
end consumer.
(some time referred as the value chain)
A supply chain is a global network of organization that
cooperate to improve the flows of material and information
between suppliers and customers at the lowest cost and the
highest speed.
Objective is customer satisfaction and to get competency
over others
Supply chain
Information flow
Material Flow
Cooperation
Value addition
Value added product
Customer satisfaction
Coordination
Information sharing
Assets Management (Inventory)
Difficulties
•
•
•
•
Increasing product variety.
Shrinking product life cycle.
Fragmentation of supply chain.
Soaring randomness because of new
comers.
Responsiveness
(High cost)
Low cost
Deterministic
Uncertainty
FMCG (Tooth paste, soaps etc )
Price sensitive, Low uncertainty
Fashionable products (Garments),
customize products etc
High responsiveness, high uncertainty
Ineffective marketing
Wrong material
High Inventories
Low order fill rates
Supply shortages
Inefficient logistics
High stock outs
Local objectives vs Global objective
Marketing
Production
- High inventories levels.
- Low production cost.
- Low prices.
- High utilization.
- Ability to accept every
customer order.
- High quality raw material.
- Short product delivery
lead times.
- Stable production.
-Various order sizes and
product mixes.
- Big order size.
-Short delivery lead times
(Raw materials)
SCM is a tool which integrate necessary activities and decomposing irrelevant
activities.
Management by projects
Management by departments
Orders
Finished products
Primary
decisions
Buy
Secondary
decisions
Store
Sell
Recruitment of employees
Training, relocation, etc
Salary, TA, DA
Strategic models
Selection of providers
- Provider provides the quantity between two limits.
- Cost is a concave function of the shipped quantity.
- Objective is to select one or more provider to satisfy the demand.
•Case of single manufacturing unit.
•Case of several manufacturing unit.
Cost function
Problem to be solved
Algorithm
 Select the cheapest provider if the quantity to be supplied
is maximum.
 Adjust the remaining quantity among rest of the providers
so that the solution remain feasible.
Exact algorithm for the integer
demand
1. Compute the cost for the first provider for
q=1,2,…A.
2. For provider=2,…N
- Compute the Q=1,2,…,A
F(Pro,Q)=Min0<=x<=Q (F(Pro-1, Q-x), fpro(x)
Case of several manufacturing units:
Approches
• Heuristic approach.
• Piece wise linearization for integer
programming.
• Bender decomposition.
Capacity Planning
Providers
Manufacturers
Retailers
1. Idle processing capacity with providers in different
periods.
2. Idle transportation capacity with providers in different
periods.
3. Idle manufacturing capacity with manufacturers.
4. Idle transportation capacity with manufacturers.
5. Demand at various retailers and the demand of one period
may differ from another period.
Objective is to decide how much and where to
invest.
Supply <= Available Capacity + Added Capacity
Added capacity <= BigNumber* Binary Variable {0,1}
Investment Cost
BinaryVariable*FixedCost + Slope*Added capacity
Formulation
Results
1. There exist at least one optimal solution in which all
the binary constraints are saturated.
2. Replacing big number by corresponding capacity, if
greater than zero, and denote new problem by P2m,
then m is definite.
Approach
- Construct the several instances P20 , P21, ... of the problem
from the relaxed solution of the problem P1 . These instance
converge towards the solution of the problem P.
Unfortunately, we do not know the conversion time.
- For this reason, we derive sub-optimal solution from the
instances and select the best solution.
Algorithm
Optimal solution
Error
1.
276518
275781
0.267
2.
257359
257359
0.0
3.
324934
322973
0.607
4.
292007
292007
0.0
5.
354365
354116
0.070
6.
322126
325881
1.910
7.
334013
333499
0.154
8.
321299
319871
0.446
9.
291253
290190
0.366
10.
310869
310869
0.0
Other approaches
- Langrangean heuristic approach to find
good lower bound.
- Branch and price approach.
Presented approach was similar to the
langrangean approach.
Short term supply chain formation
•
•
•
•
Multi-echelon system.
Selection of a partner from each echelon.
Expected demand is known for a given horizon.
Objective is not to invest at any location.
- Utilization of idle capacity (Production,
transportation, storage etc).
• Solution should be feasible for entire horizon.
• Decision: Whether the new chain exists and
profitable?
Demand
Costs
• Storage cost at entry and at exit (running).
• Production cost (running).
• Connection cost (Fixed)
Note: It is possible that solution may not exist
Minimisation
Path relaxation approach
1. Resolve two echelon problem for each
pair of nodes using final demand.
2. Consider the cost corresponding to
these arcs as surrogate length.
3. Solve the k-shortest path problem and
compute the k-shortest path.
4. For each shortest path, compute the
real cost.
5. If the relax path length is bigger than
best real cost, stop.
D1
D2
D3
D1
D2
D3
Demand
Insertion of new project
1
1
2
3
2
3
Problem data
1
(2, 1)
2
(5,1)
3
(2,0)
Solution
1
5
1
3
Formulation
Min xm1
s.t.
An optimal algorithm is known for the above
case.
Simple assembly
Algorithm
1.
2.
Computing two times: Early start time – Latest start time
Select the common interval.
Complex schedule
3
4
1
7
5
6
14
2
8
9
12
10
11
13
Two approaches
• Simple- easy to program but time
consuming.
• Little tidy – difficult to program but on
average performance is better.
• Both gives the optimal schedule.
• Worst case complexity is also same.
Simple approach
S1
1
3
4
7
14
S2
2
3
4
7
14
S3
8
9
12
13
14
5
6
7
14
11
12
13
14
S4
S5
10
For each assembly operation
• If the idle windows for two different lines are not the
same then select the window which has higher lower limit
(beginning time) and restart the calculation.
• If the windows are the same but starting time are
different, then set the lower limit of this window as the
greatest starting time of the two and restart the calculation.
If neither of the above case is present, then the solution is optimal.
The algorithm converge towards an optimal solution.
Second approach
1. Decompose the assembly into subassemblies.
2. Solve the sub-assemblies.
3. Coordinate the timing of sub-assemblies.
• Recursive approach.
• Each time early start time (EST) and
latest start time (LST) of assembly has to
be computed.
• Advantage:
If the time lies between EST and LST
then re-computation is not required.
Second approach
3
4
1
7
5
6
14
2
8
9
12
10
11
13
3
4
7
1
5
5
6
2
7
8
9
12
10
14
13
11
13
WIP Control (Extension)
First case
Number of finished jobs at the exit of each
machine is not limited in quantity but limited
by time.
Approach
Introduce one virtual machine, following the real
machine with operation time 0 and flexibility [0, T]
• Case 2
Number of finished jobs are limited in time
and in quantity too.
Approach
Introduce as many virtual machines as the
number of finished jobs permitted.
In both the cases, the algorithm presented
before are applicable.
Delivery
date
Instant of ordering
Delivery instant
Inventory
holding cost
Three cots are to be considered
I1, Inventory cost between the arrival of first
component and last component.
I2, Inventory cost between the arrival of last
component and the delivery date.
B, Backlogging cost if the last component
arrives after the delivery date.
Next
W(Z)I2 B
is continuous and differentiable in [R, +∞]
Basic property
n
Fk (Z rk )
k 1
h
n
h sk
k 1
1
n
Fk (Z rk )
Propriété fondamentale: 
k 1
h
n
h sk
1
k 1
Algorithme général


•
Partir d’une solution admissible. R r1,r2 ,...,rn
•
Chercher une solution admissible R1 du voisinage de R
qui vérifié (1)
•
Conserver ou rejeter R1 (recuit simulé)
•
Retour à 2.
Algorithm
1. Start with one feasible solution.
(First feasible solution can easily be generated
considering the same ordering time for all components.)
2. Define new solution R1 in the neighborhood of R that
satisfies relation (1) (Use gradient method)
3. Conserve or reject R1 (Simulated annealing)
4. Go to 2.
The behavior of cost I1 depends upon the density function.
The I1 may be convex or concave based on the nature of
density functions. Hence, with an exact information of
density functions an specialize algorithm could have been
devised.
With uniform densities, the problem can be solved using
gradient method only.
For general problem we proposed an approach based on
simulated annealing which looks, in each iteration, for a
closer solution which satisfies the relation 1.
Partnership formation: A model
Assumptions
 Customer is price sensitive.
 Average customer demand depleted as price increases.
 Customer demand is stochastic.
Backordering cost at supplier is higher than at retailer.
Inventory cost at supplier is cheaper than retailer.
 Inventory can be transferred between supplier and
retailer in negligible time. In other words customer is ready
to wait during the lead time.
Example
Model
• Each maintain a stock of Ip and Ir.
• Retailer pays for the holding and also pays for stock out.
• Supplier pays for holding and also pays for stock out.
This stock out penalty goes to retailer (Compensation).
• Profit is shared according to their relative risk i.e.
investment.
Objective is to maximize total benefit.
Fractional demand
Fractional demand is given by f(wr), a
concave function of selling price.
Lost sell due to high
price
Price wr
Algorithm
1.Take any starting price wr
2. Optimize Ip and Ir => Ip and Ir , keeping Wr fix.
Total profit function is convex w.r.t stocks and wr constant.
3. Optimize Wr, Ip and Ir are fixed.
Combined profit function is concave w.r.t Wr.
4. Go to 2 until profit increases.
Numerical illustration
Continue
Hot areas in SCM
• Dynamic pricing
- Online bidding, (Ebay.com)
- Price setting and discount for
perishable goods in supermarket.
- Customize pricing: different prices for
different customer segment.
• Inventory management in advance
demand information sharing.