Presentetion and analysis of three hybridization models

PRESENTATION AND ANALYSIS OF THREE HYBRIDIZATION MODELS WITH TABOO SEARCH AND SIMILAR PARTICLE SWARM OPTIMIZATION HEURISTICS FOR THE JOB SHOP SCHEDULING PROBLEM
1

Tatiana Balbi Fraga

SUMMARY OF THIS PRESENTATION
Problem’s presentation  Solution’s methods  Local Search heuristics


Taboo Search  Similar Particles Swarm Optimization
 

Hybridization models proposed
Hybrid Successive Application  Hybrid Neighborhood  Hybrid Improved Neighborhood




Results, conclusions and future work
2

GENERAL SCHEDULING PROBLEM

Tasks

Machines

3

Clothes manufacturing

EXAMPLE:

4

JOB SHOP SCHEDULING PROBLEM (JSSP)

Machine 1

Machine 2

Machine 3

Machine 4

Machine 5

Machine 6

5

SOLUTION’S METHODS FOR THE JSSP
Optimization


Approximation
 

Efficient methods


Johnson’s method Mathematical
Mixed Integer Linear Programming  Interger Linear Programming




Enumerative methods

 

Priority Dispatch Rules Bottleneck Based Heuristics Artificial Intelligence Local Search Heuristics
Taboo Search  Simulated Annealing  Genetic Algorithms  Particle Swarm Optimization




Branch and Bound

6

LOCAL SEARCH HEURISTICS
Constructive method Initial parent solutions Neighborhood generation operator Neighborhood Selection method New parent solutions Best solution found

No

Yes

Stopping criterion is satisfied ?
7

HYBRIDIZATION MODELS
Constructive method Initial parent solutions Different neighborhood generation operators Hybrid neighborhood Selection method New parent solutions Best solution found

No

Yes

Stopping criterion is satisfied ?
8

HYBRIDIZATION MODELS
Hybrid Successive Aplication  Hybrid Neighborhood  Hybrid Improved Neighborhood


9

HYBRID SUCCESSIVE APPLICATION
Constructive method Initial parent solutions Best solution found

Operator 1
Operador 2 Operador N Hybrid neighborhood

No

Yes

Stopping criterion is satisfied