The aim in this thesis is to develop efficient enumeration algorithms to solve certain strongly NP-hard scheduling problems. These algorithms were developed using a combination of ideas from Integer Programming, Constraint Programming and Scheduling Theory. In order to combine different techniques in one algorithm, decomposition methods are applied. The main idea on which the first part of our results is based is to separate the optimality and feasibility components of the problem and let different methods tackle these components. Then IP is ``responsible' for optimization, whereas specific combinatorial algorithms tackle the feasibility aspect. Branch-and-cut and branch-and-price algorithms based on this idea are proposed to solve the single-machine and multi-machine variants of the scheduling problem to minimize the sum of the weights of late jobs. Experimental research shows that the algorithms proposed outperform other algorithms available in the literature. Also, it is shown that these algorithms can be used, after some modification, to solve the problem of minimizing the maximum tardiness on unrelated machines. The second part of the thesis deals with the one-machine scheduling problem to minimize the weighted total tardiness. To tackle this problem, the idea of a partition of the time horizon into intervals is used. A particularity of this approach is that we exploit the structure of the problem to partition the time horizon. This particularity allowed us to propose two new Mixed Integer Programming formulations for the problem. The first one is a compact formulation and can be used to solve the problem using a standard MIP solver. The second formulation can be used to derive lower bounds on the value of the optimal solution of the problem. These lower bounds are of a good quality, and they can be obtained relatively fast.

[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.