Este trabalho propõe uma heurística construtiva determinística e uma heurística construtiva probabilística para resolver o problema de programação de projetos com custo de disponibilidade de recursos e custo de penalidade por atraso no término do projeto (RACPT - Resource Availability Cost Problem with Tardiness). Os algoritmos combinam a flexibilidade da atividade com a flexibilidade do recurso para selecionar a próxima atividade a ser programada. A data de início de uma atividade é a data mais cedo em que sua execução não gera o maior pico de utilização dos recursos ou a data mais cedo na qual o custo total do projeto for menor. A melhor versão das heurísticas foi obtida após o teste de várias regras de prioridade, conforme a revisão bibliográfica realizada. As heurísticas propostas foram testadas em 360 instâncias de testes e seus resultados foram comparados aos obtidos pela formulação matemática baseada em strip packing e restrições disjuntivas implementada no programa CPLEX. A heurística construtiva determinística gera uma solução viável rapidamente, porém de baixa qualidade. Já a heurística construtiva probabilística gera soluções ótimas ou próximas da ótima para problemas pequenos ou para problemas fáceis e gera soluções muito melhores do que o CPLEX na metade do tempo computacional para os problemas médios e grandes ou para problemas difíceis. Dado os bons resultados obtidos e à implementação no programa VBA for Microsoft Excel, a heurística construtiva probabilística proposta é um método bom e prático para resolução do RACPT. / This work proposes a deterministic constructive heuristic and a probabilistic constructive heuristic for solving the resource availability cost problem with tardiness (RACPT). The algorithms combine the flexibility of an activity with the flexibility of a resource to select the next activity to be scheduled. The start time of the activity is the earliest date in which the activity\'s execution does not create resources usage peak or the earliest date with the lowest total project cost. We tested several priority rules according to the literature review and determined the best version of the heuristics. Afterwards, we tested the proposed heuristics in 360 instances and compared its results with the solutions obtained by the optimization software CPLEX. The RACPT implementation on CPLEX utilized a mathematical formulation based on strip packing concepts and disjunctive constraints. The computational results showed that the deterministic constructive heuristic generates feasible solutions of poor quality in low computational time. The probabilistic constructive heuristic achieved better results. For small instances or easy problems, it found optimal or near-optimal solutions. For medium and large instances or hard problems, it obtained better results than CPLEX in half-computational time. We believe that the probabilistic constructive heuristic is a good and practical method for solving the RACPT. The proposed algorithm produced good results in reasonable computational time and was implemented on the popular software VBA for Microsoft Excel.

Este trabalho propõe uma heurística construtiva determinística e uma heurística construtiva probabilística para resolver o problema de programação de projetos com custo de disponibilidade de recursos e custo de penalidade por atraso no término do projeto (RACPT - Resource Availability Cost Problem with Tardiness). Os algoritmos combinam a flexibilidade da atividade com a flexibilidade do recurso para selecionar a próxima atividade a ser programada. A data de início de uma atividade é a data mais cedo em que sua execução não gera o maior pico de utilização dos recursos ou a data mais cedo na qual o custo total do projeto for menor. A melhor versão das heurísticas foi obtida após o teste de várias regras de prioridade, conforme a revisão bibliográfica realizada. As heurísticas propostas foram testadas em 360 instâncias de testes e seus resultados foram comparados aos obtidos pela formulação matemática baseada em strip packing e restrições disjuntivas implementada no programa CPLEX. A heurística construtiva determinística gera uma solução viável rapidamente, porém de baixa qualidade. Já a heurística construtiva probabilística gera soluções ótimas ou próximas da ótima para problemas pequenos ou para problemas fáceis e gera soluções muito melhores do que o CPLEX na metade do tempo computacional para os problemas médios e grandes ou para problemas difíceis. Dado os bons resultados obtidos e à implementação no programa VBA for Microsoft Excel, a heurística construtiva probabilística proposta é um método bom e prático para resolução do RACPT. / This work proposes a deterministic constructive heuristic and a probabilistic constructive heuristic for solving the resource availability cost problem with tardiness (RACPT). The algorithms combine the flexibility of an activity with the flexibility of a resource to select the next activity to be scheduled. The start time of the activity is the earliest date in which the activity\'s execution does not create resources usage peak or the earliest date with the lowest total project cost. We tested several priority rules according to the literature review and determined the best version of the heuristics. Afterwards, we tested the proposed heuristics in 360 instances and compared its results with the solutions obtained by the optimization software CPLEX. The RACPT implementation on CPLEX utilized a mathematical formulation based on strip packing concepts and disjunctive constraints. The computational results showed that the deterministic constructive heuristic generates feasible solutions of poor quality in low computational time. The probabilistic constructive heuristic achieved better results. For small instances or easy problems, it found optimal or near-optimal solutions. For medium and large instances or hard problems, it obtained better results than CPLEX in half-computational time. We believe that the probabilistic constructive heuristic is a good and practical method for solving the RACPT. The proposed algorithm produced good results in reasonable computational time and was implemented on the popular software VBA for Microsoft Excel.

Underground mining is a complex operation that requires careful planning. The short-term scheduling, which is the scheduling of the tasks involved in the excavation process, is an important part of the planning process. In this master thesis we propose a new method for short-term scheduling of a cut-and-fill mine operated by the mining company Boliden AB. We include a new aspect of the problem by incorporating a priority between the excavation locations of the mine. The priority feature allows the user to control the output of the scheduling and to direct resources to the locations where they are most needed according to the long-term plans. Our solution method consists of two components: a constructive heuristic method that construct a complete solution by solving partial scheduling problems containing subsets of tasks, and a logic-based Benders decomposition scheme for solving these partial problems. The computational performance of the proposed method is evaluated on industrially relevant largescale instances generated from data provided by Boliden. Comparisons are made with applying a constraint programming solver on the complete problem and with replacing the logic-based Benders scheme by applying a constraint programming solver on the partial scheduling problems, respectively. Results show that the heuristic method combined with the logic-based Benders decomposition scheme outperforms the other two methods on all instances.

Workforce scheduling is widely used within most industries. A well-outlined and efficient schedule gives cost savings, such as reduced number of overtime hours, increases overall utilization, and facilitates meeting demands. A large and complex schedule, for example, scheduling of a health care workforce, needs to consider many parameters when constructed; it is essential to account for all critical constraints regarding who can dispense a particular medicine, laws restricting the health care system, etcetera. This thesis evaluates two different methods for implementing a workforce scheduling system for one of Linköping’s most well-known restaurants and bars for students, using mixed integer programming and heuristics. Flamman Pub & Disco recruits new employees prior to every semester. Usually, the workforce consists of around 100 employees, and the vast majority of them work either in the bar or in the kitchen. Historically, the scheduling process has been handled manually using Excel. This does, however, take up much time for the operations manager, something considered frowned upon. Therefore, this thesis suggests an automated scheme for future scheduling processes. Because Flamman is a student organization, they do not hold the capital to invest in expensive licensed optimization software. However, literature studies have shown that heuristics such as large neighborhood search can generate sufficient performance, and therefore the investigation of free-of-charge software using a heuristic approach is conducted. The constructed framework uses a mixed integer programming model, which also lays the cornerstone for the two heuristics: a reverse constructive heuristic and a large neighborhood search. The results retrieved from the analysis prove that a heuristic can be a helpful tool for upcoming recruitment periods. There are, however, recommended areas for improvement regarding the current state of the heuristic.

Este trabalho trata do problema de sequenciamento e programação de atividades em máquinas diferentes em paralelo, considerando elegibilidade de máquina, e tempo de liberação das máquinas e das atividades com o objetivo de minimizar o custo de atraso total. Tal problema é descrito pela literatura como NP-hard. Foi proposto um método otimizante que envolve modelagem matemática, um algoritmo de geração de colunas e, além disso, uma heurística para tratar problemas com instancias maiores. O algoritmo de geração de colunas é baseado no método proposto por Akker, Hurkens e Savelsbergh (2000), que foi adaptado para o problema de múltiplas máquinas diferentes. Assim, o método foi aplicado em instâncias da literatura e em instâncias geradas para este trabalho de até 25 atividades e 4 máquinas. Os resultados foram analisados e observou-se que o modelo de programação inteira mista e eficiente para encontrar limitantes superiores de boa qualidade. Por outro lado, o algoritmo de geração de colunas é eficiente para encontrar limitantes inferiores para o problema. Desta forma, o método proposto utiliza o modelo MILP e o algoritmo de geração de colunas de maneira a se complementar. Assim, soluções ótimas foram encontradas para 84% das instancias geradas, sendo que o GAP médio para as instancias restantes foi de 2,1%. A heurística proposta e baseada na ideia de heurística construtiva probabilística, que foi apresentada por Arcus (1965). Ela foi executada na massa de dados gerada, resultando em um GAP médio de 10,6%. / This paper deals with the problem of scheduling activities in unrelated parallel parallel, considering machine eligibility, and machine and activity release time in order to minimize total weighted tardiness.Such a problem is described in the literature as NPhard. It has been proposed an optimizing method that involves mathematical modeling and a column generation algorithm, in addition, it is proposed a heuristic to treat problems with larger instances. The column generation algorithm was based on the method proposed by Akker, Hurkens e Savelsbergh (2000), which has been adapted to the problem of multiple diferent machines. Thus, the method was applied in instances of the literature and in instances generated for this paper up to 25 jobs and 4 machines. The results were analyzed and it was noted that the mixed integer programming model is eficient to find good quality upper bounds. On the other hand, the column generation algorithm is eficient to find lower bounds for the problem. Therefore, the proposed method uses the MILP model and the column generation algorithm to complement each other. Thus, optimal solutions were found for 84 % of the generated instances, with the mean GAP for the remaining instances being 2.1 %. The proposed heuristic is based on the idea of probabilistic constructive heuristics, which was presented by Arcus (1965). It was run on the mass of data generated, resulting in an average GAP of 10,6%.

Este trabalho trata do problema de sequenciamento e programação de atividades em máquinas diferentes em paralelo, considerando elegibilidade de máquina, e tempo de liberação das máquinas e das atividades com o objetivo de minimizar o custo de atraso total. Tal problema é descrito pela literatura como NP-hard. Foi proposto um método otimizante que envolve modelagem matemática, um algoritmo de geração de colunas e, além disso, uma heurística para tratar problemas com instancias maiores. O algoritmo de geração de colunas é baseado no método proposto por Akker, Hurkens e Savelsbergh (2000), que foi adaptado para o problema de múltiplas máquinas diferentes. Assim, o método foi aplicado em instâncias da literatura e em instâncias geradas para este trabalho de até 25 atividades e 4 máquinas. Os resultados foram analisados e observou-se que o modelo de programação inteira mista e eficiente para encontrar limitantes superiores de boa qualidade. Por outro lado, o algoritmo de geração de colunas é eficiente para encontrar limitantes inferiores para o problema. Desta forma, o método proposto utiliza o modelo MILP e o algoritmo de geração de colunas de maneira a se complementar. Assim, soluções ótimas foram encontradas para 84% das instancias geradas, sendo que o GAP médio para as instancias restantes foi de 2,1%. A heurística proposta e baseada na ideia de heurística construtiva probabilística, que foi apresentada por Arcus (1965). Ela foi executada na massa de dados gerada, resultando em um GAP médio de 10,6%. / This paper deals with the problem of scheduling activities in unrelated parallel parallel, considering machine eligibility, and machine and activity release time in order to minimize total weighted tardiness.Such a problem is described in the literature as NPhard. It has been proposed an optimizing method that involves mathematical modeling and a column generation algorithm, in addition, it is proposed a heuristic to treat problems with larger instances. The column generation algorithm was based on the method proposed by Akker, Hurkens e Savelsbergh (2000), which has been adapted to the problem of multiple diferent machines. Thus, the method was applied in instances of the literature and in instances generated for this paper up to 25 jobs and 4 machines. The results were analyzed and it was noted that the mixed integer programming model is eficient to find good quality upper bounds. On the other hand, the column generation algorithm is eficient to find lower bounds for the problem. Therefore, the proposed method uses the MILP model and the column generation algorithm to complement each other. Thus, optimal solutions were found for 84 % of the generated instances, with the mean GAP for the remaining instances being 2.1 %. The proposed heuristic is based on the idea of probabilistic constructive heuristics, which was presented by Arcus (1965). It was run on the mass of data generated, resulting in an average GAP of 10,6%.

Balancing trade-offs between production cost and holding cost is critical for production and operations management. Utilization of an operating room affects production cost, which relates to makespan, and patient flowtime affects holding cost. There are trade-offs between two objectives, to minimize makespan and to minimize flowtime. However, most existing constructive heuristics focus only on single-objective optimization. In the current literature, NEH is the best constructive heuristic to minimize makespan, and LR heuristic is the best to minimize flowtime. In this thesis, we propose a current and future deviation (CFD) heuristic to balance trade-offs between makespan and flowtime minimizations. Based on 5400 randomly generated instances and 120 instances in Taillard’s benchmarks, our CFD heuristic outperforms NEH and LR heuristics on trade-off balancing, and achieves the most stable performances from the perspective of statistical process control.

Neste trabalho é proposta uma nova técnica de solução para resolver o problema de planejamento da expansão de sistemas de transmissão estático através da introdução da tomada de decisão fuzzy. Na técnica apresentada neste trabalho, a tomada de decisão fuzzy é aplicada para o desenvolvimento de um algoritmo heurístico construtivo. O sistema fuzzy é utilizado para contornar alguns problemas críticos das heurísticas que utilizam o índice de sensibilidade como guia para inserção de novas linhas. A heurística apresentada nesse trabalho é baseada na técnica dividir para conquistar. Verificou-se que a deficiência das heurísticas construtivas é decorrente da decisão de inserir novas linhas baseada em valores não seguros encontrados através da solução do modelo utilizado. Para contornar tal deficiência, sempre que surgirem valores não seguros divide-se o problema original em dois subproblemas, um que analisa a qualidade da resposta para o caso em que a linha é inserida e outro para verificar a qualidade da resposta para o caso em que a linha não é inserida. A tomada de decisão fuzzy é utilizada para decidir sobre quando dividir o problema em dois novos subproblemas. Utilizou-se o modelo cc com a estratégia de Villasana-Garver-Salon para realizar a modelagem da rede elétrica para os problemas da expansão de sistemas de transmissão aqui propostos. Ao serem realizados testes em sistemas de pequeno, médio e grande portes certificou-se que o método pode encontrar a solução ótima de sistemas de pequeno e médio portes. Porém, a solução ótima dos sistemas de grande porte testados não foi encontrada. Para melhorar a qualidade da solução encontrada utilizou, em uma segunda fase, a metaheurística busca tabu. A busca tabu utiliza o modelo cc. Os resultados se mostraram bastante promissores. Os testes foram realizados em alguns sistemas reais brasileiros e com o sistema real colombiano. / A new solution technique to solve the long-term static transmission expansion planning (TEP) problem based on fuzzy decision making is proposed. The technique applies the concepts of fuzzy decision making in a constructive heuristic algorithm. The fuzzy system is used to circumvent some critical problems of heuristics that use sentivity indices as a guide for insertion and construction of new lines. The heuristic algorithm proposed in this work is based on the divide and conquer technique. It has been verified that the deficiency of the constructive heuristics is due to the decision of inserting new lines based only on information given by the index, which usually is calculated from a relaxed mathematical representation of the problem and can become less accurate during the solution process. In order to be able to deal with such problem, whenever the quality of the index decreases, the original problem is divided into two sub-problems: one examines the quality of the solution when the transmission line indicated by the sensitivity index is inserted and the other subproblem checks the opposite. Fuzzy decision-making is used to decide the moment to divide the problem into two subproblems based on other information. The hybrid linear model is used to model the long-term transmission expansion planning problem and is used in the proposed algorithm. Tests was done with systems of small-term, medium-term and long-term. The optimal solution of small-term and medium-term was foundo using just the construtive heuristic algorithm with fuzzy decision-making. To deal with long-term systems was used the solutions of the construtive heuristic algorithm with fuzzy decision-making to init a tabu search. The tabu search uses the dc model. The results are very promising. The test was done with some real brazilian systems and with the real colombian system.

Neste trabalho é proposta uma nova técnica de solução para resolver o problema de planejamento da expansão de sistemas de transmissão estático através da introdução da tomada de decisão fuzzy. Na técnica apresentada neste trabalho, a tomada de decisão fuzzy é aplicada para o desenvolvimento de um algoritmo heurístico construtivo. O sistema fuzzy é utilizado para contornar alguns problemas críticos das heurísticas que utilizam o índice de sensibilidade como guia para inserção de novas linhas. A heurística apresentada nesse trabalho é baseada na técnica dividir para conquistar. Verificou-se que a deficiência das heurísticas construtivas é decorrente da decisão de inserir novas linhas baseada em valores não seguros encontrados através da solução do modelo utilizado. Para contornar tal deficiência, sempre que surgirem valores não seguros divide-se o problema original em dois subproblemas, um que analisa a qualidade da resposta para o caso em que a linha é inserida e outro para verificar a qualidade da resposta para o caso em que a linha não é inserida. A tomada de decisão fuzzy é utilizada para decidir sobre quando dividir o problema em dois novos subproblemas. Utilizou-se o modelo cc com a estratégia de Villasana-Garver-Salon para realizar a modelagem da rede elétrica para os problemas da expansão de sistemas de transmissão aqui propostos. Ao serem realizados testes em sistemas de pequeno, médio e grande portes certificou-se que o método pode encontrar a solução ótima de sistemas de pequeno e médio portes. Porém, a solução ótima dos sistemas de grande porte testados não foi encontrada. Para melhorar a qualidade da solução encontrada utilizou, em uma segunda fase, a metaheurística busca tabu. A busca tabu utiliza o modelo cc. Os resultados se mostraram bastante promissores. Os testes foram realizados em alguns sistemas reais brasileiros e com o sistema real colombiano. / A new solution technique to solve the long-term static transmission expansion planning (TEP) problem based on fuzzy decision making is proposed. The technique applies the concepts of fuzzy decision making in a constructive heuristic algorithm. The fuzzy system is used to circumvent some critical problems of heuristics that use sentivity indices as a guide for insertion and construction of new lines. The heuristic algorithm proposed in this work is based on the divide and conquer technique. It has been verified that the deficiency of the constructive heuristics is due to the decision of inserting new lines based only on information given by the index, which usually is calculated from a relaxed mathematical representation of the problem and can become less accurate during the solution process. In order to be able to deal with such problem, whenever the quality of the index decreases, the original problem is divided into two sub-problems: one examines the quality of the solution when the transmission line indicated by the sensitivity index is inserted and the other subproblem checks the opposite. Fuzzy decision-making is used to decide the moment to divide the problem into two subproblems based on other information. The hybrid linear model is used to model the long-term transmission expansion planning problem and is used in the proposed algorithm. Tests was done with systems of small-term, medium-term and long-term. The optimal solution of small-term and medium-term was foundo using just the construtive heuristic algorithm with fuzzy decision-making. To deal with long-term systems was used the solutions of the construtive heuristic algorithm with fuzzy decision-making to init a tabu search. The tabu search uses the dc model. The results are very promising. The test was done with some real brazilian systems and with the real colombian system.

Orientador: Sérgio Azevedo de Oliveira / Banca: Rubén Augusto Romero Lazaro / Banca: Eduardo Nobuhiro Asada / Resumo: Neste trabalho foram implementados diversos agentes heuristicos construtivos, baseados no modelo híbrido linear, que fazem parte de um time assíncrono que tem como objetivo gerar configurações de boa qualidade para inicializar as metaheuríticas que resolvem o problema do planejamento da expansão da transmissão dos sistemas de energia elétrica. A teoria de times assíncronos foi aplicada para reunir as qualidades individuais dos métodos heurísticos, de uma maneira que, partindo de uma configuração base (sem adições) e utilizando um fluxo de dados cíclico, os agentes construtivos adicionassem circuitos a esta configuração de maneira sistemática e aleatória até que esta atenda as demandas de carga solicitadas pelo sistema elétrico em um horizonte futuro. Estas configurações foram então utilizadas por um algoritmo genético no intuito de validar a qualidade das mesmas. Os algoritmos foram implementados em Fortran, utilizando as rotinas de trocas de mensagens do LAM-MPI e simulados para sistemas teste de pequeno, médio e grande porte em ambiente de processamento distribuido. Os resultados comprovam que os times ass'ıncronos de vários metodos heurísticos são mais eficazes comparados com uma única heurística. / Abstract: In this study, it was implemented several constructive heuristic algorithms, based on hybrid linear model, which are part of a asynchronous team that aims to generate initial solutions with good quality for meta-heuristics that solve the transmission expansion planning problem of electric power systems. The theory of asynchronous team was applied to meet the individual qualities of each heuristic method, in a way that, starting from a base network configuration and using a cyclical flow of data, heuristic agents add circuits to is configuration in a systematic and random way until they meet the load demands requested by the electrical system on a future horizon. Then these configurations are utilized by a genetic algorithm in order to validate the quality of them. The algorithms were implemented in Fortran, using exchanging messages routines from LAM-MPI and simulated for small, medium and large size test-systems in distributed processing environment. The results show that the solutions obtained with asynchronous teams of several heuristic methods are more effective than the solutions with a single heuristic algorithm. / Mestre