O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta-heurísticas de diferentes categorias. Essas meta-heurísticas são: Iterated Local Search (ILS), classificada como meta-heurística de trajetória; Greedy Randomized Adaptive Search (GRASP), meta-heurística construtiva; e Artificial Bee Colony (ABC), meta-heurística populacional recentemente proposta. Esses métodos foram selecionados por alcançarem bons resultados para diversos problemas de otimização da literatura. São realizados experimentos computacionais com 600 instâncias do JSF, permitindo comparações entre os métodos de resolução. Os resultados mostram que explorar as características do problema permite que uma das regras de prioridade propostas supere a melhor regra da literatura em 81% das instâncias. As meta-heurísticas ILS, GRASP e ABC chegam a conseguir mais de 31% de melhoria sobre as soluções iniciais e a obter atrasos, em média, somente 2,24% superiores aos das soluções ótimas. Também são propostas modificações nas meta-heurísticas que permitem obter melhorias ainda mais expressivas sem aumento do tempo de execução. Adicionalmente é estudada uma versão do JSF com operações de Montagem e Desmontagem (JSFMD) e os experimentos realizados com um conjunto de 150 instâncias também indicam o bom desempenho dos métodos desenvolvidos. / The production environment addressed herein is the Flexible Job Shop (FJS), a generalization of the Job Shop (JS). In the JS environment, the jobs scheduling problem is classified by Garey; Johnson and Sethi (1976) as NP-Hard and the FJS is at least as difficult as the JS. FJS is composed of a set of jobs, each consisting of operations. Each operation must be processed individually, without interruption, in a single machine of a subset of enabled machines. The main performance criterion is minimizing the jobs tardiness. Mixed Integer Linear Programming (MILP) models are presented. These models minimize the total tardiness and the completion time of the last operation, makespan. New priority rules of jobs are proposed, as well as adaptations of rules from the literature. These rules are used by constructive heuristics and are combined with strategies aimed at exploiting specific characteristics of FSJ. In order to improve the solutions initially obtained, local searches and other improvement mechanisms are proposed and used in the development of metaheuristics of three different categories. These metaheuristics are: Iterated Local Search (ILS), classified as trajectory metaheuristic; Greedy Randomized Adaptive Search (GRASP), constructive metaheuristic, and Artificial Bee Colony (ABC), recently proposed population metaheuristic. These methods were selected owing to their good results for various optimization problems in the literature. Computational experiments using 600 FJS instances are carried out to allow comparisons between the resolution methods. The results show that exploiting the characteristics of the problem allows one of the proposed priority rules to exceed the best literature rule in about 81% of instances. Metaheuristics ILS, GRASP and ABC achieve more than 31% improvement over the initial solutions and obtain an average tardiness only 2.24% higher than the optimal solutions. Modifications in metaheuristics are proposed to obtain even more significant improvements without increased execution time. Additionally, a version called Disassembly and Assembly FSJ (DAFJS) is studied and the experiments performed with a set of 150 instances also indicate good performance of the methods developed.

O objetivo de estudo desta dissertação é o desenvolvimento de um modelo de planejamento agregado da produção que apóie as decisões de nível gerencial e de diretoria das usinas de açúcar e álcool no que tange às variedades de cana colhidas em cada semana, às compras de cana-de-açúcar de terceiros, ao tipo de transporte (próprio ou terceirizado) a se utilizar em cada semana, ao total de cana moída por semana para atendimento da demanda e aos processos (industrial e comercial) que se devem escolher para produzir e comercializar açúcar e álcool. As decisões devem ocorrer em função de preços nos mercados interno, externo e mercado futuro, do fluxo de caixa da empresa, da capacidade da usina para armazenar açúcar e álcool e da possibilidade de uso de estoque de terceiros. As decisões por compra de cana, escolha de processos e venda de produtos são tomadas semanalmente num horizonte móvel de planejamento de 52 semanas, que inclui o tempo de safra no centro-sul do Brasil (meados de março a meados de dezembro, aproximadamente 36 semanas) mais o período de entressafra (aproximadamente 16 semanas, de meados de dezembro a meados de março). A procura por melhores estratégias de comercialização de tal forma a auxiliar a tomada de decisões é uma necessidade constante dos empresários do setor, que muitas vezes são surpreendidos pelas variações de preços de açúcar e álcool no mercado interno, externo e mercado futuro. Na parte comercial, este trabalho utiliza o método Delphi de previsão de preços de açúcar e álcool que balizam as tomadas de decisão no planejamento e controle da produção das usinas de açúcar e álcool. Define-se Hedge como a operação financeira de proteger determinado ativo de uma empresa contra variações inesperadas de preços. Neste trabalho, utiliza-se um modelo de escolha de mix de produto para Hedge vinculado à lucratividade e minimização de risco denominado Modelo de Semi- Variância com análise de cenários de Markowitz. Nas decisões relacionadas com as partes agrícola, industrial e comercial, faz-se uso de um modelo de programação linear inteira mista e para resolvê-lo utiliza-se o software de programação matemática LINGO e suas interfaces com a planilha eletrônica Excel. Nas decisões vinculadas ao mix ótimo para o Hedge em cada semana, faz-se uso de um modelo de programação quadrática resolvido pelo LINGO e suas interfaces com a planilha eletrônica Excel. Um estudo de caso foi realizado numa usina de açúcar e álcool no município de Junqueirópolis (SP) para validar o modelo proposto. / The objective of study this dissertation is to develop a model of aggregate production planning to support the decisions of management and board level of sugar and alcohol plants in regard to varieties of cane harvested each week, purchasing cane of nonsugar, the type of transport (own or outsourced) to use each week, the total cane processed per week for taking care of the demand and processes (industrial and commercial) and that must be chosen to produce and sell sugar and alcohol. Decisions must occur in terms of domestic, foreign and future market prices, the company\'s cash flow and the capacity to store sugar and alcohol and the possibility of using stock to third parties. Decisions about buying cane, choice of processes and products for sale are made in a weekly mobile planning horizon of 52 weeks, which includes the time of harvest in central-southern Brazil (mid-March to mid-December, approximately 36 weeks) plus the off-season (approximately 16 weeks, from mid-December to mid March). The demand for better marketing strategies to help such decision making is a constant need for entrepreneurs in the sector, which are often surprised by the changes in prices of sugar and alcohol in the internal, external and future market. In the commercial part, this study uses the Delphi method of forecasting the price of sugar and alcohol that guides the decision-making in planning and controlling the production of sugar and alcohol plants. Hedging is defined as a financial transaction to protect certain assets of a business against unexpected changes in prices. In this work, it is used a model of choice of product mix for Hedge linked to profitability and minimizing risk named Model of Semi-Variance analysis with scenarios of Markowitz. In decisions related to the agricultural, industrial and commercial parts it is used a type of mixed integer linear programming and to solve it is used the mathematical programming software LINGO and its interface with Excel spreadsheets. In decisions related to the optimal mix for Hedge in each week, is used a quadratic programming model solved by LINGO and its interface with Excel spreadsheets. A case study was conducted in a sugar mill and alcohol in the city of Junqueirópolis (SP) to validate the proposed model.

Orientador: Rubén Augusto Romero Lázaro / Resumo: Neste trabalho, consideram-se a análise teórica e a implementação computacional dos algoritmos Primal Simplex Canalizado (PSC) e Dual Simplex Canalizado (DSC) especializados. Esses algoritmos foram incorporados em um algoritmo Branch and Bound (B&B) de modo a resolver o problema de Planejamento da Expansão de Sistemas de Transmissão (PEST). Neste caso, o problema PEST foi modelado usando os chamados modelo de Transportes e modelo Linear Disjuntivo (LD), o que produz um problema de Programação Linear Inteiro Misto (PLIM). O algoritmo PSC é utilizado na resolução do problema de Programação Linear (PL) inicial após desconsiderar a restrição de integralidade do problema PLIM original. Juntamente com o algoritmo PSC, foi implementada uma estratégia para reduzir o número de variáveis artificiais adicionadas ao PL, consequentemente reduzindo o número de iterações do algoritmo PSC. O algoritmo DSC é utilizado na reotimização eficiente dos subproblemas gerados pelo algoritmo B&B, através do quadro ótimo do PL inicial, excluindo, assim, a necessidade da resolução completa de cada subproblema e, consequentemente, reduzindo o consumo de processamento e memória. Nesta pesquisa, é apresentada uma nova proposta de otimização, e, consequentemente, a implementação computacional usando a linguagem de programação FORTRAN que opera independentemente de qualquer solver. / Doutor

Submitted by JEFERSON BACK VANDERLINDE null (jefersonbv@yahoo.com.br) on 2017-11-01T16:38:25Z No. of bitstreams: 1 jeferson_tese_final_20171101.pdf: 4860852 bytes, checksum: 2f99c37969be3815f82b1b4455a40230 (MD5) / Approved for entry into archive by LUIZA DE MENEZES ROMANETTO (luizamenezes@reitoria.unesp.br) on 2017-11-13T15:38:34Z (GMT) No. of bitstreams: 1 vanderlinde_jb_dr_ilha.pdf: 4860852 bytes, checksum: 2f99c37969be3815f82b1b4455a40230 (MD5) / Made available in DSpace on 2017-11-13T15:38:34Z (GMT). No. of bitstreams: 1 vanderlinde_jb_dr_ilha.pdf: 4860852 bytes, checksum: 2f99c37969be3815f82b1b4455a40230 (MD5) Previous issue date: 2017-09-06 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho, consideram-se a análise teórica e a implementação computacional dos algoritmos Primal Simplex Canalizado (PSC) e Dual Simplex Canalizado (DSC) especializados. Esses algoritmos foram incorporados em um algoritmo Branch and Bound (B&B) de modo a resolver o problema de Planejamento da Expansão de Sistemas de Transmissão (PEST). Neste caso, o problema PEST foi modelado usando os chamados modelo de Transportes e modelo Linear Disjuntivo (LD), o que produz um problema de Programação Linear Inteiro Misto (PLIM). O algoritmo PSC é utilizado na resolução do problema de Programação Linear (PL) inicial após desconsiderar a restrição de integralidade do problema PLIM original. Juntamente com o algoritmo PSC, foi implementada uma estratégia para reduzir o número de variáveis artificiais adicionadas ao PL, consequentemente reduzindo o número de iterações do algoritmo PSC. O algoritmo DSC é utilizado na reotimização eficiente dos subproblemas gerados pelo algoritmo B&B, através do quadro ótimo do PL inicial, excluindo, assim, a necessidade da resolução completa de cada subproblema e, consequentemente, reduzindo o consumo de processamento e memória. Nesta pesquisa, é apresentada uma nova proposta de otimização, e, consequentemente, a implementação computacional usando a linguagem de programação FORTRAN que opera independentemente de qualquer solver. / In this research, the theoretical analysis and computational implementation of the specialized dual simplex algorithm (DSA) and primal simplex algorithm (PSA) for bounded variables is considered. These algorithms have been incorporated in a Branch and Bound (B&B) algorithm to solve the Transmission Network Expansion Planning (TNEP) problem. In this case, the TNEP problem is modeled using transportation model and linear disjunctive model (DM), which produces a mixed-integer linear programming (MILP) problem. After relaxing the integrality of investment variables of the original MILP problem, the PSA is used to solve the initial linear programming (LP) problem. Also, it has been implemented a strategy in PSA to reduce the number of artificial variables which are added into the LP problem, and consequently reduces the number of iterations of PSA. Through optimal solution of the initial LP, the DSA is used in efficient reoptimization of subproblems, resulting from the B&B algorithm, thus excludes the need for complete resolution of each subproblems, which results reducing the CPU time and memory consumption. This research presents the implementation of the proposed approach using the FORTRAN programming language which operates independently and does not use any commercial solver.

O objetivo de estudo desta dissertação é o desenvolvimento de um modelo de planejamento agregado da produção que apóie as decisões de nível gerencial e de diretoria das usinas de açúcar e álcool no que tange às variedades de cana colhidas em cada semana, às compras de cana-de-açúcar de terceiros, ao tipo de transporte (próprio ou terceirizado) a se utilizar em cada semana, ao total de cana moída por semana para atendimento da demanda e aos processos (industrial e comercial) que se devem escolher para produzir e comercializar açúcar e álcool. As decisões devem ocorrer em função de preços nos mercados interno, externo e mercado futuro, do fluxo de caixa da empresa, da capacidade da usina para armazenar açúcar e álcool e da possibilidade de uso de estoque de terceiros. As decisões por compra de cana, escolha de processos e venda de produtos são tomadas semanalmente num horizonte móvel de planejamento de 52 semanas, que inclui o tempo de safra no centro-sul do Brasil (meados de março a meados de dezembro, aproximadamente 36 semanas) mais o período de entressafra (aproximadamente 16 semanas, de meados de dezembro a meados de março). A procura por melhores estratégias de comercialização de tal forma a auxiliar a tomada de decisões é uma necessidade constante dos empresários do setor, que muitas vezes são surpreendidos pelas variações de preços de açúcar e álcool no mercado interno, externo e mercado futuro. Na parte comercial, este trabalho utiliza o método Delphi de previsão de preços de açúcar e álcool que balizam as tomadas de decisão no planejamento e controle da produção das usinas de açúcar e álcool. Define-se Hedge como a operação financeira de proteger determinado ativo de uma empresa contra variações inesperadas de preços. Neste trabalho, utiliza-se um modelo de escolha de mix de produto para Hedge vinculado à lucratividade e minimização de risco denominado Modelo de Semi- Variância com análise de cenários de Markowitz. Nas decisões relacionadas com as partes agrícola, industrial e comercial, faz-se uso de um modelo de programação linear inteira mista e para resolvê-lo utiliza-se o software de programação matemática LINGO e suas interfaces com a planilha eletrônica Excel. Nas decisões vinculadas ao mix ótimo para o Hedge em cada semana, faz-se uso de um modelo de programação quadrática resolvido pelo LINGO e suas interfaces com a planilha eletrônica Excel. Um estudo de caso foi realizado numa usina de açúcar e álcool no município de Junqueirópolis (SP) para validar o modelo proposto. / The objective of study this dissertation is to develop a model of aggregate production planning to support the decisions of management and board level of sugar and alcohol plants in regard to varieties of cane harvested each week, purchasing cane of nonsugar, the type of transport (own or outsourced) to use each week, the total cane processed per week for taking care of the demand and processes (industrial and commercial) and that must be chosen to produce and sell sugar and alcohol. Decisions must occur in terms of domestic, foreign and future market prices, the company\'s cash flow and the capacity to store sugar and alcohol and the possibility of using stock to third parties. Decisions about buying cane, choice of processes and products for sale are made in a weekly mobile planning horizon of 52 weeks, which includes the time of harvest in central-southern Brazil (mid-March to mid-December, approximately 36 weeks) plus the off-season (approximately 16 weeks, from mid-December to mid March). The demand for better marketing strategies to help such decision making is a constant need for entrepreneurs in the sector, which are often surprised by the changes in prices of sugar and alcohol in the internal, external and future market. In the commercial part, this study uses the Delphi method of forecasting the price of sugar and alcohol that guides the decision-making in planning and controlling the production of sugar and alcohol plants. Hedging is defined as a financial transaction to protect certain assets of a business against unexpected changes in prices. In this work, it is used a model of choice of product mix for Hedge linked to profitability and minimizing risk named Model of Semi-Variance analysis with scenarios of Markowitz. In decisions related to the agricultural, industrial and commercial parts it is used a type of mixed integer linear programming and to solve it is used the mathematical programming software LINGO and its interface with Excel spreadsheets. In decisions related to the optimal mix for Hedge in each week, is used a quadratic programming model solved by LINGO and its interface with Excel spreadsheets. A case study was conducted in a sugar mill and alcohol in the city of Junqueirópolis (SP) to validate the proposed model.

O ambiente de produção abordado neste trabalho é o Job Shop Flexível (JSF), uma generalização do Job Shop (JS). O problema de programação de tarefas, ou jobs, no ambiente JS é classificado por Garey; Johnson e Sethi (1976) como NP-Difícil e o JSF é, no mínimo, tão difícil quanto o JS. O JSF é composto por um conjunto de jobs, cada qual constituído por operações. Cada operação deve ser processada individualmente, sem interrupção, em uma única máquina de um subconjunto de máquinas habilitadas. O principal critério de desempenho considerado é a minimização dos atrasos dos jobs. São apresentados modelos de Programação Linear Inteira Mista (PLIM) para minimizar o atraso total e o instante de término da última operação, o makespan. São propostas novas regras de prioridade dos jobs, além de adaptações de regras da literatura. Tais regras são utilizadas por heurísticas construtivas e são aliadas a estratégias cujo objetivo é explorar características específicas do JSF. Visando aprimorar as soluções inicialmente obtidas, são propostas buscas locais e outros mecanismos de melhoria utilizados no desenvolvimento de três meta-heurísticas de diferentes categorias. Essas meta-heurísticas são: Iterated Local Search (ILS), classificada como meta-heurística de trajetória; Greedy Randomized Adaptive Search (GRASP), meta-heurística construtiva; e Artificial Bee Colony (ABC), meta-heurística populacional recentemente proposta. Esses métodos foram selecionados por alcançarem bons resultados para diversos problemas de otimização da literatura. São realizados experimentos computacionais com 600 instâncias do JSF, permitindo comparações entre os métodos de resolução. Os resultados mostram que explorar as características do problema permite que uma das regras de prioridade propostas supere a melhor regra da literatura em 81% das instâncias. As meta-heurísticas ILS, GRASP e ABC chegam a conseguir mais de 31% de melhoria sobre as soluções iniciais e a obter atrasos, em média, somente 2,24% superiores aos das soluções ótimas. Também são propostas modificações nas meta-heurísticas que permitem obter melhorias ainda mais expressivas sem aumento do tempo de execução. Adicionalmente é estudada uma versão do JSF com operações de Montagem e Desmontagem (JSFMD) e os experimentos realizados com um conjunto de 150 instâncias também indicam o bom desempenho dos métodos desenvolvidos. / The production environment addressed herein is the Flexible Job Shop (FJS), a generalization of the Job Shop (JS). In the JS environment, the jobs scheduling problem is classified by Garey; Johnson and Sethi (1976) as NP-Hard and the FJS is at least as difficult as the JS. FJS is composed of a set of jobs, each consisting of operations. Each operation must be processed individually, without interruption, in a single machine of a subset of enabled machines. The main performance criterion is minimizing the jobs tardiness. Mixed Integer Linear Programming (MILP) models are presented. These models minimize the total tardiness and the completion time of the last operation, makespan. New priority rules of jobs are proposed, as well as adaptations of rules from the literature. These rules are used by constructive heuristics and are combined with strategies aimed at exploiting specific characteristics of FSJ. In order to improve the solutions initially obtained, local searches and other improvement mechanisms are proposed and used in the development of metaheuristics of three different categories. These metaheuristics are: Iterated Local Search (ILS), classified as trajectory metaheuristic; Greedy Randomized Adaptive Search (GRASP), constructive metaheuristic, and Artificial Bee Colony (ABC), recently proposed population metaheuristic. These methods were selected owing to their good results for various optimization problems in the literature. Computational experiments using 600 FJS instances are carried out to allow comparisons between the resolution methods. The results show that exploiting the characteristics of the problem allows one of the proposed priority rules to exceed the best literature rule in about 81% of instances. Metaheuristics ILS, GRASP and ABC achieve more than 31% improvement over the initial solutions and obtain an average tardiness only 2.24% higher than the optimal solutions. Modifications in metaheuristics are proposed to obtain even more significant improvements without increased execution time. Additionally, a version called Disassembly and Assembly FSJ (DAFJS) is studied and the experiments performed with a set of 150 instances also indicate good performance of the methods developed.