Task assignment optimization in SAP Extended Warehouse ...

1 Task assignment optimization in SAP Extended WarehouseManagementAkos Monori2008 Master thesisComputer EngineeringNr: E3600D kos MonoriDegree ProjectAugust 20082H gskolan DalarnaR da V gen 3S-781 88 Borl ngeTel:+46-23-778800 Fax:+46-23-778050http: PROJECTIn Computer EngineeringProgrammeMaster in Computer EngineeringReg. numberE3600 DExtent30 ECTSName of student kos RebreyendExaminerMark DoughertyCompanySAP Hungary KFTS upervisor at the companyIstv n Gell rtTitle Task assignment optimization in SAP Extended WarehouseManagementKeywords in EnglishWarehouse management , taskassignment, generalized assignmentproblem, SAP, EWM kos MonoriDegree ProjectAugust 20083H gskolan DalarnaR da V gen 3S-781 88 Borl ngeTel:+46-23-778800 Fax:+46-23-778050http: in the world of mass consumption there is big demand for distributioncenters of bigger size.

2 Managing such a center is a very complex and difficult taskregarding to the different processes and factors in a usual Warehouse when we want tominimize the labor costs. Most of the workers working time is spent with travelingbetween source and destination points which cause deadheading. Even if a worker knowsthe structure of a Warehouse well and because of that he or she can find the shortest pathbetween two points, it is still not guaranteed that there won t be long traveling t imebetween the locations of two consecutive tasks. We need optimal assignments betweentasks and the scientific literature Generalized assignment Problem (GAP) is a well-known problem which deals with the assignment of m workers to n tasks consideringseveral constraints.

3 The primary purpose of my thesis project was to choose a heuristics(genetic algorithm, tabu search or ant colony optimization ) to be implemented into SAPE xtended Warehouse management (SAP EWM) by with task assignment will be moreeffective between tasks and system analysis I had to realize that due different constraints and businessdemands only 1:1 assingments are allowed in SAP EWM. Because of that I had to use adifferent and simpler approach instead of the introduced heuristics which could gainbetter assignments during the test phase in several cases. In the thesis I described indetails what ware the most important questions and problems which emerged during theplanning of my optimized assignment method. kos MonoriDegree ProjectAugust 20084H gskolan DalarnaR da V gen 3S-781 88 Borl ngeTel:+46-23-778800 Fax:+46-23-778050http.

4 31. INTRODUCTION .. The problem to be solved .. Generalized assignment Problem .. Complexity of the Generalized assignment 102. Warehouse management SYSTEMS AND SAP EWM .. Why do we need warehouses?.. Warehouse management Systems .. What is SAP EWM? .. The structure of a Warehouse in EWM .. Storage types .. Activity areas .. Storage Storage Warehouse tasks and Attributes of a resource .. 273. optimization METHODS FOR SOLVING THE GENERALIZEDASSIGNMENT PROBLEM .. Ant colony Analogy with the real ants .. Applications of the Ant Colony Solving GAP with ACO .. Evolutionary algorithms .. Solution representations in genetic 33 kos MonoriDegree ProjectAugust 20085H gskolan DalarnaR da V gen 3S-781 88 Borl ngeTel:+46-23-778800 Fax:+46-23-778050http: Operators: mutation and crossover.

5 Initial population and candidate selection .. Performance of the GA .. Solving GAP with GA .. Local search A local search method - tabu search .. Tabu The aspiration criteria of the tabu search .. 424. THE CURRENT WAY OF TASK/RESOURCE assignment IN SAP EWMVERSION AND THE NEW PROPOSED Route optimization or task assignment optimization ? .. Task interleaving .. The purpose of task interleaving .. Practical example of task interleaving .. Task assignment in the latest SAP EWM release .. Connecting queues to resources via resource Task interleaving in SAP EWM .. Special cases during the assignment The new model for the Number of Warehouse orders to be assigned to the A problem estimating the execution time of a Warehouse How to compute the processing time of a specific Warehouse order?

6 The decision about the number of Warehouse Organizing the Warehouse orders from different queues .. When and how to search for available Warehouse orders?.. A second searching approach .. Why don t use GA, ACO or TS for this scenario? .. 665. DEVELOPMENT PHASE IMPLEMENTATION ISSUES AND TECHNICALDETAILS .. Where to place the call of the new function into the old logic? .. How to store the data? .. Are new data types required and can I reuse existing functions? .. 73 kos MonoriDegree ProjectAugust 20086H gskolan DalarnaR da V gen 3S-781 88 Borl ngeTel:+46-23-778800 Fax:+46-23-778050http: What is ABAP? .. 746. TEST PHASE ANALYZING THE The process of the Test Test case Test case Test case Test case Test case Test case Test case Test case Analysis of the results and conclusion.

7 The running time of the Comparing the new method to the proposed heuristics .. The effectiveness of the new algorithm .. Future Work .. 93 APPENDIX A ..961. 962. List of abbreviations .. 983. List of figures .. 994. List of 102 APPENDIX B ..1121. Source code samples .. 112 kos MonoriDegree ProjectAugust 20087H gskolan DalarnaR da V gen 3S-781 88 Borl ngeTel:+46-23-778800 Fax:+46-23-778050http: handle the contents of this thesis workconfidentially. kos MonoriDegree ProjectAugust 20088H gskolan DalarnaR da V gen 3S-781 88 Borl ngeTel:+46-23-778800 Fax:+46-23-778050http: ForewordFirst of all I would like to thank Istv n Gell rt for his help as a supervisor duringthe making of my thesis project. His professional advices regarding the ABAP environment and the EWM software both from technical and business aspects helped mea lot when I had to plan and implement my own solution for the resource/taskassignment.

8 Also I would like to thank all my colleagues who gave me good advices inABAP development. Last but not least I would like to thank Krisztina, my girlfriend whosupported me all the time and sometimes missed my attention due to the The problem to be solvedThe problem sketched in the abstract part is a very complex one since manyconstraints shall be considered. Empty travels are not welcome because they need energyand time but don t denote effective work. This can happen frequently in a Warehouse ifscheduling lines are not well organized, the location of subsequent tasks are far from eachother. If a worker can find out the shortest (or almost the shortest) path between twolocations then it s still not the best situation, since maybe there were another location andtask but in shorter primary goal of my thesis is to find a solution to be implemented into SAPE xtended Warehouse management by with task assignment will be more effective.

9 This kos MonoriDegree ProjectAugust 20089H gskolan DalarnaR da V gen 3S-781 88 Borl ngeTel:+46-23-778800 Fax:+46-23-778050http: assignment problem is called General assignment Problem (GAP) in thescientific literature which consists in assigning a set of tasks to a set of agents withminimum cost. Each agent has a limited amount of a single resource and each task mustbe assigned to one and only one agent, requiring a certain amount of the resource of theagent. Later I will show how the practical example differs from the original GAP andwhat kind of approach did I use instead of the different popular solutions such asevolutionary Generalized assignment ProblemThe objective of the GAP is to find a minimum cost assignment matrix for m>0tasks and n>0 workers such that each job is assigned to exactly one worker.

10 Such anassignment requires a cost and resource from the worker s side. This problem occurs inmany fields such as communication networks, vehicle routing, machine scheduling. Inmy thesis project the application field is task / worker assignment in a the problem can be described as follows [13]:I: set of tasks (i=1 ..n)J: set of agents (j= )aj= resource capacity of agentjbij= resource needed if taskiis assigned to agentjcij= cost of taskiif assigned to agentj kos MonoriDegree ProjectAugust 200810H gskolan DalarnaR da V gen 3S-781 88 Borl ngeTel:+46-23-778800 Fax:+46-23-778050http: variables are:xij= 1, if taskiis assigned to agentj; 0, (x) njijijmixc112. d nijijijaxb1 j = 1,..,m3. dmjijx11 i= 1,.., ,..,jn1,..,i}1,0{ xijThe object ive is to find an assignment matrixx=xij, withxij= 1 if agentiperforms job j and 0 otherwise, which minimizes the total costs.