ࡱ> ,.+bjbjUU >??   OOOOOccccw c$ GIIIIIIfIOIOO^OOGGtͦ/Ic3t0OxII  :Heursticas para o Problema da Partio Cromtica de Custo Mnimo Resumo O Problema da Partio Cromtica de Custo Mnimo (PPCCM), considerado uma das diversas variantes do Problema Clssico de Colorao de Grafos (PCG), utiliza nmeros reais como custos das cores, tendo como objetivo colorir os vrtices de um grafo de modo que os adjacentes tenham cores diferentes e a soma dos custos das cores utilizadas seja mnima. Embora seja um problema NP-Difcil para grafos em geral, foram elaborados algoritmos polinomiais para algumas poucas classes de grafos. Do ponto de vista prtico, o mesmo foi empregado no projeto de circuitos VLSI e na soluo de determinados problemas de escalonamento modelados como grafos de intervalo. Nesta tese so propostos algoritmos para o PPCCM considerando um grafo simples no-direcionado como entrada. Inicialmente foram desenvolvidas duas heursticas baseadas na metaheurstica Algoritmos Genticos com Chaves Aleatrias Tendenciosas (Biased Random Key Genetic Algorithms - BRKGA, em ingls). Posteriormente, foi implementada uma heurstica de trajetria que faz uso de duas estratgias de busca local seguidas por um procedimento de path-relinking. Para os experimentos computacionais foram geradas instncias para o problema a partir de grafos comumente empregados no PCG. Palavras-chave: Problema da Partio Cromtica de Custo Mnimo, Colorao de Grafos, Heursticas, Metaheursticas, Busca Local, Algoritmos Genticos. Heuristics for the Minimum Cost Chromatic Partition Problem Abstract The Minimum Cost Chromatic Partition Problem (MCCPP) is one of several variants of the classical Graph Coloring Problem (GCP), in which there are real number as color costs and the aim is to color the vertices of a graph so that the adjacent ones have different colors and the sum of the costs of the used colors is minimal. Although the MCCPP is a NP-hard problem for general graphs, polynomial time algorithms were developed for some classes of graphs. From a practical point of view, the MCCPP has application in the design of VLSI circuits and in the solution of scheduling problems modeled as interval graphs. In this thesis, algorithms for the problem considering undirected simple graphs are proposed. Initially, two heuristics based on the metaheuristic Biased Random Key Genetic Algorithm (BRKGA) were developed. Following, we propose a trajectory search heuristic using local search and path-relinking. For computational experiments, instances for the problem from graphs commonly used in PCG were generated. Keywords: Minimum Cost Chromatic Partition Problem, Graph Coloring, Heuristics, Metaheuristics, Local Search, Genetic Algorithms. BCJ  ! /  ͹ͫͫnYnE0(hhaCJOJQJ^JaJmH sH 'haB*CJOJ^JaJmH ph!!!sH (hhaCJOJQJ^JaJmH sH .hha5CJOJQJ\^JaJmH sH &h`Mha5CJOJQJ\^JaJ ha5CJOJQJ\^JaJhaCJOJQJ^JaJ&h`Mha6CJOJQJ]^JaJ h`MhaCJOJQJ^JaJhaCJOJQJ^JaJ&hGha5CJOJQJ\^JaJBCJ !  $a$gd`M $dha$gdfVp$dh`a$gdfVp$a$gdG ӻ.hha5CJOJQJ\^JaJmH sH (hhaCJOJQJ^JaJmH sH .hha5CJOJQJ\^JaJmH sH <P1h:pB. A!"#$% Dpj 666666666vvvvvvvvv666666>6666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~ OJPJQJ_HmHnHsHtHR`R fVpNormal d CJPJ^J_HaJmHsHtH DA D 0Default Paragraph FontRiR 0 Table Normal4 l4a (k ( 0No List pp `M0Texto pre9formatadod7$8$H$CJOJQJ^JaJtHPK![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]    tw-target-text6 6 BM`f`M 'atbHvkfVp/n0U[cFZLBGQaH @ @@UnknownG*Ax Times New Roman5Symbol3" Arial7.@CalibriG5 x@Liberation MonoI xP!Liberation SerifACambria Math"Si'Si'0$P `f!xxAHeursticas para o Problema da Partio Cromtica de Custo MnimoPhilippeHelioOh+'04 DP t  DHeursticas para o Problema da Partio Cromtica de Custo Mnimo PhilippeNormal_WordconvHelio2Microsoft Office Outlook@@R/I@R/I՜.+,0( hp|   BHeursticas para o Problema da Partio Cromtica de Custo Mnimo Title  !"$%&'()*-Root Entry F.Ҧ/I/1TableWordDocument>SummaryInformation(DocumentSummaryInformation8#CompObjy  F'Microsoft Office Word 97-2003 Document MSWordDocWord.Document.89q  F#Documento do Microsoft Office Word MSWordDocWord.Document.89q