Production and Operation Managements Scheduling in Supply Chain Management Prof.JIANG Zhibin Dr GENG Na Department of Industrial Engineering Management Shanghai Jiao Tong University
Production and Operation Managements Prof. JIANG Zhibin Dr GENG Na Department of Industrial Engineering & Management Shanghai Jiao Tong University Scheduling in Supply Chain Management
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
Determining Delivery Routes in Supply Chains Traveling Salesman Problem Description: A salesman starts at his home base,labeled City 1.He must make stops at n-1 other cities,visit each city exactly once.The problem is to optimize sequence in which to visit all the cities to minimize the total distance traveled
Determining Delivery Routes in Supply Chains • Traveling Salesman Problem Description: A salesman starts at his home base, labeled City 1. He must make stops at n-1 other cities, visit each city exactly once. The problem is to optimize sequence in which to visit all the cities to minimize the total distance traveled
Determining Delivery Routes in Supply Chains The complexity in finding the solution: If the number is small,it is possible to enumerate all the possible tours,and select the shortest one; For n cities,there are n!different sequences; If we could evaluate 1 trillion(1012)sequences per second on a supercomputer,then a 25-city problem,nearly 500,000 years are required to evaluate all the sequences; Mathematically NP hard--No Polynomial,meaning that the time required to solve such problems is an exponential function of the number of cities rather than a polynomial function
Determining Delivery Routes in Supply Chains • The complexity in finding the solution: If the number is small, it is possible to enumerate all the possible tours, and select the shortest one; For n cities, there are n! different sequences; If we could evaluate 1 trillion (1012) sequences per second on a supercomputer, then a 25-city problem, nearly 500,000 years are required to evaluate all the sequences; Mathematically NP hard--No Polynomial, meaning that the time required to solve such problems is an exponential function of the number of cities rather than a polynomial function
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
Determining Delivery Routes in Supply Chains Custom Location Example 6.4-Whole Grains is a bakery that Daily Req. supplies five major customers with bread each (Loaves) morning.The locations of the bakery and the five 1 (15,30) 85 customers and their demand are given as 2 (5,30) 162 described in a grid.The bakery has several 3 (10,20) 26 delivery trucks,each having a capacity of 300 4 (5,5) 140 loaves. 5 (20,10) 110 Cost Matrix(c)(=distance) 30 ⊙ Customer 2 Customer 1 TO g25 0 2 34 5 20 ◇Customer3 F 0 33.530.4 22.47.1 22.4 15 R 1 10.0 11.2 26.9 20.6 Customer 5 0 2 11.2 25.0 25.0 10 Customer 4 M 3 15.8 14.1 5 4 15.8 Bakery 5 10 15 2025
Determining Delivery Routes in Supply Chains Example 6.4-Whole Grains is a bakery that supplies five major customers with bread each morning. The locations of the bakery and the five customers and their demand are given as described in a grid. The bakery has several delivery trucks, each having a capacity of 300 loaves. Custom Location Daily Req. ( Loaves) 1 2 3 4 5 (15, 30) (5, 30) (10, 20) (5, 5) (20, 10) 85 162 26 140 110 Cost Matrix (cij) (=distance) TO F 0 R 1 O 2 M 3 4 0 1 2 3 4 5 33.5 30.4 22.4 7.1 22.4 10.0 11.2 26.9 20.6 11.2 25.0 25.0 15.8 14.1 15.8
Determining Delivery Routes in Supply Chains Saving for all pairs (i,j),i,j=1~5: 85+162=247(2,3)→(1,5) 15 →(1,4)(3,4)，(4,5)→(2,4) Customer 5 10 Customer 4 Customer Daily Req.(Loaves) 5 110+140=250<300 1 85 2 162 3 26 Bakery 5 1015 2025 4 140 XI- 5 110
Determining Delivery Routes in Supply Chains • Saving for all pairs (i, j), i, j=1~5: s12=c01+c02-c12=33.5+30.4-10=53.9 s13=44.7, s14 =13.7, s15=35.3, s23=41.6, s24=12.5, s25=27.8 s34=13.7, s35=30.7, s45=13.7 •Rank the customer pairs in the decreasing order of all the saving values: (1, 2) (1, 3) (2, 3) (1, 5) (1, 4), (3, 4), (4, 5) (2, 4) Customer Daily Req.( Loaves) 1 2 3 4 5 85 162 26 140 110 85+162=247<300 247+26=273<300 110+140=250<300
Determining Delivery Routes in Supply Chains Practical Issues in VS Frequency requirements; Visits to customers may have to occur at a certain frequency, and that frequency may vary from customer to customer. ·Time windows, This refers to the requirement that visits to customer locations be made at specific times. Time-dependent travel time; When deliveries are made in urban centers,rush-hour congestion can be an important factor
Determining Delivery Routes in Supply Chains Practical Issues in VS • Frequency requirements; Visits to customers may have to occur at a certain frequency, and that frequency may vary from customer to customer. • Time windows; This refers to the requirement that visits to customer locations be made at specific times. • Time-dependent travel time; When deliveries are made in urban centers, rush-hour congestion can be an important factor