Klepnutím lze upravit styl předlohy. Klepnutím lze upravit styl předlohy. nadpisů. nadpisů. Optimization of Warehouse Processes

Signal Processing Laboratory

SPLab, BUT

1 / 32

Klepnutím lze upravit styl předlohy Klepnutím lzenadpisů. upravit styl předlohy nadpisů.

http://splab.cz/en

Optimization of Warehouse Processes Jan Karásek Brno University of Technology Faculty of Electrical Engineering and Communication Department of Telecommunications, Signal Processing Laboratory

[email protected]

Brno University of Technology


2 / 32

SPLab, BUT

Klepnutím lzeOutline upravit styl předlohy nadpisů. • Introduction •

Problem Definition, Main Goals, Warehouse Description

• Problem Solutions • Generation I, II, III

• • • • • • •

Related Problems, New Ideas Java Evolutionary Framework Grammar Driven Genetic Programming GDGP Algorithm Design Benchmark Definition Experimental Results Conclusion + Further Research

[email protected]



3 / 32

SPLab, BUT

Introduction Klepnutím lze upravit styl předlohy Problem Definition nadpisů. Definition of Research Problem How to spread the tasks among employees and assign the equipment, so that the system can work as a cooperating whole with minimal time demands and with collision avoidance...

Main goals are to minimize a time of job processing, and to avoid the collisions of fork-lift trucks. [email protected]



SPLab, BUT

4 / 32

y, height

Introduction Klepnutím lze upravit styl předlohy Warehouse Description x, width nadpisů. Typical rectangular shape of warehouse. Coordinates: x, y, z (level of shelf).

Goals, more concretely:

a) to minimize time of: searching (location of goods) travelling (how to get there) picking (both together) b) to avoid collision by minimization of: idle times (truck waiting for another) crash of trucks (were not waiting) not available path (congestion) [email protected]



5 / 32

SPLab, BUT

Problem Solutions Klepnutím lze upravit styl předlohy nadpisů. The processes in the warehouse are driven by: • Human Operators/Shift leaders, • Warehouse Management Systems • Methods based on Artificial Intelligence

[email protected]



SPLab, BUT

6 / 32

Problem Solutions – Generation I Klepnutím lze upravit styl předlohy How the problem is being solved usually nadpisů.

? [email protected]



SPLab, BUT

7 / 32

Problem Solutions – Generation II Klepnutím lzeTheupravit styl předlohy TOP solution (Mibcon, Certified by SAP) nadpisů.

? [email protected]



SPLab, BUT

8 / 32

Problem Solutions – Generation III Klepnutím lzeSolution upravit styl předlohy based on GDGP we are working on nadpisů.

? [email protected]



SPLab, BUT

9 / 32

Related Problems andstyl New Ideas Klepnutím lze upravit předlohy nadpisů. Warehouse Optimization • Technical Structure (layout, dimensions, racks, aisles…) • Operational Structure (random/dedicated storing, grouping, zoning…) • Management Systems (interconnection between various systems) Scheduling Problems (Shop Scheduling)

+ Routing Problems (Vehicle Routing) [email protected]

}

Robotic Cells Hoists AGV’s



SPLab, BUT

10 / 32

Related Problems andstyl New Ideas Klepnutím lze upravit předlohy nadpisů. 2

2

Going in this direction empty, can help to another employee. 13 2

[email protected]



SPLab, BUT

11 / 32

Related Problems andstyl New Ideas Klepnutím lze upravit předlohy nadpisů.

No goods

There is no goods during the planning process, But before the fork-lift truck will come, the goods will be replenished.

[email protected]



SPLab, BUT

12 / 32


?

Postponing the employee break one more operation further can have a significantly positive impact on the other jobs.

[email protected]



SPLab, BUT

13 / 32


• Solution is less demanding on human resources • Higher utilization of employees and trucks • Saves labor energy • Solution does not require highly skilled operational managers. [email protected]



SPLab, BUT

14 / 32

Java Evolutionary Klepnutím lze upravitFramework styl předlohy nadpisů. Genetic Programming • New Java Evolutionary Framework based on Genetic Programming

• Driven by Context-free Grammar • Thousands of possible variants of problem • The more complicated problem, the better and successful solution in comparison with human [email protected]

Simulace

Simulace Simulation GDGP can “see” to the future, and can predict the most probable situations and properly react to them.



15 / 32

SPLab, BUT

Java Evolutionary Klepnutím lze upravitFramework styl předlohy nadpisů.

[email protected]



SPLab, BUT

16 / 32

Grammar Driven Geneticstyl Programming Klepnutím lze upravit předlohy nadpisů. • Set of Terminal Symbols (inputs) – Coordinates[x,y] (start, end), Employee, Equipment, Commodity, Deadline…

• Set of Non-Terminal Symbols (functions = tasks) – Operation, Job, various Task (TaskInStore, TaskOutStore…) – Load, Unload, Move, Relax, Wait…

• Fitness Function – Minimization of Completion time, Number of Collisions…

• Run Control – Size of Population, Grammar, Operator Rates…

• End Control – Number of generations [email protected]



17 / 32

SPLab, BUT

Grammar Driven Geneticstyl Programming Klepnutím lze upravit předlohy nadpisů. Definition of Grammar (G = V, ∑, R, S) • • • •

V (Set of Non-Terminal characters) ∑ (Set of Terminal characters) R (Set of Rules) S (Start) S ::= Workplan R :: = Workplan Operation Job

::= Operation Employee Equipment ::= Operation Job | Operation null ::= TaskInStore | TaskOutStore | TaskRelax | TaskWait…. TaskInStore ::= Load Move Unload Commodity, Start, End… TaskOutStore ::= Load Move Unload Commodity, …. Deadline TaskRelax ::= Wait Position Duration | Relax … [email protected]



SPLab, BUT

18 / 32

Advantages Innovative Klepnutím lzeofupravit stylMethod předlohy nadpisů. + Simulation of Future and Expected Events/Operations + + + + +

It Plans Jobs for Employees, Utilization and Energy It looks at the Warehouse as one Cooperating Unit Less Requirements on Skilled Human Resources An Efficient Break Scheduling Increases Resistance: + Failure of Operational Manager + Effect of Emotions and Stress + Panic in Crisis Situations

[email protected]



SPLab, BUT

19 / 32

Design KlepnutímAlgorithm lze upravit styl předlohy nadpisů. Tasks Job Job Buffer Employees & Equipment

Workplan 1

Job 1

Workplan 2 Workplan 3

Job 5

Job 2

Job 3

Gene Chromosome

Job 6

Job 4

Population fitness function [email protected]



SPLab, BUT

20 / 32

Genetic Operators – Path Klepnutím lze upravit stylMutation předlohy nadpisů. Workplan 1


Job 1

Job 5

Job 2

Job 3

Chromosome

Job 6

Job 4

Path mutation with rate RPM 1) Randomly select the Workplan (no. 3) 2) Randomly select the Job (no. 4) 3) Apply Path mutation on Move Task Workplan 3

[email protected]

Job 4



SPLab, BUT

21 / 32

Genetic Operators – Job Order Mutation Klepnutím lze upravit styl předlohy nadpisů. Workplan 1

Workplan 2

Job 1

Job 5

Job 2

Job 3

Workplan 3

Chromosome

Job 6

Job 4

Job Order mutation with rate RTO 1) Randomly select the Workplan (no. 2) 2) Apply Job Order mutation

Workplan 2

[email protected]

Job 6

Job 3



SPLab, BUT

22 / 32

Genetic Operators – Swapstyl Job předlohy Mutation Klepnutím lze upravit nadpisů. Workplan 1

Workplan 2

Job 1

Job 3

Workplan 3

Workplan 2 Workplan 3 [email protected]

Job 5

Job 2

Chromosome

Job 6

Job 4

Job 4

Swap Job mutation with rate RST 1) Randomly select the Workplans (no. 2 and no. 3) 2) Randomly Select Two Jobs Job 6 3) Swap Selected Jobs

Job 3 Brno University of Technology


SPLab, BUT

23 / 32

Genetic Operators Swap Workplan Mutation Klepnutím lze –upravit styl předlohy

nadpisů. Workplan 1

Workplan 2

Job 1

Job 3

Workplan 3

[email protected]

Chromosome

Job 6

Job 4


Job 5

Job 2

Swap Workplan mutation with rate RSW 1) Randomly select the Workplans (no. 2 and no. 3) 2) Swap All Jobs

Job 4

Job 3

Job 6 Brno University of Technology


SPLab, BUT

24 / 32

Genetic Operators – Splitstyl Job Mutation Klepnutím lze upravit předlohy nadpisů. Workplan 1

Job 1

Workplan 2

Job 3

Workplan 3

Workplan 1 Workplan 3 [email protected]

Job 5

Job 2

Chromosome

Job 6

Job 4

Job 1

Job 2

Job 4

Split Job mutation with rate RSA 1) Randomly select the Workplan (no. 1) Job 5.1 2) Randomly select Job (Job 5) 3) Apply Task Order mutation Job 5.2



SPLab, BUT

25 / 32

Benchmarks Definition Klepnutím lze upravit styl předlohy nadpisů.

• State the benchmark

– Manually measure the time and performance – Based on human decision – Automatically measure the time and performance – Use different genetic operators and combinations – Based on evolution [email protected]



•

SPLab, BUT

26 / 32

Benchmarks Definition Klepnutím lze upravit styl předlohy nadpisů. Data from warehousing company from pre Christmas time, when human operator was stressed, tired . . . extracted to simple scenarios => benchmark sets

• How the operator spread the work, e.g.: • Emp1, Truck1, WP1 • T1, T2

Visual Validation

• Emp2, Truck2, WP2 • T3, T4, T5

empID, truckID, jobEndTime, commID, destX, destY, job, task

• 2 Sets of Simple Benchmarks (2 x 10 Scenarios) [email protected]


Benchmark Set #1


Experimental Klepnutím lze upravitResults styl předlohy nadpisů. 2-4 employees with hand pallet truck Human Operator 13,00 16,50 13,00 16,50 12,50 14,50 15,00 9,00 13,00 16,50

Genetic Programming

Path Mutation Task Order M. Both Mutation 15,50 13,00 13,00 16,50 16,50 16,50 28,50 28,50 28,50 16,50 18,50 16,50 12,50 12,50 12,50 26,50 26,50 26,50 15,00 15,00 15,00 8,00 8,00 8,00 13,00 12,50 14,00 16,00 16,00 16,00

values are measured in standardized time units [t.u.]

Benchmark Set #2

SPLab, BUT

27 / 32

Human Operator 8,00 14,00 13,00 14,00 11,00 14,50 15,00 8,50 13,00 16,50

Genetic Programming Path Mutation Task Order M. Both Mutation 11,50 8,00 8,00 14,50 14,50 14,50 15,50 13,88 14,63 12,50 12,25 12,25 11,00 11,00 11,00 16,50 15,00 15,00 11,50 11,50 11,50 8,00 8,00 8,00 12,50 12,00 12,00 12,13 13,00 12,13

[email protected]

Speed of hand pallet truck = 2 t.u. Collision detection is not implemented Each employee has own tasks Size of population: # of generations: Path mutation rate: Task order mutation rate: Tournament selection

10 10 30% 30%

2-4 emps with hand/low fork-lift Speed of fork-lift low truck = 8 t.u. Collision detection is not implemented Each employee has own tasks Brno University of Technology


28 / 32

SPLab, BUT

Experimental Klepnutím lze upravitResults styl předlohy nadpisů. Time: R: 5.38 Y: 16.50 G: 6.50

Red = [0,3] > [0,0] > [1,0] > [4,0] > [4,5] > [5,5] Yellow = [4,8] > [4,0] > [5,0] > [14,0] > [14,8] > [15,8] Green = [12,1] > [12,0] > [11,0] > [8,0] > [8,1] > [7,1] [email protected]



29 / 32

SPLab, BUT

Experimental Klepnutím lze upravitResults styl předlohy nadpisů. Time: R: 7.00 Y: 13.00 G: 7.50

Red = [0,3] > [0,0] > [4,0] > [5,0] > [14,0] > [14,8] > [15,8] Yellow = [4,8] > [4,0] > [2,0] > [1,0] > [4,0] > [4,5] > [5,5] Green = [12,1] > [12,0] > [11,0] > [6,0] -> [6,1] -> [7,1] [email protected]



30 / 32

SPLab, BUT

Conclusion Klepnutím lze upravit styl předlohy nadpisů. • The system can automatically model and evaluate • • • •

thousands of possible variants of solution Competitive results has been reached even if the scenarios were so simple for human to design solution The more complex problem the better solution in comparison with human based solutions Employee gets into his PDA the information about what to do and how exactly get there The system re-computes results each 5 minutes for current tasks, so the employees information are updated

[email protected]



SPLab, BUT

31 / 32

Acknowledgement Klepnutím lze upravit styl předlohy nadpisů. Research and development of the system for manufacturing optimization

Project no: FR-TI1/444 [email protected]



32 / 32

SPLab, BUT

Klepnutím lze upravit styl předlohy Klepnutím lzenadpisů. upravit styl předlohy nadpisů.

http://splab.cz/en

Czech Republic

[email protected]

European Union


Klepnutím lze upravit styl předlohy. Klepnutím lze upravit styl předlohy. nadpisů. nadpisů. Optimization of Warehouse Processes

Recommend Documents