Nof S.Y. Springer Handbook of Automation
Подождите немного. Документ загружается.
Evolutionary Techniques for Automation 29.3 AGV Dispatching in Manufacturing System 495
T
11
T
12
T
13
s
T
21
T
22
t
T
31
T
32
T
33
T
14
147
s
25
t
368
9
Job J
1
: T
11
→ T
12
→ T
13
→ T
14
Job J
2
: T
21
→ T
22
Job J
3
: T
31
→ T
32
→ T
33
Fig. 29.3 Illustration of the network structure of the example
transition task for operation o
ij
, t
ij
: transition time from
M
i, j−1
to M
ij
. Decision variables: x
ij
: assigned AGV
number for task T
ij
, t
S
ij
: starting time of task T
ij
, c
S
ij
:
starting time of operation o
ij
.
The objective functions are to minimize the time re-
quired to complete all jobs (i.e., the makespan) t
MS
and
the number of AGVs n
AGV
, and the problem can be
formulated as follows:
min t
MS
=max
i
.
t
S
i,n
i
+t
M
i,n
i
,0
/
,
(29.1)
min n
AGV
=max
i, j
x
ij
,
(29.2)
s.t. c
S
ij
−c
S
i, j−1
≥ p
i, j−1
+t
ij
, ∀i, j =2,...,n
i
,
(29.3)
c
S
ij
−c
S
i
j
− p
i
j
+Γ
M
ij
−M
i
j
≥0
∨
c
S
i
j
−c
S
ij
− p
ij
+Γ
M
ij
−M
i
j
≥0
,
∀(i, j), (i
, j
) , (29.4)
t
S
ij
−t
S
i
j
−t
i
j
+Γ
x
ij
−x
i
j
≥0
∨
t
S
i
j
−t
S
ij
−t
ij
+Γ
x
ij
−x
i
j
≥0
,
∀(i, j), (i
, j
) , (29.5)
t
S
i,n
i
−t
S
i
j
−t
i
j
+Γ
x
ij
−x
i
j
≥0
∨
t
S
i
j
−t
S
i,n
i
−t
i
+Γ
x
ij
−x
i
j
≥0
,
∀(i, n
i
), (i
, j
) , (29.6)
c
S
ij
≥t
S
i, j+1
− p
ij
, (29.7)
x
ij
≥0 , ∀i, j , (29.8)
t
S
ij
≥0 , ∀i, j , (29.9)
where Γ is a very large number, and t
i
is the transi-
tion time from the pickup point of machine M
in
to the
delivery point of loading/unloading. Constraint (29.3)
describes the operation precedence constraints. In
(29.4)–(29.6), since one or the other constraint must
hold, it is called disjunctive constraint. This represents
the operation nonoverlapping constraint (29.4)andthe
AGV nonoverlapping constraint (29.5, 29.6).
29.3.2 Evolutionary Approach:
Priority-Based GA
For solving the AGV dispatching problem in FMS,the
special difficultyarises from(1) thatthe tasksequencing
is NP-hard problem, and (2) that a random sequence of
AGV dispatching usually does not satisfy the operation
precedence constraint and routing constraint.
Firstly, we give a priority-based encoding method
that is an indirect approach, encoding some guiding in-
formation to construct a sequence of all tasks. As is
known, a gene in a chromosome is characterized by two
factors: the locus, i.e., the position of the gene within
the structure of the chromosome, and the allele, i.e., the
value the gene takes. In this encoding method, the posi-
tion of a gene is used to represent the ID which mapping
thetaskinFig.29.3 and its value is used to represent the
priority of the task for constructing a sequence among
candidates. A feasible sequence can be uniquely de-
termined from this encoding with consideration of the
operation precedence constraint. An example of a gen-
Priority : 157268394
123456789Task ID :
T
11
→ T
12
→ T
13
→ T
14
→ T
21
→ T
22
→ T
31
→ T
32
→ T
33
Fig. 29.4 Example generated chromosome and its de-
coded task sequence
Part C 29.3
496 Part C Automation Design: Theory, Elements, and Methods
t
MS
= 574
M
1
Time t
Machine
O
11
O
22
O
63
O
10,2
O
13
O
71
O
93
M
2
O
21
O
12
O
44
O
43
O
64
O
52
M
3
O
33
O
10,3
O
42
O
32
O
72
M
4
O
61
O
62
O
51
O
82
O
92
O
84
M
5
O
31
O
41
O
10,1
O
81
O
91
O
83
AGV1 : T
11
→ T
12
→ T
41
→ T
81
→ T
91
→ T
82
→ T
92
→ T
83
→ T
84
,
AGV2 : T
21
→ T
41
→ T
12
→ T
15
→ T
10.2
→ T
52
→ T
71
→ T
44
,
AGV3 : T
61
→ T
62
→ T
63
→ T
64
→ T
43
→ T
72
,
AGV4 : T
31
→ T
32
→ T
10.1
→ T
33
→ T
13
→ T
10.3
→ T
93
.
Fig. 29.5 Gantt chart of the schedule of the case study considering AGVs routing (after [29.1], by permission of
Macmillan Nature 2004)
erated chromosome and its decoded path is shown in
Fig.29.4 for the network structure of Fig.29.3.
After generating the task sequence, we separate
tasks into several groups for assigning different AGVs.
We find the breakpoints, which the tasks are the final
transport of job i from pickup point of operation O
in
to delivery point of loading/unloading. Then we sepa-
rate the part of tasks sequence by the breakpoints. An
example of grouping is shown as follows, using the
chromosome (Fig.29.4):
AGV1: T
11
→ T
12
→ T
13
→ T
14
AGV2: T
21
→ T
22
AGV3: T
31
→ T
32
→ T
33
.
As geneticoperators, we combine a weight mapping
crossover (WMX), insertion mutation, and immigration
operator based on the characteristic of this representa-
tion, and adopt an interactive adaptive-weight fitness
assignment mechanism that assigns weights to each
objective and combines the weighted objectives into
a single objective function. The detailed procedures are
showed in [29.38].
29.3.3 Case Study
For evaluating the efficiency of the AGV dispatching
algorithm suggested in the case study, a simulation
program was developedusing Java ona PentiumIV pro-
cessor (3.2GHz clock). The detailed test data is given
by Yang [29.42]andKim et al. [29.43]. GA parameter
settings were taken as follows: population size, pop-
Size= 20; crossover probability, p
C
= 0.70; mutation
probability, p
M
=0.50; immigration rate, μ = 0.15. In
an FMS case study, ten jobs are to be scheduled on
five machines. The maximum number of processes for
the operations is four. The detailed date sets are shown
in [29.44].
We can draw a network depended on the prece-
dence constraints among tasks {T
ij
} of the case study.
The best result is shown in Fig. 29.5. The final time re-
quired to complete all jobs (i.e., the makespan) is 574,
and four AGVs are used. Figure 29.5 shows the result on
a Gantt chart. As discussed above, the AGV dispatching
problem is a difficult problem to solve by conventional
heuristics. Adaptability,robustness,and flexibility make
EA very effective for such automation problems.
Part C 29.3
Evolutionary Techniques for Automation 29.4 Robot-Based Assembly-Line System 497
29.4 Robot-Based Assembly-Line System
Assembly lines are flow-oriented production systems
which are still typical in the industrial production of
high-quantity standardized commodities and are even
gaining importance in low-volume production of cus-
tomized products. Usually, specific tooling is developed
to perform the activities needed at each station. Such
tooling is attached to the robot at the station. In order to
avoid the wasted time required for tool change, the de-
sign of the tooling can take place only after the line has
been balanced. Different robot types may exist at the
assembly facility. Each robot type may have different
capabilities and efficiencies for various elements of the
assembly tasks. Hence, allocating the most appropriate
robot for each station is critical for the performance of
robotic assembly lines.
29.4.1 Assembly-Line Balancing Problems
This problem concerns how to assign the tasks to sta-
tions and how to allocate the available robots for each
station in order to minimize cycle time under the con-
straint of precedence relationships. Let us consider
a simple example to describe the problem, in which
ten tasks are to be assigned to four workstations, and
7
46
5
1
3
2
8
10
9
Fig. 29.6 Precedence graph of the example problem
Table 29.2 Data for the example
i Suc(i) R
1
R
2
R
3
R
4
1 4 17 22 19 13
2 4 21 22 16 20
3 5 12 25 27 15
4 6 29 21 19 16
5 10 31 25 26 22
6 8 28 18 20 21
7 8 42 28 23 34
8 10 27 33 40 25
9 10 19 13 17 34
10 – 26 27 35 26
8910
164
35
27
50 85
stn/rbn
Time
4/4
3/3
2/1
1/2
Fig. 29.7 The feasible solution for the example (stn –
workstation number, rbn – robot number)
four robots are to be equipped on the four stations. Fig-
ure 29.6 shows the precedence constraints for the ten
tasks, and Table 29.2 gives the processing time for each
of thetasks processed by each robot. We show a feasible
solution for this example in Fig.29.7.
The balancing chart for the solution can be drawn
to analyze the solution. Figure 29.7 shows that the idle
time of stations 1–3 is very large, which means that this
line is not balanced for production. In the real world, an
assembly line is not just used for producing one unit of
the product; it should produce several units. So we give
the Gantt chart for three units to analyze the solution, as
showninFig.29.8.
29.4.2 Robot-Based Assembly-Line Model
The following assumptions are stated to clarify the set-
ting in which the problem arises:
1. The precedence relationship among assembly activ-
ities is known and invariable.
2. The duration of an activity is deterministic. Activi-
ties cannot be subdivided.
27
35
146
8910
50 100 150 200 250 300
Part waiting
Processing waiting
350 400
stn/rbn (case of 3 products)
Time
1/2
2/1
3/3
4/4
Fig. 29.8 Gantt chart for producing three units
Part C 29.4
498 Part C Automation Design: Theory, Elements, and Methods
3. The duration of an activity depends on the assigned
robot.
4. There are no limitations on the assignment of an ac-
tivities or a robot to any station. If a task cannot be
processed on a robot, the assembly time of the task
on the robot is set to a very large number.
5. A single robot is assigned to each station.
6. Material handling, loading, and unloading times, as
well as setup and tool changing times are negligible,
or are included in the activity times. This assump-
tion is realistic on a single model assembly line that
works on the single product for which it is balanced.
Tooling on such a robotic line is usually designed
such that tool changes are minimized within a sta-
tion. If tool change or other type of setup activity
is necessary, it can be included in the activity time,
since the transfer lot size on such line is of a single
product.
7. The number of workstations is determined by the
number of robots, since the problem aims to maxi-
mize the productivity by using all robots at hand.
8. The line is balanced for a single product.
The notation used in this section can be sum-
marized as follows. Indices: i, j: index of assembly
tasks, i, j = 1, 2,...,n; k: index of workstations,
k =1, 2,...,m; l: index of robots, l = 1, 2,...,m. Par-
ameters: n: total number of assembly tasks, m:total
number of workstations (robots), t
il
: processing time of
the i-th task by robot l, pre(i): the set of predecessor of
task i in the precedence diagram. Decision variables
x
jk
=
⎧
⎨
⎩
1iftaskj is assigned to workstation k
0 otherwise ,
y
kl
=
⎧
⎨
⎩
1 if robot l is allocated to workstation k
0 otherwise .
Task sequence (υ
1
)Phase 1: 2
1
1
2
3
3
4
4
9
5
6
6
5
7
7
8
8
9
10
10Locus
Robot assignment (υ
2
)Phase 2: 1
1
2
2
3
3
4
4Locus: station
S
1
S
1
123
S
2
S
2
946
S
3
S
3
57
S
4
S
4
810
Fig. 29.9 Solution representation of a sample problem
Problem formulation
min C
T
= max
1≤k≤m
0
n
i=1
m
l=1
t
il
x
ik
y
kl
1
,
(29.10)
s.t.
m
k=1
kx
jk
−
m
k=1
kx
ik
≥0, ∀i, j ∈ pre(i) ,
(29.11)
m
k=1
x
ik
=1 , ∀i , (29.12)
m
l=1
y
kl
=1 , ∀k , (29.13)
m
k=1
y
kl
=1 , ∀l , (29.14)
x
ik
∈{0, 1}∀k, i , (29.15)
y
kl
∈{0, 1}∀l, k . (29.16)
The objective (29.10) is to minimize the cycle time,
C
T
. Constraint (29.11) represents the precedence con-
straints. It ensures that, for each pair of assembly
activities, the precedent cannot be assigned to a station
before the station of the successor if there is precedence
between the two activities. Constraint (29.12) ensures
that each task has to be assigned to one station. Con-
straint (29.13)ensures that each stationis equipped with
one robot. Constraint (29.14) ensures that each robot
can only be assigned to one station.
29.4.3 Hybrid Genetic Algorithm
Order encoding for task sequence:AGA’s structure
and parameter settings affect its performance. However,
the primary determinants of a GA’s success or failure
are the coding by which its genotypes represent candi-
date solutions, and the interaction of the coding with the
GA’s recombination and mutation operators.
A solution of the robot-based assembly line bal-
ancing (rALB) problem can be represented by two
integer vectors: the task sequence vector, v
1
,which
contains a permutation of assembly tasks ordered ac-
cording to their technological precedence sequence, and
the robot assignment vector, v
2
. The solution represen-
tation method is illustrated in Fig. 29.9. The detailed
processes of decoding the task sequence and assigning
robots to workstations are shown in [29.34].
In the real world, an assembly line is not just
for producing one unit of the product; tt should
produce several units. So we give the Gantt chart
Part C 29.4
Evolutionary Techniques for Automation 29.4 Robot-Based Assembly-Line System 499
810
57
469
123
52
stn/rbn (Balancing chart of the best solution)
Time
4/4
3/3
2/2
1/1
Fig. 29.10 The balancing chart of the best solution (stn –
workstation number, rbn – robot number)
Table 29.3 Performance of the proposed algorithm
Test problem Cycle time (C
T
)
No. of tasks
No. of stations WEST ratio Levitin et al. Levitin et al. Proposed
recursive consecutive approach
25 3 8.33 518 503 503
4 6.25 351 330 327
6 4.17 343 234 213
9 2.78 138 125 123
35 4 8.75 551 450 449
5 7.00 385 352 244
7 5.00 250 222 222
12 2.92 178 120 113
53 5 10.60 903 565 554
7 7.57 390 342 320
10 5.30 35 251 230
14 3.79 243 166 162
70 7 10.00 546 490 449
10 7.00 313 287 272
14 5.00 231 213 204
19 3.68 198 167 154
89 8 11.13 638 505 494
12 7.42 455 371 370
16 5.56 292 246 236
21 4.24 277 209 205
111 9 12.33 695 586 557
13 8.54 401 339 319
17 6.53 322 257 257
22 5.05 265 209 192
148 10 14.80 708 638 600
14 10.57 537 441 427
21 7.05 404 325 300
29 5.10 249 210 202
297 19 15.63 1129 674 646
29 10.24 571 444 430
38 7.82 442 348 344
50 5.94 363 275 256
1
23
469
57
810
50 100 150 200 250 300
Part waiting
Processing waiting
stn/rbn (case of 3 products)
Time
1/1
2/2
3/3
4/4
Fig. 29.11 Gantt chart for producing three units
Part C 29.4
500 Part C Automation Design: Theory, Elements, and Methods
with three units for analyzing the solution as in
Fig.29.11. We can see the solution reduce the wait-
ing time for the line by comparing with the feasible
Ball joint
Bar
Infinite
plane
+
+
–
+
–
Linear
actuator
Neuron
Synapse
Morphology
(body)
Control
(brain)
a)
c)
e)
f)
d)
b)
0 50 100 150 200 250 300 350
Generations
Fig. 29.12a–f Evolving bodies and brains. (a) Schematic illustration of an evolvable robot. (b) An arbitrarily sampled
instance of an entire generation, thinned down to show only significantly different individuals.
(c) Phylogenetic trees of
two different evolutionary runs, showing instances of speciation and massive extinctions.
(d) Progress of fitness versus
generation for one of the runs. Each dot represents a robot (morphology and control).
(e) Three evolved robots, in
simulation.
(f) The three robots from (c) reproduced in physical reality using rapid prototyping (after Lipson and Pollack
(2000))
solution from Fig. 29.8. This also means that the
better solution improved the assembly-line balanc-
ing.
Part C 29.4
Evolutionary Techniques for Automation References 501
29.4.4 Case Study
In order to evaluate the performance of the pro-
posed method, a large set of problems were tested.
In the literature, no benchmark data sets are available
for rALB. There are eight representative precedence
graphs [29.45], used inthe simple assemblyline balanc-
ing (sALB) literature [29.46]. These precedence graphs
contain 25–297 tasks.
Table 29.3 shows the experiment results of Lev-
itin et al.’s two algorithms and proposed approach
for 32 different scale test problems [29.47]. As de-
picted in Table 29.3, all of the results by the
proposed approach are better than Levitin et al.’s re-
cursive assignment method, and most results of the
proposed approach are better than Levitin et al.’s
consecutive assignment method, except for tests 25-
3, 35-7, and 111-17. Depending on the experiment
results, the way in which a solution of the au-
tomation problem is encoded into a chromosome
is a key issue for applying the evolutionary algo-
rithm.
29.5 Conclusions and Emerging Trends
The techniques presented in this Chapter are bioinspired
and their influence on factory, planning and scheduling,
manufacturing, logistics and transportation is discussed.
Emerging trends will continue to follow bioinspired
control and automation, such as the development of
evolvable robots to better meet the needs of evolving
and flexible lines (Fig.29.12). For a related discussion
refer to Chap.14 in an earlier section of this Handbook.
29.6 Further Reading
•
T. Gomi (Ed.): Evolutionary Robotics: From Intel-
ligent Robotics to Artificial Intelligence (Springer,
Tokyo 2001)
•
H. Lipson: Evolutionary robotics and open-ended
design automation. In: Biomemetics: Biologically
Inspired Technologies, ed. by Y. Bar-Cohen (CRC
Press, Boca Raton 2006) pp. 129–156
•
H. Lipson, J.B. Pollack: Automatic design and man-
ufacture of artificial lifeforms, Nature 406, 974–978
(2000)
•
S. Nolfi, D. Floreano: Evolutionary Robotics:
The Biology, Intelligence, and Technology of
Self-Organizing Machines (MIT Press, Cambridge
2000)
References
29.1 J. Bongard, H. Lipson: Integrated Design, Deploy-
ment and Inference for Robot Ecologies, Proc.
Robosphere 2004 (NASA Ames Research Center 2004)
29.2 I. Rechenberg: Evolution Strategie: Optimierung
Technischer Systeme nach Prinzipien der Biolo-
gischen Evolution (Frommann-Holzboog, Stuttgart
1973)
29.3 L.A. Fogel, M. Walsh: Artificial Intelligence Through
Simulated Evolution (Wiley, New York 1966)
29.4 J. Holland: Adaptation in Natural and Artificial Sys-
tems (University of Michigan Press, Ann Arbor 1975),
(MIT Press, Cambridge 1992)
29.5 D. Goldberg: Genetic Algorithms in Search, Opti-
mization and Machine Learning (Addison-Wesley,
Reading 1989)
29.6 J.R. Koza: Genetic Programming (MIT Press, Cam-
bridge 1992)
29.7 H. Schwefel: Evolution and Optimum Seeking,2nd
edn. (Wiley, New York 1995)
29.8 Z. Michalewicz: Genetic Algorithm + Data Structures
= Evolution Programs, 3rd edn. (Springer, New York
1996)
29.9 M. Gen, R. Cheng: Genetic Algorithms and Engi-
neering Design (Wiley, New York 1997)
29.10 K. Deb: Multi-Objective Optimization Using Evolu-
tionary Algorithms (Wiley, New York 2001)
29.11 M. Gen, R. Cheng, L. Lin: Network Models and
Optimization: Multiobjective Genetic Algorithm Ap-
proach (Springer, London 2008)
29.12 Wikipedia: Evolutionary Computation, http://en.
wikipedia.org/wiki/Evolutionary_computation
29.13 J.D. Schaffer: Multiple Objective Optimization with
Vector Evaluated Genetic Algorithms, Proc. 1st
Int. Conf. on Genet. Algorithms (1985) pp. 93–
100
29.14 C. Fonseca, P. Fleming: An overview of evolutionary
algorithms in multiobjective optimization, Evolut.
Comput. 3(1), 1–16 (1995)
Part C 29
502 Part C Automation Design: Theory, Elements, and Methods
29.15 N. Srinivas, K. Deb: Multiobjective function
optimization using nondominated sorting ge-
netic algorithms, Evolut. Comput. 3, 221–248
(1995)
29.16 H. Ishibuchi, T. Murata: A multiobjective genetic
local search algorithm and its application to flow-
shop scheduling, IEEE Trans. Syst. Man Cybern.
28(3), 392–403 (1998)
29.17 E. Zitzler, L. Thiele: Multiobjective evolutionary
algorithms: a comparative case study and the
strength Pareto approach, IEEE Trans. Evolut. Com-
put. 3(4), 257–271 (1999)
29.18 E. Zitzler, L. Thiele: SPEA2: Improving the Strength
Pareto Evolutionary Algorithm, Technical Report
103, (Computer Engineering and Communication
Networks Lab, Zurich 2001)
29.19 D. Tate, A. Smith: Unequal-area facility layout by
genetic search, IIE Trans. 27, 465–472 (1995)
29.20 J. Cohoon, S. Hegde, N. Martin: Distributed genetic
algorithms for the floor-plan design problem, IEEE
Trans. Comput.-Aided Des. 10, 483–491 (1991)
29.21 K. Tam: Genetic algorithms, function optimization,
facility layout design, Eur. J. Oper. Res. 63, 322–346
(1992)
29.22 A. Kusiak, S. Heragu: The facility layout problem,
Eur. J. Oper. Res. 29, 229–251 (1987)
29.23 M. Pinedo: Scheduling Theory, Algorithms and Sys-
tems (Prentice-Hall, Upper Saddle River 2002)
29.24 I. Kacem, S. Hammadi, P. Borne: Approach
by localization and multiobjective evolutionary
optimization for flexible job-shop scheduling
problems, IEEE Trans. Syst. Man Cybern. Part C 32(1),
408–419 (2002)
29.25 H. Zhang, M. Gen: Multistage-based genetic algo-
rithm for flexible job-shop scheduling problem, J.
Complex. Int. 11, 223–232 (2005)
29.26 K.W. Kim, Y.S. Yun, J.M. Yoon, M. Gen, G. Yamazaki:
Hybrid genetic algorithm with adaptive abilities for
resource-constrained multiple project scheduling,
Comput. Ind. 56(2), 143–160 (2005)
29.27 D. Turbide: Advanced planning and scheduling
(APS) systems, Midrange ERP Mag. (1998)
29.28 C. Moon, J.S. Kim, M. Gen: Advanced planning
and scheduling based on precedence and resource
constraints for e-Plant chains, Int. J. Prod. Res.
42(15), 2941–2955 (2004)
29.29 C. Moon, Y. Seo: Evolutionary algorithm for
advanced process planning and scheduling in
a multi-plant, Comput. Ind. Eng. 48(2), 311–325
(2005)
29.30 Y. Tsujimura, M. Gen, E. Kubota: Solving fuzzy
assembly-line balancing problem with genetic
algorithms, Comput. Ind. Eng. 29(1/4), 543–547
(1995)
29.31 M. Gen, Y. Tsujimura, Y. Li: Fuzzy assembly line
balancing using genetic algorithms, Comput. Ind.
Eng. 31
(3/4), 631–634 (1996)
29.32 J. Rubinovitz, G. Levitin: Genetic algorithm for line
balancing, Int. J. Prod. Econ. 41, 343–354 (1995)
29.33 J. Gao, G. Chen, L. Sun, M. Gen, An efficient ap-
proach for type II robotic assembly line balancing
problems, Comput. Ind. Eng., in press (2007)
29.34 L. Qiu, W. Hsu, S. Huang, H. Wang: Scheduling and
routing algorithms for AGVs: a survey, Int. J. Prod.
Res. 40(3), 745–760 (2002)
29.35 I.F.A. Vis: Survey of research in the design and con-
trol of automated guided vehicle systems, Eur. J.
Oper. Res. 170(3), 677–709 (2006)
29.36 T. Le-Anh, D. Koster: A review of design and control
of automated guided vehicle systems, Eur. J. Oper.
Res. 171(1), 1–23 (2006)
29.37 J.K. Lin: Study on guide path design and path plan-
ning in automated guided vehicle system. Ph.D.
Thesis (Waseda University, Japan 2004)
29.38 L. Lin, S.W. Shinn, M. Gen, H. Hwang: Network
model and effective evolutionary approach for AGV
dispatching in manufacturing system, J. Intell.
Manuf. 17(4), 465–477 (2006)
29.39 Y.K. Lau, Y. Zhao: Integrated scheduling of
handling equipment at automated container ter-
minals, Ann. Operat. Res. 159(1), 373–394 (2008)
29.40 A. Imai, H.C. Chen, E. Nishimura, S. Papadimitriou:
The simultaneous berth and quay crane allocation
problem, Transp. Res. Part E: Logist. Transp. Rev.
44(5), 900–920 (2008)
29.41 P. Preston, E. Kozan: An approach to determine
storage locations of containers at seaport termi-
nals, Comput. Oper. Res. 28(10), 983–995 (2001)
29.42 J.B. Yang: GA-based discrete dynamic program-
ming approach for scheduling in FMS environment,
IEEE Trans. Syst. Man Cybern. B 31(5), 824–835 (2001)
29.43 K. Kim, G. Yamazaki, L. Lin, M. Gen: Network-based
hybrid genetic algorithm to the scheduling in FMS
environments,J.Artif.LifeRobot.8(1), 67–76 (2004)
29.44 S.H. Kim, H. Hwang: An adaptive dispatching al-
gorithm for automated guided vehicles based on
an evolutionary process, Int. J. Prod. Econ. 60/61,
465–472 (1999)
29.45 A. Scholl, N. Boysen, M. Fliedner, R. Klein: Home-
page for assembly line optimization research,
http://www.assembly-line-balancing.de/
29.46 A. Scholl: Data of Assembly Line Balancing
Problems. Schriften zur Quantitativen Betriebs-
wirtschaftslehre 16/93, (TH Darmstadt, Darmstadt
1993)
29.47 G. Levitin, J. Rubinovitz, B. Shnits: A genetic algo-
rithm for robotic assembly balancing, Eur. J. Oper.
Res. 168, 811–825 (2006 )
Part C 29
503
Automating E
30. Automating Errors and Conflicts Prognostics
and Prevention
Xin W. Chen, Shimon Y. Nof
Errors and conflicts exist in many systems. A fun-
damental question from industries is How can
errors and conflicts in systems be eliminated by
automation, or can we at least use automa-
tion to minimize their damage? The purpose of
this chapter is to illustrate a theoretical back-
ground and applications of how to automatically
prevent errors and conflicts with various de-
vices, technologies, methods, and systems. Eight
key functions to prevent errors and conflicts are
identified and their theoretical background and
applications in both production and service are
explained with examples. As systems and net-
works become larger and more complex, such
as global enterprises and the Internet, error
and conflict prognostics and prevention become
more important and challenging; the focus is
shifting from passive response to proactive prog-
nostics and prevention. Additional theoretical
developments and implementation efforts are
needed to advance the prognostics and preven-
tion of errors and conflicts in many real-world
applications.
30.1 Definitions........................................... 503
30.2 Error Prognostics
and Prevention Applications.................. 506
30.2.1 Error Detection in Assembly
and Inspection ........................... 506
30.2.2 Process Monitoring
and Error Management ................ 506
30.2.3 Hardware Testing Algorithms ........ 507
30.2.4 Error Detection in Software Design 509
30.2.5 Error Detection and Diagnostics
in Discrete-Event Systems ............ 510
30.2.6 Error Detection in Service
and Healthcare Industries ............ 511
30.2.7 Error Detection and Prevention
Algorithms for Production
and Service Automation ............... 511
30.2.8 Error-Prevention Culture (EPC) ...... 512
30.3 Conflict Prognostics and Prevention ....... 512
30.4 Integrated Error and Conflict Prognostics
and Prevention .................................... 513
30.4.1 Active Middleware....................... 513
30.4.2 Conflict and Error Detection Model 514
30.4.3 Performance Measures................. 515
30.5 Error Recovery and Conflict Resolution.... 515
30.5.1 Error Recovery............................. 515
30.5.2 Conflict Resolution ...................... 520
30.6 Emerging Trends .................................. 520
30.6.1 Decentralized and Agent-Based
Error and Conflict Prognostics
and Prevention........................... 520
30.6.2 Intelligent Error and Conflict
Prognostics and Prevention .......... 521
30.6.3 Graph and Network Theories ........ 521
30.6.4 Financial Models
for Prognostics Economy .............. 521
30.7 Conclusion ........................................... 521
References .................................................. 522
30.1 Definitions
All humans commit errors (“To err is human”) and en-
counter conflicts. In the context of automation, there
are two main questions: (1) Does automation com-
mit errors and encounter conflicts? (2) Can automation
help humans prevent errors and eliminate conflicts? All
human-made automation includes human-committed
errors and conflicts, for example, human program-
ming errors, design errors, and conflicts between
Part C 30
504 Part C Automation Design: Theory, Elements, and Methods
Table 30.1 Examples of errors and conflicts in production automation
Error Conflict
•
A robot drops a circuit board while moving it
between two locations
•
A machine punches two holes on a metal sheet
while only one is needed, because the size of the
metal sheet is recognized incorrectly by the vision
system
•
A lathe stops processing a shaft due to power
outage
•
The server of a computer-integrated manufactur-
ing system crashes due to high temperature
•
A facility layout generated by a software pro-
gram cannot be implemented due to irregular shapes
•
Two numerically controlled machines request
help from the same operator at the same time
•
Three different software packages are used to
generate optimal schedule of jobs for a production
facility; the schedules generated are totally different
•
Two automated guided vehicles collide
•
A DWG (drawing) file prepared by an engineer
with AutoCAD cannot be opened by another engi-
neer with the same software
•
Overlapping workspace defined by two cooperat-
ing robots
human planners. Two automation systems, designed
separately by different human teams, will encounter
conflicts when they are expected to collaborate, for
instance, the need for communication protocol stan-
dards to enable computers to interact automatically.
Some errors and conflicts are inherent to automa-
tion, similar to all human-made creations, for instance,
a robotmechanical structurethat collapsesunder weight
overload.
An error is any input, output or intermediate result
that has occurred or will occur in a system and does
not meet system specification, expectation or compar-
ison objective. A conflict is an inconsistency between
different units’ goals, plans, tasks or other activities in
a system. A system usually has multiple units, some of
which collaborate, cooperate, and/or coordinate to com-
plete tasks. The most important difference between an
error and a conflict is that an error can involve only one
a) c) e) f)d)b)
Fig. 30.1a–f Errors and conflicts in a pin insertion task: (a) successful insertion; (b–f) are unsuccessful insertion with
(1) errors if the pin and the two other components are considered as one unit in a system, or (2) conflicts if the pin is
a unit and the two other components are considered as another unit in a system [30.1]
unit, whereas a conflict involves two or more units in
a system. An error at a unit may cause other errors or
conflicts, for instance, a workstation that cannot pro-
vide the required number of products to an assembly
line (a conflict) because one machine at the workstation
breaks down (an error). Similarly, a conflict may cause
other errors and conflicts, for instance, a machine that
did not receive required products (an error) because the
automated guided vehicles that carry the products col-
lided when they were moving toward each other on the
same path (a conflict). These phenomena, errors lead-
ing to other errors or conflicts, and conflicts leading to
other errors or conflicts, are called error and conflict
propagation.
Errors and conflicts are different but related. The
definition of the two terms is often subject to the un-
derstanding and modeling of a system and its units.
Mathematical equations can help define errors and con-
Part C 30.1