[pt] Esta dissertação apresenta um estudo de caso em seqüenciamento da produção de bobinas de aço em um laminador de tiras a quente com enfornamento a frio das placas de aço. O laminador em questão é o da Companhia Siderúrgica de Tubarão, uma grande usina siderúrgica integrada localizada no estado do Espírito Santo, Brasil. Seu start up está previsto para o segundo semestre de 2002. Num primeiro momento, o problema parece ser de tratamento complexo, comportando-se como um grande problema combinatorial com restrições difíceis de serem representadas. Algumas considerações para um bom seqüenciamento são comuns tanto no forno de reaquecimento quanto no laminador desbastador. Isto permite que as placas possam ser seqüenciadas como se esses dois equipamentos fossem um único estágio (equipamento) para alguns agrupamentos de produtos. Assim, o foco pode ser deslocado para o seqüenciamento no estágio final do laminador, isto é no trem acabador. Inicialmente, a idéia era resolver um modelo da mochila compartimentada para a seleção das placas de aço a serem processadas entre duas trocas consecutivas de cilindros de trabalho do trem acabador e usar algumas heurísticas para seqüenciá-las dentro de cada compartimento (faixa de largura). Um estudo do mix de produção planejado mostrou que, devido à grande variedade e quantidade de ordens, a fase de seleção não era crítica e o seqüenciamento poderia ser feito semimanualmente com ajuda do computador. Para aumentar a vida útil dos cilindros de trabalho, assim como atender a qualidade desejada e a data de entrega prometida, no decorrer de uma boa seqüência de laminação deve ocorrer decréscimo nas larguras e na qualidade superficial, trocas suaves de espessuras e de dureza. O sistema computacional proposto implementa um algoritmo simples que seqüencia lexicograficamente o grupo de produtos a ser laminado de acordo com as prioridades dadas a cada critério de seqüenciamento pelo próprio programador da produção, que pode interagir e trocá-las de acordo com as condições prevalecentes. / [en] This thesis reports a case study on scheduling the cold charged production of coils in a hot strip mill with start- up planned for the second semester of 2002 at Companhia Siderúrgica de Tubarão, a large integrated steel plant in Espírito Santo, Brazil. At first glance, the problem seems intractably complex, being essentially a very large-scale combinatorial problem with ill-defined and difficult to represent constraints. Considerations on the requirements for good sequencing at the reheating and roughing stages showed that they could be scheduled as a single stage for some groups of products, and in doing so, the focus could be on sequencing the finishing stage. Initially, the idea was to solve a compartmented knapsack model for selecting the slabs to be processed between two consecutive changes of working rolls, and using some heuristics for sequencing within each compartment (width range). Examination of the projected product mix showed that, due to the large number and variety of orders, the selection phase was not critical, and the scheduling could be performed semi-manually with a simple computer aid. For extending the life of the working rolls, as well as attaining the desirable quality and promised dates, a good sequence must present decreasing width and surface quality, increasing promised dates, and smooth changes of thickness and hardness. The proposed computer system implements a simple algorithm that lexicographically sorts the set of products to be rolled according to priorities given to these criteria by the scheduler who can interactively change them according to the prevailing conditions.

[pt] A maioria das pesquisas científicas publicadas sobre sequenciamento da produção na indústria automobilística consideram os pedidos já alocados em um dia ou turno de trabalho, desconsiderando especificidades do planejamento da cadeia de suprimentos. Esta dissertação procura contribuir no campo do planejamento da produção, propondo um modelo matemático de programação inteira mista que aborda de maneira integrada dois problemas de otimização fundamentais da cadeia: o problema de seleção de pedidos e o problema de sequenciamento de carros em uma única linha de montagem. A fim de abordar questões bem próximas a realidade, incluindo apresentação de experimentos numéricos com o modelo proposto, utilizou-se como cenário o segmento de caminhões, dentro da indústria automotiva. Considerou-se, como objetivo no modelo, além das abordagens tradicionais (minimizar sobrecarga de trabalho, troca de cores e violação de restrições), a demanda dos clientes com relação a prazos de entrega do pedido – principal reforço para uma indústria que pretende cada vez mais migrar para um ambiente de produção orientado pela demanda. / [en] Most published scientific research on production sequencing in the automotive industry consider orders already allocated in a day or shift, disregarding specificities of supply chain planning. This paper aims to contribute in production planning field, proposing a mathematical model of mixed-integer programming that addresses in a integrated way two fundamental problems from chain: the problem of order selection and car sequencing problem on a single assembly line. In order to approach practical issues, including presentation of numerical experiments from proposed model, the truck segment within the automotive industry was used as scenario. It was considered as objective in the model, beyond traditional approaches (minimize work overload, color changing and violation of restrictions), customer demand with respect promised due dates, the main reinforcement for an industry that increasingly want migrate to a production environment driven by demand.

[pt] A presente dissertação propõe um sistema de planejamento e controle da produção a ser utilizado pela fábrica de vacinas de Bio- Manguinhos cuja missão é contribuir para a melhoria dos padrões de saúde pública, através da pesquisa tecnológica e da produção de imunobiológicos, demandado pelo quadro epidemiológico do país. A Bio-Manguinhos cresceu muito nos últimos cinco anos e agora demanda ajustes no processo de planejamento e gestão da produção. A proposta apresentada é composta de um modelo híbrido de planejamento de produção, formado por um módulo de MRPII, que responde pelo planejamento de materiais e necessidades de recursos e um seqüenciador de produção com capacidade finita para apoiar o estabelecimento das prioridades das ordens, otimizando os recursos produtivos. A expectativa gerada pelo projeto é auxiliar a Bio-Manguinhos a atender melhor o seu cliente e se consolidar como uma importante produtora de vacinas. / [en] This master s thesis considers a production planning and control system proposed to the vaccine plant of Bio-Manguinhos, a public foundation with the mission of contributing to the improvement of public health standards, through technological research and the production of immunobiologicals. Bio-Manguinhos has grown significantly in last five years, and now requires adjustments in its planning process and its production management. The proposal presented in this thesis is composed of a hybrid model of production planning, composed of a module of MRPII, that addresses the planning of materials and other resources requirements and a fine capacity scheduler production that sets priorities among orders and supports optimization of resources. The expectation generated by the project is to enable Bio-Manguinhos to improve customer service and to qualify the company as a major vaccine producer.

[pt] O seqüenciamento por hibridação é uma alternativa interessante para a tarefa de seqüenciamento de DNA. Este método ainda está sendo aperfeiçoado e pode superar as técnicas utilizadas em termos de tempo e custo. Uma etapa crucial do método consiste em resolver um problema combinatório que pode ser formulado como um caso especial do problema do caixeiro viajante com coleta de prêmios. Neste trabalho, propõe-se uma nova heurística construtiva multi-partida para resolver este problema. Uma estratégia de aprendizado baseada em uma memória adaptativa e um procedimento de construção de vocabulário são utilizados para melhorar o desempenho da heurística multi-partida. A memória adaptativa é utilizada para intensificar as construções de novas soluções com os elementos que aparecem com uma freqüência maior nas melhores soluções encontradas anteriormente pela heurística multi-partida. O procedimento de construção de vocabulário consiste em construir novas soluções através da combinação de partes comuns a boas soluções. Testes computacionais mostraram que estas duas estratégias aumentam significativamente o desempenho da heurística multi-partida e são particularmente indicadas para problemas de escalonamento nos quais as melhores soluções são na maioria dos casos formadas por blocos de elementos que aparecem juntos com muita freqüência. A heurística proposta supera os resultados dos melhores algoritmos encontrados na literatura, tanto em termos da qualidade das soluções encontradas, como do tempo de computação. / [en] Sequencing by hybridization is an attractive alternative for DNA sequencing. This novel method can be less time and cost consuming than the techniques applied nowadays. A very important step of this method is to solve a combinatorial problem formulated as a special case of the prize-collecting traveling salesman problem. In this work, we propose a new multistart construtive heuristic to solve this problem. A learning strategy based on adaptive memory and a vocabulary building procedure are used to improve the performance of the multistart heuristic. The adaptive memory is used to intensify the construction of new solutions with the elements that appear frequently in the best solutions previously found by the multistart heuristic. The objective of the vocabulary building procedure is to construct new solutions combining parts of good solutions. Computational experiments have shown that these two methods significantly improves the performance of the multistart heuristic and are particularly suitable for scheduling problems whose best solutions are in most cases built by blocks of elements that appear together very often. The proposed heuristic obtains systematically better solutions and is less time consuming than the best algorithms found in the literature.

[pt] Construção de vocabulário é uma heurística para problemas de otimização combinatória que propõe identificar porções de boas soluções e recombiná-las de modo a intensificar a busca em regiões do espaço de soluções identificadas como promissoras. A técnica de construção de vocabulário pode ser aplicada de diversas maneiras na resolução de problemas. Para facilitar a implementação e comparação de algoritmos de um mesmo domínio, a tecnologia de frameworks é uma solução que já demonstrou ser muito eficaz. O objetivo deste trabalho é desenvolver um framework para a implementação de heurísticas baseadas em construçao de vocabulário. O desenvolvimento foi fundamentado em extensa revisão bibliográfica sobre a técnica e em boas práticas de engenharia de software, como frameworks orientados a objetos e padrões de projeto. Como um estudo de caso, foram geradas aplicações a partir do framework para a resolução do problema de seqüenciamento da produção de carros, que é um problema combinatório proposto a partir de necessidades reais da indústria / [en] Vocabulary building is a heuristic for solving combinatorial optimization problems, based on the identification of solution fragments which are common to good solutions and on their combination to intensify the search on promising regions of the solution space. This technique can be vastly applied on problem solving. The technology of frameworks is an efficient strategy to facilitate the implementation and comparison of same domain algorithms. The objective of this work is to develop a framework for the implementation of heuristics based on vocabulary building. Its development was based on a wide bibliographic revision about the technique and good software engineering practices, like oriented objects frameworks and design patters. We generated applications of the framework to solve the car sequencing problem, which is a combinatorial problem proposed by real requirements of the industry

[pt] O desenvolvimento de conteúdos instrucionais utilizando as novas tecnologias de informação é um processo caro, demorado e complexo, que aponta para o estabelecimento de novas metodologias. É neste contexto que surge o conceito de Objeto de Aprendizagem (LO), cujo enfoque está em promover a reutilização do conteúdo. Entretanto, ao considerar o reuso de conteúdo, também se observa uma necessidade de seqüência - lo para formar conteúdos mais elaborados ou mais complexos. Nesta tese adota-se uma estratégia de representar LOs cada vez menores, representando separadamente conteúdo e prática, aqui denominados Objetos Componentes (OCs). Para a estruturação do conteúdo, adaptou-se uma proposta já existente e definiu-se um esquema conceitual adequado à representação de atividades (ou práticas) de aprendizagem. Com vista à composição dos OCs, foi igualmente definido um esquema conceitual envolvendo conteúdos e práticas. Assim, com base em um algoritmo de seqüenciamento de OCs, um professor pode compreender melhor a forma de implementar um objeto complexo, como uma aula ou um curso, reduzindo erros e eventuais omissões na implementação da solução. Este seqüenciamento deve seguir uma metodologia e deve ser especificado de modo não ambíguo. É neste contexto que também é apresentada uma linguagem para especificação de seqüências de objetos de aprendizagem, com uma sintaxe adequada à descrição das possíveis formas de seqüenciamento de LOs. Finalmente, descreve-se um estudo de caso ilustrando a utilização dos esquemas conceituais desenvolvidos, do algoritmo proposto e da linguagem de especificação de seqüências OCs. / [en] The development of instructional content using new Information Technologies is an expensive, time-consuming and complex process that leads to the development of new methodologies. It was in this context that the concept of Learning Objects (LOs) was proposed as an approach that promotes content reuse. However, if content is expressed as small LOs, it is also necessary to sequence them in order to build more elaborated and complex content. In this thesis we adopt a strategy to represent smaller LOs, modeling not only content but also practice, called Component Objects (COs) herein. In order to structure content we adapted an existing proposal and defined a conceptual schema to structure learning practices (or activities). We also defined a conceptual schema for composing these COs. Then, based on these conceptual schemas it was possible to propose an algorithm for sequencing COs, which supports a teacher/professor to better control the implementation of a complex content such as a class or a course, thus reducing errors and eventual omissions in its implementation. The sequencing process must follow a methodology and must be specified in a nonambiguous way. It is in this context that we also present a specification language for sequences of LOs, with a syntax that is adequate to the description of the possible ways of sequencing LOs. Finally, we describe a case study that shows the conceptual schemas that were proposed and the use of the sequencing algorithm and the specification language.

[pt] Oleodutos têm um papel importante no transporte de petróleo e de seus derivados, pois são a maneira mais eficaz de transportar grandes volumes por longas distâncias. A motivação deste trabalho é que uma parte não negligenciável do preço final de um derivado de petróleo é influenciada pelo custo de transporte. Apesar disso, até onde sabemos, apenas alguns autores trabalharam neste problema específico, a maioria utilizando técnicas de programação inteira. Este trabalho analisa a utilização de técnicas de inteligência artificial, arcabouços de software e simulação discreta orientada a eventos para a construção de planejadores automáticos capazes de lidar com instâncias reais de problemas de transporte em oleodutos. A primeira contribuição dessa tese é a especificação de um novo domínio para problemas de planejamento, denominado PIPESWORLD. Este domínio é inspirado no problema de transporte em oleodutos e especificado em PDDL. Por sua estrutura original, ele foi incorporado ao benchmark oficial da 4th International Planner Competition, evento bi-anual que compara o desempenho de diversos planejadores automáticos de propósito geral. Mesmo sendo uma simplificação do problema original, o PIPESWORLD se mostra um domínio bastante desafiador para o estado da arte dos planejadores. É demonstrado também que problemas de decisão derivados de diversas configurações do Pipesworld são NP-Completos. A segunda contribuição dessa tese é o arcabouço de software PLANSIM. Este framework incorpora uma máquina de busca que pode utilizar diversas estratégias, e define uma estrutura que facilita a construção de planejadores automáticos baseados em busca heurística direta que utilizam como modelo do processo a ser planejado simuladores orientados a eventos discretos. São apresentadas instanciações do PLANSIM para a construção de planejadores para problemas clássicos de como o das Torres de Hanoi e Blocksworld. A terceira contribuição da tese é a instanciação do PLANSIM para a construção de um planejador automático capaz de tratar instâncias reais de planejamento de transporte em oleodutos, denominado PLUMBER 05. A utilização de técnicas de simulação discreta orientada a eventos para a representação do modelo do sistema a ser planejado permite que este seja bastante fiel ao problema original. Isto somado ao uso do PLANSIM facilita a construção de planejadores capazes de lidar com instâncias reais. / [en] Pipelines have an important role in oil and its derivatives transportation, since they are the most effective way to transport high volumes through long distances. The motivation for this work is that a non negligible part of the final price for those products are due to transportation costs. Few authors have addressed this problem, with most of the previous work using integer programming techniques. This work analyses the use of Artificial Intelligence techniques, discrete event simulators and software frameworks for building automated planners that are able to deal with real-world oil pipeline transportation instances. The first contribution of this thesis is the specification of a new planning domain called PIPESWORLD. This domain is inspired by the oil pipeline transportation problem, and is defined in PDDL. Due to its original structure, the PIPESWORLD domain has been incorporated to the 4th International Planning Competition benchmark. Even being a simplification of the original problem, PIPESWORLD instances in the benchmark are challenging to state of art solvers. It is also shown that decision problems based on PIPESWORLD configurations are NP-Hard. The second contribution of this thesis is the PLANSIM opensource framework. This framework incorporates a search engine that may use several different strategies, and defines a structure that facilitates the construction of automated planners based on heuristic forward search that use discrete event simulators as the model for the process to be planned. The third contribution of this thesis is a PLANSIM instantiation that results in an automated planner able to deal with real-world oil pipeline transportation instances, called PLUMBER 2. The use of discrete event simulation techniques for the model of the system to be planned allows this model to be very close to the original problem. This, in conjunction with PLANSIM usage, facilitates the construction of planners that are able to cope with real-world instances.

[pt] A exploração e produção de petróleo do Pré-sal ocorre em regiões de águas ultra profundas, com condições complexas de instalação e operação de equipamentos. A interligação dos poços, última etapa que antecede o início da operação de produção, é realizada por embarcações de alto custo, especialmente equipadas para este fim, conhecidas como PLSVs (Pipe Laying Support Vessels). Esta dissertação visa o desenvolvimento de um modelo de programação matemática capaz de alocar e sequenciar as atividades de interligação de poços submarinos em embarcações PLSV, de forma a maximizar a produção de óleo acumulada durante o horizonte de planejamento. Para tanto, foi utilizado como base um problema real enfrentado pela Petrobras, que permitiu estender a abordagem clássica baseada em máquinas paralelas, com a adição de novas restrições. Para tornar a otimização viável, foi criado um método de resolução que utiliza o conceito de blocos de atividades. Visando reduzir a complexidade de resolução, foram realizados testes utilizando apenas blocos compostos por atividades de poços próximos entre si. Tais estratégias se mostraram eficazes e o modelo foi capaz de gerar soluções de execução viável e de qualidade até 21,5 por cento superiores em produção de óleo quando comparadas à solução contruída pelos especialistas do problema. / [en] Pre-salt oil exploration and production occurs in ultra-deep water regions, with complex conditions of equipament installation and operation. The wells connections, last stage before the production phase, is carried out by high-cost vessels, specially equipped for this purpose, known as PLSVs (Pipe Laying Support Vessels). This dissertation aims to develop a mathematical programming model to assign and schedule a PLSV fleet, in order to maximize the oil production during the planning horizon. For this purpose, a real problem faced by Petrobras was used, which allowed to extend the classic parallel machine approach, adding new constraints to the problem. To make the optimization feasible, a resolution method was created using the activities blocks concept. In order to reduce the resolution complexity, tests were performed using blocks composed by activities of wells close to each other. These strategies were effective, generating solutions with quality up to 21.5 percent higher (in oil production) when compared to the solution built by the problem specialists.

[pt] O problema de sequenciamento de tarefas e troca de ferramentas (job sequencing and tool switching problem - SSP) tem sido extensivamente estudado na área de pesquisa operacional, devido à sua relevância prática e interesse metodológico. Dada uma máquina que pode carregar uma quantidade limitada de ferramentas simultaneamente e um número de tarefas que requerem um subconjunto das ferramentas disponíveis, o SSP procura uma sequência de tarefas que minimize o número total de trocas de ferramentas na máquina. Para resolver este problema, é proposta uma busca genética híbrida simples e efetiva baseada em uma representação de solução genérica, um operador de decodificação sob medida, buscas locais eficientes e técnicas de gerenciamento de diversidade. Para orientar a busca, um objetivo secundário desenvolvido para tratar empates é introduzido. Essas técnicas permitem explorar soluções estruturalmente distintas e escapar de ótimos locais. Conforme apresentado nos experimentos computacionais em instâncias clássicas, o algoritmo proposto supera significativamente todas as abordagens anteriores, mesmo sendo de fácil entendimento e implementação. Por fim, resultados obtidos em um novo conjunto de instâncias maiores são reportados para estimular futuras pesquisas e análises comparativas. / [en] The job sequencing and tool switching problem (SSP) has been extensively studied in the field of operations research, due to its practical relevance and methodological interest. Given a machine that can load a limited amount of tools simultaneously and a number of jobs that require a subset of the available tools, the SSP seeks a job sequence that minimizes the number of tool switches in the machine. To solve this problem, we propose a simple and efficient hybrid genetic search based on a generic solution representation, a tailored decoding operator, efficient local searches and diversity management techniques. To guide the search, we introduce a secondary objective designed to break ties. These techniques allow to explore structurally different solutions and escape local optima. As shown in our computational experiments on classical benchmark instances, our algorithm significantly outperforms all previous approaches while remaining simple to apprehend and easy to implement. We finally report results on a new set of larger instances to stimulate future research and comparative analyses.

[pt] Este trabalho trata do problema real de avaliar a capacidade de processamento de pátios ferroviários planos de classificação. Nesses pátios, os vagões são recebidos em trens e movimentam respeitando a disposição dos trilhos e a formação sequencial do trem de saída. Movimentações ineficientes implicam em uma capacidade de processamento inferior à potencial do pátio dado seu layout. O objetivo desta pesquisa é descrever o problema e incitar um método capaz de calcular a capacidade de processamento de pátios ferroviários planos de classificação no horizonte estratégico, indicando se existe ou não a necessidade de um projeto de expansão para garantir atendimento à demanda prevista. O problema foi modelado através de programação linear inteira mista (MILP) baseado na teoria de sequenciamento de produção. O modelo foi aplicado em instâncias de teste, reproduzindo movimentações reais de vagões, e provou avaliar diferentes layouts adequadamente, porém com elevado tempo de execução. A inicialização de algumas variáveis binárias do modelo permitiu um incremento de tamanho nas instâncias, porém ainda inviável para aplicação na prática. / [en] This work deals with the real problem of evaluating the processing capacity of flat rail classification yards. In these yards, the railway cars are received on trains and move respecting the car sequence of the outgoing train. Inefficient movements imply a lower processing capacity than the yard s potential given its layout. The objective of this research is to describe the problem and to incite a method capable of calculating the processing capacity of flat rail classification yards in the strategic horizon, indicating whether or not there is a need for an expansion project to ensure meeting the expected demand. The problem was modeled using mixed integer linear programming (MILP) based on production scheduling theory. The model was applied to test instances, reproducing real railway car movements, and proved to evaluate different layouts properly, but with a high execution time. The initialization of some binary variables of the model allowed an increase in the size of the instances, however it is still unfeasible for practical application.