аЯрЁБс>ўџ *,ўџџџ)џџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџьЅСq`№П‹bjbjqPqP4 ::‹џџџџџџЄ0000000D((((< D• HTTTTTTTT       $н hE J: 0TTTTT: 00TTO фффT*0T0T фT фф00фTH Вd”Aг(~Fф e 0• ф Ф  ф 0ф$TTфTTTTT: : ЮTTT• TTTTDDDф(DDD(DDD000000џџџџ Resumo O Problema de Bin Packing щ um dos problemas mais estudados na сrea de Otimizaчуo Combinatѓria. No entanto, as aplicaчѕes prсticas do problema acrescentam restriчѕes adicionais р definiчуo clсssica dificultando sua resoluчуo utilizando os mщtodos existentes. Portanto, nesta tese sуo estudados novos mщtodos de resoluчѕes para duas variantes do bin packing, o Problema de Bin Packing com Conflitos (PBPC) e o Problema de Bin Packing com Dependъncias (PBPD). Esses problemas surgem em diversas aplicaчѕes reais, tais como no problema de alocaчуo de horсrios, na alocaчуo de recursos de computaчуo em nuvem, na сrea de transporte e logэstica, entre outros. Para resolver estas duas variantes, foram desenvolvidos mщtodos heurэsticos e exatos. Para o PBPC foi proposta uma abordagem baseada na metaheurэstica Iterated Local Search. Esse mщtodo щ combinado com vсrias classes de vizinhanчas locais e de larga escala. Foram introduzidos ainda procedimentos de avaliaчуo em O(1) dos movimentos clсssicos da busca local, variantes polinomiais do ejection chains e da vizinhanчa assignment, alщm de uma vizinhanчa adaptativa baseada no problema de cobertura de conjuntos, e finalmente um uso controlado de movimentos de custo-0 como mecanismo de diversificaчуo da busca. O mщtodo desenvolvido produz soluчѕes de alta qualidade em instтncias da literatura. Experimentos computacionais foram realizados para medir a respectiva contribuiчуo de cada vizinhanчa proposta. Para o PBPD, щ apresentado uma definiчуo formal do problema com um modelo matemсtico de programaчуo linear inteira mista. Um mщtodo exato щ proposto para resolver o problema, mais especificamente, um algoritmo de branch-and-price. Para testar essa abordagem sуo apresentadas novas instтncias para o problema criadas a partir das instтncias do PBPC existentes na literatura. Palavras-chave: Bin Packing com Conflitos; Bin Packing com Dependъncias; Iterated Local Search; Busca em Vizinhanчa Larga; Branch-and-price Abstract The Bin Packing Problem is one of the most studied problems in the Combinatorial Optimization area. However, its practical applications add additional constraints to the classical definition. Therefore, this thesis aimed to study new resolution methods for two bin packing variants, the Bin Packing Problem with Conflicts (BPPC) and the Bin Packing Problems with Dependencies (BPPD). These problems have many real applications, such as in timetabling problems, in cloud computing management resources, in transportation and logistics areas, among others. To solve these two variants, heuristic and exact methods were developed. For the PBPC, an approach based on the metaheuristic Iterated Local Search was proposed. This method is combined with several classes of local and large-scale neighborhoods. We introduce O(1) evaluation procedures for classical local-search moves, polynomial variants of ejection chains and assignment neighborhoods, an adaptive set covering-based neighborhood, and finally a controlled use of 0-cost moves to further diversify the search. The overall method produces solutions of high quality on the classical benchmark instances of the literature. Extensive computational experiments are conducted to measure the respective contribution of each proposed neighborhood. For PBPD, a formal definition of the problem is presented with a mathematical formulation. An exact method is proposed to solve the problem, more specifically a Branch-and-price algorithm. To test this approach, new instances for the problem are created from the PBPC benchmark instances. Keywords: Bin Packing with Conflicts; Bin Packing with Dependencies; Iterated Local Search; Large Neighborhood Search; Branch-and-price !a l | ‡ ­ И 0 E в ж  ( 9 C Ц Э ’Ђ56E~‡АСТУЫЬЭўђхплдлдлдлдлдлдлдлдлдлдлЫСНлНлЖпЄ“†{m{hUh7?/6]mH sH hUh7?/mH sH hUh7?/^JmH sH  hUh7?/CJ ^JaJ mH sH "hUh7?/5CJ \aJ mH sH  hќ“h7?/hќ“hUh7?/5\h7?/5\^J h7?/6]h7?/ h7?/^JhUh7?/CJ ^JaJ hUh7?/5CJ \aJ &— ˜ 56ТУЬЭјљ‹єьссссжсЪєссссс $$dha$gdU $dha$gdќ“ $dha$gdUdhgdU $dha$gdU‹§ GVyŠ‹іщлгШгШНhќ“h7?/mH sH hUh7?/mH sH hќ“mH sH hUh7?/5\mH sH h7?/5\^JmH sH h7?/^JmH sH 2P:p7?/Аа/ Ар=!Аn"Аn#n$n%ААаАа а†œ˜žžžžžžžž666666666vvvvvvvvv6666668666666666666666666666666666Ј6666666666И666666666666hH66666666666666666666666666666666666666666666666666666666666666666А6Z@ёџZ Normal*$1$,CJKHOJQJ^J_HaJmHnHsHtH>AђџЁ> 0Fonte parсg. padrуoTiѓџГT 0 Tabela normalі4ж l4жaі ,kєџС, 0 Sem lista JўOJ 0Tэtulo1 $Є№ЄxCJOJQJ^JaJBB@B 0Corpo de texto d ЄŒLўЂL o0 Char Char CJKHOJQJ^JaJnHtH&/@"& 0Lista<"@2< 0Legenda  $ЄxЄx6],ўOB, 0Эndice $‹ џџџџ—˜56ТУЬЭј љ ˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€˜0€€‹ ‹ ‹!adel|€‡­АБИ!/08?E!"(9C’ЂFIJQadel‡Ž”ЊЏБСj w OYвдЬзМСў 3ЊЏхU7?/ќ“џ@€ААNюАА‹@@џџUnknownџџџџџџџџџџџџGџ:рAxР џTimes New Roman5€Symbol3& џ:рCxР џArialIџрџxP!ПLiberation SerifG& џрџxP!ПLiberation Sans"Aˆ ХЉТJZ'ФJZ'EF EF a €24„„ џџ(№џ$PџџџџџџџџџџџџџџџџџџџџџUВџџResumoHelioHelioўџр…ŸђљOhЋ‘+'Гй0l˜ЈДФамь ќ ( 4 @LT\dфResumoHelioNormalHelio3Microsoft Office Word@вIk@М-Aг@HtAгEF ўџеЭеœ.“—+,љЎ0№ hp|„Œ” œЄЌД М Яф„ц Resumo Tэtulo ўџџџўџџџ ўџџџ"#$%&'(ўџџџ§џџџ+ўџџџўџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџRoot Entryџџџџџџџџ РF№ћf”Aг-€1TableџџџџџџџџWordDocumentџџџџџџџџ4 SummaryInformation(џџџџDocumentSummaryInformation8џџџџџџџџџџџџ!CompObjџџџџџџџџџџџџuџџџџџџџџџџџџџџџџџџџџџџџџўџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџџўџ џџџџ РF#Documento do Microsoft Office Word MSWordDocWord.Document.8є9Вq