close

Вход

Забыли?

вход по аккаунту

?

Application of Nature Inspired Algorithms For Job Shop

код для вставкиСкачать
School of Computer Science
University of Birmingham
Application of Nature Inspired
Genetic Algorithms For
Job Shop Scheduling
Bhuvan Sharma
Research Associate
Advanced Computation in Design and Decision Making Group
University West of England, Bristol, UK
bhuvan.sharma@uwe.ac.uk
Aim of Presentation
пѓ� Understanding job shop scheduling
пѓ� Why Nature Inspired Algorithms
пѓ� Issues in GA, when applied to job shop problems
пѓ� Review of various approaches within GA
пѓ� Practical Problem from Rolls Royce
пѓ� My approach
2
Job Shop Scheduling
Job
:
A piece of work that goes through series of
operations.
Shop
:
A place for manufacturing or repairing of
goods or machinery.
Scheduling : Decision process aiming to deduce the
order of processing.
3
A typical Job Shop Problem
Parameters
пѓ� Number of jobs
пѓ� Number of operations within each job
пѓ� Processing time of each operation within each job
пѓ� Machining sequence of operations within each job
Objectives
пѓ� Minimization of make span
пѓ� Minimization of cost
пѓ� Minimization of delays
4
A 3 job 3 machine problem
Machining Sequence
Jobs
Operations
Processing time
Jobs
Operations
J1
M1
M2
M3
J1
6
5
3
J2
M1
M3
M2
J2
4
3
4
J3
M3
M2
M1
J3
10
5
2
5
Why Nature Inspired Algorithms
GA’s
vs
• Evaluation on a set of
points. Better search.
• Better chances for global
optimal solution.
• Suitable for Multiobjective optimisation.
• Flexibility, because
constraints can be taken
care of.
Other methods
• Evaluation on a point
each time.
• Often terminate into
local optima.
• Not suited for multiobjective optimisation.
• Not flexible, driven by
heuristics, constraints
not handled easily.
6
Issues in Genetic Algorithms when
applied to job shop problems
пѓ� Representation of schedule(phenotype) by suitable
genotype.
пѓ� Conversion of genotype to phenotype
пѓ� Choice of Schedule Builder
пѓ� Type of Crossover and Mutation to be used
пѓ� Avoiding Premature convergence.
7
Schedule Builder!! What’s That
J1
M1
M2
M3
J2
M1
M3
M2
J3
M3
M2
M1
J1
6
5
3
J2
4
3
4
J3
10
5
2
8
Representation schemes for
schedules in job shop
пѓ� Conventional Binary representation
пѓ� Job Based Representation
пѓ� Permutation Representation (Partitioned)
пѓ� Permutation Representation (Repetitive)
пѓ� Priority Rule Based Representation (Random /
guided)
9
1. Binary Representation
пѓ� Genotype is binary matrix of
Rows = Number of job pairs
Columns = Number of machines
пѓ� Interpretation
Mij = 0 / 1 depending on whether job1
is executed later or prior to job2.
10
Job 1
M1
M3
M2
Job 2
M2
M3
M1
Job 3
M2
M1
M3
(a) Machine Sequence
Job1 & 2
110
M/c 1
J1 J3
J2
Job1 & 3
110
M/c 2
J3 J2
J1
Job2 & 3
010
M/c 3
J1 J2
J3
(b) Binary Representation
(c) Symbolic Representation
11
Crossover
пѓ� The crossover applied is simple one point
crossover.
Demerits
пѓ� Redundancy in representation.
2mj(j-1)/2 bits are required for (!j)m schedules.
пѓ� Forcing techniques required for replacement of
illegal schedules.
12
2. Job Based Representation
пѓ� Typical chromosome [ Ji Jj Jk ]
пѓ� For [ J2 J1 J3 ]
пѓ� All operations of job 2 folllowed by 1 and then by 3
are scheduled in the available processing times.
13
Merits
пѓ� Scheduling is very easy
пѓ� Always yields a feasible schedule, hence forcing
not required.
Demerits
пѓ� Approach is very constrained
пѓ� Not many possibilities are explored
14
3. Permutation Representation
(Partitioned)
пѓ� Chromosome is set of permutation of jobs on
each machine.
M1
M2
M3
132
3 2 1
312
Job sequence matrix for 3 X 3 problem
Cross Over (SXX)
пѓ� Subsequence Exchange Crossover
пѓ� Searches for exchangeable subsequence pairs
in parents, and swaps them.
15
Subsequence Exchange Crossover
M1
M2
M3
P0
123645
321564
235614
P1
621345
326451
635421
C0
213465
325164
263514
C1
612345
326415
356421
16
Merits
пѓ� GA operators used for TSP can be applied here
пѓ� Simple representation
Demerits
пѓ� Does not always give active schedules
пѓ� Robust Schedule builder is required
пѓ� SXX does not always guarantee a crossover
4. Permutation Representation
(Repetitive)
пѓ� Also known as operation based representation
пѓ� Typical genotype is a unpartitioned permutation
with m repetitions for each job.
1
M1
M2
M3
2
2
3
1
1
2
3
2
3
2
3
2
1
3
1
1
3
18
Crossover (PPX)
пѓ� Precedence Preservation Crossover (PPX)
пѓ� The offspring inherits partial characteristic
of both parents
P0
3 2 2 3 1 1 3 1 2
0 1 1 1 0 0 1 0 1
P1
2 3 3 2 1 3 1 1 2
C1
3 2 3 2 1 1 3 1 2
19
Merits
пѓ� Very simple representation
пѓ� All decoding leads to active schedules
пѓ� Schedule building is straightforward
пѓ� Crossover results in passing of characteristics from
both parents in most cases.
Demerits
пѓ� Problem of Premature convergence
пѓ� This is often case with long chromosomes
20
5. Priority(Random/Guided)Rule
Based Representation
Characteristics
пѓ� Use of GT Algorithm, with one of priority rule
used in ith iteration to select ith operation
пѓ� Priority rules could be assigned randomly, or
guided by heuristics.
Representation
� [ SPT, LPT, MTPT, LTPT, MLFT, ….. ]
21
Crossover
пѓ� Both PPX and SXX can be used
Merits
пѓ� Always give feasible active schedules
пѓ� Incorporates heuristics to an extent
Demerits
пѓ� Problem of fast, premature convergence of
first few genes in the chromosome
22
Practical Problem from Rolls
Royce
Parameters
пѓ� 17 batches of jobs
пѓ� 10 operations per job
пѓ� 4 identical machines, each can perform any
operation subject to tool set
Constraints
пѓ� Only one tool-set for each operation
пѓ� Opn. 2 must not begin until opn 1 is complete
пѓ� Opn 3-9 can be performed in any sequence
пѓ� Opn 10 should be the last for each batch of job
23
Basic Scenario
Operation
Time (min)
1
120
2
288
Leave Shop
24hrs
3
180
4
90
5
288
6
120
7
60
8
60
9
90
Leave Shop
10
24 hrs
60
24
My Approach
Representation
пѓ� Permutation based
пѓ� The catch here is that it is permutation of machines
not jobs
пѓ� For eg. [ 3 5 9 6 : 7 4 8 | 10 ]
Crossover
пѓ� Precedence Preservation Crossover (PPX)
25
Start with heuristics
Select a set of jobs out of 17 to process first. (random)
Schedule builder
пѓ� Identify conflicting set of jobs
пѓ� Selection of one from conflicting set based on
one of heuristic priority rules
пѓ� Change toolset for machine as it finishes requisite
jobs. Change is guided by time factor.
26
27
Документ
Категория
Презентации
Просмотров
5
Размер файла
190 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа