Information Technology Reference
In-Depth Information
Step 1
Select new job.
min
;
j
∗
= 3
min =
c
34
but 4 is already considered. Hence,
j
∗
= 3.
j
∈
S
a
{
c
34
,
c
54
,
c
43
,
c
45
}
= min
{
1
,
2
,
5
,
3
}
Step 2
Insert job 3
There are the following possibilities from
{
1
,
2
,
4
}
:
{
1
,
2
,
4
,
3
}
:
c
43
+
c
31
−
c
41
= 5 + 12
−
12 = 5
{
1
,
2
,
3
,
4
}
:
c
23
+
c
34
−
c
24
= 15 + 1
−
11 = 5
{
1
,
3
,
2
,
4
}
:
c
13
+
c
32
−
c
12
= 14 + 17
−
8 = 25
{
1
,
2
,
4
,
3
}
Choosing
breaks the tie. Updating
r
[5]=3
Step 1
Select new job.
Since job 5 remains,
j
∗
= 5
Step 2
Insert job 5
There are the following possibilities from
{
1
,
2
,
4
,
3
}
{
1
,
2
,
4
,
3
,
5
}
:
c
35
+
c
51
−
c
31
= 3 + 13
−
12 = 4
{
1
,
2
,
3
,
4
,
3
}
:
c
45
+
c
53
−
c
43
= 3 + 15
−
5 = 13
{
1
,
3
,
2
,
4
,
3
}
:
c
25
+
c
54
−
c
24
= 13 + 2
−
11 = 4
{
1
,
5
,
2
,
4
,
3
}
:
c
15
+
c
52
−
c
12
= 12 + 18
−
8 = 22
Choosing
breaks the tie as the final sequence. The cost =
c
12
+
c
24
+
c
43
+
c
35
= 8 + 11 + 5 + 3 = 27
{
1
,
2
,
4
,
3
,
5
}
The TSP construction is shown in Fig 2.3. The meaning of this solution is that batch
1
is first produced, followed by batch
2
, then batch
4
, then batch
3
, and finally batch
5
.
4
5
3
3
5
11
8
1
2
Fig. 2.3.
TSP solution for Example 2.1
Search WWH ::
Custom Search