Combining Heu is ics in
Assembly Sequence Planning
Ca melo DEL VALLE1, Miguel TORO1, Edua do F. CAMACHO2, Ra ael M. GASCA1
1Dep . Lenguajes y Sis emas In o má icos, Uni . Se illa, Spain
2Dep . Ingenie ía de Sis emas y Au omá ica, Uni . Se illa, Spain
Abs ac . Assembly Sequence Planning is ackled by modelling and sol ing a
planning p oblem ha conside s he execu ion o he plan in a sys em wi h mul iple
assembly machines. The objec i e o he plan is he minimiza ion o he o al
assembly ime (makespan). To mee his objec i e, he model akes in o accoun he
du a ions and esou ces o he assembly asks, he change o con igu a ion in he
machines, and he anspo a ion o in e media e subassemblies be ween di e en
wo ks a ions. In o de o sol e he p oblem, di e en heu is ics has been de ined
om wo elaxed model o i , one conside ing only he p ecedence cons ain s among
asks, and he o he one conside ing only he use o sha ed esou ces. F om hese
basic heu is ics, o he ones ha e been de ined, combining bo h ypes o in o ma ion
om he p oblem, so ha he e inemen p oduces subs an ial imp o emen s o e he
ini ial heu is ics.
1. In oduc ion
Assembly planning is a e y impo an p oblem in he manu ac u ing o p oduc s. I
in ol es he iden i ica ion, selec ion and sequencing o assembly ope a ions, s a ed as hei
e ec s on he pa s. The iden i ica ion o assembly ope a ions is done h ough he analysis
o he p oduc s uc u e, using in e ac i e planne s [1] [2], o au oma ically om a
geome ic and ela ional model o he assembly [3] and om a CAD model and o he non-
geome ic in o ma ion [4] [5]. The iden i ica ion o assembly ope a ions usually leads o he
se o all easible assembly plans. The numbe o hem g ows exponen ially wi h he
numbe o pa s, and depends on o he ac o s, such as how he single pa s a e
in e connec ed in he whole assembly, ep esen ed in he g aph o connec ions. In ac , his
p oblem has been p o ed o be NP-comple e [6].
The ep esen a ion o assembly plans is an impo an issue wi hin his scope. The
use o And/O g aphs o his pu pose [7] has became one o he mos s anda d ways o
ep esen ing all possible assembly plans. The esul is a ep esen a ion which is adequa e o
a goal-di ec ed app oach. Mo eo e , his s uc u e is mo e e icien in mos cases han o he
enume a i e ones [7] [8].
Two kinds o app oaches ha e been used o sea ching he op imal assembly plan.
One, he mo e quali a i e, uses ules in o de o elimina e assembly plans ha include
di icul asks o awkwa d in e media e subassemblies. A mo e quan i a i e app oach uses
an e alua ion unc ion ha compu es he me i o assembly plans. Se e al o hese
p oposals can be ound in [9] and [10].
The c i e ion ollowed in his wo k is he minimiza ion o he o al assembly ime
(makespan) o he plan execu ed in a sys em wi h mul iple machines [11]. To mee his
objec i e, a scheduling-based model is used [12], which akes in o accoun all ac o s
ha ing an e ec on he makespan: an es ima ion o he du a ion o asks; he esou ces used
o hem (machines and con igu a ions); he imes needed o changing ools in he obo s;
and he delays due o he anspo a ion o in e media e subassemblies be ween di e en
wo ks a ions.
The es o he pape is o ganized as ollows: Sec ion 2 desc ibes he assembly
sequence planning p oblem and he model p oposed. The de ails o he A* algo i hm a e
desc ibed in Sec ion 3. Sec ion 4 p esen s he basic heu is ics aken om wo elaxed
models o he p oblem, and Sec ion 5 shows how hese heu is ics a e combined in o de o
imp o e hei es ima ions. Some compa a i e esul s when using he di e en heu is ics a e
shown in Sec ion 6, and some inal ema ks a e made in he concluding sec ion.
2. Assembly Sequence Planning
The p ocess o joining pa s oge he o o m a uni is known as assembly. An assembly
plan is a se o assembly asks wi h o de ing amongs i s elemen s. Each ask consis s o
joining a se o sub-assemblies o gi e ise o an e e la ge sub-assembly. A sub-assembly
is a g oup o pa s ha can be assembled independen ly o o he pa s o he p oduc . This
wo ks supposes ha in an assembly ask he e a e wo ini ial sub-assemblies o o m a inal
one. An assembly sequence is an o de ed sequence o he assembly asks sa is ying all he
o de ing cons ain s. Each assembly plan co esponds o one o mo e assembly sequences.
An And/O g aph [7] is a ep esen a ion o he se o all assembly plans o a
p oduc . The O nodes co espond o sub-assemblies, he op node co esponding o he
whole assembly, and he lea nodes o he indi idual pa s. Each And node co esponds o
he assembly ask joining he sub-assemblies o i s wo O nodes below i p oducing he
sub-assembly o he O node abo e i . An And/O g aph consis s on se e al ees whose op
nodes a e he op node o he And/O g aph and whose lea nodes a e he lea nodes o he
And/O g aph. Each ee is associa ed o an assembly plan, and is e e ed o as an assembly
ee. An impo an ad an age o his ep esen a ion, used in his wo k, is ha he And/O
g aph shows how di e en assembly asks can be execu ed in pa allel. Figu e 1 shows an
example o his ep esen a ion, whe e O nodes a e ep esen ed as ec angles, and And
nodes a e ep esen ed as hype a cs.
This wo k is abou he selec ion o he bes assembly plan, ha is, one o he And/O
A B C D E
A B C D
A C D
A B A C A D C D B E
AB C D E
T1 T2
T3
T4
T5 T6
T7 T8 T9 T10 T11
Figu e 1. And/O g aph o p oduc ABCDE
ees o he And/O g aph. Mos o app oaches used up o now make his selec ion in a
planning phase in which nei he he assembly sys em, no how he assembly asks wi hin i
will be ma e ialized, is aken in o accoun .
This wo k akes in o accoun he physical ealiza ion o he assembly. I is assumed
ha he assembly asks co esponding o he And/O g aph ha e been e alua ed sepa a ely,
in o de o es ima e he esou ces necessa y o hei ealiza ion ( obo s, ools, ix u es...) as
well as hei app oxima e du a ion imes. Fo an And/O g aph wi h a la ge numbe o
nodes his is no an easy ask, and he help o a compu e -aided sys em is necessa y. The
nodes co esponding o asks which a e no ealizable a e elimina ed om he And/O
g aph, as he sub-assemblies which canno be pa o a solu ion.
An assembly plan can be de ined by means o he assembly asks ha o m he
successi e sub-assemblies un il he inal p oduc is made. An assembly ask is de ined om
he ini ial and inal sub-assemblies in ol ed. An assembly ask is de ined o be pe o med
in an assembly machine wi h a de e mined con igu a ion, and has an es ima ed du a ion. I
he e a e di e en ways (machine-con igu a ion-du a ion) o joining wo sub-assemblies o
o m ano he la ge sub-assembly, we e e o hose as di e en assembly asks, which
would co espond o addi ional And nodes in he And/O g aph.
The selec ion o he assembly plan is made h ough e alua ing he op imal
sequencing o hei asks, so ha we would be sol ing a he same ime a planning and
scheduling p oblem. In o de o e alua e mo e p ecisely he cos o he solu ions, i.e. he
o al assembly ime, o he ac o s ha e been aken in o accoun : he change o
con igu a ions in he machines and he anspo a ion o subassemblies be ween di e en
machines. The co esponding asks (ac ions) a e easily gene a ed and sequenced om he
se o assembly asks de ined by he sub-assemblies in ol ed in hem: o each wo
successi e assembly asks execu ed in a machine using di e en con igu a ions he e will
be an adequa e change o con igu a ion ask on he machine be ween hem; i a sub-
assembly is gene a ed by an assembly ask in a machine and i is equi ed o be used as an
ini ial sub-assembly by ano he assembly ask in ano he machine, he e will be a
anspo a ion ask o his sub-assembly om one machine o he o he one be ween he
execu ion o he wo assembly asks.
Since assembly plans and assembly sequences a e de ined using only he assembly
asks, some delays a e used o modelling bo h auxilia y asks: Δch (M, C, C') deno es he
ime needed o changing he con igu a ion o he machine M om C o C'; and, on he
o he hand, Δmo (SA, M, M') deno es he ime needed o anspo ing he subassembly SA
om machine M o machine M'.
The model p oposed supposes a well-dimensioned sys em, wi h a pe ec planning
when execu ing he assembly plan, so ha , when a pa would be equi ed in a machine o
execu ing an assembly ask, i will be p esen he e. The same canno be gua an eed o an
in e media e sub-assembly, because i could be buil in a machine and equi ed immedia ely
in ano he one o o m ano he subassembly.
In o de o an easie easoning, we will suppose in he es o he pape ha he
p ecedence cons ain s a e in he opposi e di ec ion, so ha we will e e o a ask p eceding
ano he one i he i s one appea s highe in he And/O g aph. This is as i we hink abou
he opposi e p oblem, ha o he disassembly. To ge he co ec solu ion o he p oblem,
we mus only e e se he sequence gi en by he algo i hm.
As men ioned abo e, wi h his model, he choice is no limi ed o he assembly plan,
bu also i can be speci ied when each assembly ask is o be ca ied ou in o de o
minimize he makespan (some assembly asks which could po en ially be ca ied ou in
pa allel ha e o be delayed because hey need common esou ces).
The esul s de i ed om his model can be used in di e en s ages o he whole
planning p ocess, om he design o he p oduc and o he manu ac u ing sys em, o he
inal execu ion o he assembly plan.
3. The A* Algo i hm
An algo i hm, based on he A* sea ch [13], has been de eloped o sol e he p oblem s a ed
in he p e ious sec ion. The algo i hm has wo well-di e en ia ed pa s: one o hem
conside s he sequen ial execu ion o assembly asks imposed by he p ecedence cons ain s
de ined in he And/O g aph, i.e. in he high pa o he And/O g aph. The o he sol es he
pa allel execu ion o assembly asks ( he ep esen a ion h ough he And/O g aph allows a
na u al s udy o his s age). This is ac ually he mos complex sec ion, because he execu ion
o asks on one side o he global assembly is no independen o he es , and can in luence
he execu ion o asks in he o he pa o assembly.
The algo i hm s a s om he oo o he And/O g aph. The sequen ial pa o he
algo i hm is used while he asks conside ed in ol es only one non- i ial sub-assembly
below he co esponding And node. I is he case o asks T1 and T4 in Figu e 1. When an
assembly ask akes wo non- i ial sub-assemblies ( o example, ask T2 in Figu e 1), he
pa allel pa o he algo i hm is used o ob aining he solu ion om he node in he sea ch
ee. In ha momen , he algo i hm gene a es all he assembly ees below ha And node.
Each o hem is used o ob aining an op imal o de o he asks included in hem, h ough
a sepa a e A* algo i hm. The global algo i hm o de s p e iously all hese ees using an
es ima ion o he ime needed o he execu ion o i s asks, so ha no all he ees mus
been comple ely sol ed, because o he p uning o he sea ch.
In he sea ch ee o he algo i hm, a node ep esen s a s a e co esponding o he
execu ion o he se o assembly asks ha ha e been included in o he solu ion in he
p e ious s eps (wi h he co esponding auxilia y asks –see Sec ion 2). The o de o
including assembly asks speci ies he o de o execu ion o hem. So, an assembly ask will
no be included un il all i s p edecesso assembly asks in he And/O g aph ha e been
included. This s a egy allows e i ying he p ecedence cons ain s o he p oblem. The s a e
o a node n can be ob ained also h ough he se o assembly asks cand(n) ha can be
included in he nex expansion s ep, deno ed candida es. Fo each candida e assembly ask
T we ake he ea lies s a ime, es (T), i i we e in oduced in he nex s ep. The
desc ip ion o he s a e o n is comple ed wi h he ime co esponding o he las used o
each machine M due o he asks ha ha e been included, las Time(n, M), and he las
con igu a ion used in each machine, las Con (n, M). An expansion s ep o he algo i hm
co esponds o selec ing a candida e assembly ask T, and including i in he pa ial solu ion
as i is execu ed s a ing a es (T), ecalcula ing he s a e o he successo node and
including in he se o candida e asks he successo assembly asks o T.
The objec i e unc ion, (n), is gi en by he ime needed o he execu ion o he
asks included in n, g(n), plus an es ima ion o he ime needed o comple e a solu ion, h(n).
Func ion g(n) can be de ined as:
() ( )
()
()
() max max (, ), max (, )
ii
ii
Tcandn M machines
gn es nT las TimenM
∈∈
= (1)
Some di e en heu is ic unc ions can be de ined o h(n). In o de o main ain he
admissibili y o he A* algo i hm, h(n) mus be an op imis ic es ima ion o he emaining
ime o an op imal solu ion om n. In o de o calcula e p ope ly he objec i e unc ion
om g and h, wo di e en ypes o slack ha e been de ined, one o he candida e asks,
e(n, T) = g(n) – es (n, T), and ano he one o he machines, e(n, M) = g(n) – las Time(n, M).
4. Basic Heu is ic Func ions
Fo he sequen ial pa o he algo i hm, h(n) can be de ined as:
()
()
() min ( )
ii
Tn O n
hn hsT
∈
= (2)
n O (n) deno ing he non i ial O nodes below he las ask in oduced in n, and
() ()
12
() ()
() () max min (),min ()
ii
ii
TO T TO T
hs T du T hs T hs T
∈∈
⎛⎞
⎜⎟
⎝⎠
=+ (3)
whe e du (T) is he du a ion o ask T and O 1(T) and O 2(T) a e he O nodes
co esponding o he ini ial sub-assemblies in ol ed in ask T. In hese exp essions, T∈O
ep esen s he asks T immedia ely below he O node in he And/O g aph.
No ice ha only he p ecedence cons ain s ha e been used in he de ini ion o h(n)
o he sequen ial pa o he algo i hm. Fo he pa allel pa , he cons ain s due o he use
o esou ces can be aken in o accoun . Because o he sepa a ion o he assembly ees, o
each sub-p oblem all asks a e de ined, i.e. he e a e no al e na i e asks, and hen he
amoun o usages o he di e en esou ces a e known.
Two basic heu is ic unc ions can be de ined o he pa allel pa o he A*
algo i hm, conside ing sepa a ely he wo ypes o cons ain s: he p ecedence o asks, and
he use o esou ces.
4.1 The heu is ic unc ion h1: p ecedence o asks
I co esponds o an es ima ion o he ime emaining i he in e dependencies be ween
di e en b anches in he ee a e no aken in o accoun . I is looked a only in dep h. I can
be de ined wi h ollowing equa ions:
()
()
11
()
() max0, max ( ) (, )
i
ii
cand n
T
hn hT enT
∈
=− (4)
()
()
11
()
() () max () ,
i
imo i
suc TT
hT du T hT TT
∈
=+ +τ (5)
() ( ) ( )
()
,max,(),(), (),(),()
mo i i mo i i
TT TMT CT saT MT MTτ=τ Δ (6)
()
)
()
()
1
() 1
(, , ) max0,max () , (), () ()
i
ii
TsucT
TMC hT TMT CT hT
∈
τ= +τ − (7)
In he abo e exp essions, M(T) and C(T) a e he machine and con igu a ion necessa y o
he execu ion o he assembly ask T. τ(T, M, C) is he added delay, due o he ac ha he
con igu a ion C is being used by machine M in ask T and successo s, because o he
necessa y changes in con igu a ion. The equa ion (7) de ines τ(T, M, C) when M
≠
M(T). In
he case M=M(T), τ(T, M, C) is de ined as Δch (M, C(T), C) ( ha could be ze o i C=C(T)).
Finally, τmo (T, T') is he delay conside ing he possible anspo a ion o he in e media e
subassembly gene a ed be ween he execu ion o T and T', and ha o he possible change
o con igu a ions.
No ice ha h1(T) does no depend on he expansion nodes, so ha i can be
calcula ed o each ask p io o using he A* algo i hm o he assembly ees.
4.2 The heu is ic unc ion h2: use o esou ces
I co esponds o an es ima ion o he ime needed i only he emaining usage imes o each
machine a e aken in o accoun , u he supposing he numbe o changes o con igu a ion
o be a a minimum. I can be de ined as ollows:

()
22
() max (, ) (, )
i
ii
Mmachines
hn hnM enM
∈
=− (8)
whe e h2(n, Mi) is he minimum ime o use o machine Mi wi hou conside ing he ask
p ecedence cons ain s. I each con igu a ion is associa ed wi h only one obo , he
calcula ion o h2(n, M) is equi alen o he a eling salesman p oblem, when conside ing
he con igu a ions used by he asks ha s ill ha e no been included in n as he ci ies and an
o igin co esponding o he las -used con igu a ion in he machine M:
()
22
()
(, ) ( , ) , ( )
ji
ij ch
CMTcandn
hnM hTC n M
∈∈
⎛⎞
=+#Δ
$%
$%
&'
!! (9)
wi h h2(T, C) he emaining ime o usage o con igu a ion C by ask T and i s successo s.
The e m
()
,()
ch
nM∑Δ e e s o he ime needed o he changes o con igu a ion. In he
usual case ha imes o change o con igu a ions do no depend on he ypes o
con igu a ion, i can be calcula ed easily. Wi hou any p ecedence in o ma ion, an in o de
o main ain he admissibili y o he heu is ic, i mus be supposed ha each emaining
con igu a ion will be es ablished only once.
5. Combina ion o heu is ics
The heu is ics de ined in he las sec ion ake in o accoun di e en elemen s o he
p oblem: h1 uses he p ecedence cons ain s aken om he And/O g aph in o de o
es ima e he mos un a ou able pa h om an assembly ask o a lea assembly ask,
supposing ha asks om di e en b anches, i.e. no ela ed by p ecedence cons ain s, can
be execu ed independen ly, ha is, igno ing i hey use he same machine. In he o he way,
h2 igno es he p ecedence cons ain s and calcula es he o al usage ime o each machine.
The wo heu is ics ha e di e en e ec s and a e incompa able. Depending on he machines
used and he s uc u e o he And/O g aph, one o hem can ob ain a be e es ima ion han
he o he one. Fo example, i he e is only one machine, he e is no pa allel execu ion o
asks, and h2 will ob ain a mo e accu a e es ima ion. In he o he way, i each assembly ask
is execu ed in a di e en machine, h1 collec s all he in o ma ion abou he p oblem and i s
es ima ion is accu a e.
In he p e ious sec ion h1 and h2 we e de ined ela ed o n, he expansion node. Bu
he na u e o he wo heu is ics a e di e en : h1(n) is he maximum o he es ima ions o he
candida e asks, and h2(n) adds he ime o usage o machines o all he candida e asks. In
o de o combine p ope ly he in o ma ion om he wo heu is ics, we will use hei
es ima ions e e ed o he candida e asks. Fo h1 we ha e h1(T) de ined in equa ions (5) o
(7). Fo h2 we can de ine h2(T) in a simila way han in (9):
() ( )
22 2
() max (, ) max (, ) , ( )
ji
ijch i
machines machines CM
hT hTM hTC T M
∈
⎛⎞
⎛⎞
==⎧+⎢Δ⎫
⎧⎫
⎧⎫
⎧⎫
⎨⎬
⎨⎬
⎢ (10)
whe e
()
,()
ch
TM⎢Δ e e s o he ime needed o he changes o con igu a ion in M o
he execu ion o T and i s successo s.
5.1 Heu is ic h3: e ining h1 using h2
As h2(T) could be a be e es ima ion han h1(T), bo h being op imis ic, he i s could be
aken in o accoun in o he calcula ion o he second, since in he ecu si e exp ession o
h1(T) i is equi ed an es ima ion o he ime needed o he execu ion o all he asks in he
sub ee below T. The new heu is ic ha i is ob ained, h3, is de ined based on equa ion (5),
subs i u ing h1 o h3 and conside ing h2, as indica ed. This way, a be e es ima ion due o
h2 is p opaga ed owa ds he p edecesso asks in he p ecedence ee. So, h3(T) is de ined
as:
()
()
()
332
()
() max () max () , , ()
i
imo i
TsucT
hT du T hT TT hT
∈
=++τ (11)
The de ini ion o h3(n) is simila o ha o h1(n), (equa ion (4)), esul ing a mo e
in o med heu is ic han h1(n). Howe e , h3(n) does no in alida e h2(n), because he las
conside s all candida e asks in he expansion node n.
5.2 Heu is ic h4: es ima ing he in e als o machine usages
In he de ini ion o h3(T), he ime o usage o he mos un a ou able machine, gi en by
h2(T), is supposed ha can ake place du ing he execu ion o all he asks o he sub ee
whose oo is T. In some cases, i could be de e mined, by an analysis o he p ecedence
ee, ha he in e al o use is smalle , so ha he es ima ion o he o al ime o he
execu ion o all asks in he ee could be imp o ed e en mo e. Two new a iables a e
de ined, δb and δe, indica ing he in e als, a he s a and he end espec i ely, o he
execu ion o all he asks in he ee, in which he machine is no used.
The calcula ion o δb is done using i s ecu si e de ini ion:
()
()
()
0i ()
(, ) () min (, ) max (), (,) i ()
i
bbi mo ch i
TsucT
M
MT
TM du T T M T T M M T
∈
=
⎧
⎪
δ=
⎨ʹ
+δ+Δ⋅Δ ≠
⎪
⎩
(12)
whe e
()
() ( ), ( ), ( )
mo mo i i
s
aT M T M TΔ⋅≡Δ and ( , )
ch i
TT
ʹ
Δ ep esen s he delay due o he
possible change o con igu a ion be ween he execu ion o Ti and T, de ined by
()
(), (), () i () ()
(,) 0i ()()
ch i i
ch i
i
M
TCTCT MT MT
TT
M
TMT
Δ=⎧
ʹ
Δ=
⎨≠
⎩ (13)
In o de o ob ain a consis en de ini ion, we ake (,)
bTMδ=∞ when ()
M
MT≠
and ()suc T =∅. This way, when a machine is no used by any ask belonging o a
p ecedence sub ee, he alue o δb will be in ini e.
In he o he way, δe is calcula ed by means o i s ecu si e de ini ion:
()
()
4
()
()
min ( , ), ( ) ( ) si ( )
(, ) min ( , ) si ( )
i
i
ei
TsucT
e
ei
TsucT
TM hT du T M MT
TM TM M MT
∈
∈
⎧δ− =
⎪
δ=
⎨δ≠
⎪
⎩
(14)
Again, o a consis en de ini ion, we ake ( , )
eTMδ=∞ when ()
M
MT≠ and
()suc T =∅.
The de ini ion o he new heu is ic h4(T) has he same s uc u e han h3(T), excep
ha ins ead o using h2(T) alone, we ake in o accoun δb and δe. Mo eo e , i is necessa y o
sepa a e he es ima ions o h2(T) o each machine, using h2(T, M):
() ( )
()
(
()()()
()
)
2
44
()
2
(, )0
() max () max , ,
max , , ,
i
i
imo i
TsucT
ib ie i
hTM
hT du T h T TT
hTM TM TM
∈
≠
=+ +τ
+δ+δ
(15)
The de ini ion o h4(n) is simila o ha o h1(n), (equa ion (4)), esul ing again a
mo e in o med heu is ic han h1(n) and h3(n), bu no necessa ily be e han h2(n), because
he las conside s all candida e asks in he expansion node n.
5.3 Heu is ic h5: conside ing all machines in h1, h3 and h4
In he de ini ion o he heu is ics h1, h3 and h4 e e ing o a ask T we ha e no aken in o
accoun he use o all he di e en machines, bu only ha o he machine used o he ask
T. In o de o ob ain his es ima ion we mus de ine a new unc ion ela ed o he maximum
delay ha can be done in he use o each machine. Based on h1, he new unc ion, τ'(T, M,
C), is de ined as
()
()
()
11
()
,(), i ()
(, , ) max ( ) , , ( ) i ( )
i
ch
ii
TsucT
M
CT C M MT
TMC hT TMC hT M MT
∈
Δ=
⎧
⎪
ʹ
τ=
⎨ʹ
+τ − ≠
⎪
⎩
(16)
and co esponds o he ime be o e he execu ion o T a which he machine M mus ha e
con igu a ion C in o de o he execu ion o T and i s successo s does no inish a e h(T).
No ice ha his de ini ion is simila o ha o τ(T, M, C) (equa ion (7)), bu now we can
ha e nega i e alues, indica ing in ha case a spa e ime o an e en ual change o
con igu a ion ha could be necessa y, o simply ha i is possible o ha e he con igu a ion
C in M a e he execu ion o T has s a ed, wi hou al e ing he o al execu ion ime o T
and i s successo s.
The same ideas used in de ining he heu is ics h3 and h4 can be employed in o de o
ha e a be e es ima ion o τ' when M≠M(T), p ese ing he same exp ession when
M=M(T). This way, o h3, τ'(T, M, C) can be de ined, when M≠M(T), as
() ()
()
(
)
33
()
23
,, maxmax () ,, (),
( ) ( , , ) ( )
i
ii
TsucT
ch
TMC hT TMC hT
hT TMC hT
∈
ʹʹ
τ= +τ−
ʹʹ
+Δ −
(17)
whe e
()
2
2
2
(, )0
0i (,)0
(, , ) min ( , , ) i ( , ) 0
j
ch
ch j
hTC
hTC
TMC MCC h TC
>
>
⎧
⎪
ʹʹ
Δ=
⎨Δ=
⎪
⎩
(18)
ha shows ha i will be needed a change o con igu a ion i C is no used below T.
Fo h4, τ'(T, M, C) can be de ined, when M≠M(T), as
() ()
()
(
)
44
()
24
,, maxmax () ,, (),
( ) ( , ) ( , , ) ( )
i
ii
TsucT
ech
TMC hT TMC h T
hT TM TMC hT
∈
ʹʹ
τ= +τ−
ʹʹ
+δ+Δ −
(19)
The new heu is ic h5(n) is de ined as
()
()
()
()
()
()
5()machines
() max max , , , ,
i
iij j j
Tcandn
hn hT TMlas Con nM enM
∈
ʹ
=+τ −
(20)
whe e h e e s o he heu is ic used in he de ini ion o τ', gi ing h ee di e en heu is ic
unc ions, named h51, h53 and h54.
6. Compa a i e esul s
The e a e di e en ac o s ha a ec he complexi y o he p oblem p oposed. Some o he
mo e impo an a e he numbe o pa s, he size and s uc u e o he And/O g aph, and he
dis ibu ion o alues o he du a ions and esou ces associa ed o he asks.
As i is known, one o he mos impo an p oblems in applying A* algo i hms is he
amoun o memo y was ed. In o de o limi his consump ion, he algo i hm was adap ed so
ha i used a dep h- i s sea ch pe iodically o inding a new solu ion whose alue could be
used o p uning he sea ch ee. Ano he imp o emen was done abou de ec ing
symme ies, so ha edundan nodes a e a oided in he expansion.
The esul s shown in Table 1, a he signi ican abou he beha iou o he heu is ics
ha ha e been de ined, a e based on a hypo he ical p oduc wi h 30 pa s, wi h 396 O
nodes and 764 And nodes in he And/O g aph, so ha he numbe o legal linea sequences
is abou 1021. Each ow o he able shows he esul s o 40 di e en p oblems sol ed using
he co esponding heu is ic, conside ing 10 di e en combina ions on du a ions and
esou ces among asks, o each o ou condi ions in he esou ces used: 2 and 4 machines
and 2 and 4 con igu a ions/machine.
Table 1 shows, apa om he numbe o nodes and he ime spen by he algo i hm,
how many imes he op imal solu ion was ound by a dep h- i s mo emen (N-D ), how
many imes he algo i hm did no ind he op imal solu ion in 30 seconds, when he
a ailable memo y was exhaus ed (N-F), and he e o a e. The esul s show he successi e
imp o emen s ha he heu is ics ha e ob ained. When analysing he esul s, i mus be
aken in o accoun ha he op imal solu ion can ha e been ound h ough a dep h- i s
mo emen , ha is ca ied ou om he bes node jus when his s a egy is used, ha
explains he appa en con adic ion in he compa a i e esul s be ween di e en heu is ics,
since he nodes used o he dep h- i s mo emen s a e (su ely) di e en in each case.
Ano he imp o emen came om he combined use o he heu is ic h2, o addi i e na u e,
wi h he o he s, which conside he mos un a ou able candida e ask o he calcula ion o
he co esponding es ima ion o each expansion node.
7. Conclusions
Di e en heu is ics ha e been de ined o selec ing op imal assembly sequences. The i s
wo ones a e based on bo h elaxed models o he p oblem, each one conside ing only a ype
o cons ain s, one ela ed o he p ecedence cons ain s, and he o he one o he use o
sha ed esou ces. F om hem, o he heu is ics ha e been de ined, combining bo h ypes o
in o ma ion, ob aining successi e imp o emen s, as i is shown in he esul s ob ained.
Table 1. Compa a i e esul s o he heu is ics.
Nodes isi ed Time (ms)
Heu is ic A e Max Min A e Max Min N-D N-F %
E o
h1 30297 93376 32 13224 30930 0 11 15 0,985
h2 4797 42775 32 668 6420 0 9 0 0,000
h3 26414 88102 32 12408 30810 0 11 14 1,114
h4 27046 87456 32 13321 30920 0 11 15 1,279
h51 28745 92326 32 12892 31420 0 11 14 0,909
h53 25641 81332 32 12598 30820 0 16 15 1,233
h54 21698 54860 32 11462 30420 0 17 13 1,279
max(h1, h2) 6008 71585 32 1453 30050 0 9 1 0,062
max(h3, h2) 3267 23167 32 535 4230 0 8 0 0,000
max(h4, h2) 4450 63996 32 1266 30050 0 6 1 0,041
max(h51, h2) 5925 70432 32 1408 30150 0 8 1 0,062
max(h53, h2) 2724 18254 32 465 4280 0 9 0 0,000
max(h54, h2) 2459 18165 32 418 4280 0 8 0 0,000