Nof S.Y. Springer Handbook of Automation

Подождите немного. Документ загружается.

Distributed Agent Software for Automation References 485

2. M. D’Inverno, M. Luck, M. Fisher, C. Preist (Eds.):

Foundations and Applications of Multi-Agent Sys-

tems: UKMAS Workshops (Springer, New York

2002)

3. S.M. Deen: Agent Based Manufacturing (Springer,

New York 2003)

4. C.Y. Huang, S.Y. Nof: Formation of autonomous

agent networks for manufacturing systems, Int. J.

Prod. Res. 38(3), 607–624 (2000)

5. N.R. Jennings, M.J. Wooldridge (Eds.): Agents

Technology Foundation, Applications and Markets

(Springer, New York 1998)

6. M. Klusch, S.P. Bergamaschi Edwards, P. Petta

(Eds.): Intelligent Information Agents (Springer,

New York 2003)

7. P. Kopacek (Ed.): Multi-Agent Systems in Produc-

tion: A Proceedings volume of the IFAC workshop

(Pergamon, Oxford 2000)

8. R.S.T. Lee, V. Loia: Computational Intelligence

for Agent-based Systems (Springer, New York

2007)

9. P. Maes: Modeling adaptive, autonomous agents,

Artif. Life 1(1/2), 135–162 (1994)

10. G. Moro, M. Koubarakis (Eds.): Agents and Peer-

to-Peer Computing: First International Workshop

(Springer, New York 2002)

11. S.Y. Nof: Intelligent collaborative agents. In:

McGraw Hill Yearbook of Science and Technology

(McGraw Hill, Columbus 2000) pp.219–222

12. S.Y. Nof: Handbook of Industrial Robotics (Wiley,

New York 1999)

13. L. Steels: When are robots intelligent, autonomous

agents?, Robot. Auton. Syst. 15, 3–9 (1995)

14. Z. Zhang: Agent-based Hybrid Intelligent Systems:

An Agent-based Framework for Complex Problem

Solving (Springer, New York 2004)

References

28.1 R.G. Smith: The Contract Net Protocol: high-level

communication and control in a distributed prob-

lem solver, IEEE Trans. Comput. 29(12), 1104–1113

(1980)

28.2 N.R. Jennings, M.J. Wooldridge: Co-operating

agents: concepts and applications. In: Agent Tech-

nology: Foundations, Applications, and Markets,

ed. by H. Haugeneder, D. Steiner (Springer, Berlin

Heidelberg 1998) pp. 175–201

28.3 W. Shen, D. Norrie, J.P. Bartès: Multi-Agent Systems

for Concurrent Intelligent Design and Manufactur-

ing (Taylor & Francis, London 2001)

28.4 Commercial Technology for Maintenance Acti-

vities – CTMA (2008),

http://ctma.ncms.org/default.htm

28.5 Research and Markets: Growth Opportunities in

Carbon Fiber Composites Market 2006-2011 (Re-

search and Markets, Dublin 2006), http://www.

researchandmarkets.com/reports/362300/growth_

opportunities_in_carbon_ﬁber_composites

28.6 T. Roberts: Rapid growth forecast for carbon ﬁbre

market, Reinf. Plast. 51(2), 10–13 (2007)

28.7 Research and Markets: Opportunities in Contin-

uous Fiber Reinforced Thermoplastic Composites

2003–2008 (Research and Markets, Dublin 2003)

p. 240

28.8 K. Burger: The changing outlook for natural rubber,

Natuurrubber 40(4), 1–4 (2005)

28.9 P. Salagnac, P. Dutournié, P. Glouannec: Curing of

composites by radiation and natural convection in

an autoclave, Am. Inst. Chem. Eng. 50(12), 3149–

3159 (2004)

28.10 P. Salagnac, P. Dutournié, P. Glouannec: Simula-

tions of heat transfers in an autoclave. Applications

to the curing of composite material parts, J. Phys.

IV France 120,467–472(2004)

28.11 J. Kim, T.J. Moon, J.R. Howell: Transient thermal

modeling of in-situ curing during tape winding of

composite cylinders, J. Heat Transf. 125(1), 137–146

(2003)

28.12 M.-H.Chang,C.-L.Chen,W.-B.Young:Optimalde-

sign of the cure cycle for consolidation of thick

composite laminants, Polym. Compos. 17(5), 743–

750 (2004)

28.13 M. Jinno, S. Sakai, K. Osaka, T. Fukuda: Smart

autoclave processing of thermoset resin matrix

composites based on temperature and internal

strain monitoring, Adv. Compos. Mater. 12(1), 57–72

(2003)

28.14 A. Mawardi, R. Pitchumani: Optimal temperature

and current cycles for curing composites using em-

bedded resistive heating elements, J. Heat Transf.

125(1), 126–136 (2003)

28.15 M.M. Thomas, B. Joseph, J.L. Kardos: Experimental

characterization of autoclave-cured glass-epoxy

composite laminates: cure cycle effects upon thick-

ness, void content and related phenomena, Polym.

Compos. 18(3), 283–299 (2004)

28.16 H.S. Kim, D.G. Lee: Reduction of fabricational ther-

mal residual stress of the hybrid co-cured structure

using a dielectrometry, Compos. Sci. Technol. 67(1),

29–44 (2007)

28.17 M.N. Ghasemi-Nejhad, R. Russ, S. Pourjalali: Man-

ufacturing and testing of active composite panels

Part C 28

486 Part C Automation Design: Theory, Elements, and Methods

with embedded piezoelectric sensors and actua-

tors, J. Intell. Mater. Syst. Struct. 16(4), 319–333

(2005)

28.18 N. Pantelelis, T. Vrouvakis, K. Spentzas: Cure cy-

cle design for composite materials using computer

simulation and optimisation tools, Forsch. Inge-

nieurwes. 67(6), 254–262 (2007)

28.19 P.George,J.Grifﬁth,G.Orient,J.Madsen,C.Teng,

R. Courdji: Exploration of composites processing

and producibility by analysis, Proc. 34th Int. SAMPE

Tech. Conf. (Baltimore 2002)

28.20 V. Pillai, A.N. Beris, P. Dhurjati: Intelligent cur-

ing of thick composites using a knowledge-based

system, J. Compos. Mater. 31(1), 22–51 (1997)

28.21 D.J. Michaud, A.N. Beris, P.S. Dhurjati: Thick-

sectioned RTM composite manufacturing, Part II.

Robust cure optimization and control, J. Compos.

Mater. 36(10), 1201–1231 (2002)

28.22 S.W. Arms, C.P. Townsend, M.J. Hamel: Valida-

tion of remotely powered and interrogated sensing

networks for composite cure monitoring (2003),

http://www.microstrain.com/white/Validationof

RemotelyPoweredandInterrogatedSensingNet-

works.pdf

28.23 S. Uryasev, A.A. Trindade: Combining Analytical

Model and Experimental Test Data for Optimal

Determination of Failure Tolerance Limits (2004).

http://www.arpa.mil/dso/thrusts/matdev/aim/

AIM%20PDFs/presentation_2004/Case2328_

attach.pdf

28.24 S. Hill: Electron Beam Curing, Mater. World 7(7),

398–400 (1999)

28.25 NASA: A New Kind of Curing (2007), http://command.

fuentek.com/matrix/success-story.cfm?

successid=154

28.26 Blair Rubber Company: Rubber Lining Manual, Sec-

tion 14: Curing Instructions, Engineering and Appli-

cation Manual (2005), http://www.blairrubber.com/

manual/PDF_Docs/Sec14_Curing/CURING_

INSTRUCTIONS_Rev3.pdf

28.27 DT9805 Series USB Thermocouple Measure-

ment Modules, Datatranslation product datasheet

(2008), http://www.datx.com/docs/datasheets/

dt9805.pdf

28.28 Flexible Thermocouple Management Programs

(2008), http://www.vulcanelectric.com/pdf/

calibration.pdf

28.29 The Hot Runner Manager (2008). http://www.fast-

heat.com/hotrunner/HR_Specialized.html

(thermocouple management)

28.30 TE Wire & Cable: Industrial Application Guide

(2008). http://www.tewire.com/10-10.html

28.31 P. Vrba, V. Marík: Simulation in agent-based man-

ufacturing control systems, Proc. IEEE Int. Conf.

Syst. Man Cybern. (Hawaii 2005) pp. 1718–1723

28.32 F.P. Maturana, P. Tichý, P.

Slechta, R. Staron: Using

dynamically created decision-making organiza-

tions (holarchies) to plan, commit, and execute

control tasks in a chiller water system, Proc.

13th Int. Workshop Database Expert Syst. Appl.

(DEXA 2002), HoloMAS 2002 (Aix-en-Provence 2002)

pp. 613–622

28.33 F.P. Maturana, R.J. Staron: Integration of Collabo-

rating Agent-based Sub-systems – Final Report,

prepared for Johns Hopkins University Applied

Physics Laboratory under Subcontract 864123 and

the Ofﬁce of Naval Research under Prime Contract

N00014-02-C-0526 (2004)

28.34 IEEE: The Foundation for Intelligent Physical Agents

(FIPA, IEEE Standards 2008), http://www.ﬁpa.org

28.35 R.J. Staron, F.P. Maturana, P. Tichý, P.

Slechta: Use

of an agent type library for the design and im-

plementation of highly ﬂexible control systems,

8th World Multiconf. Syst. Cybern. Inf. (SCI2004)

(Orlando 2004)

28.36 F.M. Discenzo, F.P. Maturana, R.J. Staron, P. Tichý,

Slechta, V. Marík: Prognostics and control in-

tegration with dynamic reconﬁgurable agents, 1st

WSEAS Int. Conf. Electrosci. Technol. Nav. Eng. All-

electr. Ship (Vouliagmeni, Athens 2004)

Part C 28

487

Evolutionary

29. Evolutionary Techniques for Automation

Mitsuo Gen, Lin Lin

In this chapter, evolutionary techniques (ETs) will

be introduced for treating automation problems in

factory, manufacturing, planning and scheduling,

and logistics and transportation systems. ET is the

most popular metaheuristic method for solving

NP-hard optimization problems. In the past few

years, ETs have been exploited to solve design

automation problems. Concurrently, the ﬁeld of ET

reveals a signiﬁcant interest in evolvable hardware

and problems such as routing, placement or test

pattern generation.

The rest of this chapter is organized as follows.

First the background developments of evolutionary

techniques are described. Then basic schemes and

working mechanism of genetic algorithms (GAs)

will be given, and multiobjective evolutionary

algorithms for treating optimization problems with

multiple and conﬂicting objectives are presented.

Lastly, automation and the challenges for applying

evolutionary techniques are speciﬁed.

Next, the various applications based on ETs

for solving factory automation (FA)problemswill

be surveyed, covering planning and schedul-

ing problems, nonlinear optimization problems

in manufacturing systems, and optimal design

problems in logistics and transportation systems.

Finally, among those applications based on

ETs, detailed case studies will be introduced. The

ﬁrst case study covers dispatching of automated

guided vehicles (AGV) and machine scheduling in

a ﬂexible manufacturing system (FMS). The second

ET case study for treating automation problems

is the robot-based assembly line balancing (ALB)

problem. Numerical experiments for various scales

of AGV dispatching problems and robot-based ALB

29.1 Evolutionary Techniques ....................... 488

29.1.1 Genetic Algorithm ....................... 489

29.1.2 Multiobjective Evolutionary

Algorithm................................... 490

29.1.3 Evolutionary Design Automation ... 491

29.2 Evolutionary Techniques

for Industrial Automation ..................... 492

29.2.1 Factory Automation ..................... 492

29.2.2 Planning

and Scheduling Automation ......... 493

29.2.3 Manufacturing Automation .......... 493

29.2.4 Logistics

and Transportation Automation .... 493

29.3 AGV Dispatching in Manufacturing System 494

29.3.1 Network Modeling

for AGV Dispatching ..................... 494

29.3.2 Evolutionary Approach:

Priority-Based GA........................ 495

29.3.3 Case Study.................................. 496

29.4 Robot-Based Assembly-Line System ....... 497

29.4.1 Assembly-Line Balancing Problems 497

29.4.2 Robot-Based Assembly-Line Model 497

29.4.3 Hybrid Genetic Algorithm ............. 498

29.4.4 Case Study.................................. 501

29.5 Conclusions and Emerging Trends .......... 501

29.6 Further Reading ................................... 501

References .................................................. 501

problems will be described to show the effec-

tiveness of the proposed approaches with greater

search capability that improves the quality of so-

lutions and enhances the rate of convergence over

existing approaches.

Part C 29

488 Part C Automation Design: Theory, Elements, and Methods

29.1 Evolutionary Techniques

Evolutionary techniques (ET) is a subﬁeld of arti-

ﬁcial intelligence (AI), and refers to a synthesis of

methodologies from fuzzy logic (FL), neural networks,

genetic algorithm (GA), and other evolutionary algo-

rithms (EAs). ET uses the evolutionary process within

a computer to provide a means for addressing complex

engineering problems involving chaotic disturbances,

randomness, and complex nonlinear dynamics that

traditional algorithms have been unable to conquer

(Fig.29.1).

Computer simulations of evolution started as early

as in 1954; however most publications were not widely

Input layer

Output layer

Hidden

layer

a) b)

c) d)

0 5 10 15 20 25 30 35 40 45 50

Error

Generations

7.5

6.5

5.5

4.5

3.5

–6 –4 –2 0 2 4 6

–1

–2

Average

Best

–6 –4 –2 0 2 4 6

–1

–2

–6 –4 –2 0 2 4 6

–1

–2

–6 –4 –2 0 2 4 6

–1

–2

Fig. 29.1a–d Evolving a controller for a ﬁxed morphology: (a) The morphology of the machine contains four legs ac-

tuated with eight motors, four ground-touch sensors, four angle sensors, and two chemical sensors.

(b) Themachineis

controlled by a recurrent neural net whose inputs are connected to the sensors and whose outputs are connected to the

motors.

show the motion of the machine towards high concentration (darker area). Black trails show tracks when the chemical

sensors are turned off (after [29.1])

noticed. From these beginnings, computer simulation

of evolution by biologists became more common in

the early 1960s. Evolution strategies (ES) was intro-

duced by Rechenberg in the 1960s and early 1970s,

and it was able to solve complex engineering prob-

lems [29.2]. Another approach was the evolutionary

programming (EP)ofFogel [29.3], which was proposed

for generating artiﬁcial intelligence. EP originally used

ﬁnite state machines for predicting environments, and

used variation and selection to optimize the predictive

logic. Genetic algorithms (GAs) in particular became

popular through the work of Holland in the early

Part C 29.1

Evolutionary Techniques for Automation 29.1 Evolutionary Techniques 489

Table 29.1 Classiﬁcation of evolutionary techniques [29.12]

Optimization algorithms Other approaches

Evolutionary algorithms Genetic algorithms Self-organization Self-organizing maps

Evolutionary programming Growing neural gas

Evolution strategy Competetive learning

demo applet

Genetic programming Differential evolution

Learning classiﬁer systems Artiﬁcial life Digital organism

Swarm intelligence Ant colony optimization Cultural algorithms

Particle swarm optimization Harmony search algorithm

Artiﬁcial immune systems

Learnable evolution model

1970s [29.4]. His work originated with studies of cel-

lular automata, conducted by Holland and his students

at the University of Michigan [29.5]. Holland intro-

duced a formalized framework forpredicting the quality

of the next generation, known as Holland’s schema

theorem. Research in GAs remained largely theoreti-

cal until the mid-1980s. Genetic programming (GP)is

an extended technique of GA popularized by Koza in

which computer programs, rather than function param-

eters, are optimized [29.6]. Genetic programming often

uses tree-based internal data structures to represent the

computer programs for adaptation instead of the list

structures typical of genetic algorithms. As academic

interest grew, the dramatic increase in desktop compu-

tational power allowed for practical application of the

new technique [29.7–11]. Evolutionary techniques are

generic population-based metaheuristic optimization al-

gorithms, summarized in Table 29.1.

Several conferences and workshops have been

held to provide an international forum for exchang-

ing new ideas, progress or experience on ETsand

to promote better understanding and collaborations

between the theorists and practitioners in this ﬁeld.

The major meetings are the Genetic and Evolution-

ary Computation Conference (GECCO), the IEEE

Congress on Evolutionary Computation (CEC), Parallel

Problem Solving from Nature (PPSN), the Founda-

tions of Genetic Algorithms (FOGA) workshop, the

Workshop on Ant Colony optimization and Swarm

Intelligence (ANTS) and the Evo* and EuroGP

workshops etc. The major journals are Evolution-

ary Computation, IEEE Transactions on Evolutionary

Computation, Genetic Programming,andEvolvable

Machines.

29.1.1 Genetic Algorithm

Among evolutionary techniques (ETs), genetic algo-

rithms (GA) are the most widely known type of ETs

today. GA includes the common essential elements of

ETs, and has wide real-world applications. The original

form of GA was described by Goldberg [29.5]. GA is

a stochastic search technique based on the mechanism

of natural selection and natural genetics. The central

theme of research on GA is to keep a balance between

exploitation and exploration in its search to the optimal

solution for survival in many different environments.

Features for self-repair, self-guidance, and reproduction

are the rules in biological systems, whereas they barely

exist in the most sophisticated artiﬁcial systems. GA

has beentheoretically and empirically proven to provide

a robust search in complex search spaces.

GA, differing from conventional search techniques,

starts with an initial set of random solutions called

the population. Each individual in the population is

called a chromosome, representing a solution to the

problem at hand. A chromosome is a string of sym-

bols, usually but not necessarily, a binary bit string.

The chromosomes evolve through successive itera-

tions, called generations. During each generation, the

chromosomes are evaluated, using some measures of

ﬁtness. To create the next generation, new chromo-

somes, called offspring, are generated by either merging

two chromosomes from the current generation using

a crossover operator and/or modifying a chromosome

using a mutation operator. A new generation is formed

by selecting some of the parents, according to the

ﬁtness values, and offspring, and rejecting others so

as to keep the population size constant. Fitter chro-

Part C 29.1

490 Part C Automation Design: Theory, Elements, and Methods

mosomes have higher probabilities of being selected.

After several generations, the algorithms converge to

the best chromosome, which hopefully represents the

optimum or suboptimal solution to the problem. In gen-

eral, GA has ﬁve basic components, as summarized by

Michalewicz [29.8]:

1. A genetic representationof potential solutions tothe

problem

2. A way to create a population (an initial set of poten-

tial solutions)

3. An evaluation function rating solutions in terms of

their ﬁtness

4. Genetic operators that alter the genetic composition

of offspring (crossover, mutation, selection, etc.)

5. Parameter values that genetic algorithms use (popu-

lation size, probabilities of applying genetic opera-

tors, etc.).

Figure 29.2 shows a general structure of GA, where

P(t)andC(t) are parents and offspring in the current

generation t.

Chromosome

Decoding

Termination

condition?

1100101010

1011101110

0011011001

1100110001

Population P(t)

Chromosome

1100101010

1011101110

1100101110

1011101010

0011001001

0011011001

Offspring C(t)

Encoding Crossover

Mutation

Decoding

Evaluation

New population

Selection P(t) + C(t)

(t)

← 0

← t+1

Initial

solutions

Best solution

Solution candidates

fitness computation

Roulette wheel

Start

Stop

Fig. 29.2 The general structure of genetic algorithms

29.1.2 Multiobjective Evolutionary

Algorithm

Multiple objective problems arise in the design, mode-

ling, and planning of many complex real systems in

the areas of industrial production, urban transporta-

tion, capital budgeting, forest management, reservoir

management, layout and landscaping of new cities, en-

ergy distribution, etc. It is easy to ﬁnd that almost

every important real-world decision problem involves

multiple and conﬂicting objectives which need to

be tackled while respecting various constraints, lead-

ing to overwhelming problem complexity. Since the

1990s, EAs have been received considerable atten-

tion as a novel approach to multiobjective optimization

problems, resulting in a fresh body of research and

applications known as evolutionary multiobjective op-

timization (EMO).

Features of Genetic Search

The inherent characteristics of EAs demonstrate why

genetic search is well suited for multiple-objective op-

Part C 29.1

Evolutionary Techniques for Automation 29.1 Evolutionary Techniques 491

timization problems. The basic feature of the EAsis

multiple-directional and global search by maintaining

a population of potential solutions from generation to

generation. It is hopedthat the population-to-population

approach will explore all Pareto solutions.

EAs do not have much mathematical requirements

about the problems, and can handle any kind of objec-

tive functions and constraints. Due to their evolutionary

nature, EAs can search for solutions without regard to

the speciﬁc internal workings of the problem. There-

fore, it is hopeful to solve complex problem by using

the evolutionary algorithms.

Because evolutionary algorithms, as a kind of meta-

heuristics, provide us with great ﬂexibility to hybridize

conventional methods into their main framework, we

can take advantage of both evolutionary algorithms and

conventional methods to make much more efﬁcient im-

plementations. The growing research on applying EAs

to multiple-objective optimization problems presents

a formidable theoretical and practical challenge to the

mathematical community [29.10].

Fitness Assignment Mechanism

A special issue in the multiobjective optimization prob-

lem is the ﬁtness assignment mechanism. Since the

1980s, several ﬁtness assignment mechanisms have

been proposed and applied to multiobjective opti-

mization problems. Although most ﬁtness assignment

mechanisms are just different approaches and are appli-

cable to different cases of multiobjective optimization

problems. In order to understanding the development of

EMO, we classify the ﬁtness assignment mechanisms

by according to the published year.

Type 1: Vector evaluation approach. The vector

evaluated genetic algorithm (veGA) was the ﬁrst no-

table work to solve multiobjective problems in which

a vector ﬁtness measure is used to create the next gen-

eration [29.13].

Type 2: Pareto ranking + diversity: Fonseca and

Fleming proposed a multiobjective genetic algorithm

(moGA) in which the rank of a certain individual cor-

responds to the number of individuals in the current

population that dominate it [29.14]. Srinivas and Deb

also developed a Pareto-ranking-based ﬁtness assign-

ment and called it the nondominated sorting genetic

algorithm (nsGA) [29.15].In eachmethod, the nondom-

inated solutions constituting a nondominated front are

assigned the same dummy ﬁtness value.

Type 3: Weighted sum + elitist preserve: Ishibuchi

and Murata proposed a weighted-sum-based ﬁtness as-

signment method, called the random-weight genetic

algorithm (rwGA), to obtain a variable search direction

toward the Pareto frontier [29.16]. The weighted-

sum approach can be viewed as an extension of

methods used in the multiobjective optimizations to

GAs. It assigns weights to each objective function

and combines the weighted objectives into a sin-

gle objective function. Gen et al. proposed another

weight-sum-based ﬁtness assignment method called

the adaptive-weight genetic algorithm (awGA), which

readjusts weights for each objective based on the

values of nondominated solutions in the current pop-

ulation to obtain ﬁtness values combined with the

weights toward the Pareto frontier [29.11]. Zitzler

and Thiele proposed the strength Pareto evolution-

ary algorithm (spEA) [29.16] and an extended version

spEA II [29.17, 18] that combines several features

of previous multiobjective genetic algorithms (moGA)

in a unique manner. Deb suggested a nondominated

sorting-based approach called the nondominated sort-

ing genetic algorithm II (nsGA II) [29.10], which

alleviates three difﬁculties: computational complex-

ity, nonelitism approach, and the need to specify

a sharing parameter. nsGA II was advanced from

its origin, nsGA. Gen et al. proposed an inter-

active adaptive-weight genetic algorithm (i-awGA),

which is an improved adaptive-weight ﬁtness assign-

ment approach with consideration of the disadvantages

of the weighted-sum and Pareto-ranking-based ap-

proaches [29.11].

29.1.3 Evolutionary Design Automation

Automation is the use of control systems such as com-

puters to control industrial machinery and processes,

replacing human operators. In the scope of industri-

alization, it is a step beyond mechanization. Whereas

mechanization provided human operators with machin-

ery to assist them with the physical requirements of

work, automation greatly reduces the need for human

sensory and mental requirements as well. Processes and

systems can also be automated.

Automation plays an increasingly important role in

the global economy and in daily experience. Engineers

strive to combine automated devices with mathematical

and organizational tools to create complex systems for

a rapidly expanding range of applications and human

activities.

Evolutionary algorithms (EAs) have received con-

siderable attention regarding their potential as novel

optimization techniques. There are three major advan-

tages when applying EA to design automation:

Part C 29.1

492 Part C Automation Design: Theory, Elements, and Methods

1. Adaptability: EAs do not have many mathematical

requirements regarding the optimization problem.

Due to their evolutionary nature, EAs will search

for solutions without regard to the speciﬁc inter-

nal workings of the problem. EAs can handle any

kind of objective functions and any kind of con-

straints (i. e., linear or nonlinear, deﬁned on discrete,

continuous or mixed search spaces).

2. Robustness: The use of evolution operators makes

EA very effective in performing global search

(in probability), while most conventional heuristics

usually perform local search. It has been proven by

many studies that EA is more efﬁcient and more

robust at locating optimal solution and reducing

computational effort than other conventional heuris-

tics.

3. Flexibility: EAs provide great ﬂexibility to hy-

bridize with domain-dependent heuristics to make

an efﬁcient implementation for a speciﬁc problem.

However, to exploit the beneﬁts of an effective EA

to solve design automation problems, it is usually nec-

essary to examine whether we can build an effective

genetic search with the encoding. Several principles

were proposed to evaluate effectiveness [29.11]:

Property 1 (Space): Chromosomes should not require

extravagant amounts of memory.

Property 2 (Time): The time required for executing

evaluation, recombination, and mutation on

chromosomes should not be great.

Property 3 (Feasibility): A chromosome corresponds to

a feasible solution.

Property 4 (Legality): Any permutation of a chromo-

some corresponds to a solution.

Property 5 (Completeness): Any solution has a corre-

sponding chromosome.

Property 6 (Uniqueness): The mapping from chromo-

somes to solutions (decoding) may be-

long to one of the following three cases

(Fig.29.5): 1-to-1 mapping, n-to-1 map-

ping, and 1-to-n mapping. The 1-to-1 map-

ping is the best among the three cases, and

1-to-n mapping is the most undesirable.

Property 7 (Heritability): Offspringof simplecrossover

(i.e., one-cut-point crossover) should corre-

spond to solutions which combine the basic

features of their parents.

Property 8 (Locality): A small change in a chromo-

some should imply a small change in its

corresponding solution.

29.2 Evolutionary Techniques for Industrial Automation

Currently, formanufacturing, the purpose of automation

has shifted from increasing productivity and reducing

costs to broader issues, such as increasing quality and

ﬂexibility in the manufacturing process. For example,

automobile and truck pistons used to be installed into

engines manually. This is rapidly being transitioned to

automated machine installation, because the error rate

for manual installment was around 1–1.5%, but has

been reduced to 0.00001% with automation. Hazardous

operations, such as oil reﬁning, manufacturing of indus-

trial chemicals, and all forms of metal working, were

always early contenders for automation.

However, many applications of automation, such

as optimizations and automatic controls, are formu-

lated with complex structures, complex constraints,

and multiple objects simultaneously, which makes the

problem intractable to traditional approaches. In re-

cent years, the evolutionary techniques community has

turned much of its attention toward applications in in-

dustrial automation.

29.2.1 Factory Automation

In a manufacturing system, layout design is concerned

with the optimum arrangement of physical facilities,

such as departments or machines, in a certain area. Usu-

ally the design criterion is considered to be minimizing

material-handling costs. Because of the combinato-

rial nature of the facility layout problem, the heuristic

technique is the most promising approach for solv-

ing practical-size layout problems. The interest in

application of ETs to facility layout design has been

growing rapidly. Tate and Smith applied GA to the

shape-constrained unequal-area facility layout prob-

lem [29.19]. Cohoon et al. proposed a distributed GA

for the ﬂoorplan design problem [29.20]. Tam reported

his experiences of applying genetic algorithms to the

facility layout problem [29.21].

A ﬂexible machining system is one of the forms

of factory automation. The design of a ﬂexible ma-

chining system (FMS) involves the layout of machine

Part C 29.2

Evolutionary Techniques for Automation 29.2 Evolutionary Techniques for Industrial Automation 493

and workstations. Kusiak and Heragu wrote a sur-

vey paper on the machine layout problem [29.22].

The layout of machines in a FMS is typically deter-

mined by the type of material-handling devices used.

The most used material-handling devices are: material-

handling robot, automated guided vehicle (AGV), and

gantry robot. Gen and Cheng provide various GA ap-

proaches for the machine layout and facility layout

problems [29.9].

29.2.2 Planning

and Scheduling Automation

The planning and scheduling of manufacturing systems

always require resource capacity constraints, disjunc-

tive constraints, and precedence constraints, owing to

the tight due dates, multiple customer-speciﬁc orders,

and ﬂexible process strategies. Here, some hot topics of

applications of ETs in advanced planning and schedul-

ing (APS) are introduced. These models mainly support

the integrated, constraint-based planning of the manu-

facturing system toreduce leadtimes, lower inventories,

increase throughput, etc.

The ﬂexible jobshop problem (fJSP) is a general-

ization of the jobshop and parallel machine environ-

ment [29.23], which provides a closer approximation

to a wide range of real manufacturing systems. Kacem

et al. proposed the operations machine-based GA

approach [29.24], which is based on a traditional rep-

resentation called the schemata theorem representation.

Zhang and Gen proposed a multistage operation-based

encoding for fJSP [29.25].

The objective of the resource-constrained project

scheduling problem (rcPSP) is to schedule activi-

ties such that precedence and resource constraints are

obeyed and the makespan of the project is to be mini-

mized. Gen and Cheng adopted priority-based encoding

for this rcPSP [29.9]. In order to improve the effec-

tiveness of priority-based GA approach for an extended

resource constrained multiple project scheduling prob-

lem, Kim et al. combined priority dispatching rules in

priority-based encoding process [29.26].

The advanced planning and scheduling (APS)

model includes a range of capabilities from ﬁnite

capacity planning at the plant ﬂoor level through

constraint-based planning to the latest applications of

advanced logic for supply-chain planning and col-

laboration [29.27]. Several related works by Moon

et al. [29.28]andMoon and Seo [29.29] have reported

a GA approach especially for solvingsuch kinds of APS

problems.

29.2.3 Manufacturing Automation

Assembly-line balancing problems (ALB) consist of

distributing work required to assemble a product in

mass or series production on an assembly line among

a set of workstations. Several constraints and different

objectives may be considered. The simple assembly-

line balancing problem consists of assigning tasks to

workstations such that precedence relations between

tasks and zoning or other constraints are met. The ob-

jective is to make the work content at each station

most balanced. GAs have been applied to solve vari-

ous assembly-line balancing problems [29.30–32]. Gao

et al. proposed an innovative GA hybridized with local

search for a robotic-based ALB problem [29.33]. Based

on different neighborhood structures, ﬁve local search

procedures are developed to enhance the search ability

of GA.

An automated guided vehicle (AGV) is a mobile

robot usedwidely in industrial applications to move ma-

terials from point to point. AGVs help to reduce costs

of manufacturing and increase efﬁciency in a manufac-

turing system. For a recent review of AGV problems

and issues the reader is referred to [29.34–37]. Lin et al.

adopted priority-based encoding for solving the AGV

dispatching problem in an FMS [29.38].

29.2.4 Logistics

and Transportation Automation

Logistics is the last frontier for cost reduction and the

third proﬁt source of enterprises [29.39]. The interest

in developing effective logistics system design models

and efﬁcient optimization methods has been stimulated

by high costs of logistics and the potential for securing

considerable savings. One of the most important topics

of logistics and transportation automation is automated

container terminals.

Handling equipment scheduling (HES) is important

for scheduling different types of handing equipment

in order to improve the productivity of automated

container terminals. Lau and Zhao give a mixed-

integer programming model, which considers various

constraints related to the integrated operations be-

tween different types of handling equipment. This

study proposes a multilayer GA to obtain the near-

optimal solution of the integrated scheduling prob-

lem [29.39].

Berth allocation planning (BAP) is to allocate space

along the quayside to incoming ships at a container ter-

minal in order to minimize some objective function.

Part C 29.2

494 Part C Automation Design: Theory, Elements, and Methods

Imai et al. introduce a formulation for the simultaneous

berth and crane allocation problem and employed GA

to ﬁnd an approximate solution for the problem [29.40].

The aim of storage locations planning (SLP)is

to determine the optimal storage strategy for various

container-handling schedules. Preston and Kozan de-

veloped a container location model and proposed a GA

approach with analyses of different resource levels and

a comparison with current practice at the Port of Bris-

bane [29.41].

29.3 AGV Dispatching in Manufacturing System

Automated material handling has been called the key

to integrated manufacturing. An integrated system is

useless without a fully integrated, automated mater-

ial handling system. In the manufacturing environment,

there are many automated material handling possi-

bilities. Currently, automated guided vehicles systems

(AGV systems), which include automated guided ve-

hicles (AGVs), are the state of the art, and are often

used to facilitateautomatic storageand retrieval systems

(AS/RS).

Traditionally, AGV systems were mostly used in

manufacturing systems. In manufacturing areas, AGVs

are used to transport all types of materials related to

the manufacturing process. The transportation network

connects all stationary installations (e.g., machines) in

the center. At stations, pickup and delivery points are

installed that operate as interfaces between the produc-

tion/storage system and the transportation system of the

center. At these points a load is transferred by, for ex-

ample, a conveyor from the station to the AGV and vice

versa. AGVs travel from one pickup and delivery point

to another on ﬁxed or free paths. Guide paths are deter-

mined by, for example, wires in the ground or markings

on the ﬂoor. More recent technologies allow AGVsto

operate without physical guide paths.

29.3.1 Network Modeling

for AGV Dispatching

In this Subsection, we introduce simultaneous schedul-

ing and routing of AGVs in a ﬂexible manufacturing

system (FMS) [29.38]. An FMS environment requires

a ﬂexible and adaptable material handling system.

AGVs provide such a system. An AGV is a material-

handling equipment that travels on a network of guide

paths. The FMS is composed of various cells, also

called workstations (or machines), each with a spe-

ciﬁc operation such as milling, washing or assembly.

Each cell is connected to the guide path network by

a pickup/delivery (P/D) point where pallets are trans-

ferred from/to the AGVs. Pallets of products are moved

between the cells by the AGVs. Assumptions consid-

ered are as follows:

1. AGVs only carry one kind of products at a time.

2. A network of guide paths is deﬁned in advance,

and the guide paths have to pass through all

pickup/delivery points.

3. The vehicles are assumed to travel at a constant

speed.

4. The vehicles can just travel forward, not backward.

5. As many vehicles travel on the guide path simulta-

neously, collisions are avoided by hardware and are

not considered herein.

6. At each workstation, there is pickup space to store

the operated material and delivery space to store the

material for the next operation.

7. The operation can be started any time after an

AGV took the material to come. And also the AGV

can transport the operated material from the pickup

point to the next delivery point any time.

Deﬁnition 1: A node is deﬁned as task T

,which

represents a transition task of the j-th process of job J

for moving from the pickup point of machine M

i, j−1

the delivering point of machine M

Deﬁnition 2: An arc can be deﬁned as many deci-

sion variables, such as, capacity of AGVs, precedence

constraints among the tasks, or costs of movement. Lin

et al. deﬁned an arc as a precedence constraint, and give

a transition time c



from the delivery point of machine

to the pickup point of machine M



on the arc.

Deﬁnition 3: We deﬁne the task precedence for

each job; for example, task precedence for three jobs

is shown in Fig.29.3.

The notation used in this Chapter is summarized as

follows. Indices: i, i



: index of jobs, i, i



=1, 2,...,n;

j, j



: index of processes, j, j



= 1, 2,...,n. Param-

eters: n: total number of jobs, m: total number of

machines, n

: total number of operations of job i, o

the j-th operation of job i, p

: processing time of op-

eration o

, M

: machine assigned for operation o

, T

Part C 29.3