162 ◾ Vehicle Scheduling in Port Automation
eorientation of the articial-basic arc depends on the amount of supply/demand
of the node. For the node j, if j is a job-output node we include (j, 0) in T
t
. If j is a
job-input node, we include arc (0, j) in T
t
.
After deleting the node 3, the node 4 in Figure7.6 must be deleted. e spanning
tree after removing node 4 and the reconstruction operation is shown in Figure7.7.
After these operations the solution paths are 1→5→6→11 and 2→7→8→11.
According to Property 7.1, the sets of nodes in the graph at time t are as follows:
FN
t
=
1, 2, 5, 6, 7, 8, 11
{ }
DN
t
=
9, 10, 3, 4
{ }
According to Property 7.2, the sets of arcs in the graph are as follows:
T
t
= 1,0
( )
, 6,11
( )
, 1,7
( )
, 7,8
( )
, 2,0
( )
, 0,5
( )
, 6,0
( )
{ }
L
t
=
2,5
( )
, 1,11
( )
, 2,11
( )
, 4,7
( )
, 4,11
( )
, 6,7
( )
,
5,6
( )
, 8,3
( )
, 8,5
( )
, 0,7
( )
, 8,0
( )
, 0,11
( )
⎧
⎨
⎪
⎩
⎪
⎫
⎬
⎪
⎭
⎪
Nil
Nil
Nil
Nil
Root
0
1
7
4 6
8
5
2
Basic arc
Right sibling
Left sibling
Child
Nil
Nil
Nil
Nil
Nil
Nil
11
Nil
Nil
T1: e first
part of the
broken
spanning tree
T2: e second
part of the broken
spanning tree
T3: e third
part of the
broken spanning
tree
Figure 7.6 New spanning tree after removing node 3 (see Figure 7.1).
Dynamic Network Simplex ◾ 163
U
t
= 1,5
( )
, 2,7
( )
, 8,11
( )
{ }
D
t
=
1,9
( )
, 9,10
( )
, 2,9
( )
, 10,3
( )
, 10,5
( )
, 10,7
( )
, 10,11
( )
, 4,9
( )
, 6,9
( )
, 8,9
( )
,
0,9
( )
, 10,0
( )
, 1,3
( )
, 3,4
( )
, 4,5
( )
, 6,3
( )
, 0,3
( )
, 4,0
( )
, 2,3
( )
⎧
⎨
⎪
⎩
⎪
⎫
⎬
⎪
⎭
⎪
Step 02: In this step, every new job is inserted into the spanning tree and the solution
paths. At rst, a couple of nodes associated with a new job (from the INSERTION
set) are selected and transferred into the L
t
set. en, a procedure called insert node
algorithm is used to insert the nodes into the spanning tree. After that, the new job
associated with the nodes is assigned to a vehicle randomly. is job is inserted into
a solution path. Based on the insertion, some arcs may be transferred into the set
L
t
or U
t
. is process is repeated for each new job.
Figure7.8 shows the operations of the insert node algorithm. e input of the
algorithm is a node, which is appended to the new spanning tree by an articial
arc. e attributes of these arcs is the same as the articial arcs in the basic feasible
solution (see Step 0 in Figure5.2). First, the most right sibling of the root’s child
is found and the new node is put at the right side of the existing children of the
root. ese operations are performed in Lines 3–5. en in Line 6, the basic-arc,
predecessor, child, right sibling, left sibling, and size of the sub-tree of this node are
adjusted.
Nil
Nil
Nil
Nil
Root
0
1
7
6 2
8
1
5
Basic arc
Right sibling
Left sibling
Child
Nil
Nil
Nil
Nil
Nil
Nil
Nil
Figure 7.7 New spanning tree after removing node 4 (see Figure 7.6).
164 ◾ Vehicle Scheduling in Port Automation
Example 7.3:
Suppose that node 9 and 10 have to be inserted into the spanning tree of Figure7.1.
e spanning tree after the insertion is demonstrated by Figure7.9. According to
the algorithm in Figure7.8, the articial arcs connect the nodes to the spanning
tree. In this example, we assumed that the new job is inserted in the second path
for AGV 2.
1: Procedure Insert-Node-Algorithm (Node)
2: Begin
3: Find the Child of the root.
4: Find the most Right sibling of the Child.
5: Set the node as a new Child for the Root by an Articial arc.
6: Set Basic-arc, Predecessor, Child, Right-sibling, Left-sibling and Sub-tree’s
size for this node and the root.
7: End Procedure.
Figure 7.8 Pseudocode of inserting a node into the spanning tree in the dynamic
network simplex algorithm.
Nil
Nil
Child
0
1
3
4
5
26
7
Nil
Nil
8
Basic arc
Left sibling
Nil
Nil
Nil
Nil
Nil
Nil
Nil
Nil
Nil
NilNil
9 10
11
Nil
Right sibling
Root
Inserting nodes 9
and 10 into the
spanning tree
Nil
Figure 7.9 New spanning tree after inserting node 9 and 10 (see Figure 7.1).
Dynamic Network Simplex ◾ 165
After these operations the solution paths are 1→3→4→5→6→11 and
2→7→8→9→10→11. Now, the sets of nodes in the graph at time t are as
follows:
FN
t
=
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
{ }
DN
t
=
{}
According to Property 7.2, the sets of arcs in the current graph are as follows:
T
t
=
1,0
( )
, 1,3
( )
, 3, 4
( )
, 4,5
( )
, 6,3
( )
, 6,11
( )
,
2,3
( )
, 1,7
( )
, 7,8
( )
, 0,9
( )
, 10,0
( )
⎧
⎨
⎪
⎩
⎪
⎫
⎬
⎪
⎭
⎪
L
t
=
1,5
( )
, 2,5
( )
, 1,11
( )
, 2,11
( )
, 4,7
( )
, 4,11
( )
, 5,6
( )
, 2,0
( )
, 0,3
( )
, 4,0
( )
,
0,5
( )
, 6,0
( )
, 10,3
( )
, 10,5
( )
, 10,7
( )
, 0,7
( )
, 6,7
( )
, 7,8
( )
, 8,11
( )
,
8,0
( )
, 8,3
( )
, 8,5
( )
, 1,9
( )
, 2,9
( )
, 4,9
( )
, 6,9
( )
⎧
⎨
⎪
⎪
⎩
⎪
⎪
⎫
⎬
⎪
⎪
⎭
⎪
⎪
U
t
= 2,7
( )
, 8,9
( )
, 9,10
( )
, 10, 11
( )
{ }
D
t
=
{}
7.4 Software Architecture for Dynamic Aspect
At the start of the process, a few jobs are generated for each crane and the memory
for the jobs and graph are allocated. en, the MCF-AGV model is made and
tackled by the NSA+. e output of this algorithm is a few job sequences for the
vehicles. Based on these sequences, the software will prepare a job list for each
vehicle.
e main architecture of the software is demonstrated in Figure 7.10 for
dynamic aspect. Note that this architecture is for the time when s>0 (see the
algorithm in Figure7.2).
While the time is being progressed, the vehicles and cranes are carrying and
handling the containers. From time to time, the software makes a few random
changes in the distance table (see Table4.1) in order to produce dynamic problems.
e job generator has to generate a few new jobs, when it nds out any crane is in
idle state.
As we see in the gure, every event is recorded in order to be processed later.
e events include modication of the vehicle’s position, the fullled jobs and new
jobs, and any change in the distance table. As we mentioned (see Section 7.3.2), a
hole will be created in the job buer when a job is fullled. After the job generator
166 ◾ Vehicle Scheduling in Port Automation
generates a job, it puts the job into a hole of the buer. e software marks the
nodes and arcs associated with the fullled and new jobs. e most important events
that aect the spanning tree are the fullled and new jobs. e fullled jobs are
removed from the list of vehicles and model, whereas the new jobs are appended to
remaining jobs and inserted into the model. Note that any change in the problem,
without any fullled or new job, does not aect the spanning tree. In this case, only
the body of the algorithm is executed and nds out the optimal solution.
e software processes the recorded events and updates the MCF-AGV model.
After removing the nodes and arcs (associated with the fullled jobs) from the
model and omitting the jobs from the vehicle’s lists, a new spanning tree is made.
Next, the nodes and arcs associated with the new jobs are put into the new model
and then the spanning tree is repaired. ese jobs are assigned to one or more
vehicles, randomly. ese two tasks are made by reconstruct new BFS. After repair-
ing the spanning tree, the main body of the algorithm is executed and it nds out
the optimal solution. Note that these tasks are not preemptive; that is, when a task
starts execution on the processor, it nishes to its completion.
Execute main body of the algorithm
(solve the MCF-AGV model and
generate new schedule based on the
solution)
List for
vehicle
1
List for
vehicle
2
List for
vehicle
M
While the time is
being progressed.
List for
vehicle
m
Generate jobs for
any idle crane
Find a hole in the
buffer and put the
job into the hole
Delete a fulfilled
job
Delete the job from the list
of vehicle and mark the
associated arcs and nodes
for deleting
Mark the job and associated
arcs and nodes with it for
inserting
Update the MCF-AGV
model in the memory
Reconstruct new BFS (repair the
basic feasible solution based on
the DELETION nodes and
INSERTION nodes associated with
the fulfilled and new jobs)
(a) Update status of each
vehicle; (b) make a few
random changes in the
distance table, from
time to time
Make a hole in the
buffer and mark the
job for deleting
Figure 7.10 Block diagram of the software and algorithm (DNSA+) in the
dynamic aspect.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.