O problema de dimensionamento de lotes, objeto desse estudo, considera um ambiente composto por múltiplas plantas independentes, múltiplos itens e múltiplos períodos. O ambiente de produção tem capacidade limitada e as plantas podem produzir os mesmos itens. Cada planta tem uma demanda própria e é permitida a transferência de lotes entre as plantas, o que envolve um certo custo. Este problema tem como caso particular o de dimensionamento de lotes com máquinas paralelas. O objetivo desta dissertação é propor uma heurística baseada na meta-heurística GRASP (Greedy Randomized Adaptive Search Procedures). Além disso, uma estratégia path relinking foi incorporada ao GRASP como uma fase de melhoria do algoritmo. Para verificar a eficiência da heurística proposta, os seus resultados são comparados aos da literatura tanto no caso de máquinas paralelas quanto no de múltiplas plantas. Como resultado, o problema de múltiplas plantas obteve melhores resultados quando comparado aos da heurística da literatura. Com relação ao problema de máquinas paralelas, a heurística proposta se mostrou competitiva / The lot sizing problem, which is the aim of this study, considers an environment consisting of multiple independent plants, multiple items and multiple periods. The production environment has limited capacity and the plants can produce the same items. Each plant has its own demand and the lot transfers between the plants are permitted, which involves a certain cost. This problem has as a particular case the parallel machines lot sizing problem. The objective of this dissertation is to propose a heuristic based on the GRASP (Greedy Randomized Adaptive Search Procedures). Furthermore, a path relinking phase is embedded in the GRASP to obtain better performance. To verify the efficiency of the proposed heuristic, its results were compared with the literature as for the multi-plant as for parallel machines problem. Computational tests showed that the proposed heuristic performed better than other literature heuristic concerning the multiplant problem. Concerning the parallel machines, the heuristic is competitive

O objetivo desta dissertação é fornecer primeiramente o arcabouço necessário para o entendimento do derivativo opções, muito utilizado nos mercados financeiros mundiais, e posteriormente executar precificações de opções americanas a partir dos modelos dos mínimos quadrados de Monte Carlo (LSM), o modelo de árvore binomial com extrapolação de Richardson e a aproximação analítica de Bjerksund e Stensland (B&S), aplicando duas plataformas de processamento paralelo computacional, a TPL (Task Parallel Library) nativa no .NET framework 4.5 e a plataforma CUDA (Compute Unified Device Architecture), demonstrando o comparativo dos resultados obtidos a cada modelo diante de cada plataforma. / The objective of this dissertation is to provide first the necessary framework for the understanding of the derivative options, widely used in the world financial markets, and later to execute the American option pricing from Monte Carlo least squares models (LSM), the binomial tree model with Richardson extrapolation and the Bjerksund and Stensland analytic approach (BJS) by applying two parallel computational processing platforms, the native TPL (Task Parallel Library) in the .NET framework 4.5 and the CUDA platform (Compute Unified Device Architecture), demonstrating the comparison of the obtained results to each model before each platform.

High school timetabling problems consist in assigning meetings between classes and teachers, with the goal of minimizing the violation of specific soft requisites. This category of problems has been extensively studied since the 1950s, mostly via mixed-integer programming and metaheuristic techniques. However, the computation of optimal or near-optimal solutions using mixed-integer programs or metaheuristics is still a challenge for most practical problems. In this thesis, we investigate new mixed-integer programming formulations, column generation approaches and parallel metaheuristic based algorithms to compute lower bounds and solutions for high school timetabling problems. Extensive computational experiments conducted with real-world instances demonstrate that our best formulations are competitive with best-known formulations, while our parallel algorithms present superior performance than the state-of-the-art methods. / Problemas de horários escolares consistem em alocar encontros entre turmas e professores, com objetivo de minimizar violações a requisitos qualitativos específicos. Esta categoria de problemas tem sido largamente estudada desde 1950, particularmente via técnicas de programação linear inteira mista e metaheurísticas. Entretanto, a computação de soluções ótimas ou quase ótimas usando programas inteiro-mistos ou metaheurísticas ainda é um desafio na maioria dos problemas práticos. Nesta tese, nós investigamos novas formulações inteiro-mistas, decomposições por geração de colunas e algoritmos baseados em metaheurísticas paralelas para computar limitantes inferiores e soluções para problemas de horários escolares. Extensivos experimentos computacionais conduzidos com instâncias reais demonstram que nossas melhores formulações são competitivas com as melhores formulações existentes, enquanto nossos algoritmos paralelos são superiores em performance computacional quando comparados com métodos que são estado-da-arte.

[pt] Este trabalho tem como objetivo propor uma metaheurística Iterated Local Search para minimizar o tempo de término ponderado de jobs em problemas de escalonamento de máquinas idênticas paralelas. O objetivo secundário do trabalho é propor uma solução prática para um problema real da companhia estudada em questão. A motivação para o trabalho consiste em uma aplicação prática na indústria de óleo e gás, onde os navios PLSV realizam operações em poços de forma ordenada e visando a antecipação dos poços de petróleo mais produtivos. As características do problema, tais quais: elegibilidade entre navio e operações, tempos de setup relativos à família de atividades, associações entre operações e poços e setups que dependem da chegada de material se adequam a modelagem baseada em escalonamento de máquinas paralelas idênticas. No trabalho uma introdução à respeito do tema é apresentada, em seguida é feita uma revisão da literatura sobre problemas de máquinas paralelas idênticas, a formulação matemática com a descrição do problema é apresentada, a metodologia contemplando representação da solução, heuristica construtiva, vizinhanças exploradas, busca local e Iterated Local Search é exposta, por fim são apresentados os resultados do método e as conclusões sobre o trabalho. / [en] This work objective is to propose an Iterated Local Search metaheuristic to minimize the weighted completion time of jobs on identical parallel machines scheduling problems. The secondary objective of this work is to propose a practical solution to the real problem of the studied company. The motivation of this work consists on a practical application in the Oil and Gas industry, where the PLSV vessels perform ordered operations in a set of wells aiming to maximize the oil production. The characteristics of the problem such as: eligibility between vessels and operations, setup times related to the family of activities, association between operations and wells and setup times depending on the material arrival fit well the identical parallel machine schedule modelling. In this work, an introduction about the theme is presented, followed by a literature review on identical parallel machine scheduling problems, the mathematical formulation with the problem description is presented, the methodology, including the solution representation, constructive heuristic, neighborhood structures, local search and Iterated Local Search is exposed, at last, the method results and conclusions of the work are summarized.

Para iniciar esta Tesis Doctoral se buscó un problema de producción sencillo pero de amplia aplicación práctica que permitiera adaptarlo para llegar a problemas más generales y de más amplia aplicación. Por este motivo, nos centramos en las máquinas paralelas, y dentro de ellas, en las no relacionadas dado que son una generalización de los casos de máquinas idénticas y de las uniformemente relacionadas. Escogimos el objetivo de minimizar el tiempo máximo de finalización o Cm ax, uno de los más comunes de la literatura. Este problema tiene la facultad de que, a pesar de su carácter teórico, tiene una amplia aplicación práctica, como el caso de secuenciar las tareas de los hornos de cocción cerámicos. Por otra parte se quería ampliar el problema para el caso en que no se usaran todas las máquinas o no se hicieran todos los trabajos necesariamente. Las metas perseguidas son el presentar unos algoritmos sencillos y potentes para la resolución del problema R//Cm ax, capaces de constituirse en el estado del arte. Dado que los modernos ordenadores montan casi en su totalidad varios núcleos en su CPU y los algoritmos se van adaptando a este hecho, también se ha buscado realizar una adaptación de los algoritmos para su uso en paralelo. Finalmente, se pone como meta el encontrar métodos eficaces y sencillos para la resolución de problemas de este tipo en donde no se emplearan todas las máquinas o no se realizaran todos los trabajos. En la presente Tesis Doctoral se realizó un amplio estudio de la literatura existente respecto al problema de máquinas paralelas no relacionadas y se extrajo el estado del arte, así como un estudio del posible tipo de instancias a emplear, dado que no existía una grupo de instancias tipo para este problema. Se presentan cuatro algoritmos iniciales sencillos que mejoran los resultados del estado del arte en algunos casos y dan mejores resultados de media en el conjunto total de instancias tratadas. / Fanjul Peyró, L. (2011). Nuevos algoritmos para el problema de secuenciación en máquinas paralelas no relacionadas y generalizaciones [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/9312

[ES] En esta tesis doctoral se estudia el problema de secuenciación de máquinas paralelas no relacionadas con necesidad de ajustes y recursos adicionales asignados en los ajustes. En este problema, se tiene un grupo de tareas (también llamadas trabajos), donde cada una debe ser procesada en una de las máquinas paralelas disponibles. Para procesar una tarea después de otra en la misma máquina, se debe hacer un ajuste en la máquina. Se asume que estos ajustes deben ser realizados por un recurso adicional limitado (por ejemplo, operarios). En esta tesis doctoral se estudian dos variantes del problema planteado: 1) considerando el problema con el único objetivo de minimizar el tiempo máximo de finalización de todos los trabajos (makespan), y 2) considerando el problema multi-objetivo minimizando simultáneamente el makespan y el consumo máximo de recursos adicionales. Inicialmente, se realiza una completa revisión bibliográfica sobre estudios relacionados con el problema planteado. En esta revisión se detecta que, a pesar de existir numerosos estudios de secuenciación de máquinas paralelas, no muchos de estos estudios tienen en cuenta recursos adicionales. Posteriormente, para introducir el problema a estudiar antes de plantear métodos de resolución, se realiza una breve explicación de los principales problemas de secuenciación de máquinas paralelas. El problema de un solo objetivo está clasificado como NP-Hard. Por ello, para abordar su resolución se han diseñado e implementado heurísticas y metaheurísticas siguiendo dos enfoques diferentes. Para el primer enfoque, que ignora la información sobre el consumo de recursos adicionales en la fase constructiva, se adaptan dos de los mejores algoritmos existentes en la literatura para el problema de máquinas paralelas con ajustes sin necesidad de recursos adicionales. En el segundo enfoque, que sí tiene en cuenta la información sobre el consumo de recursos adicionales en la fase constructiva, se proponen nuevos algoritmos heurísticos y metaheurísticos para resolver el problema. Tras analizar los resultados de los experimentos computacionales realizados, concluimos que hay diferencias entre los dos enfoques, siendo significativamente mejor el enfoque que tiene en cuenta la información sobre los recursos adicionales. Al igual que en el caso de un solo objetivo, la complejidad del problema multi-objetivo obliga a presentar algoritmos heurísticos o metaheurísticos para resolverlo. En esta tesis se presenta un nuevo algoritmo metaheurístico multi-objetivo eficiente para encontrar buenas aproximaciones a la frontera de Pareto del problema. Además, se adaptaron otros tres algoritmos que han mostrado buenos resultados en diferentes estudios de problemas de secuenciación de máquinas multi-objetivo. Después de realizar experimentos computacionales exhaustivos, concluimos que el nuevo algoritmo propuesto en esta tesis es significativamente mejor que los otros tres algoritmos existentes, y que se han adaptado para resolver este problema. / [CAT] En aquesta tesi doctoral s'estudia el problema de seqüenciació de màquines paral·leles no relacionades amb necessitat d'ajustos i recursos addicionals assignats en els ajustos. En aquest problema, es tenen un grup de tasques (també anomenades treballs), on cadascuna ha de ser processada en una de les màquines paral·leles disponibles. Per processar una tasca després d'una altra en la mateixa màquina, s'ha de fer un ajustament en la màquina. S'assumeix que aquests ajustos en les màquines per a processar una tasca després del processament d'una altra, han de ser realitzats per un recurs addicional limitat (per exemple, operaris). En aquesta tesi doctoral s'estudien dos variants al problema plantejat: 1) considerant el problema com l'únic objectiu de minimitzar el temps màxim de finalització de tots els treballs (makespan), i 2) considerant el problema multi-objectiu minimitzant simultàniament el makespan i el consum màxim de recursos addicionals. Inicialment, es realitza una completa revisió bibliogràfica sobre estudis relacionats amb el problema plantejat. En esta revisió es detecta que, tot i existir nombrosos estudis de seqüenciació de màquines paral·leles, hi ha molts pocs que tenen en compte recursos addicionals. Posteriorment, per introduir el problema a estudiar abans de plantejar mètodes de resolució, es realitza una breu explicació dels principals problemes de seqüenciació de màquines paral·leles. El problema d'un sol objectiu està classificat com NP-Hard. Per això, per abordar la seua resolució s'han dissenyat i implementat heurístiques y metaheurístiques seguint dos enfocs diferents. El primer enfoc ignora la informació sobre el consum de recursos en la fase constructiva, adaptant dos dels millors algoritmes existents en la literatura per al problema de seqüenciació de màquines paral·leles amb ajustaments sense necessitat de recursos. Per al segon enfoc si es té en compte la informació sobre el consum de recursos en la fase constructiva. Després d'analitzar els resultats dels experiments computacionals realitzats, concloem que hi ha diferencies entre els dos enfocs, sent significativament millor l'enfoc que té en compte la informació sobre el recursos. De la mateixa manera que en el cas d'un sol objectiu, la complexitat del problema multi-objectiu obliga a presentar algoritmes heurístics o metaheurístics per a resoldre-ho. En aquesta tesi es presenta un nou algoritme metaheurístic multi-objectiu eficient per trobar bones aproximacions a la frontera de Pareto del problema. A més, es van adaptar altres tres algoritmes que han mostrat bons resultats en diferents estudis de problemes de seqüenciació de màquines multi-objectiu. Després de realitzar experiments computacionals exhaustius, concloem que el nou algoritme proposat en aquesta tesi és significativament millor que els altres tres algoritmes existents i que s'han adaptat per resoldre aquest problema. / [EN] In this thesis we study the unrelated parallel machine scheduling problem with setup times and additional limited resources in the setups. In this problem, we have a group of tasks (also called jobs), where each one must be processed on one of the available parallel machines. To process one job after another on the same machine, a setup must be made on the machine. It is assumed that these setups on machines must be made by a limited additional resource (eg, operators). In this thesis two variants of the problem are studied: 1) considering the problem with the objective of minimizing the maximum completion time of all jobs (makespan), and 2) considering the multi-objective problem, minimizing the makespan and the maximum consumption of additional resources. Initially, a complete literature review is carried out on studies related to the problem addressed in this thesis. This review finds that despite numerous parallel machine scheduling studies, there are very few that take into account additional resources. Subsequently, to introduce the problem addressed before proposing resolution methods, a brief explanation of the main parallel machines scheduling problems is made. The problem with a single objective is classified as NP-Hard. Therefore, to solve it, heuristics and metaheuristics have been designed and implemented following two different approaches. For the first approach, which ignores the information on the consumption of resources in the construction phase, two of the best algorithms existing in the literature for the problem of parallel machines with setups without additional resources are adapted. For the second approach, which does take into account information on the consumption of resources in the construction phase, new heuristic and metaheuristic algorithms are proposed to solve the problem. Following the results of the computational experiments, we conclude that there are differences between the two approaches, the approach that takes into account the information on resources being significantly better. As in the case of a single objective, the complexity of the multi-objective problem requires the formulation of heuristic or metaheuristic algorithms to solve it. In this thesis, a new efficient multi-objective metaheuristic algorithm is presented to find good approximations to the Pareto front of the problem. In addition, three other algorithms that have shown good results in different studies of multi-objective machine scheduling problems were adapted. After carrying out exhaustive computational experiments, we concluded that the new algorithm proposed in this thesis is significantly better than the other three adapted algorithms. / Yepes Borrero, JC. (2020). Secuenciación de máquinas con necesidad de ajustes y recursos adicionales [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/158742

Submitted by Cássio da Cruz Nogueira (cassionogueirakk@gmail.com) on 2017-02-13T14:35:51Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_SolucoesHibridasTransformadas.pdf: 4506596 bytes, checksum: a15026cb83d1e9712967da31dae0f84a (MD5) / Approved for entry into archive by Edisangela Bastos (edisangela@ufpa.br) on 2017-02-14T16:37:26Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_SolucoesHibridasTransformadas.pdf: 4506596 bytes, checksum: a15026cb83d1e9712967da31dae0f84a (MD5) / Made available in DSpace on 2017-02-14T16:37:26Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_SolucoesHibridasTransformadas.pdf: 4506596 bytes, checksum: a15026cb83d1e9712967da31dae0f84a (MD5) Previous issue date: 2015-06-26 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O presente estudo consiste em analisar a dinâmica do escoamento magnetohidrodinâmico de fluidos newtonianos condutores elétricos no interior de um canal de placas planas paralelas submetido a um campo magnético externo uniforme, em que a formulação matemática dos modelos é dada em termos de função corrente, obtida a partir das Equações de Navier-Stokes e da Equação da Energia. As suposições adotadas são de regime permanente, escoamento laminar e incompressível e propriedades físicas constantes. Admite-se também que o campo magnético externo, aplicado na direção normal ao escoamento, permanece uniforme, não sendo, dessa forma, influenciado por nenhum efeito magnético interno. Para a solução das equações governantes do problema físico, a Técnica da Transformada Integral Generalizada (GITT) é aplicada a este sistema de equações diferenciais parciais e uma solução híbrida (numérico-analítica), a qual é computacionalemente implementada utilizando-se a linguagem de programação científica FORTRAN 90. Com o objetivo de ilustrar a consistência da técnica da transformação integral, análises de convergência são efetuadas e apresentadas. Resultados para os campos de velocidade e de temperatura, bem como potenciais correlatos são gerados e comparados com os da literatura em função dos principais parâmetros de governo. Uma análise aprofundada sobre a sensibilidade paramétrica dos principais parâmetros adimensionais, tais como número de Reynolds, número de Hartmann, número de Eckert, parâmetro elétrico e número de Prandtl, para algumas situações típicas é realizada. / The present study is to analyze the dynamics of the magnetohydrodynamic flow of electrical conductors newtonian fluids within a parallel flat plate channel subjected to a uniform external magnetic field, wherein the mathematical formulation of the model is given in terms of stream-function, obtained from the Navier-Stokes equations and the Energy Equation. The adopted assumptions are steady state, laminar and incompressible flow and constant physical properties. It is also admitted that the external magnetic field applied in the normal direction of flow remains uniform, not being thus influenced by any internal magnetic effect. For the solution of the governing equations, the Generalized Integral Transform Technique (GITT) is applied to this system of partial differential equations and a hybrid solution (numerical and analytical), which is computationally implemented using the programming scientific language FORTRAN 90. In order to illustrate the consistency of the integral transformation, convergence analysis is performed and presented. Results for velocity and temperature fields as well as potential correlates are generated and compared with the literature on the basis of the main parameters of government. An in-depth analysis of parametric sensitivity of the main dimensionless parameters such as the Reynolds number, Hartmann number, Eckert number, electric parameter and Prandtl number for some typical situations is performed.

[pt] A dissertação aborda um problema real de reprogramação de uma frota de embarcações do tipo PLSV (Pipe Laying Support Vessel), responsáveis pelas interligações de poços petrolíferos submarinos. O cronograma de curto prazo dessas embarcações está sujeito à inúmeras incertezas inerentes às operações realizadas, acarretando em ociosidade nas embarcações ou postergações na produção de petróleo, que podem resultar em prejuízo de milhões de reais. Uma metaheurística ILS (Iterated Local Search) é proposta para atender a frequente demanda por reprogramações dos PLSVs. O método é composto de uma fase inicial de viabilização, para tratar potenciais inconsistências nas programações. Na sequência, iterativamente, são realizadas perturbações na solução por meio de movimentos de swap e aplicada uma busca local baseada na vizinhança insert, a fim de fugir de ótimos locais e encontrar soluções que aprimorem o cronograma. Foram feitos experimentos com diferentes parâmetros e critérios do ILS, sendo definidas duas abordagens aplicadas a dez instâncias oriundas de uma programação real de PLSVs. A partir de uma função de avaliação, capaz de medir o impacto operacional na programação, o ILS proporcionou uma melhoria média nos cronogramas acima de 91 por cento, quando comparados aos cronogramas originais. As soluções foram obtidas em um tempo computacional médio de 30 minutos, aderente ao processo da companhia. Em função dos resultados alcançados, o método provou ser uma boa base para uma ferramenta de apoio à decisão para a reprogramação dos PLSVs. / [en] This dissertation addresses a real-life rescheduling problem of a Pipe Laying Support Vessels (PLSVs) fleet, in charge of subsea oil wells interconnections. The short-term schedule of these vessels is subject to uncertainties inherent to its operations, resulting in ships idleness or delays in oil production, which may lead to losses of millions of Brazilian Reais. A method based on the ILS (Iterated Local Search) metaheuristic is proposed to meet the frequent demand of PLSVs rescheduling. The first step of this method aims to find a feasible initial solution from an incoming schedule with potencial inconsistencies. The following steps consists in, iteratively, performing a perturbation on a solution through swap movements and applying a local search based on the insertion neighborhood, in order to escape from local optimal and find better solutions. Extensive preliminary experiments were conducted considering different ILS parameters setups. The two most performing setups were selected and applied to ten instances of a real PLSV schedule. Taking into account an objective function that measures the operational impact on schedules, the ILS provided an average improvement above 91 percent in schedules when compared to the original planning. These solutions were obtained in an average computational time of 30 minutes, which fits in the company process. The obtained results showed that the proposed method might be a basis for a decision support tool for the PLSVs rescheduling problem.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The evolution of computer hardware as well as new applications of mathematical programming techniques, efficiently implemented in many commercial solvers, has given rise to new algorithms called hybrid metaheuristic, which have been applied to solve combinatorial problems. This work presents several approaches which try to deal with the hybridization of local search based metaheuristics with exact algorithms to solve two problems of combinatorial optimization. More specifically, the first problem, capacitated p-median problem, the proposed approach considers heuristic elimination of variable of the original mathematical model, that produce solutions of very good quality in a short amount of time, and a combination with an iterative procedure in which only a certain subset of points is considered. As regards the second problem, unrelated parallel machine scheduling with sequence and machine dependent setup time problem of minimizing makespan, is proposed a mathematical model to search the neighborhood of a solution and identify movement sequences to minimize the objective function. In both cases, mathematical models are solved using a commercial solver. Extensive computational experiments are carried out to demonstrate the good performance of the proposed approaches. / A recente evolução dos computadores como também dos métodos exatos oriundos da programação matemática, muitos destes eficientemente implementados em otimizadores comerciais, propiciou o surgimento de novos algoritmos, denominados metaheurísticas híbridas, que têm sido aplicados para resolução de problemas combinatoriais. Este trabalho apresenta abordagens que hibridizam metaheurísticas baseadas em busca local com algoritmos exatos de programação matemática para resolver dois problemas de otimização combinatória. Mais especificamente, para o primeiro problema, o problema das p-medianas capacitado, a proposta considera a eliminação heurística de variáveis do modelo matemático, que permite a obtenção de soluções de boa qualidade em um curto tempo computacional, e a combinação com um procedimento iterativo no qual apenas um determinado subconjunto de pontos é considerado. No que se refere ao segundo problema, programação de tarefas em máquinas paralelas não relacionadas com tempo de preparação dependente da sequência e da máquina com objetivo de minimizar o tempo de processamento total da máquina com maior carga entre todas (makespan), propõe-se um modelo matemático para varrer a vizinhança de uma solução e identificar sequências de movimentos de tarefas que podem ser aplicadas na respectiva solução de modo a minimizar a função objetivo. Nos dois casos os modelos matemáticos são resolvidos utilizando um otimizador comercial. Extensivos testes computacionais são realizados para demonstrar o bom desempenho das abordagens propostas.

[pt] A programação de máquinas é um processo de tomada de decisão que desempenha um importante papel na maioria das indústrias de manufatura e serviços. Esta dissertação aborda o problema de programação de máquinas paralelas idênticas sem preempção, considerando características da programação de data de liberação e data limite para execução do início das tarefas, restrição de precedência entre pares de tarefas, elegibilidade e disponibilidade de máquinas. Para resolver este problema, uma formulação de programação linear inteira mista é proposta. O novo modelo, chamado de bucket-indexed (BI), particiona o horizonte de planejamento em períodos de tempos de mesmo tamanho (buckets). O tamanho dos buckets é um par âmetro que varia de acordo com a instância e influencia o porte do modelo, podendo assumir valores entre 1 e o menor tempo de processamento das tarefas. Quanto maior o tamanho do bucket, menor é o número de buckets criados e, consequentemente, menor o porte do modelo. A formulação proposta é testada em instâncias reais referentes ao problema de programação de sondas para construção de poços de petróleo de uma indústria brasileira de óleo e gás. A fim de avaliar os resultados obtidos pela formulação BI, a formulação clássica time-indexed (TI) foi também implementada para comparação dos tempos computacionais e qualidade da solução. Os resultados da formulação proposta apontam um melhor desempenho nas instâncias testadas, reduzindo o tempo computacional em todos os casos e resolvendo instâncias de grande porte não resolvidas pela formulação TI. / [en] Machine scheduling is a decision-making process that plays an important role in most manufacturing and service industries. This dissertation tackles a nonpreemptive identical parallel machine scheduling problem, considering release dates, deadlines, precedences, eligibility, and machine availability constraints. To solve this problem, a mixed-integer linear programming formulation is proposed. The new model, called bucketindexed, partitions the planning horizon in periods of equal length (buckets). The bucket size is a parameter which varies according to instances and influences the model size, assuming values between 1 and the shortest processing time of jobs. The larger the bucket size, the smaller is the number of buckets created and, consequently, the smaller the model size. The proposed formulation is tested in real instances of the rig scheduling problem for a Brazilian oil and gas industry. To evaluate the results obtained by the BI formulation, the classical time-indexed (TI) formulation was also implemented for comparison of computational times and solution quality. The results of the proposed formulation highlight a better performance in all the tested instances, reducing computational time in all cases and solving large instances unsolvable by the TI formulation.