Optimization in SAP Supply Chain Management - Inria

1 Heinrich Braun, Thomas KasperSAP AGOp t i m i za t i o n i n SA PSu p p l y Ch a i n M a n a g e m e n t SAP AG 2002, CP AI OR 2004, Heinrich Braun 2A g e n d aOptimization in SAP SCMA cceptance of Optimization Summary SAP AG 2002, CP AI OR 2004, Heinrich Braun 3 PlantsDCs CustomersSupplierSupply Chain Management :Set of approaches utilized to integrate suppliers, manufactures, warehouses and stores so that merchandise is produced and distributed at right quantity locations time in order to minimize costwhile satisfying service level requirements[Simchi-Levi et al 2000]Prerequisite:Integrated Supply Chain ModelI n t r o d u c t i o n : Su p p l y Ch a i n M a n a g e m e n t SAP AG 2002, CP AI OR 2004, Heinrich Braun 4Su p p l y Ch a i n M a n a g e m e n t m y SA P SCMN etworkPrivateTradingExchangeNetworkSuppl ierPartnerPartnerCustomerDirectProcureme ntSourceDeliverOrderFulfillmentMakeManuf acturingSupply Chain DesignStrategizeDemand and Supply PlanningPlanSupply Chain Performance ManagementMeasureSupply Chain Event ManagementTrackSupply Chain CollaborationCollaborateSupply Chain CollaborationCollaboratePrivateTradingEx change SAP AG 2002, CP AI OR 2004, Heinrich Braun 5 OperationalTacticalStrategicm y SA P SCM : Pl a n n i n g L e v e l sDirectProcurementSourceDeliverOrderFulf illmentMakeManufacturingSupply Chain DesignStrategizeDemand and Supply PlanningPlan SAP AG 2002, CP AI OR 2004, Heinrich Braun 6Ch a l l e n g e.

2 M a x i m i ze t h e a p p l i c a t i o n o f Op t i m i za t i o n i n SCMDo s Model Planning Problems as Optimization problems Use the best Optimization algorithms Respect the given run time for solutionDon t do s Restrict the modeling to optimal solvable instances Size Constraints Restrict your Optimization algorithms to exact approaches neglecting Iterated Local Search Evolutionary Algorithms GoalLeverage Optimization algorithms by Aggregation Decompositionfor solving the Planning and Scheduling problems in SCM SAP AG 2002, CP AI OR 2004, Heinrich Braun 7Op t i m i za t i o n - Ex p e c t a t i o n b y o u r c u s t o m e = Efficiency Acceptance! Depending on problem complexity (model, size) Given run timeEfficiency Scalability Decomposition = quasi linear Toolbox: alternative algorithms Parallelization Return On Investment (ROI) Solution Quality Total Cost of Ownership (Licenses, Maintenance, Administration, Handling)-Optimal Solution ?

3 -At most 5% above Optimum ? // SAP AG 2002, CP AI OR 2004, Heinrich Braun 8Pr o b l e m v e r s u s A l g o r i t h m sOR-Researcher: acceptsProblems, which solves his algorithm optimallyOR-developer: acceptsProblems, which solves his algorithm efficientlyOR-user: acceptsalgorithms, which solves his problem effectivelyModel-SpecificationOptimizati on-Algorithms SAP AG 2002, CP AI OR 2004, Heinrich Braun 9Op t i m i ze r - Ex p e c t a t i o n b y o u r c u s t o m e rIdealist Searchingfor the global OptimumRealist Improving the first feasible solution until Time OutSisyphus Knows, that the problem has changed during run timePragmatic Solves unsolvable problems SAP AG 2002, CP AI OR 2004, Heinrich Braun 10Ch a l l e n g e : M a s t e r i n g t h e p l a n n i n g c o m p l e x i t y o f SCM Modeling is crucial !

4 !Hierarchical planning Global Optimization using aggregation ( Supply Network Planning) Feasible plans by local Optimization (Detailed Scheduling) Integration by rolling planning schema SAP AG 2002, CP AI OR 2004, Heinrich Braun 11 Supply Network Planning (SNP) Mid term horizon Time in buckets (day, week,..) Global Optimization Maximize profit Decide Where to produce How much to produce How much to deliver How much capacities Linear Optimization (MILP)Detailed Scheduling (DS) Short term horizon Time in seconds Local Optimization Disaggregate global plan Time: When to produce Resource: On which alternative resource Optimize production sequence Scheduling algorithms (GA, CP)H i e r a r c h i c a l Pl a n n i n g SAP AG 2002, CP AI OR 2004, Heinrich Braun 12 TransportDiscrete Lots Minimal LotsPiecewise linear CostsSatisfy DemandPriority Classes Delay CostsNon-Delivery CostsProcurePiecewise linear CostsPPMP roductsProduceDiscrete LotsMinimal LotsFixed Resource ConsumptionPiecewise linear CostsStorewith Shelf lifeHandling-InCapacityStorageCapacitySa fety StockTransportCapacityHandling-Out CapacityProduction CapacitySN P Op t i m i ze r.

5 M o d e l Ov e r v i e w SAP AG 2002, CP AI OR 2004, Heinrich Braun 13 Time Windowsearliest starting timedue date, deadlinedelay costsDistances(with calendars)minimalmaximalSetupsequence dependentsetup costsResource SelectionAlternative resourcesResource costsUnaryResourcesProduct FlowdiscretecontinuousStorageresourcesMu lti-CapResourcesPP/DS Op t i m i ze r : M o d e l Ov e r v i e w SAP AG 2002, CP AI OR 2004, Heinrich Braun 14Ex a m p l e : Co m p l e x M o d e l i n g SAP AG 2002, CP AI OR 2004, Heinrich Braun 15PP/DSSNPSNP HorizonSNP Planning only in SNP horizon Release SNP Orders only in PP/DS horizon Respect PP/DS orders as fixed capacity reduction material flow PP/DS Respect pegged SNP Orders as due dates No capacity reduction But material flow No restrictions for scheduling PP/DS ordersI n t e g r a t i o n b e t w e e n SN P a n d PP/DSPP/DS Horizon SAP AG 2002, CP AI OR 2004.

6 Heinrich Braun 16PP/DSSNPSNP HorizonSNP Planning only in SNP horizon Release SNP Orders only in PP/DS horizon Respect PP/DS orders as fixed capacity reduction material flow PP/DS Respect pegged SNP Orders as due dates No capacity reduction But material flow No restrictions for scheduling PP/DS ordersI n t e g r a t i o n b e t w e e n SN P a n d PP/DSPP/DS Horizon SAP AG 2002, CP AI OR 2004, Heinrich Braun 17M a s t e r i n g t h e a l g o r i t h m i c c o m p l e x i t y : A g g r e g a t i o nModel Accuracy versus Solution Quality -> SNP Time Aggregation (telescopic buckets) Limit the discretization Product Aggregation (families of finished products) Location Aggregation (transport zones, distribution centers)However: Sufficient model accuracy of SNP for DS Modeling of setup (important for process industry) SAP AG 2002, CP AI OR 2004, Heinrich Braun 18 Multi-Level Capacitated Lot Sizing Problem (MLCLSP)Setup cost and/or consumption in each bucketBad resultsSetup consumption big compared to bucket capacity (big lots) SN P Op t i m i za t i o n : A n t i c i p a t i o n o f Se t u pGood resultsSetup consumption small compared to bucket capacity (small lots) SAP AG 2002, CP AI OR 2004, Heinrich Braun 19 Proportional Lot Sizing Problem (PLSP) Considering setup in preceding bucket At most one setup per bucketConstraints on cross-period lots (= campaign quantity) Minimal campaign quantity Campaign quantity integer multiple of batch sizeSN P Op t i m i za t i o n.

7 L o t Si zi n g i n SA P SCM SAP AG 2002, CP AI OR 2004, Heinrich Braun 20SN P Ca m p a i g n Op t i m i za t i o n : B e n c h m a r k sComparison: real word problems of process industryca. 500 000 decision variables, 200 000 constraints0,000000%0,000001%0,000010%0, 000100%0,001000%0,010000%0,100000%1,0000 00%10,000000%100,000000%0102030405060708 090100time in minutesOptimality DeviationPI-Bench2PI-Bench7PI-Bench8PI-B ench9 SAP AG 2002, CP AI OR 2004, Heinrich Braun 21M a s t e r i n g t h e a l g o r i t h m i c c o m p l e x i t y : De c o m p o s i t i o n Global versus local optimality -> SNP + DS Local optimality depends on neighborhood High solution quality by local Optimization Local Optimization = Decomposition Decomposition strategies SNP: time, resource, product, procurement DS: time, resource Parallelization by Agents SAP AG 2002, CP AI OR 2004, Heinrich Braun 22T i m e De c o m p o s i t i o n - L o c a l I m p r o v e m e n tResourcesTimeCurrent windowGliding window script1.

8 Optimize only in current window2. Move window by a time delta3. Go to first step SAP AG 2002, CP AI OR 2004, Heinrich Braun 23SN P Pr o d u c t De c o m p o s i t i o n SAP AG 2002, CP AI OR 2004, Heinrich Braun 24SN P Pr o d u c t De c o m p o s i t i o n SAP AG 2002, CP AI OR 2004, Heinrich Braun 25SN P Pr o d u c t De c o m p o s i t i o n SAP AG 2002, CP AI OR 2004, Heinrich Braun 26SN P Pr o d u c t De c o m p o s i t i o nOPAL ExecutableCPLEX IV 1,5 GHz1 GB Main memoryCustomer model Production Grouping ~15 comparable selections179 086 Variables66 612 Constraints10 218 Binary variables30,0040,0050,0060,0070,0080,009 0,00100,00 Solution time [hrs]Delivery [%]LP Relaxation99,1799,1799,1799,17 Decomposed MIP94,4098,9899,0799,09 Global MIP45,116253,3362,8165,130,251230, , , , , ,00 Solution time [hrs]

9 Total costLP , , , ,00 Decomposed , , , ,00 Global MIP2,44E+ , , ,000,25123 SAP AG 2002, CP AI OR 2004, Heinrich Braun 27M u l t i A g e n t Op t i m i za t i o n D+SObjective Multi Criteria Optimization user selects out of solutions with similar overall quality different components Use power ofPallelization Multi Agent Strategy Different AGENTS focusing on Setup or Delay or Makespan Agents may use any optimizer (CP, GA, ..) New solutions by local improvement Integrated in Optimizer Architecture Performance Speedup |available processors SAP AG 2002, CP AI OR 2004, Heinrich Braun 28Se v e r a l So l u t i o n sDelay0 Setup SAP AG 2002, CP AI OR 2004, Heinrich Braun 29Sc h e d u l i n g Op t i m i ze r A r c h i t e c t u r eCore ModelLiveCacheModel GeneratorCampaignOptimizerConstraintProg rammingGenetic AlgorithmBasic OptimizerSequenceOptimizerTime ResourceDecompositionMulti AgentReportingGUIC ontrolChecking SAP AG 2002, CP AI OR 2004, Heinrich Braun 30 LiveCacheOp t i m i zi n g w i t h T i m e De c o m p o s i t i o nCore-ModelModel GeneratorSNPD eploymentBasic-OptimizersTimeProductDeco mpositionReportingGUIC ontrolCheckingResourceVehicleAllocation SAP AG 2002, CP AI OR 2004.

10 Heinrich Braun 31solvedsolvedOp t i m i zi n g w i t h T i m e De c o m p o s i t i o nTime-Decomposition123456123-6extractmer geSNP LP/MILP solvestore SAP AG 2002, CP AI OR 2004, Heinrich Braun 32solvedsolvedsolvedsolvedOp t i m i zi n g w i t h T i m e De c o m p o s i t i o nTime-Decomposition123456345-6extractmer geSNP LP/MILP solvestore SAP AG 2002, CP AI OR 2004, Heinrich Braun 33solvedsolvedsolvedsolvedsolvedsolvedOp t i m i zi n g w i t h T i m e De c o m p o s i t i o nTime-Decomposition12345656extractmergeS NP LP/MILP solvestore SAP AG 2002, CP AI OR 2004, Heinrich Braun 34 Detailed Scheduling Up to 200 000 activities(no hard limitation) First solution as fast as greedy heuristics More run time improves solution qualitySupply Network Planning Pure LP Without discrete constraints Up to several million decision variables and about a million constraints Global optimum guaranteed For discrete constraints No global optimum guaranteed Quality depends on run time and approximation by pure LPOp t i m i za t i o n Pe r f o r m a n c e SAP AG 2002, CP AI OR 2004, Heinrich Braun 35Su m m a r y - M a s t e r i n g t h e A l g o r i t h m i c c o m p l e x i t y Aggregation SNP: time, product, location Automated Generation: SNP model deduced from DS model !