Task Scheduling Op imiza ion on En e p ise Applica ion
In eg a ion Pla o ms Based on he Me a-heu is ic Pa icle
Swa m Op imiza ion
Daniela F. Sella o
Unijuí Uni e si y
Ijuí, RS
[email p o ec ed]
Ra ael Z. F an z
Unijuí Uni e si y
Ijuí, RS
[email p o ec ed]
Inma He nández
Uni e si y o Se ille
Espanha
[email p o ec ed]
Fab icia Roos-F an z
Unijuí Uni e si y
Ijuí, RS
[email p o ec ed]
Sand o Sawicki
Unijuí Uni e si y
Ijuí, RS
[email p o ec ed]
ABSTRACT
Companies seek echnological al e na i es ha p o ide compe i i-
eness o hei business p ocesses. Among hese al e na i es, he e
a e in eg a ion pla o ms ha allow you o connec applica ions o
you so wa e ecosys ems. These ecosys ems a e o en composed
o local applica ions and cloud compu ing se ices, such as SaaS
and PaaS, and s ill, in e ac wi h social media. In eg a ion pla o ms
a e specialized so wa e ha allows you o design, execu e and
moni o in eg a ion solu ions, which connec unc ionali y and
da a om di e en applica ions. In eg a ion pla o ms ypically
p o ide a speci ic domain language, de elopmen oolki , un ime
engine, and moni o ing ool. The e iciency o he engine in sche-
duling and pe o ming in eg a ion asks has a di ec impac on
he pe o mance o a solu ion and his is one o he challenges
aced by in eg a ion pla o ms. Ou li e a u e e iew has iden i ied
ha in eg a ion engines adop ask scheduling algo i hms based
on he ex i Fi s -In-Fi s -Ou discipline, which may be ine icien .
The e o e, i is app op ia e o seek a ask scheduling algo i hm
ha op imizes engine pe o mance, p o iding a posi i e impac on
he pe o mance o he in eg a ion solu ion in di e en scena ios.
This a icle p oposes an algo i hm o ask scheduling based on he
me a-heu is ic op imiza ion echnique, which assigns he asks o
he compu a ional esou ces, conside ing he wai ing ime in he
queue o eady asks and he compu a ional complexi y o Each ask
in o de o op imize he pe o mance o he in eg a ion solu ion.
CCS CONCEPTS
•So wa e and i s enginee ing → So wa e pe o mance
;
Cloud
compu ing; Real- ime schedulabili y;␣
KEYWORDS
In eg a ing En e p ise Applica ions, Op imiza ion, Cloud compu-
ing, Run ime Sys em, Task Scheduling Algo i hm.
1 INTRODUÇÃO
As emp esas possuem um ecossis ema de so wa e compos o po
di e sas aplicações que ge almen e são desen ol idas in e namen e
ou adqui idas de e cei os. O a anço das ecnologias de desen ol-
imen o de aplicações e a inco po ação de se iços de so wa e
disponí eis na in e ne êm deixado os ecossis emas de so wa e
ainda mais he e ogêneos. Os p ocessos de negócio de uma emp esa
p ecisam se supo ados po um conjun o de aplicações e se iços
de so wa e que in eg am seu ecossis ema, po ém, equen emen e,
ais aplicações e se iços não es ão p epa ados pa a abalha de
o ma conjun a. A In eg ação de Aplicações Emp esa iais (EAI) é o
campo de es udo que o e ece me odologias, écnicas e e amen as
pa a que os p ocessos de negócio uncionem de o ma sinc onizada,
p omo endo epos as ápidas e con iá eis.
As pla a o mas de in eg ação são so wa es especializados que
pe mi em p oje a , execu a e moni o a soluções de in eg ação, as
quais conec am uncionalidades e dados de di e en es aplicações.
Uma solução de in eg ação implemen a um luxo de in eg ação
compos o po dis in as a e as a ômicas que são execu adas ao
longo desse luxo. G ego Hophe e Bobby Wool [
16
] documen a-
am um conjun o de pad ões de in eg ação que em inspi ado o
desen ol imen o de pla a o mas de in eg ação de código abe o
e que po sua ez o ganizam o luxo de in eg ação seguindo uma
a qui e u a Pipes&Fil e s [
3
]. Usualmen e, essas pla a o mas o ne-
cem uma linguagem de domínio especí ico, um ki de e amen as
de desen ol imen o, um mo o de execução e uma e amen a de
moni o amen o. A linguagem de domínio especí ico possibili a a
desc ição de modelos concei uais pa a soluções de in eg ação. O
ki de desen ol imen o é um conjun o de e amen as de so wa e
que pe mi e a implemen ação de soluções, ou seja, ans o ma uma
solução concei ual em código execu á el. O mo o p opo ciona odo
o supo e necessá io à execução das soluções de in eg ação. A e a-
men a de moni o amen o é u ilizada pa a de ec a e os que possam
oco e du an e a execução de soluções de in eg ação. O mo o é o
esponsá el pela execução das soluções de in eg ação [14].
As a e as da solução de in eg ação são execu adas po meio de
ecu sos compu acionais p esen es no mo o de execução, den e
os quais es ão as h eads de execução. Nes e con ex o, as h eads
são usadas pa a p opo ciona que as a e as sejam execu adas de
o ma simul ânea, po meio da p og amação mul i h eads [
8
,
27
].
Nesse ipo de p og amação, a c iação de h eads pode impac a o
desempenho da execução de uma solução de in eg ação.
Um algo i mo de agendamen o de a e as inadequado aumen a o
empo de execução, impac ando o desempenho da solução de in e-
g ação. A abo dagem mais comum é a con a ação de mais ecu sos
compu acionais, po ém essa al e na i a é inancei amen e one osa
e nem semp e iá el. Nossa e isão da li e a u a iden i icou que os
mo o es de in eg ação ado am como polí ica de agendamen o de
a e as as polí icas de p io idade e a Fi s -In-Fi s -Ou (FIFO). Há
p opos as de algo i mos de agendamen o de a e as pa a máquina
i uais em sis emas dis ibuídos [
2
,
23
], po ém não o am iden-
i icadas p opos as que oquem na o imização de desempenho de
mo o es de execução de pla a o mas de in eg ação de sis emas.
O agendamen o de luxo de abalho em sido amplamen e es u-
dado ao longo dos anos, nos quais os algo i mos se concen am na
ge ação de soluções ap oximadas ou quase ó imas, po se a a de
um p oblema não polinomial di ícil [
26
]. Pandey e al. [
22
] p opõem
um algo i mo baseado em PSO pa a minimiza o cus o de execução
de um único luxo de abalho enquan o equilib a a ca ga da a e a
nos ecu sos disponí eis. Wu e al. [
29
] usam PSO pa a p oduzi
um agendamen o quase ideal, se p eocupando em minimiza cus o
e empo, mas assume que um conjun o limi ado de ecu sos, sem
le a em con a a elas icidade p opo cionada com a compu ação em
das nu ens. O algo i mo de Byun e al. [
6
] es ima o núme o ó imo
de ecu sos que p ecisam se alocados pa a que o cus o de execução
de um luxo de abalho seja minimizado. Sua abo dagem ap o ei a
a elas icidade dos ecu sos da nu em, mas não conside a a na u eza
he e ogênea dos ecu sos compu acionais.
A con ibuição des e abalho é a aplicação da me a-heu ís ica
Pa icle Swa m Op imiza ion (PSO) pa a o con ex o dos mo o es
de execução, nos quais as polí icas de agendamen o ado adas, não
conside am o empo de espe a na ila de a e as p on as, nem a com-
plexidade compu acional das a e as. PSO é ácil de implemen a e
exis i em poucos pa âme os pa a se em ajus ado, adequando-se ao
p oblema de encon a melho agendamen o das a e as. Classi ica-
se como uma pesquisa explo a ó ia, a medida que busca um mé odo
mais e icien e do que os exis en es, na esolução do p oblema. Um
esumo com ideias iniciais pa a esse abalho oi ap esen ado em
um seminá io de pesquisa [
25
], e o p esen e a igo as discu e de
o ma mais ampla e comple a a p opos a de um algo i mo que busca
o mapeamen o ó imo das a e as pa a os pools de h eads.
O es o des e a igo es á o ganizado como segue. A Seção 2 ap e-
sen a a o mulação do p oblema. A Seção 3 desc e e sucin amen e
a écnica PSO. A Seção 4 expõe a abo dagem p opos a. E a Seção 5
ap esen a nossas conclusões e pe spec i as de abalhos u u os.
2 FORMULAÇÃO DO PROBLEMA
Numa solução de in eg ação, baseada no es ilo a qui e u al Pi-
pes&Fil e s [
3
], os pipes são ep esen ados po canais de mensagens
e os il e s po a e as a ômicas que implemen am um pad ão de in e-
g ação conc e o e p ocessam dados encapsulados em mensagens. A
Figu a 1 mos a o modelo concei ual de uma solução de in eg ação
pa a o p oblema Ca é, in oduzido po G ego Hohpe [
17
] mode-
lado com Gua aná [
14
]. O modelo concei ual pode se ep esen ado
Figu a 1: Solução de in eg ação Ca é
como luxos de abalho modelados como G a os Di ecionados Ací-
clicos, de inidos po W(T,E), onde
T={ 1, 2, .. n}
é o conjun o de
a e as e
E
é o conjun o de a es as di ecionadas. Uma a es a
eij
da
o ma
( i, j)
exis e, se hou e uma dependência de dados en e
i
e
j
, onde
i
é a e a pai de
j
e
j
é a e a ilha de
i
. Logo, uma
a e a ilha não pode se execu ada a é que odas as suas a e as pai
es ejam concluídas. Conside a-se que o mo o de execução o e ece
uma a iedade de ecu sos compu acionais pa a execução das a e-
as da solução de in eg ação. Essa a iedade de ecu sos é de inida
po pool de h eads, com di e en es núme os de h eads, onde uma
h ead é a unidade básica de p ocessamen o. Assim, assume-se que
um mo o de execução pode e mais de um pool de h eads e que
o núme o de h eads em cada um pode se di e en e, ou seja, um
pool com uma quan idade x h eads e ou o com uma quan idade
y. Conside a-se ainda, que um mo o de execução em uma quan-
idade limi ada de ecu sos compu acionais
δ
, sendo um ecu so
compu acional
Pool
, um pool de h eads que em um ipo
Pooli
, uma
capacidade de p ocessamen o
PPoolj
. O ipo di e encia os pools, a
capacidade de p ocessamen o é a quan idade de h eads do pool. A
capacidade de memó ia não é a ada; assume-se que é su icien e
pa a execu a as a e as do luxo de abalho. Assume-se que pa a
cada ipo de ecu so, a capacidade de p ocessamen o é de inida em
e mos de ins uções po ciclo (IPC), que pode se es imada [
1
]. Es a
in o mação é usada no algo i mo, pa a calcula o empo de execução
de uma a e a em um de e minado pool de h eads
Pool
. A a iação
do desempenho pode se modelada pelo ajus e da capacidade do
Pool
e in oduzindo uma deg adação de desempenho
deдPoolj
[
23
].
O empo de execução
TEPoolj
i
da a e a
i
em um
Pool
de ipo
Poolj
é es imado pelo amanho
Tam i
da a e a em ins uções po ciclo
(IPC), calculado pela Equação 1.
TEPoolj
i
=Tam i/(PPoolj∗ (1−degPoolj)) (1)
O empo médio de espe a na ila de a e as
TFieij
é de inido como
o empo pa a ans e i dados en e uma a e a pai
i
e sua a e a
ilha je assume-se que ele pode se moni o ado e medido.
Finalmen e, o empo o al de p ocessamen o
TPPoolj
i
de uma
a e a em um
Pool
é calculado na Equação 2, onde k é o núme o
de a es as,
i
é uma a e a pai e
sk
ep esen a o empo gas o pelo
mo o na oca de pool de h eads, de manei a que
sk
= 0, quando
ie jsão p ocessadas no mesmo pool esk= 1, caso con á io.
TPPoolj
i
=TEPoolj
i
+(
k
Õ
1
TFij +sk)(2)
O obje i o é encon a um agendamen o de a e as que possibili e
execu a as a e as da solução de in eg ação em pools de h eads do
mo o de execução, minimizando o empo o al de execução e sem
aumen a a quan idade de ecu sos compu acionais. O agendamen o
de a e as é de inido po
A=(R,M,TR,TTE)
, sendo
R
um conjun o
de ecu sos;
M
o mapeamen o de a e as em ecu sos,
TR
,
TR =
|R|=n
, o o al de ecu sos,
TTE
o empo o al de execução. Um
exemplo é mos ado na Figu a 2, ep esen ando o agendamen o pa a
o luxo de abalho, em que cada uma das qua o a e as é mapeada
pa a se execu ada po um dos ês ecu sos disponí eis, e onde as
a e as pais são execu adas an es das sua a e as ilhas, man endo
assim a dependência dos dados.
R={ 1, 2, ..., n}
é o conjun o de
Figu a 2: Agendamen o pa a o wo k low do Ca é.
ecu sos (pools de h eads) do mo o de execução, onde cada ecu so
i
em associado a ele um
Pool
do ipo
Pooli
, um empo de início
es imado pa a alocação do ecu so es imado
TIni i
. e um empo
de inalização es imado
TFim i
. M ep esen a um mapeamen o
pa a cada uma das a e as do luxo de abalho e é cons i uído po
uplas
m j
i
=( i, j,T Ini i,T Fin i)
, signi icando que a a e a
i
se á
execu ada pelo ecu so
j
, com o início da execução agendado pa a
TIni i
e p e isão de é mino em
TFin i
. A Equação 3 mos a como
o empo o al de execução TTE é calculado:
TTE =max{T Fim i: i∈T}(3)
Assim, o p oblema pode se o mulado como: encon a um agen-
damen o
A
com o meno empo o al de execução
TTE
da solução de
in eg ação, sem excede um alo p é-de inido pa a o o al de ecu sos
TR. Essa o mulação é ep esen ada pela Equação 4:
MinimizeTTE (4)
sujei o a TR ≤δ
3 PARTICLE SWARM OPTIMIZATION
Pa icle Swa m Op imiza ion (PSO) oi in oduzido po Kennedy e
Ebe ha em 1995 [
10
], e oi inspi ado no compo amen o social de
o ganismos biológicos, mais especi icamen e na habilidade de algu-
mas espécies de animais de abalha em conjun o pa a localiza
boas egiões com on es de alimen o, assim como oco e em ca du-
mes e em bandos de pássa os [
5
]. Em ou as pala as, é baseado
em um enxame de pa ículas (Pa icle Swa m) que se mo em pelo
espaço e se comunicam pa a de e mina uma di eção de busca ideal.
O PSO em melho desempenho compu acional pa a es e ipo de
p oblema de o imização de unções não-linea es de al a dimensiona-
lidade com a iá eis con ínuas, do que ou os algo i mos [
4
,
5
,
10
] e
em menos pa âme os pa a ajus a , acili ando sua implemen ação.
O PSO em sendo u ilizado com sucesso na solução de p oblemas
da ciência e da engenha ia de ido à sua simplicidade, e icácia e
obus ez [
2
,
4
,
11
,
15
,
21
,
23
,
26
,
28
]. Ap esen a como des an agens,
a necessidade de in o mação do omado de decisão, pa âme os
di íceis de ajus a , e ainda incapacidade de alcança a F en e de Pa-
e o, p incipalmen e em p oblemas com mul imodalidade, aqueles
com múl iplas soluções ó imas, onde algumas podem se melho-
es soluções globais e ou as melho es soluções locais [
12
], po ém
adap a-se ao p oblema abo dado.
Cada pa ícula
i
do enxame
S
é ep esen ada po sua posição e
sua elocidade. A posição é um e o de
n
dimensões, cujos compo-
nen es ep esen am os pa âme os da unção obje i o. As pa ículas
con olam a sua melho posição
pbes
e a melho posição global
дbes , a melho solução conhecida den o de sua izinhança.
Inicialmen e, as pa ículas do enxame possuem posições alea ó-
ias no espaço de busca, obedecendo uma dis ibuição de p obabili-
dade uni o me. Pos e io men e, a posição
xi( )
de cada pa ícula
i
na i e ação
é modi icada po uma elocidade es ocás ica
i( )
que
depende da dis ância que a pa ícula es á da sua melho solução
conhecida e da dis ância pa a a melho solução conhecida den o
de sua izinhança. Cada pa ícula
i∈S
se mo imen a em cada
dimensão
j∈{1,2, ..n}
do espaço de busca em um ins an e disc e o
de empo , segundo as Equações 5 e 6:
−→
xi( +1)=−→
xi( )+−→
i( )(5)
−→
i( +1)=w−→
i( )+c1 1−→
x∗
i( )−−→
xi( )+c2 2−→
x∗( )−−→
xi( )
(6)
onde: w= iné cia
ci= coe icien e de acele ação, i=(1,2)
i
= núme o alea ó io pe encen e a uma dis ibuição de p oba-
bilidade uni o me , i=(1,2)e i∈[0,1]
−→
x∗
i( )= melho posição da pa ícula i
−→
x∗( )= posição da melho pa ícula da população
−→
xi( )= posição a ual da pa ícula i
Quando a izinhança das pa ículas consis e no enxame in ei o, a
posição
−→
xi( )
é denominada de
дbes
. O e o elocidade é quem
o ien a o p ocesso de o imização, usando an o o conhecimen o
adqui ido pa icula men e pela pa ícula quan o o conhecimen o
adqui ido pela pa ícula baseada na in e ação com sua izinhança.
O e mo
c1 1−→
x∗
i( )−−→
xi( )
da equação de a ualização da e-
locidade é a componen e cogni i a e ep esen a a expe iência da
pa ícula. Essa componen e é a esponsá el pela endência que a
pa ícula em de ol a pa a a melho solução encon ada po ela no
passado. O e mo
c2 2−→
x∗( )−−→
xi( )
, po sua ez, é conhecido
como componen e social da equação da elocidade, e ep esen a
o conhecimen o cole i o do enxame, sendo esponsá el po a ai
cada pa ícula pa a a melho solução encon ada po alguma pa -
ícula de sua izinhança. O e o elocidade
−→
i
é a soma e o ial
das componen es cogni i a e social com a iné cia da pa ícula. A
iné cia
w
a ua como uma memó ia da di eção da elocidade an e io
da pa ícula e impede que haja al e ações b uscas na di eção da
elocidade pa ícula [
11
]. Assim, caso a pa ícula es eja se di igindo
a uma boa egião, a descobe a de um no o líde social não al e a á
comple amen e essa di eção. O papel da componen e cogni i a é
ap oxima a pa ícula na di eção da melho posição encon ada
po ela desde o início da busca. Dessa o ma, a pa ícula de e á
encon a uma boa posição que p o a elmen e es á p óxima do seu
líde cogni i o a ual. A a és da componen e social, as pa ículas
comunicam a in o mação sob e as melho es posições encon adas
po elas desde o início do p ocesso de busca, sendo conside ada
como a mais impo an e componen e na equação da elocidade das
pa ículas.
O pseudo-código do PSO é ap esen ado no Algo i mo 1. A cada
passo, o algo i mo i á muda a elocidade de cada pa ícula em
di eção às posições
pbes
e
дbes
, onde a posição e a elocidade
da pa ícula são a ualizadas con o me as Equações 5 e 6, espec-
i amen e. Um e mo alea ó io
ponde a o quan o a pa ícula se
mo imen a em di eção a esses alo es, onde di e en es núme os
alea ó ios são ge ados em di eção à acele ação pa a
pbes
e
дbes
locais [
20
]. O algo i mo con inua á a i e a a é que um c i é io de
pa ada seja alcançado. Ge almen e, esse c i é io de pa ada é um
núme o máximo de i e ações especi icado ou um alo ap idão p é-
de inido conside ado bom o su icien e. A equação de elocidade
con ém á ios pa âme os que a e am o desempenho do algo i mo
e alguns a e am signi ica i amen e na con e gência do algo i mo.
A iné cia
w
, po exemplo, é undamen al pa a a con e gência do
algo i mo. Ela de e mina o quan o as elocidades an e io es a e a-
ão a elocidade a ual e de ini á um equilíb io en e o componen e
cogni i o local e o global social das pa ículas. Se o alo da iné cia
o al o, a elocidade aumen a á, a o ecendo a busca global. Mas,
se o alo o baixo, as pa ículas so e ão uma desacele ação, a-
o ecendo a busca local. Dessa o ma, um alo
w
que equilib a a
pesquisa global e local implica menos i e ações pa a que o algo i mo
possa con e gi . Apesa de
c1
e
c2
não in luencia em di e amen e
Algo i hm 1 Pa icle Swa m Op imiza ion
1: d←n◃Inicializa a dimensão das pa ículas pa a d
2: x[i] ← xalea o io ◃Inicializa a população de pa ículas com
posições e elocidades alea ó ias [i] ← alea o io
3: while c i e iopa ada = also do ◃
Repe e enquan o o c i é io
de pa ada não i e sido alcançado
4: o ido1n ◃Pa a cada pa ícula calcula o
seu alo ap idão, compa a o alo ap idão da pa ícula com o
alo pbes e com o alo de дbes
5: i xa ual ↔pbes hen ◃Se o alo a ual da pa ícula
é melho do que pbes
6: x[i] ← xa ual pbes ←xa ual
7: end i
8: i xa ual ↔дbes hen ◃Se o alo a ual da pa ícula
é melho do que дbes
9: x[i] ← xa ual дbes ←xa ual
10: end i
11: x[i] ← xcalculada ◃
A ualiza a posição e elocidade da
pa ícula Equações 5 e 6
[i] ← calcculada
12: end o
13: end while
na con e gência do PSO, o ajus e desses pa âme os agiliza e e i a
que o algo i mo seja pego em mínimos locais. O pa âme o
c1
é
e e ido como pa âme o cogni i o e o alo
c1 1
, na Equação 6,
de ine a ele ância da melho posição an e io .
c2
é e e ido como o
pa âme o social e
c2 2
e de e mina o compo amen o da pa ícula
em elação a ou os izinhos.
O núme o, a dimensão das pa ículas, o alcance e a elocidade
máxima das pa ículas são pa âme os u ilizados como en ada pa a
o algo i mo, embo a não componham a de inição de elocidade.
Quan o ao núme o de pa ículas, um alo al o cos uma aumen a
a p obabilidade de encon a o ó imo global. O alo des e núme o
depende da complexidade do p oblema de o imização, mas um
in e alo ípico é en e 20 e 40 pa ículas [
23
]. Os alo es pa a a
dimensão das pa ículas e o alcance, no qual sua mo imen ação é
pe mi ida, são de e minados unicamen e pela na u eza do p oblema
que es á sendo esol ido e de como ele é modelado pa a se adequa
ao PSO. A elocidade máxima de ine a mudança máxima que uma
pa ícula pode e em uma i e ação e no malmen e seu alo é
ap oximadamen e a me ade do alcance de posição da pa ícula [
23
].
4 ALGORITMO
A modelagem de um p oblema PSO é di idida em duas ases: de ini-
ção do p oblema e de inição da unção ap idão. A p imei a consis e
em de ini como o p oblema se á codi icado, ou seja, de ini como
a solução se á ep esen ada. A segunda, em de ini o quão boa uma
pa ícula se á medida, ou seja, de ini a unção de ap idão. Já pa a
ans o ma o p oblema PSO em um algo i mo, é p eciso de ini a
pa ícula e sua dimensão. Na abo dagem ado ada nes e a igo, uma
pa ícula ep esen a um luxo de abalho e suas a e as, e dimensão
da pa ícula ep esen a o núme o de a e as no luxo de abalho.
A dimensão de uma pa ícula se e pa a localiza sua posição no
espaço, de inindo o sis ema de coo denadas. No exemplo do wo k-
low do Ca é, a dimensão da pa ícula é qua o, sendo sua posição
especi icada po um sis ema com qua o coo denadas.
Uma pa ícula mo imen a-se num espaço limi ado, denomina-se
alcance. Na abo dagem ado ada nes e a igo, o alcance é de e mi-
nado pelo núme o de pools de h eads disponí eis pa a execu a a
a e a. Assim, o alo de uma coo denada no sis ema de coo dena-
das, que de ine o espaço de mo imen ação da pa ícula, em um
alcance de 0 a é o núme o máximo de pools de h eads disponí eis.
A pa e in ei a do alo de uma coo denada na posição de uma
pa ícula co esponde ao núme o de pools de h eads e ep esen a
o ecu so compu acional a ibuído a uma a e a de inida po essa
coo denada especí ica. Assim, a posição da pa ícula co esponde a
um mapeamen o da a e a em ecu sos.
Pa a o wo k low do Ca é, alo es pa a as qua o coo denadas( a e as)
do nosso sis ema de coo denadas, no qual exis em ês ecu sos com-
pu acionais (pools de h eads disponí eis), de o ma que o alo de
cada coo denada pode á a ia en e 0 e 3. Há 4 a e as pa a se em
mapeadas, o que co esponde a dimensão 4 da pa ícula, po an o a
posição da pa ícula e á 4 coo denadas. O índice da coo denada (de
1 a 4) co esponde a uma a e a (de
1
a
4
). O alo da coo denada
é um núme o eal de 0 a 3 , co espondendo ao núme o de ecu sos
disponí eis pa a cada a e a, com o máximo de 3 no nosso exemplo.
Quando esse núme o in ei o é a edondado, é de e minado o nú-
me o de ecu sos disponí eis pa a cada a e a. A unção de ap idão
de e e le i os obje i os do p oblema de agendamen o, pois ela
é usada pa a de e mina o quão boa uma de e minada solução é.
Nessa abo dagem, ela é minimizada e seu alo se á o empo o al
de execução
TTE
con ido no agendamen o
A
de i ado da posição da
pa ícula. Conside ando que o mo o de execução é capaz de aumen-
a elás ica e dinamicamen e a quan idade de ecu sos, o modelo de
aquisição o e ecido pela compu ação em nu em pa ece ilimi ado,
ou seja, não há um conjun o de ecu sos disponí eis que pode se
usado no algo i mo. A es a égia é de ini um conjun o inicial de e-
cu sos que o algo i mo pode usa pa a explo a di e en es soluções
e alcança o agendamen o. O amanho desse conjun o se á nossa
es ição
TR ≤δ
, con o me a Equação 4. Tal es a égia em de
e le i a he e ogeneidade dos pools de h eads (di e en es núme os
de h eads) e o e ece opções su icien es de PSO, a im de que seja
p oduzida uma pa ícula adequada, ou seja, a solução. O conjun o
de ecu sos inicial e limi ado con e á os ecu sos que podem se
usados. Se esse conjun o é mui o g ande, o núme o de agendamen o
possí eis aumen a á, assim como, o espaço de pesquisa explo ado
pelo PSO, o nando di ícil pa a o algo i mo con e gi e encon a
uma solução adequada [23].
Pa a eduzi o amanho do espaço de pesquisa, o qual se á
usado pelo PSO pa a encon a um agendamen o p óximo do ó imo,
conside a-se um conjun o de ecu sos inicial
Rinicial
, compos o po
um
Pool
de cada ipo, pa a cada a e a em P; onde P é o conjun o que
con ém o núme o máximo de a e as que podem se execu adas em
pa alelo pa a um dado luxo de abalho. O algo i mo seleciona á
o núme o e o ipo ap op iados de Pools pa a o mo o de execução,
den o das opções con idas em
Rinicial
. Assim, e le e-se a he e-
ogeneidade dos ecu sos compu acionais e eduz-se o amanho
do espaço de busca, além de pe mi i mapea odas as a e as que
podem se execu adas em pa alelo. O amanho de
Rinicial
se ia
igual a
|P|∗n
, onde
n
é o núme o de ipos de
Pools
disponí eis,
sendo ainda possí el, que o PSO selecione mais de um ecu so
|P|
,
se necessá io (a menos que n=1).
O p oblema abo dado possui a es ição
TR ≤δ
, u iliza-se uma
e são do PSO que inco po a uma es a égia pa a a a es i-
ções [
7
]. Nela, semp e que duas soluções es ão sendo compa adas e
(i) ambas as soluções o em iá eis, en ão a solução com melho
ap idão é selecionada; (ii) se uma solução é iá el e a ou a não é,
en ão a iá el é selecionada; e inalmen e, (iii) se ambas as soluções
são in iá eis, aquela que iola menos a es ição é selecionada.
No úl imo caso, implica que uma medida de quan o uma solução
iola a es ição p ecisa se encon ada. O p oblema de ine o alo
de iolação de es ição de uma solução
δk
, a es ição pode se
a ibuída a limi ação de ecu sos que se deseja con a a na compu-
ação em nu em ou simplesmen e e a quan idade de h eads ísicas
das máquinas que i ão se u ilizadas na execução da solução de
in eg ação. Uma solução do PSO que u ilize ecu sos p óximos de
δkse á p e e ida em elação a uma solução menos ecu sos.
O Algo i mo 2 ap esen a o pseudo-código pa a mapea a posição
de uma pa ícula em um agendamen o. O conjun o de ecu sos
R
pa a se em alocados e o conjun o de mapeamen os
M
de a e as
pa a ecu sos são inicializados sem elemen os, ou seja, azios, e
empo o al de execução
TTE
é inicializado com o alo ze o. Na
sequência, o algo i mo es ima o empo de execução de cada a e a
do luxo de abalho pa a odo o ecu so
i∈Rinicial
. A ep e-
sen ação é uma ma iz em que as linhas ep esen am as a e as,
as colunas ep esen am os ecu sos e a en ada
TempoExec[i,j]
co esponde ao empo gas o pa a execu a a a e a
i
no ecu so
j
, calculado con o me a Equação 1. O p óximo passo é o cálculo
ou a ibuição da ma iz de empo de ans e ência de dados, ou
empo de espe a na ila de a e as, o qual assume-se que es á sendo
ob ido po um p ocedimen o, não a ado nesse abalho, al como
po uma e amen a de moni o amen o. Essa ma iz é ep esen ada
como uma ma iz de adjacência ponde ada do wo k low DAG, onde
a en ada
TempoT ans e [i,j]
con ém o empo que le a pa a ans-
e i os dados de saída da a e a
i
pa a a a e a
j
e esse alo é
ze o semp e que
i=j
ou não há a es a di ecionada conec ando
i
( a e a pai) e
j
( a e a ilha). De posse dessas in o mações, o
algo i mo inicia de e minando a posição da pa ícula e cons uindo
o agendamen o. Pa a isso, i e a pa a oda
i
do a ay de posição
pos
e a ualiza
R
e
M
. P imei o, de e mina a a e a e o ecu so que es á
associado à coo denada a ual e seu alo . A es a égia usada pa a
isso é a desc i a an e io men e, a qual indica que a coo denada
i
co esponde à a e a
i
e seu alo
pos[i]
co esponde ao ecu so
pos[i]∈Rinicial
. Encon ados os componen es,
i
e
j
, de uma
upla de mapeamen o
m j
i
, o algo i mo calcula os demais, o empo
de inicio TIni ie empo de inalização T Fin ida a e a.
O alo de empo de início
TIni i
di e encia-se em duas si uações.
Na p imei a, a a e a não em a e a pai e, po an o, pode começa
a se execu ada, assim que o ecu so alocado pa a ela
pos[i]
es i e
disponí el, o que oco e á quando o e e ido ecu so e mina a exe-
cução que es i e em andamen o. Na segunda si uação, a a e a em
um ou mais pais e, nesse caso, além de espe a que o ecu so pa a ela
alocado es eja disponí el, ambém e á que agua da pelo é mino
da execução das suas a e as pai, além do empo de ans e ência
dos dados.
O alo de
TFin i
é calculado baseado no empo o al de p oces-
samen o e no empo de início da a e a. Pa a de e mina o empo
de p ocessamen o
TP pos[j]
i
, é necessá io calcula o empo de execu-
ção e o empo de ans e ência. O p imei o é
TempoExec[i,pos[i]]
,
enquan o o úl imo é calculado pela soma dos alo es do empo
de ans e ência
TempoT ans [i, ilha(i)]
pa a oda a e a ilha
ilha(i)
de
i
, que es á mapeada pa a oda em um ecu so di e-
en e de
pos[i]
. Esses dois alo es são en ão somados pa a ob e
TP pos[j]
i
, como de inido na Equação 2. Po im, o alo de
TFin i
é ob ido pela sub ação de
TIni i
de
TP pos[j]
i
. Calculados os ele-
men os de
m
, adiciona-se ecu so pa a
R
, se necessá io. Quando o
algo i mo e mina de p ocessa , cada coo denada do e o posição,
R
con e á odos os ecu sos necessá ios e os empos de início e
inalização. Além disso, o mapeamen o comple o das a e as pa a
os ecu sos es a á em
M
e cada a e a e á um ecu so a ibuído
a ela e o empo es imado de início e o de é mino. Com essas in-
o mações o algo i mo pode calcula o
TTE
associado a solução
a ual, con o me Equação 2. Nesse pon o, o algo i mo calculou
R
,
M
e
TTE
e pode á cons ui e ap esen a o agendamen o associado
pa a essa posição da pa ícula. Finalmen e, os Algo i mos 1 e 2 são
combinados pa a o agendamen o p óximo de ó imo. Na linha 4 do
Algo i mo 1, em ez de calcula o alo de ap idão da pa ícula,
ge a-se o agendamen o, con o me Algo i mo 2. Em seguida, usa-se

Algo i hm 2 Ge ação de agendamen o
En ada: Conjun o de luxo de abalho de a e as T
Conjun o Inicial de ecu sos Rinicial
Um a ay pos[|T|] ep esen ando a posição da pa ícula
Saída: Um agendamen o A
1: R=∅,M=∅,TTE =0◃Inicializa componen es
2: Calcula TempoExec[|T|×|Rinicial |]
3: Calcula TempoT ans [|T|×|T|]
4: o ido0|T|−1
5: i=T[i], pos[i]=Rinicial [pos[i]]
6: i inão em pai hen
7: TIni i=T Fin pos[i]
8: else
9: TIni i=(max {T Fin pai : pai [∈ pais( i)},T Fin pos[i])
10: end i
11: exe = empoExec [i] [pos [i]]
12: o cada ilha ilha de ido
13: i ilha
é mapeada pa a um ecu so di e en e de
pos[i]
hen
14: as e + = TempoT ans [i][c]
15: end i
16: end o
17: TP pos[j]
i
=exe + ans
18: TFin i=TP pos[j]
i−TIni i
19: m pos[j]
i
=( i, pos[i],TIni i,TFin i)
20: M=M∪ {m pos[i]
i}
21: i pos[i]<R hen
22: R=R∪ pos[i]
23: end i
24: end o
25: Calcula TTE con o me Equação 3
26: A=(R,M,TR,TTE)
oTTE como alo de ap idão nas e apas seguin es e é in oduzido
o mecanismo de manipulação de es ição, al que TR ≤δ .
5 ACKNOWLEDGEMENTS
This wo k was pa ially suppo ed by he B azilian Coo dina ion
o he Imp o emen o Highe Educa ion Pe sonnel (Capes), unde
pos doc o al esea ch g an 88881.119518/2016-01
6 CONCLUSÃO
A e iciência dos mo o es de execução das pla a o mas de in eg a-
ção es á di e amen e elacionado com o algo i mo de agendamen o
das a e as e a alocação de h eads pa a execu á-las. Um algo i mo
ine icien e le a a um aumen o do empo de execução, deg adando
assim o desempenho das soluções de in eg ação. Es e a igo p opõe
um algo i mo baseado na me a-heu ís ica Pa icle Swa m Op imiza-
ion pa a a alocação de h eads em mo o es de execução baseados
em ilas FIFO. O algo i mo p opos o a ibui h eads pa a as a e as
conside ando a complexidade compu acional da a e a e a he e oge-
neidade na capacidade compu acional das h eads. Apesa do PSO
localiza de o ma ápida a egião das boas soluções, é len o no
ajus e ino da solução, como acon ece em ou as écnicas, como no
caso dos algo i mos gené icos. Como abalho u u o, p e ende-se
implemen a esse algo i mo em um mo o de execução da pla a-
o ma Gua aná pa a a alia o ganho de desempenho com dis in os
casos de uso.
REFERÊNCIAS
[1]
A. A. Ab aham, G. M. King, D. V. Rosa, and D. W. Schmid . Run ime capaci y
planning in a simul aneous mul i h eading (sm ) en i onmen , Aug. 16 2016. US
Pa en 9,417,927.
[2]
A. Al-maama i and F. A. Oma a. Task scheduling using pso algo i hm in cloud
compu ing en i onmen s. In e na ional Jou nal o G id and Dis ibu ed Compu ing,
8(5):245–256, 2015.
[3]
C. Alexande , S. Ishikawa, and M. Sil e ein. A pa e n language: owns, buildings,
cons uc ion. Ox o d Uni e si y P ess, 1977.
[4]
M. R. AlRashidi and M. E. El-Hawa y. A su ey o pa icle swa m op imiza-
ion applica ions in elec ic powe sys ems. IEEE T ansac ions on E olu iona y
Compu a ion, 13(4):913–918, 2009.
[5]
D. B a on and J. Kennedy. De ining a s anda d o pa icle swa m op imiza ion.
In Swa m In elligence Symposium, 2007. SIS 2007. IEEE, pages 120–127. IEEE, 2007.
[6]
E.-K. Byun, Y.-S. Kee, J.-S. Kim, and S. Maeng. Cos op imized p o isioning o
elas ic esou ces o applica ion wo k lows. Fu u e Gene a ion Compu e Sys ems,
27(8):1011–1026, 2011.
[7]
K. Deb, A. P a ap, S. Aga wal, and T. Meya i an. A as and eli is mul iobjec i e
gene ic algo i hm: Nsga-ii. IEEE ansac ions on e olu iona y compu a ion, 6(2):
182–197, 2002.
[8] P. Die el. Ja a how o p og am. PHI, 2009.
[9] D. Dosso , J. D’Emic, and V. Rome o. Mule in ac ion. Manning, 2014.
[10]
R. Ebe ha and J. Kennedy. Pa icle swa m op imiza ion. In neu al ne wo ks,
1995., P oceedings o he IEEE in e na ional join con e ence on, pages 1942–1948.
IEEE, 1995.
[11]
A. P. Engelb ech . Compu a ional in elligence: an in oduc ion. John Wiley &
Sons, 2007.
[12]
E. M. d. N. FIGUEIREDO. Algo i mo baseado em enxame de pa ículas pa a
o imização de p oblemas com mui os obje i os. 2013.
[13]
M. Fishe , J. Pa ne , M. Bogoe ice, and I. Fuld. Sp ing in eg a ion in ac ion.
Manning Publica ions Co., 2012.
[14]
R. Z. F an z, R. Co chuelo, and F. Roos-F an z. On he design o a main ainable
so wa e de elopmen ki o implemen in eg a ion solu ions. Jou nal o Sys ems
and So wa e, 111:89–104, 2016.
[15]
Y. Fukuyama and Y. Nakanishi. A pa icle swa m op imiza ion o eac i e powe
and ol age con ol conside ing ol age s abili y. In P oc. 11 h IEEE In . Con .
In ell. Sys . Appl. Powe Sys , pages 117–121, 1999.
[16]
B. Hohpe, G ego ; Wool . En e p ise in eg a ion pa e ns: Designing, building, and
deploying messaging solu ions. Addison-Wesley P o essional, 2004.
[17]
G. Hohpe. You co ee shop doesn’ use wo-phase commi [asynch onous
messaging a chi ec u e]. IEEE so wa e, 22(2):64–66, 2005.
[18] J. Ibsen, Claus & Ans ey. Camel in ac ion. Manning Publica ions Co., 2010.
[19] K. Ind asi i. In oduc ion o WSO2 ESB. Sp inge , 2016.
[20] A. Lazinica. Pa icle swa m op imiza ion. InTech Ki chengasse, 2009.
[21]
C. O. Ou ique, E. C. Biscaia, and J. C. Pin o. The use o pa icle swa m op imiza ion
o dynamical analysis in chemical p ocesses. Compu e s & Chemical Enginee ing,
26(12):1783–1793, 2002.
[22]
S. Pandey, L. Wu, S. M. Gu u, and R. Buyya. A pa icle swa m op imiza ion-based
heu is ic o scheduling wo k low applica ions in cloud compu ing en i onmen s.
In Ad anced in o ma ion ne wo king and applica ions (AINA), 2010 24 h IEEE
in e na ional con e ence on, pages 400–407. IEEE, 2010.
[23]
M. A. Rod iguez and R. Buyya. Deadline based esou ce p o isioningand schedu-
ling algo i hm o scien i ic wo k lows on clouds. IEEE T ansac ions on Cloud
Compu ing, 2(2):222–235, 2014.
[24] J. Russell and R. Cohn. Fuse Esb. Book on Demand, 2012. ISBN 9785510817041.
[25]
D. F. Sella o. Pa icle swa m op imiza ion pa a agendamen o de a e as na
in eg ação de aplicações emp esa iais. V SFCT, 14, 2017.
[26]
T. Sousa, A. Sil a, and A. Ne es. Pa icle swa m based da a mining algo i hms
o classi ica ion asks. Pa allel Compu ing, 30(5):767–783, 2004.
[27] A. Tanenbaum. Mode n ope a ing sys ems. Pea son Educa ion, Inc., 2009.
[28]
F. Van Den Be gh and A. P. Engelb ech . A s udy o pa icle swa m op imiza ion
pa icle ajec o ies. In o ma ion sciences, 176(8):937–971, 2006.
[29]
Z. Wu, Z. Ni, L. Gu, and X. Liu. A e ised disc e e pa icle swa m op imiza ion
o cloud wo k low scheduling. In Compu a ional In elligence and Secu i y (CIS),
2010 In e na ional Con e ence on, pages 184–188. IEEE, 2010.