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