Download PDF
ads:
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ads:
60 100 150
S
F 1=1/pos(i) F 2(i)=−(pos(i)/n)+1
15000
20
15000
60
15000
100
15000
150
60 100 150
GP
PRF
AP I
P
U
R
• p
im
m i
• r
i
i
• d
i
i
•
˜
d
i
i
˜
d
i
• ν
i
i
•
C
max
Z
C
j
j
¯
F =
n
j=1
F
j
F
j
= C
j
− r
j
F
j
j
L
max
= max{L
j
} L
j
= C
j
− d
j
j
lb lb ≥ f(x
)
x
∗
•
•
•
• x
1
x
2
x
2
x
1
•
•
α|β|γ
R|s
ijm
|C
max
+
T
i
· v
i
Job List ← rule
← iterations
Local Solution ← Sort List
Local Solution ← Local Solution
Local Solution < Best Solution
Best Solution ← Local Solution
LB[i]=d
i
− max
m
{p
im
}
Solution ←∅
Rnd list ← Job list
Local Solution
(i) Rnd list
Local Solution ← Local Solution ∪{i}
Local Solution
F 1(i)=1/pos(i) pos(i)
F 2(i)=−(pos(i)/n)+1
O(n
2
)
•
•
•
• x
1
x
2
x
2
x
1
•
•
F 2
F 1=1/pos(i) F 2(i)=−(pos(i)/n)+1
F 1
F 1
F 1
F 2
F 1
F 1
F 2
F 1
F 2
F 1
F 2
F 2
F 1
F 2
F 2
F 2
•
•
•
150
PD =
X − LB
LB
X
1.00 15, 000
15000
20
15000
60
15000
100
15000
150
60, 100
150
F 2
60 100 150
2.5
3
3.5
4
4.5
5
20 40 60 80 100 120 140 160
APD
Number of Jobs
GP
GP-LB
GPS
GPS-LB
GP-C2
GP-LB-C2
F 1
60 100 150
150
1.00
300, 000 2, 500
150 15, 000
2000 100
1000
1100
1200
1300
1400
1500
1600
1700
1800
1900
0 2 4 6 8 10
Obj. Function
Seeds
GP
GP-LB
GPS
GPS-LB
GP-F2
GP 50000 6
1, 2000, 5000 10000, 15000 20000
GP
• M 6
• M 321
• M 3111
• M 222
• M 2211
• M 21111
150
1.00 15, 000
M = {1, 2, .., m} J = {1, 2, .., n}
p
jk
w
j
j ∈ J
k ∈ M
j j
s
jj
k
j ≺ j
k ∈ M
j C
j
= C
j
+ p
jk
+ s
j
jk
C
j
j j
ρ
j
ρ
j
= max((C
j
− d
j
), 0) d
j
j
C
max
+
n
j=1
ν
j
.ρ
j
J
k
k
I
k
⊆ 2
J
2
J
J
J
k
∩ J
k
= ∅∀k ∈ M,k = k
k∈M
J
k
= J
F S = {J
1
,J
2
, .., J
m
}∈F
S ∈ F N
l
(S) ⊆ F S
N
1
(S) N
2
(S) N
3
(S)
N
1
(S) O(m.n
2
) N
2
(S) O(m
2
.n
2
)
N
3
(S) O(m.n
2
)
←
←
←
∈ N
l
(S)
← N
l
(S
)
<
←
←
←
O(n
3
.m)
j
←
k
j k p
<
MKS ← MKS
k p
N
l
N
1
(S)
k ∈ M
j
1
k
j
2
j
1
= j
2
j
1
j
2
<
j
1
j
2
• k
• j
1
j
2
k
• j
1
j
2
N
2
(S)
• k, k
• j
1
k j
2
k
• j
1
j
2
N
3
(S)
• j
1
k
j
1
k
• k
• j
1
k
O(m.n
2
)
O(m
2
.n
2
)
k ∈ M
j
1
k
k
∈ M,k = k
j
2
∈ k
j
1
j
2
<
j
1
j
2
k
k
k = k
j k
k
j k k
<
j k k
O(n
2
)
=1
0
50
100
150
200
250
300
0
20 40 60 80 100 120 140 160
Solution
Jobs
GRASP with local search 1
GRASP with local search 2
GRASP with local search 3
VNS
0
1000
2000
3000
4000
5000
6000
7000
8000
9000
10000
0
20 40 60 80 100 120 140 160
Solution
Jobs
GRASP with local search 1
GRASP with local search 2
GRASP with local search 3
VNS
0
1000
2000
3000
4000
5000
6000
7000
8000
0 20 40 60 80 100 120 140 160
Solution
Jobs
GRASP with local search 1
GRASP with local search 2
GRASP with local search 3
VNS
0
20
40
60
80
100
120
140
0 20 40 60 80 100 120 140 160
Time [sec]
Jobs
GRASP with local search 1
GRASP with local search 2
GRASP with local search 3
VNS
2
4
6
8
10
12
14
16
18
20
22
0 1 2 3 4 5
APD
Algorithm
Confidence Intervals for 150 job instances
GRASP with local search 1
GRASP with local search 2
GRASP with local search 3
VNS
im
ii
m
i
ν
i
ii
m
(i, i
)
g
ii
m
= p
im
+ s
ii
m
C
m
• t
i
i
• α
im
1 i m,
0
• β
ii
m
1 i i
i i
,
0
• ρ
i
i
• Z
Z
m
m
Z
t
E
m
(i, i
)
m
min
Z +
N
i
(ρ
i
· ν
i
)
M
m
α
im
=1, ∀i ∈ N
Z ≥ t
i
+ p
im
− (1 − α
im
) · G, ∀i ∈ N, m ∈ M
d
i
+ ρ
i
≥ t
i
+ p
im
− (1 − α
im
) · G, ∀i ∈ N, m ∈ M
(1 − α
im
) · G +(1− α
i
m
) · G +(1− β
ii
m
) · G + t
i
≥ t
i
+ p
im
+ s
ii
m
, ∀(i, i
) ∈ E
m
,m∈ M
(1 − α
im
) · G +(1− α
i
m
) · G + β
ii
m
· G + t
i
≥ t
i
+ p
i
m
+ s
i
im
, ∀(i, i
) ∈ E
m
,m∈ M
α
im
∈{0, 1}, ∀i ∈ N, m ∈ M
β
ii
m
∈{0, 1}, ∀(i, i
) ∈ E
m
,i
∈ N, m ∈ M
t
i
,ρ
i
≥ 0, ∀i ∈ N
Z ≥ 0
β
ρ
i
• t
(o)
m
o
th
m
• α
(o)
im
1
i m o
th
0
• β
(o)
ii
m
⎧
⎪
⎨
⎪
⎩
1
i i
m o
th
(o +1)
th
0
• ρ
i
i
• Z
min
Z +
N
i
(ρ
i
· ν
i
)
M
m
|N |
o=1
α
(o)
im
=1, ∀i ∈ N
N
i
α
(o)
im
≤ 1, ∀m ∈ M, o =1,...,|N|
N
i
α
(o)
im
≤
N
i
α
(o−1)
im
, ∀m ∈ M, o =2,...,|N |
d
i
+ ρ
i
≥ t
(o)
m
+ p
im
−
1 − α
(o)
im
· G, ∀m ∈ M, ∀i ∈ N,o =1,...,|N|
Z ≥ t
(|N |)
m
+
N
i
α
(|N |)
im
· p
im
, ∀m ∈ M
t
(1)
m
=0, ∀m ∈ M
β
(o−1)
ii
m
≥ 1 −
2 − α
(o−1)
im
− α
(o)
i
m
· G, ∀m ∈ M, ∀i, i
∈ N,o =2,...,|N|
t
(o)
m
≥ t
(o−1)
m
+
N
i
α
(o−1)
im
· p
im
+
N
i
N−{i}
i
β
(o−1)
ii
m
· s
ii
m
, ∀m ∈ M, o =2,...,|N|
α
(o)
im
,β
(o)
ii
m
∈{0, 1}, ∀i ∈ N, i
∈ N, m ∈ M, o =1,...,|N|
ρ
i
≥ 0, ∀i ∈ N
t
(o)
m
≥ 0, ∀m ∈ M, o =2,...,|N|
Z ≥ 0
o − 1 o
o ≥ 2 o
th
m
ρ
i
i i
o − 1 o m i
i
m i o − 1 i
o
α
(o−1)
im
= α
(o)
i
m
=0 β
(o−1)
ii
m
≥ 1−2·G β
(o−1)
ii
m
0 1 β
(o−1)
ii
m
0
node
node
UB ← node
n ∈ node
n <UB
n
UB =
firstNode
UB
bestSol
localSol
iterations 1 bestSol
iterations
jobs ← N
i ← 1, iterations
jobsRand ← jobs
jobsRand
localSol < bestSol
bestSol ← localSol
f(x) ∼ 1/x f(x) x
th
i i
i
1, 1
job ← jobs[i]
m ←
job, m
presentSol <bestSol
i +1
job, m
LB
k
LB
t
LB
k
()M1
()M2
()M1
()M2
(1)M1
()M2
(1,3,5)M1
(2,4)M2
(1)M1
()M2
(1,3,5)M1
(2,4)M2
(1,5)M1:3
(2,4)M2
(1)M1:3>5
(2,4)M2
()M1:3>5>1
(2,4)M2
()M1:3>5>1
(2)M2:4
()M1:3>5>1
()M2:4>2
First Branching.
Each time a job is assigned to a machine, a new node in the
enumeration tree is created.
Second Branching.
The process decides the processing order on each
machine, at a time. On each machine, the first job
to be processed is chosen, then the second, until
there are no more jobs assigned to that machine.
At node Z a feasible solution is completed. All the
jobs are sequenced.
1,
A
B
Z
At node A, no jobs are assigned.
At node B, job one is assigned to machine M1
At node Z, all jobs are assigned to a
machine, but not sequence is considered.
Z
1
•
n u n
LB
kt
• m n
n
m
m LB
ka1
m
LB
k
N
u
N
a
m
m S
a
m
N
a
m
LB
k
=max
LB
kt
|M|
,
M
max
m
LB
ka1
m
LB
kt
=
N
u
i
M
min
m
(p
im
)+
M
m
N
a
m
i
p
im
+ n · u
LB
ka1
m
=
N
a
m
i
(p
im
)+
S
a
m
{ii
m}
(s
ii
m
)
LB
k
n n
LB
k
N
as
m
m N
au
m
m
i, m
bestSol ← presentSol
m
1,m+1
job ← m
job, m,i
presentSol <bestSol
i +1,m
S
as
m
N
as
m
S
au
m
n
N
au
m
N
as
m
n
N
au
m
LB
k
=
M
max
m
LB
ka2
m
LB
ka2
m
=
N
a
m
i
(p
im
)+
S
as
m
{ii
m}
(s
ii
m
)+
S
au
m
{ii
m}
(s
ii
m
)
LB
t
LB
k
LB
tu
LB
ta
m
m
LB
t
= LB
tu
+
M
m
LB
ta
m
LB
tu
=
N
u
i
w
i
· max
M
min
m
(p
im
) − d
i
, 0

LB
ta
m
= LB
ta1
m
+max
LB
ta2
m
,LB
ta3
m
LB
ta1
m
=
N
as
m
i
[w
i
· max (t
i
+ p
im
− d
i
, 0)]
LB
ta2
m
=
N
au
m
i
[w
i
· max (t
i
+ p
im
− d
i
, 0)]
LB
ta3
m
=
N
au
m
min
i
(w
i
) ·
N
a
m
i
max (t

i
+ p
im
− d
i
, 0)
LB
ta1
m
t
i
i
LB
ta2
m
LB
ta3
m
LB
ta2
m
t
i
i LB
ta3
m
m t

i
i
t
i
N
u
LB
tu
LB
tu
LB
U(x, y)
x y
U(5, 200)
U(25, 50)
U(1, 3)
U
,
2·h
q
q 1
h
2·h
q
q
q
q =2
q =3
q =4
q =5
p = U(5, 150)
p = U(5, 100)
s = U (25, 100)
s = U (25, 150)
S
P
S, P
n ← S.rows
k ← 1 n
i ← 1 n
j ← 1 n
s
ij
← min(s
ij
,s
ik
+ p
k
+ s
kj
)
s
ij
≤ s
ik
+ p
k
+ s
kj
k
i j k
10
−2
10
−1
10
0
10
1
10
2
10
3
10
4
12 11 10 9 8 7 6 5 4
Execution time (s)
Number of jobs
Manne’s
Wagner’s
B&B
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
n
n +1
10
−2
10
−1
10
0
10
1
10
2
10
3
10
4
10
5
10
6
10
7
30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
Branched nodes x1000
Number of jobs
q = 1
q = 2
q = 3
q = 4
q = 5
q =1 q =2 q =3 q =4 q =5
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ± ±
± ± ± ±
± ± ±
± ± ±
± ± ±
10
−2
10
−1
10
0
10
1
10
2
10
3
10
4
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
Branched nodes x1000
Number of jobs
Small (class G)
Medium (class F)
Large (class A)
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
10
−2
10
−1
10
0
10
1
10
2
10
3
10
4
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6
Branched nodes x1000
Number of jobs
Small (class A)
Medium (class H)
Large (class I)
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
± ± ±
−
−
9.8 −2.31
T T
t t t +1
T
p
im
s
ii
m
τ
ii
m
τ
ii
m
= p
im
+ s
ii
m
i
ν
i
x
t
im
x
t
im
i m t x
t
im
C
i
i
Z
ρ
i
i
MinZ +
N
i=1
ν
i
ρ
i
M
m=1
T −p
im
t=1
x
t
im
=1 ∀i
x
t
im
+
t+τ
ijm
s=t+1
x
s
jm
≤ 1 ∀i∀t(t ≤ T − p
im
)∀m∀j(i = j)
C
i
≥
M
m=1
T −p
im
t=1
(t + p
im
).x
t
im
∀i
ρ
i
≥ C
i
− d
i
∀i
Z ≥ C
i
∀i
ρ
i
≥ 0 ∀i
C
i
≥ 0 ∀i
Z ≥ 0
x
t
im
∈{0, 1}∀i∀t∀m
τ
x
t
im
i m t
Min
N
i=1
ν
i
ρ
i
M
m=1
T −p
im
t=1
x
t
im
=1 ∀i
x
t
im
+
t+τ
ijm
s=t+1
x
s
jm
≤ 1 ∀i, ∀t(t ≤ T − p
im
), ∀m, ∀j(i = j)
ρ
i
≥
M
m=1
T −p
im
t=1
(t + p
im
).x
t
im
− d
i
∀i
ρ
i
≥ 0 ∀i
x
t
im
∈{0, 1}∀i, ∀t, ∀m
P
(P ) z = min
x
{c
x : Ax ≤ b, Bx ≤ c, x ∈ R
n
}
b, c ∈ R
n
A ∈ R
m
1
,n
B ∈ R
m
2
,n
Ax ≤ b P
λ
λ
(P
λ
) z
(λ)=min
x
{c
x + λ
(Ax − b):Bx ≤ c, x ∈ R
n
}
λ ∈ R
m
1
+
P
λ
P z
(λ) ≤ z
P
λ
D
(D) d = max
λ
{z
(λ):λ ∈ R
m
1
+
}
z
(λ) ≤ z ∀λ ∈ R
m
1
+
D P d ≤ z
λ
t
ijm
≥ 0 ∀i ∀j(i = i) ∀t(t ≤ T −p
im
)
∀m
P (λ)= Min
N
i=1
ν
i
ρ
i
+
N
i=1
N
j=1,(i=j)
M
m=1
T −p
im
t=1
λ
t
ijm
x
t
im
+
t+τ
ijm
s=t+1
x
s
jm
− 1
M
m=1
T −p
im
t=1
x
t
im
=1 ∀i
ρ
i
≥
M
m=1
T −p
im
t=1
(t + p
im
).x
t
im
− d
i
∀i
ρ
i
≥ 0 ∀i
x
t
im
∈{0, 1}∀i, ∀t, ∀m
x
t
im
=1, ∀i, ∀t, ∀m
x
t
im
β
β
t
im
= ν
i
(max (0,t+ p
im
− d
i
)) +
N
j=1,(i=j)
⎛
⎝
λ
t
ijm
+
t
s=t−τ
jim
λ
s
jim
⎞
⎠
β P
(β)
m t
P
(β)= Min
N
i=1
M
m=1
T −p
im
t=1
x
t
im
· β
t
im
M
m=1
T −p
im
t=1
x
t
im
=1 ∀i
x
t
im
∈{0, 1}∀i, ∀t, ∀m
λ
λ P (λ)
max
λ
{P (λ):λ
t
ijm
≥ 0, ∀i, ∀j, ∀t, ∀m}
P (λ)
Lower Bound()
π θ ← (2,LB best, 1.05)
UB ←
λ ← 0
M
π ≤ 0.0001
β ← λ
Inspect Solution ← β
LB ← Inspect Solution
LB > LB best
LB best ← LB
non imp ← 0
non imp = non imp +1
non imp = 300
π ← π/2
non imp =0
SG ← Inspect Solution
Step ← π · (θ · UB − LB)/||SG
i
||
2
λ
t
ijm
λ
t
ijm
← max(0,λ
t
ijm
+ Step · SG
t
ijm
)
LB best
λ
β π(λ)
π
SG
SG
n
m
m>3
• x
ij
1
i j ,
0
• w
jm
m j − th
• y
jm
j − th m m +1
• Z
min Z
|N |
j=1
x
ij
=1, ∀i ∈ N
|N |
i=1
x
ij
=1, ∀j ∈ N
|N |
i=1
p
im
.x
ij+1
+ y
j+1m
+ w
j+1m
= y
jk
+
|N |
i=1
p
im+1
.x
ij
+ w
j+1m+1
,
∀m =1...|M|−1, ∀j =1...|N|−1
|N |
j=1
|N |
i=1
p
im
.x
ij+1
+
|N |
j=1
x
jm
= Z,
k−1
m=1
|N |
i=1
p
im
.x
i1
= w
1k
∀k, k =2,...,|M|−1
y
1k
=0,k=1,...,|M|−1
x
ij
∈ (0, 1), ∀i, j ∈ N
w
jk
≥ 0, ∀i ∈ N∀k ∈ M
y
ik
≥ 0, ∀i ∈ N∀k ∈ M
Z ≥ 0
i =3 n
i i
p
T
> 0
n m p
ij
i j T
T =0.5 ·
n
i=1
m
j=1
p
ij
n · m · 10
.
n
Guiding S
ol
2
5
7
1
3
4
6
Initial Sol
R
and
2
5
7
1
3
4
66
4
3
5
1
7
2
2
5
3
4
6
1
7
2
5
1
3
7
4
6
2
3
7
1
5
4
66
4
5
7
1
3
2
S
S
2
7
1
3
5
4
6
Solution CurrSol BestSolution
PoolSolution
JobSorted
NonImproves
CurrSol
PRF PRF
BestSolution
PoolSolution
SolPR
NImp
Rand
2571346
2713546
P1
P2
2
2
5
5
7
7
1
1
3
3
4
4
6
6
O1
O2
X
S
2
2
2
2
5
5
5
5
3
3
3
3
7
7
7
7
1
1
1
1
4
4
4
4
6
6
6
6
P1
P3
O3
O4
6
6
6
64
4
4
4
2
2
2
2
1
1
1
1
5
5
5
5
3
3
3
3
7
7
7
7
P3
P4
O5
O6
X
S
Return the Best Offspring
2 5461
237 5461
O2
O3
73
S
X
= O
6
S
PRF
PRF
PRF PRF =0
AP I
AP I
AP I R X
UB
AP I =
1
R
R
i=1
X − UB
UB
· 100
PRF =2
PRF
· PRF =2 PRF =5 PRF =10 PRF =20
50 · 20
100 · 20
200 · 20
AP I
AP I
· AP I AP I
·
1.8
1.9
2
2.1
2.2
2.3
2.4
2.5
2.6
0/1005/9520/8050/5080/2095/5100/0
Average percentage increase over best known solution
% time GRASP-ILS / % time MA
0
0.2
0.4
0.6
0.8
1
1 10 100 1000 10000 100000
cumulative probability
time to target solution (2.5%)
Exponencial distribution comparison
Hybrid A
Hybrid B
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
JobSorted ←
Solution ← NEH(JobsSorted)
PoolInsertion(Solution)
Solution ← LSInsertion(Solution)
PoolInsertion(Solution, Proximity)
CurrSol ← BestSolution
NonImproves ← 0
i ← 1,...,MaxIterations
Solution ← Perturbation(CurrSol)
Solution ← LSInsertion(Solution)
PoolInsertion(Solution, Proximity)
i mod PRF =0
SolPR ← PathRelinking(BestSolution, PoolSolution)
PoolInsertion(SolPR, Proximity)
CurrSol > SolPR
CurrSol ← SolPR
RND(0, 1) < exp(−SolPR − CurrSol)/T
CurrSol ← SolPR
CurrSol > Solution
CurrSol ← Solution
RND(0, 1) < exp(−Solution − CurrSol)/T
CurrSol ← Solution
BestSolution
NonImproves ← 0
NonImproves ← NonImproves +1
NonImproves = NImp
RestartPOOL()
m
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo