上游充通大￥ SHANGHAI JIAO TONG UNIVERSITY 1896 1920 1987 2006 Production Planning and Control Professor JIANG Zhibin Dr.GENG Na Department of Industrial Engineering Logistics Management Shanghai Jiao Tong University IAO TONG
1896 1920 1987 2006 Production Planning and Control Professor JIANG Zhibin Dr. GENG Na Department of Industrial Engineering & Logistics Management Shanghai Jiao Tong University
Scheduling in Supply Chain Management Contents ·Introduction Transportation Problem Generalizations of the Transportation; More General Network Formulations Distribution Resources Planning; Determining Delivery Routes in Supply Chain The Role of information in the SCM Multilevel Distribution Systems Designing the Supply Chain in a Global Environment
Scheduling in Supply Chain Management Contents • Introduction • Transportation Problem • Generalizations of the Transportation; • More General Network Formulations • Distribution Resources Planning; • Determining Delivery Routes in Supply Chain • The Role of information in the SCM • Multilevel Distribution Systems • Designing the Supply Chain in a Global Environment
Supply Chain Management The clearest description appeared in a Fortune magazine article devoted to the subject: Call it distribution or logistics or supply chain management.By whatever name,it is the sinuous,gritty,and cumbersome process by which companies move material,parts,and products to customers.In industry after industry,from cars and clothing to computers and chemicals,executives have plucked this once dismal discipline off the loading dock and placed it near the top of the corporate agenda.Hard-pressed to knock out competitors on quality or price,companies are trying to gain an edge through their ability to deliver the right stuff in the right amount at the right time. (Henkoff,1994)
Supply Chain Management The clearest description appeared in a Fortune magazine article devoted to the subject: Call it distribution or logistics or supply chain management. By whatever name, it is the sinuous, gritty, and cumbersome process by which companies move material, parts, and products to customers. In industry after industry, from cars and clothing to computers and chemicals, executives have plucked this once dismal discipline off the loading dock and placed it near the top of the corporate agenda. Hard-pressed to knock out competitors on quality or price, companies are trying to gain an edge through their ability to deliver the right stuff in the right amount at the right time. (Henkoff, 1994)
Transportation Problem Solve TP by Greedy Heuristic:sub-optimal The total cost- 45×250+35×,1280+ Min(45,80) Min(78,120) .=S304,900, Factories Warehouse (Sinks) Amarillo Teaneck Chicago Siouk Falls (sources) 250 420 380 280 Sunnyvale 5 45 1,280 990 1,440 1,520 Dublin 35 78 120 1,550 1,420 1,660 1,730 Bangkok 40 5 95 80 78 47 55 Min(80-45,120-78) Min(120-35-78,47) Min(47-7,95)
Solve TP by Greedy Heuristic: sub-optimal Transportation Problem Amarillo Teaneck Chicago Sioux Falls Warehouse (Sinks) Factories (sources) Sunnyvale Dublin Bangkok 250 420 380 280 1,280 990 1,440 1,520 1,550 1,420 1,660 1,730 45 120 95 80 78 47 55 55 45 Min (45, 80) 78 Min (78, 120) 35 Min (80-45, 120-78) 7 Min (120-35-78, 47) 40 Min(47-7, 95) The total cost= 45 250+35 ,1280+ …=$304,900
Transportation Problem Solve TP by LP 。 Let m (=3)be the number of sources and n(=4)be the number of sinks, a;=the supply from the source i,1s ism bi=the demand of sink j,1sjsn; cthe cost of shipping one unit from source i to sink j; Xthe flow from the source i to sink j for 1s ism and 1sj<n; m n Subject to Min ∑∑， i=1 j=l S4gpW:∑y=a,or1≤i≤m i=l Dend:∑x=b,or1sjsr Nonegtive:x,≥0，for1≤i≤nand1≤j≤n
Solve TP by LP • Let m (=3) be the number of sources and n (=4) be the number of sinks; • ai= the supply from the source i, 1 im • bj =the demand of sink j, 1jn; • cij =the cost of shipping one unit from source i to sink j; • xij=the flow from the source i to sink j for 1 im and 1jn; Transportation Problem 1 1 m n ij ij i j Min c x Subject to 1 1 : ,1 ; : ,1 ; : 0, 1 1 n ij i j m ij j i ij Supply x a for i m Demand x b for j n Nonegtive x for i mand j n
Unbalanced TP:Demand Supply Solve TP by LP Let m be the number of sources and n be the number of sinks; ·a,the supply from the source i,.l≤ism b,=the demand of sink j,1sjsn; C-the cost of shipping one unit from source i to sink j; X-the flow from the source i to sink j for 1s ism and 1sj<n; n m Min ∑x Min ∑x 目 St. St. ∑y=aarl≤i≤r → xa frlsisn ∑为，=bor1≤j≤m ∑y≤b,r1≤j≤m i= 出≥0 for1≤i≤nand1≤j≤m 书≥0 for1≤i≤nand1≤j≤m
1 1 1 1 . . 1 ; 1 ; 01 1 n m ij ij i j m ij i j n ij j i ij Min c x St x a for i n x b for j m x for i nand j m 1 1 1 1 . . 1 ; 1 ; 01 1 n m ij ij i j m ij i j n ij j i ij Min c x St x a for i n x b for j m x for i nand j m Unbalanced TP： Demand > Supply Solve TP by LP • Let m be the number of sources and n be the number of sinks; • ai= the supply from the source i, 1 im • bj =the demand of sink j, 1jn; • cij =the cost of shipping one unit from source i to sink j; • xij=the flow from the source i to sink j for 1 im and 1jn;
More General Network Formulations Rules for balancing flow of general network If Apply the following rules at each node 1.Total supply>Total demand Inflow -Outflow>Supply or demand 2.Total supply<Total demand Inflow-Outflows Supply or demand 3.Total supply=Total demand Inflow-Outflow=Supply or demand Rule: Supply-a negative number attached the node; Demand-a positive number attached to the node xthe total flow from node i to node j;
Rule： Supply—a negative number attached the node; Demand—a positive number attached to the node xij—the total flow from node i to node j; More General Network Formulations If Apply the following rules at each node 1. Total supply>Total demand 2. Total supply<Total demand 3. Total supply=Total demand Inflow - Outflow Supply or demand Inflow - Outflow Supply or demand Inflow - Outflow= Supply or demand Rules for balancing flow of general network
Determining Delivery Routes in Supply Chains Finding optimal rout in vehicle scheduling is similar,but more complex problem; Assume that there is a central depot with one or more delivery vehicles and n customer locations,each having a known requirement.The question is how to assign vehicles to customer locations to meet customer demand and satisfy whatever constraints there may exits at minimum cost. Optimal solution is impossible and only good solution is possible (proposed by Clark and Wright). Suppose that there is a single depot all vehicles depart from and return to. Identify the depot as location 0 and the customers as locations 1, 2,…,n. Assume all the costs traveling from depot to each customer location and among customer locations are coi and ci respectively
Determining Delivery Routes in Supply Chains Finding optimal rout in vehicle scheduling is similar, but more complex problem; • Assume that there is a central depot with one or more delivery vehicles and n customer locations, each having a known requirement. The question is how to assign vehicles to customer locations to meet customer demand and satisfy whatever constraints there may exits at minimum cost. • Optimal solution is impossible and only good solution is possible (proposed by Clark and Wright). • Suppose that there is a single depot all vehicles depart from and return to. • Identify the depot as location 0 and the customers as locations 1, 2, …, n. • Assume all the costs traveling from depot to each customer location and among customer locations are c0j and cij respectively
Clark and Wright's Saving Method Only consider situation of c Suppose that initially a separate vehicle is assigned to each customer location.Then the initial solution consists of n separate routes from the depot to each customer location and back,so that the initial solution is2 ● Suppose that link customer i and j,then save two trips 0-j and 0-i, however add one trip i-j.The saved cost by linking i and j is Si-coi-cor Ci
Clark and Wright’s Saving Method • Only consider situation of cij = cji. • Suppose that initially a separate vehicle is assigned to each customer location. Then the initial solution consists of n separate routes from the depot to each customer location and back, so that the initial solution is 0 1 2 n j j c • Suppose that link customer i and j, then save two trips 0-j and 0- i, however add one trip i -j. The saved cost by linking i and j is : 0 i j sij = c 0 i + c 0j - cij
Clark and Wright's Saving Method The total number of calculation of s,is: Procedures: n! n(n-1) 2(n-2)！ 2 1.Compute s,for all possible pairs of customer locations i andj, and rank the s in decreasing order. 2.According to descending order of savings,include link(i,in a route if it does not violate feasibility constraints. 3.If including the current link(i,violates the feasibility, consider other feasible link (i,until all the lists is exhausted,and then stop the current route. 4.If the current route includes all the remaining locations,stop; otherwise,go to Step 2 to form a new route
Clark and Wright’s Saving Method Procedures: 1. Compute sij for all possible pairs of customer locations i and j, and rank the sij in decreasing order. 2. According to descending order of savings, include link ( i, j) in a route if it does not violate feasibility constraints. 3. If including the current link ( i, j) violates the feasibility, consider other feasible link ( i, j) until all the lists is exhausted, and then stop the current route. 4. If the current route includes all the remaining locations, stop; otherwise, go to Step 2 to form a new route. The total number of calculation of is: ! ( 1) 2 2!( 2)! 2 ij s n n nn n