AlgoritmosparaProblemasdeEmpacotamento EduardoCandidoXavier TesedeDoutorado i InstitutodeComputação UniversidadeEstadualdeCampinas Algoritmos para Problemas de Empacotamento Eduardo Candido Xavier1 5dedezembro de2006 Banca Examinadora: • Prof. Dr. FlávioKeidiMiyazawa InstitutodeComputação,Unicamp(Orientador) • Prof. Dra. YoshikoWakabayashi InstitutodeMatemáticaeEstatística,USP • Prof. Dr. HorácioHideki Yanasse LaboratórioAssociadodeComputação eMatemáticaAplicada,INPE • Prof. Dr. Cid CarvalhodeSouza InstitutodeComputação,Unicamp • Prof. Dr. OrlandoLee InstitutodeComputação,Unicamp 1AuxíliofinanceirodaCapesedoCNPq ii Substitua pela ficha catalográfica iii Algoritmos para Problemas de Empacotamento EsteexemplarcorrespondeàredaçãofinaldaTese devidamente corrigida e defendida por Eduardo Candido Xavier e aprovada pela Banca Examina- dora. Campinas,5 dedezembro de2006. Prof. Dr. FlávioKeidiMiyazawa InstitutodeComputação,Unicamp(Orientador) Tese apresentada ao Instituto de Computação, UNICAMP, comorequisitoparcialparaaobtenção do títulodeDoutorem CiênciadaComputação. iv Substitua pela folha com a assinatura da banca v (cid:13)c EduardoCandido Xavier, 2007. Todosos direitosreservados. vi Resumo NestetrabalhoestudamosdiversosproblemasdeempacotamentoconsideradosNP-difíceis. As- sumindoahipótesedequeP 6= NP,sabemosquenãoexistemalgoritmoseficientes(complexi- dadedetempopolinomial)exatospararesolvertaisproblemas. Umadasabordagensconsidera- dasparatratartaisproblemaséadealgoritmosdeaproximação,quesãoalgoritmoseficientese quegeramsoluçõescomgarantiadequalidade. Nestetrabalhoapresentamosalgunsalgoritmos aproximados para problemas de empacotamento com aplicações práticas. Outra maneira de se lidar com problemas NP-difíceis é o desenvolvimento de heurísticas. Neste trabalho também apresentamos heurísticas baseadas no método de geração de colunas para problemas de corte e empacotamento bidimensional. Resultados computacionais sugerem que tais heurísticas são eficientes egeram soluçõesdemuitoboaqualidade. vii Abstract In this work westudyseveral packingproblemsthat are NP-hard. Ifwe considerthat P 6= NP, we know that there are no efficient (polynomial time complexity) exact algorithms to solve these problems. One way to deal with these kind of problems is to use approximation algo- rithms, that are efficient algorithms that produce solutions with quality guarantee. We present several approximation algorithms for some packing problems that have practical applications. Anotherway todeal with NP-hard problemsis todevelopheuristics. Wealso considercolumn generation based heuristics for packing problems. In this case, we present column generation algorithms for some two dimensional packing problems and also present computational tests with the proposed algorithms. The computational results shows that the heuristics are efficient and producesolutionsofvery goodquality. viii À meus pais,Joãoe Dita, meus irmãosJose, AlexandreeCésar eà Silvana. Agradecimentos Hojeconsidero a educação umadas coisas mais importantesdaminhavida. Passei quasevinte e dois anos da minhavida freqüentando algum tipo de escola. Vintee dois anos tentando fazer comqueeuficasseeducado,eeuaindaestoutentando. Penaqueagoranãomerestaoutracoisa anãoserestudarporcontaprópria. Considerandoaimportânciaquedouàeducação,gostariade agradecer atodosaqueles queainfluenciaram. Todos osprofessores do ensinobásicoe médio, professores da graduação na UFPR e da pós-graduação na UNICAMP. Agradecimentos espe- ciaisvão parameu orientadordeiniciaçãocientífica, AlexandreDireneeao Renato Carmo por me introduzir à Teoria da Computação. Também gostaria de agradecer aos excelentes profes- sores que tiveaqui na UNICAMP, e em especial a alguns, que na minhaopinião estão entre os melhoresprofessoresquetiveemminhavida: CéliadeMello,CiddeSouza,FlávioMiyazawa, Ricardo Dahab eOrlando Lee. Eutiveafelicidadedenasceremumafamíliaquevalorizaaeducação,emeusmaissinceros agradecimentos vão para os meus pais João e Dita, por terem me proporcionado o melhor que podiam, e aos meus irmãos (Alexandre, Zinho e César), que por serem mais velhos do que eu, sempre tinham alguma coisa para me ensinar. Quando era criança me recordo do Zinho, do CésaredoSandre,váriasvezesmeensinandoalgumacoisadematemáticaoufísica,oualguma outracoisaquetinhadúvidas. Algumas pessoas quando terminam o doutorado acabam por receber um doutorado duplo. O primeiro é outorgado pela instituição onde estudou, e é dado na área de estudo. O outro é outorgadopelaprópriapessoa,eéemarrogância. Tiveasortedeterumorientadorquerecusou o segundo título. Por isso agradeço ao Flávio Miyazawa pelos quase 6 anos de orientação produtivaetranqüila. AgradeçoàtodoscolegaseamigosdoICporteremtornadoapós-graduaçãomaisdivertida. Não vou citar nomes pra não esquecer de alguém, mas se você está lendo isso, estes agradeci- mentosvãopara você. Agradeço ao pessoal do Laboratório LOCO, e aos “irmãos” deorientação: André (Piazão), Carlos (Louco), Evandro,Mamão(Rafael), Meira, Nilton(O Cara), e Victor. AgradeçoespecialmenteàminhanoivaSilvana,pelocarinho,amoreamizadedurantetodos estes anos. x