ࡱ> .0-abjbjUU :??T -----AAAA M A2YYYYYYYY --YYYYY--YYYYYY-Y-YYYYY]YaAAYu02}F YF F -$YYYYYYYYYYYY2YYYYF YYYYYYYYY :Resumo: O Problema de Biclusterizao por Edio de Arestas (PBEA) um problema NP-difcil em que, dado um grafo bipartido G = (V , U , E ) e um inteiro k e" 0, deseja-se adicionar ou remover no mximo k arestas de forma a tornar G uma unio disjunta de subgrafos bipartidos completos (bicliques). Este trabalho prope a aplicao do PBEA na resoluo do Problema de Formao de Clulas de Manufatura (PFCM). Desenvolvemos um mtodo exato para o PBEA com um novo algoritmo de separao baseado em programao dinmica e trs novos pr-processamentos para o PBEA derivados de resultados tericos. Outras contribuies deste trabalho so duas novas abordagens exatas para o PFCM com base em formulaes matemticas para o PBEA. Ambas as abordagens usam a medida de eficcia de agrupamento como funo objetivo. Alm disso, duas heursticas hbridas GRASP foram propostas para o PBEA e para o PFCM, respectivamente. Experimentos computacionais realizados em instncias do PFCM encontrados na literatura mostram que os mtodos propostos para o PFMC so capazes de provar a otimalidade de solues previamente desconhecidas (no caso dos mtodos exatos), alm de encontrar solues de alta qualidade em um baixo tempo de execuo (no caso de mtodos heursticos). H J `aҼUh9(^JmHsHh8h9(mHsH*h8h9(mHsHh9(mHsHh8h9(^JmHsHh8h9(5\mHsH 1 `agd8$a$gd8Palavras-chaves: Biclusterizao, Particionamento em grafos, Formao de Clulas de Manufatura 8P:p9(/ =!n"n#n$n% Dp^ 666666666vvvvvvvvv66666686666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~_HmHnHsHtHZ`Z Normal*$1$,CJKHOJQJ^J_HaJmH nHsH tH`!2` 0 Heading 1& & F hP@&^`P5CJ$\aJ$d!2d 0 Heading 2* & F h@@@&^@`5CJ \aJ \!2\ 0 Heading 3* & F h0@&^`05\DA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List f/f ,Heading 1 Char25CJ KH OJPJQJ\^JaJ mH nHsH tHl/l ,Heading 2 Char856CJKHOJPJQJ\]^JaJmH nHsH tHf/f ,Heading 3 Char25CJKHOJPJQJ\^JaJmH nHsH tHJ2J 0Heading $xCJOJQJ^JaJ8B28 0 Body Text d \/A\ ,0Body Text Char(CJKHOJQJ^JaJmH nHsH tH$/1R$ 0List<"b< 0Caption  $xx6]*r* 0Index $DD 0 Quotations77]7^7:>!2: 0Title$a$5CJ8\aJ8^/^ , Title Char25CJ KHOJPJQJ\^JaJ mH nHsH tH>J!2> 0Subtitle $<a$CJ$aJ$^/^ , Subtitle Char,CJKHOJPJQJ^JaJmH nHsH tHPK![Content_Types].xmlj0Eжr(΢Iw},-j4 wP-t#bΙ{UTU^hd}㨫)*1P' ^W0)T9<l#$yi};~@(Hu* Dנz/0ǰ $ X3aZ,D0j~3߶b~i>3\`?/[G\!-Rk.sԻ..a濭?PK!֧6 _rels/.relsj0 }Q%v/C/}(h"O = C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xml M @}w7c(EbˮCAǠҟ7՛K Y, e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+& 8PK!Ptheme/theme/theme1.xmlYOo6w toc'vuر-MniP@I}úama[إ4:lЯGRX^6؊>$ !)O^rC$y@/yH*񄴽)޵߻UDb`}"qۋJחX^)I`nEp)liV[]1M<OP6r=zgbIguSebORD۫qu gZo~ٺlAplxpT0+[}`jzAV2Fi@qv֬5\|ʜ̭NleXdsjcs7f W+Ն7`g ȘJj|h(KD- dXiJ؇(x$( :;˹! I_TS 1?E??ZBΪmU/?~xY'y5g&΋/ɋ>GMGeD3Vq%'#q$8K)fw9:ĵ x}rxwr:\TZaG*y8IjbRc|XŻǿI u3KGnD1NIBs RuK>V.EL+M2#'fi ~V vl{u8zH *:(W☕ ~JTe\O*tHGHY}KNP*ݾ˦TѼ9/#A7qZ$*c?qUnwN%Oi4 =3ڗP 1Pm \\9Mؓ2aD];Yt\[x]}Wr|]g- eW )6-rCSj id DЇAΜIqbJ#x꺃 6k#ASh&ʌt(Q%p%m&]caSl=X\P1Mh9MVdDAaVB[݈fJíP|8 քAV^f Hn- "d>znNJ ة>b&2vKyϼD:,AGm\nziÙ.uχYC6OMf3or$5NHT[XF64T,ќM0E)`#5XY`פ;%1U٥m;R>QD DcpU'&LE/pm%]8firS4d 7y\`JnίI R3U~7+׸#m qBiDi*L69mY&iHE=(K&N!V.KeLDĕ{D vEꦚdeNƟe(MN9ߜR6&3(a/DUz<{ˊYȳV)9Z[4^n5!J?Q3eBoCM m<.vpIYfZY_p[=al-Y}Nc͙ŋ4vfavl'SA8|*u{-ߟ0%M07%<ҍPK! ѐ'theme/theme/_rels/themeManager.xml.relsM 0wooӺ&݈Э5 6?$Q ,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-![Content_Types].xmlPK-!֧6 +_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!Ptheme/theme/theme1.xmlPK-! ѐ' theme/theme/_rels/themeManager.xml.relsPK] TaaP^`P@@^@`0^`0``^``^`^`^``^``00^0`9(8TV@(T@@@@(@UnknownG*Ax Times New Roman5Symbol3" ArialmNimbus Roman No9 LTimes New RomanO"Nimbus Sans LArial7@CambriaACambria Math" 33Dg33Dg! 0 $PT!xx#Aluno: Rian Gabriel Santos PinheiroHelioHelio Oh+'0 , P \ ht|$Aluno: Rian Gabriel Santos PinheiroHelioNormal_WordconvHelio3Microsoft Office Outlook@Ik@J@J՜.+,0  hp|   $Aluno: Rian Gabriel Santos Pinheiro Title  !"#$&'()*+,/Root Entry F@mA11Table V WordDocument:SummaryInformation(DocumentSummaryInformation8%CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q