close

Вход

Забыли?

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

?

Flow Shop Scheduling

код для вставкиСкачать
Flow Shop Scheduling
Production Scheduling
1
P.C. Chang, IEM, YZU.
Definitions
• Contains m different machines.
• Each job consists m operators in different
machine.
• The flow of work is unidirectional.
• Machines in a flow shop = 1,2,…….,m
• The operations of job i , (i,1) (i,2) (i ,3)…..(i, m)
• Not processed by machine k , P( i , k) = 0
Production Scheduling
2
P.C. Chang, IEM, YZU.
Flow Shop Scheduling
Baker p.136
The processing sequence on each machine are all the same.
1
2 3 1 5 4
2.
2 3 1 5 4 пѓџ Flow shop
M
1 3 2 4 5 пѓџ Job shop
...
.
n! - flow shop permutation schedule
n!.n! …….n! - Job shop
( n!)
( n!) m
m
or
Production Scheduling
k
k : constraint
(в€µ routing problem)
3
P.C. Chang, IEM, YZU.
Workflow in a flow shop
Baker p.137
Type 1.
Input
Machine
1
Machine
2
Machine
3
….
Machine
M-1
Machine
M
output
Type 2.
Input
Input
Input
Machine
1
Machine
2
Machine
3
output
output
output
Production Scheduling
….
4
Input
Input
Machine
M-1
Machine
M
output
output
P.C. Chang, IEM, YZU.
Johnson’s Rule
Baker p.142
Step 1 : Find min i {t i1 , t i2 }
Step 2 a : If the min t requires machine 1, place the job in the first available
position
in sequence . go to step 3 .
Step 2 b : If the min t requires machine
2 , place the job in the first available
position
in sequence . go to step 3 .
Step 3 : Remove
the assigned job from considerat ion and return to step 1 until all
positions in sequence are filled .
Note:
Johnson’s rule can find an optimum with two machines
Flow shop problem for makespan problem.
Production Scheduling
5
P.C. Chang, IEM, YZU.
Ex.
j
tj1
tj2
1
3
6
2
5
2
3
1
2
4
6
6
5
7
5
Stage
U
Min tjk
Assignment
Partial Schedule
1
1,2,3,4,5
t31
3=[1]
3xxxx
2
1,2,4,5
t22
2=[5]
3xxx2
3
1,4,5
t11
1=[2]
31xx2
4
4,5
t52
5=[4]
31x52
5
4
t11
4=[3]
31452
Production Scheduling
6
P.C. Chang, IEM, YZU.
Ex.
M1 3
M2
1
3
4
1
5
4
2
5
2
24
The makespan is 24
Production Scheduling
7
P.C. Chang, IEM, YZU.
The B&B for Makespan Problem
The Ignall-Schrage Algorithm
(Baker p.149)
- A lower bound on the makespan associated with any
completion of the corresponding partial sequence Пѓ is
obtained by considering the work remaining on each
machine. To illustrate the procedure for m=3.
For a given partial sequence Пѓ, let
q1= the latest completion time on machine 1 among jobs in Пѓ.
q2= the latest completion time on machine 2 among jobs in Пѓ.
q3= the latest completion time on machine 3 among jobs in Пѓ.
The amount of processing yet required of machine 1 is  t j1
jпѓЋ пЃі '
Production Scheduling
8
P.C. Chang, IEM, YZU.
The Ignall-Schrage Algorithm
In the most favorable situation, the last job
1) Encounters no delay between the completion of one operation
and the start of its direct successor, and
2) Has the minimal sum (tj2+tj3) among jobs j belongs to σ’
Hence one lower bound on the makespan is
A second lower bound on machine 2 is
A lower bound on machine 3 is
b 1  q 1   t j1  min { t j 2  t j3 }
jпѓЋ пЃі '
jпѓЋ пЃі '
b 2  q 2   t j 2  min { t j3 }
jпѓЋ пЃі '
jпѓЋ пЃі '
b 3  q 3   t j3
jпѓЋ пЃі '
The lower bound proposed by Ignall and Schrage is
Production Scheduling
9
B пЂЅ max{ b 1 , b 2 , b 3 }
P.C. Chang, IEM, YZU.
The Ignall-Schrage Algorithm
Job in σ’
…….
.
M1
q1
tk1
……..
M2
tk2
q2
M3
……..
tk3
q3
b1
……..
M2
tk2
q2
……..
M3
q3
Production Scheduling
tk3
b2
10
P.C. Chang, IEM, YZU.
Ex. B&B
m=3
j
tj1
1
3
2
11
3
7
4
10
tj2
4
1
9
12
tj3 10
5
13
2
For the first node: Пѓ =1
q 1 пЂЅ t 11 пЂЅ 3
q 2 пЂЅ t 11 пЂ« t 12 пЂЅ 7
q 3 пЂЅ t 11 пЂ« t 12 пЂ« t 13 пЂЅ 17
The lower bound пЂЅ
b 1 пЂЅ 3 пЂ« 28 пЂ« 6 пЂЅ 37
b 2 пЂЅ 7 пЂ« 22 пЂ« 2 пЂЅ 31
пѓ¬ 1пЂ« 5 пѓј
пѓЇ
пѓЇ
6 пЂЅ min пѓ­ 9 пЂ« 13 пѓЅ
пѓЇ12 пЂ« 2 пѓЇ
пѓ®
пѓѕ
Production Scheduling
b 3 пЂЅ 17 пЂ« 20 пЂЅ 37
B пЂЅ max( 37 ,31 ,37 ) пЂЅ 37
11
P.C. Chang, IEM, YZU.
Ex.
1
0
Partial Sequence
( q1 , q2 , q3 )
(b1,b2,b3)
B
1xxx
( 3 , 7 , 17 )
( 37 , 31 , 37 )
37
2xxx
( 11 , 12 , 17 )
( 45 , 39 , 42 )
45
3xxx
( 7 , 16 , 29 )
( 37 , 35 , 46 )
46
4xxx
( 10 , 22 , 24 )
( 37 , 41 , 52 )
52
12xx
( 14 , 15 , 22 )
( 45 , 38 , 37 )
45
13xx
( 10 , 19 , 32 )
( 37 , 34 , 39 )
39
14xx
( 13 , 25 , 27 )
( 37 , 40 , 45 )
45
132x
( 21 , 22 , 37 )
( 45 , 36 , 39 )
45
134x
( 20 , 32 , 34 )
( 37 , 38 , 39 )
39
b 1  q 1   t j1  min { t j 2  t j3 }
2
3
jпѓЋ пЃі '
14
1
7
1
пѓ¬ 9 пЂ« 13 пѓј
пЂЅ 14 пЂ« ( 7 пЂ« 10 ) пЂ« min пѓ­
пѓЅ
12
пЂ«
2
пѓ®
пѓѕ
пЂЅ 45
2
15
2
17
Production Scheduling
jпѓЋ пЃі '
22
12
P.C. Chang, IEM, YZU.
Ex. B&B
P0
1xxx
2xxx
B=37
12xx
13xx
B=45
B=45
4xxx
B=46
B=52
14xx
B=39
132x
3xxx
B=45
134x
B=45
Production Scheduling
B=39
13
P.C. Chang, IEM, YZU.
Refined Bounds
The use of q2 in the calculation of b2 ignores the possibility that
the starting time of job j on the machine 2 may be constrained
by commitments on machine1. Hence:
Modification1: consider idle time
пѓ¬
пѓј
пѓЇ
пѓЇ
q ' 2 пЂЅ max пѓ­ q 2 , q 1 пЂ« min[ t j1 ] пѓЅ
пѓЇ
пѓЇ
jпѓЋ пЃі '
пѓ®
пѓѕ
пѓ¬
пѓј
пѓЇ
пѓЇ
q ' 3 пЂЅ max пѓ­ q 3 , q 2 пЂ« min[ t j 2 ], q 1 пЂ« min[ t j1 пЂ« t j 2 ] пѓЅ
пѓЇ
пѓЇ
jпѓЋ пЃі '
jпѓЋ пЃі '
пѓ®
пѓѕ
Production Scheduling
14
P.C. Chang, IEM, YZU.
Refined Bounds
Modification2: (McMahon and Burton)
b4
пѓ¬
пѓЇ
 q 1  max  t k 1  t k 2  t k 3   min t j1 , t j3
kпѓЋпЃі '
jпѓЋ пЃі '
пѓЇ
jп‚№ k
пѓ®
пЃ›
пѓ¬
пѓЇ
b 5  q ' 2  max  t k 2  t k 3   min t j 2 , t j3
kпѓЋпЃі '
jпѓЋ пЃі '
пѓЇ
jп‚№ k
пѓ®
B ' пЂЅ max{ B , b 4 , b 5 }
пЃ›
пѓј
пѓЇ
пѓЅ
пѓЇ
пѓѕ
пЃќ
пѓј
пѓЇ
пѓЅ
пѓЇ
пѓѕ
пЃќ
Previous : Machine-based bound
Modification2 : Job-based bound
Production Scheduling
15
P.C. Chang, IEM, YZU.
Refined Bounds
Obviously, B’>=B, This means that the combination
of machine-based and job-based bounds represented
by B’ will lead to a more efficient search of the
branching tree in the sense that fewer nodes will be
created.
Production Scheduling
16
P.C. Chang, IEM, YZU.
Hw.
Consider the following four-job three-machine problem
a.
b.
j 1
tj1 13
2
7
3
26
4
2
tj2
12
9
6
tj3 12 16
7
1
3
Find the min makespan using the basic Ignall-Schrage
algorithm. Count the nodes generated by the branching
process.
Find the min makespan using the modified algorithm.
Production Scheduling
17
P.C. Chang, IEM, YZU.
Heuristic Approaches
Traditional B&B:
• The computational requirements will be severe for large
problems
• Even for relatively small problems, there is no guarantee
that the solution can be obtained quickly,
Heuristic Approaches
• can obtain solutions to large problems with limited
computational effort.
• Computational requirements are predictable for problem of
a given size.
Production Scheduling
18
P.C. Chang, IEM, YZU.
Palmer
Palmer proposed the calculation of a slope index, sj, for
each job.
s j пЂЅ ( m пЂ­ 1) t j, m пЂ« ( m пЂ­ 3 ) t j, m пЂ­ 1 пЂ« ( m пЂ­ 5 ) t j, m пЂ­ 2 пЂ« пЃЊ пЂ­ ( m пЂ­ 3 ) t j, 2 пЂ­ ( m пЂ­ 1) t j,1
Then a permutation schedule is constructed using the
job ordering
s [1] п‚і s [ 2 ] п‚і пЃЊ п‚і s [ n ]
Production Scheduling
19
P.C. Chang, IEM, YZU.
Gupta
Gupta thought a transitive job ordering in the form of follows
that would produce good schedules. Where
sj пЂЅ
ej
min{ t j1 пЂ« t j 2 , t j 2 пЂ« t j3 }
Where
пѓ¬ 1 if
ej пЂЅ пѓ­
пЂ­ 1 if
пѓ®
t j1 пЂј t j3
t j1 п‚і t j3
Production Scheduling
20
P.C. Chang, IEM, YZU.
Gupta
Generalizing from this structure, Gupta proposed that for m>3,
the job index to be calculated is
sj пЂЅ
ej
min
{ t jk пЂ« t j, k пЂ« 1 }
1п‚Ј k п‚Ј m пЂ­1
Where
пѓ¬ 1 if
ej пЂЅ пѓ­
пЂ­ 1 if
пѓ®
t j1 пЂј t jm
t j1 п‚і t jm
Production Scheduling
21
P.C. Chang, IEM, YZU.
CDS
Its strength lies in two properties:
1.It use Johnson’s rule in a heuristic fashion
2.It generally creates several schedules from which a “best”
schedule can be chosen.
The CDS algorithm corresponds to a multistage use if
Johnson’s rule applied to a new problem, derived from the
original, with processing times t ' j1 and t ' j 2 . At stage 1,
t ' j1 пЂЅ t j1
and
t ' j 2 пЂЅ t jm
Production Scheduling
22
P.C. Chang, IEM, YZU.
CDS
In other words, Johnson’s rule is applied to the first and mth
operations and intermediate operations are ignored. At stage
2,
t' пЂЅ t пЂ« t
and t ' пЂЅ t
пЂ«t
j1
j1
j2
j2
jm
j, m пЂ­ 1
That is, Johnson’s rule is applied to the sums of the first two
and last two operation processing times. In general at stage i,
i
t ' j1   t jk
i
and
k пЂЅ1
Production Scheduling
t ' j 2   t j, m  k  1
k пЂЅ1
23
P.C. Chang, IEM, YZU.
Ex.
j
tj1
tj2
1
6
8
2
4
1
3
3
9
4
9
5
5
5
6
tj3
2
1
5
8
6
Palmer: s j пЂЅ пЂЁ m пЂ­ 1 пЂ©t j 3 пЂ­ пЂЁ m пЂ­ 1 пЂ©t j 1 пЂЅ 2 t j 3 пЂ­ 2 t j 1
s1 пЂЅ пЂ­ 8
s2 пЂЅ пЂ­6
пЃњ 3 пЂ­ 5 пЂ­ 4 пЂ­ 2 пЂ­1
Gupta:
s1 пЂЅ пЂ­
1
s2 пЂЅ пЂ­
1
s3 пЂЅ 4
s4 пЂЅ пЂ­2
s5 пЂЅ 2
M пЂЅ 37
s3 пЂЅ
1
s4 пЂЅ пЂ­
10
2
12
пЃњ 5 пЂ­ 3 пЂ­ 4 пЂ­ 1 пЂ­ 2 M пЂЅ 36
1
13
s5 пЂЅ
1
11
CDS: 3-5-4-1-2 M=35
Production Scheduling
24
P.C. Chang, IEM, YZU.
HW.
j
tj1
tj2
1
8
3
2
11
2
3
7
5
4
6
7
5
9
11
tj3
6
5
7
13 10
Let пЃі пЂЅ {1,3}
1. Use Ignall-Schrage & McMahon-Burton
to solve b1 , b2 , b3 , b4 , b5 of P132 xxx , P312 xxx
2. Use Palmer, Gupta, CDS to solve this
problem.
Production Scheduling
25
P.C. Chang, IEM, YZU.
Документ
Категория
Презентации
Просмотров
9
Размер файла
284 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа