WIXLIB

Op 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 tHeinrich Braun,Thomas KasperSAP AG

AgendaOptimization in SAP SCMAcceptance of OptimizationSummarySAP AG 2002,CP AI OR 2004,Heinrich Braun2

I 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 tSupply 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 cost while satisfying service level requirements[Simchi-Levi et al 2000]Prerequisite: Integrated Supply Chain ModelCustomersSAP AG 2002,CP AI OR 2004,Heinrich Braun3DCsPlantsSupplier

Su p p l y Ch a i n M a n a g e m e n t – m y SA P SCMMeasurePartnerPlanSupply Chain DesignSourceDemand andSupply tePrivateTradingExchangeSupply Chain CollaborationSupplierStrategizeSupply Chain CollaborationSupply Chain Performance kSupply Chain Event ManagementSAP AG 2002,CP AI OR 2004,Heinrich Braun4

m y SA P SCM : Pl a n n i n g L e v e l sStrategicStrategizeSupply Chain DesignTacticalPlanDemand andSupply PlanningOperationalSourceMakeDirectProcurementSAP AG 2002,CP AI OR 2004,Heinrich Braun5ManufacturingDeliverOrderFulfillment

Ch a l l e n g e : 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 etc.Our GoalLeverage optimization algorithms by Aggregation Decompositionfor solving the Planning and Scheduling problems in SCMSAP AG 2002,CP AI OR 2004,Heinrich Braun6

Op 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 r-Optimal Solution ?/-At most 5% above Optimum ?/.Best-of-Breed Efficiency Æ Acceptance ! Depending on problem complexity (model, size)Given run timeEfficiency Scalability Decomposition quasi linearToolbox: alternative algorithmsParallelization Return On Investment (ROI) SAP AG 2002,CP AI OR 2004,Solution QualityTotal Cost of Ownership (Licenses, Maintenance, Administration, Handling)Heinrich Braun7

Pr o b l e m v e r s u s A l g o r i t h m sOR-Researcher: accepts Problems, which solves his algorithm optimallyOR-developer: accepts Problems, which solves his algorithm efficientlyOR-user: accepts algorithms, which solves his problem effectivelyModelSpecificationSAP AG 2002,CP AI OR 2004,Heinrich Braun8OptimizationAlgorithms

Op 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 Searching for the global OptimumRealist Improving the first feasible solution until Time OutSisyphus Knows, that the problem has changed during run timePragmatic Solves unsolvable problemsSAP AG 2002,CP AI OR 2004,Heinrich Braun9

Ch 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 SCMHierarchical 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,Modeling is crucial !!Heinrich Braun10

H i e r a r c h i c a l Pl a n n i n gSupply Network Planning (SNP) Mid term horizon Time in buckets (day, week,.) Short term horizon Time in seconds Global optimization Local optimization Maximize profit Disaggregate global plan Decide Where to produce How much to produce How much to deliver How much capacities Linear optimization (MILP)SAP AG 2002,Detailed Scheduling (DS)CP AI OR 2004,Heinrich Braun11 Time: When to produce Resource:On which alternative resource Optimize production sequence Scheduling algorithms (GA, CP)

SN P Op t i m i ze r : M o d e l Ov e r v i e wProduceDiscrete LotsMinimal LotsFixed Resource ConsumptionPiecewise linear CostsTransportTransportCapacityDiscrete LotsMinimal LotsPiecewise linear afety ith Shelf lifeSatisfy DemandProcurePiecewise linear CostsSAP AG 2002,CP AI OR 2004,Heinrich Braun12Priority ClassesDelay CostsNon-Delivery Costs

PP/DS Op t i m i ze r : M o d e l Ov e r v i e wTime WindowsDistancesearliest starting timedue date, deadlinedelay costs(with calendars)minimalmaximalResource SelectionAlternative resourcesResource costsSetupsequence dependentsetup costsUnaryResourcesProduct ourcesSAP AG 2002,CP AI OR 2004,Heinrich Braun13

Ex a m p l e : Co m p l e x M o d e l i n gSAP AG 2002,CP AI OR 2004,Heinrich Braun14

I n t e g r a t i o n b e t w e e n SN P a n d PP/DSSNP Planning only in SNP horizon Release SNP Orders only in PP/DShorizon Respect PP/DS orders as fixed capacity reduction material flowPP/DS Respect pegged SNP Orders as duedates No capacity reduction But material flow No restrictions for schedulingPP/DS ordersSNPPP/DSPP/DS HorizonSNP HorizonSAP AG 2002,CP AI OR 2004,Heinrich Braun15

I n t e g r a t i o n b e t w e e n SN P a n d PP/DSSNP Planning only in SNP horizon Release SNP Orders only in PP/DShorizon Respect PP/DS orders as fixed capacity reduction material flowPP/DS Respect pegged SNP Orders as duedates No capacity reduction But material flow No restrictions for schedulingPP/DS ordersSNPPP/DSPP/DS HorizonSNP HorizonSAP AG 2002,CP AI OR 2004,Heinrich Braun16

Mast ering t he algorit hm ic c om plex it y: Aggregat ionModel 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 Braun17

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 pMulti-Level Capacitated Lot Sizing Problem (MLCLSP)Setup cost and/or consumption in each bucketGood resultsSetup consumption small compared to bucket capacity (small lots)Bad resultsSetup consumption big compared to bucket capacity (big lots)SAP AG 2002,CP AI OR 2004,Heinrich Braun18

SN P Op t i m i za t i o n : L o t Si zi n g i n SA P SCMProportional 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 sizeSAP AG 2002,CP AI OR 2004,Heinrich Braun19

SN 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 000%Optimality ,000001%0,000000%time in minutesSAP AG 2002,CP AI OR 2004,Heinrich Braun20

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 : De c o m p o s i t i o nGlobal versus local optimality - SNP DS Local optimality depends on neighborhood High solution quality by local optimization Local Optimization DecompositionDecomposition strategies SNP: time, resource, product, procurement DS: time, resource Parallelization by “Agents”SAP AG 2002,CP AI OR 2004,Heinrich Braun21

T 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 tResourcesCurrent windowGliding window script1. Optimize only in current window2. Move window by a time delta3. Go to first stepSAP AG 2002,CP AI OR 2004,Heinrich Braun22Time

SN P Pr o d u c t De c o m p o s i t i o nSAP AG 2002,CP AI OR 2004,Heinrich Braun23

SN P Pr o d u c t De c o m p o s i t i o nSAP AG 2002,CP AI OR 2004,Heinrich Braun24

SN P Pr o d u c t De c o m p o s i t i o nSAP AG 2002,CP AI OR 2004,Heinrich Braun25

SN P Pr o d u c t De c o m p o s i t i o n100,0090,00Delivery [%]80,0070,0060,0050,0040,0030,00LP RelaxationDecomposed MIPGlobal 45,116253,3362,8165,13Solution time [hrs]Total cost200.000.000,00150.000.000,00100.000.000,00OPAL ExecutableCPLEX 8.050.000.000,000,000,25123LP 4.075.500,00Decomposed 00,002,44E 08215.404.000,00195.649.000,00187.900.000,00Global MIPSolution time [hrs]CP AI OR 2004,„Production Grouping“ 15 comparable selections179‘086 Variables66‘612 Constraints10‘218 Binary variables250.000.000,00SAP AG 2002,Customer modelHeinrich Braun26Pentium IV 1,5 GHz1 GB Main memory

M u l t i A g e n t Op t i m i za t i o nObjective Multi Criteria Optimization250200 user selects out of solutions withDelaySetupQuality D S similar overall qualitydifferent components Use power of Pallelization150Multi Agent Strategy Different AGENTS focusing on Setup or Delayor Makespan100 Agents may use any optimizer (CP, GA, .) New solutions by local improvement Integrated in Optimizer Architecture500SAP AG 2002,Solut. Solut. Solut. Solut.1234CP AI OR 2004,Heinrich Braun27Performance Speedup available processors

SetupSe v e r a l So l u t i o n s0SAP AG 2002,CP AI OR 2004,Heinrich BraunDelay28

Sc 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 eLiveCacheGUITimeModel GeneratorResourceReportingCore ModelCheckingMulti ticAlgorithmSequenceOptimizer Basic OptimizerSAP AG 2002,CP AI OR 2004,Heinrich Braun29CampaignOptimizer

Op 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 nLiveCacheGUITimeModel DecompositionSNPDeployment Basic-OptimizersSAP AG 2002,CP AI OR 2004,ResourceHeinrich Braun30VehicleAllocation

Op 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 actstoresolveSNP LP/MILPSAP AG 2002,CP AI OR 2004,Heinrich Braun31

Op 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 ition5-6extractstoresolveSNP LP/MILPSAP AG 2002,CP AI OR 2004,Heinrich Braun32

Op 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 imeDecomposition6extractstoresolveSNP LP/MILPSAP AG 2002,CP AI OR 2004,Heinrich Braun33

Op t i m i za t i o n Pe r f o r m a n c eSupply Network Planning Pure LP Without discrete constraints Up to several million decisionvariables and about a millionconstraints Global optimum guaranteed For discrete constraints No global optimum guaranteed Quality depends on run time andapproximation by pure LPSAP AG 2002,CP AI OR 2004,Heinrich Braun34Detailed Scheduling Up to 200 000 activities(no hard limitation) First solutionas fast as greedy heuristics More run timeimproves solution quality

Su 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 !! SNP: time, resource, product, procurement DS: time, resource Parallelization by “Agents” SNP ÅÆ DS Decomposition Hierarchy of Goals (customized by scripts) SNP: Service Level ÅÆ Production CostsDS: Service Level ÅÆ Storage Costs Open to partner solutions: Optimizer extension workbenchOur Mission Optimization as an integrated standard software solutionSAP AG 2002,CP AI OR 2004,Heinrich Braun35

Fo c u s o f De v e l o p m e n tIn the past larger optimization problems better solution quality more functionalityCurrent customer view Very confident with performance, solution quality, functionality Problem: Mastering the solution complexity (e.g. data consistency)Current focus of development More sophisticated diagnostic tools Parallelization by GRID ComputingSAP AG 2002,CP AI OR 2004,Heinrich Braun36

AgendaOptimization in SAP SCMAcceptance of Optimization SummarySAP AG 2002,CP AI OR 2004,Heinrich Braun37

A c c e p t a n c e Cr i t e r i aHeuristic (relaxing capacity) versus OptimizationOr Why do not all SNP-Customers use optimization?SAP AG 2002,CP AI OR 2004,Heinrich Braun38

Model Ac c urac ySNP Heuristic Interactive Planning: Planner responsible for feasibilityÆ limited model accuracy sufficientSNP Optimizer Automated Planning: Optimizer responsible for feasibilityÆ high model accuracy necessary Application in complex scenariosSAP AG 2002,CP AI OR 2004,Heinrich Braun39