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

Submitted by Fernando Souza (fernandoafsou@gmail.com) on 2017-08-16T11:42:54Z No. of bitstreams: 1 arquivototal.pdf: 2606529 bytes, checksum: e6d5e9c7169bad77fb641468b804b962 (MD5) / Made available in DSpace on 2017-08-16T11:42:54Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2606529 bytes, checksum: e6d5e9c7169bad77fb641468b804b962 (MD5) Previous issue date: 2016-07-04 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The problem of scheduling on a single machine, proven to be NP-hard, consists of de ning the job grouping in batches and of the sequence in which these batches will be processed on a machine. Each job is associated with a release date, a processing time, a due date, a priority level in relation to the others and a size. The machine is able to process a group of jobs (batch) simultaneously, provided that the sum of the job sizes belonging to the referred batch does not exceed the machine capacity. Each job must be processed only once and only one batch is processed at a time on the machine. In this work, we consider the objective as the minimization of total weighted tardiness, where the tardiness of a job is the di erence between its completion time and its due date, in case the job processing is nished after its due date and hence is late, or equals zero, otherwise. In the literature, this problem is usually referred to as 1jbatch; rj ; sj ; comptjPwjTj . When all jobs are available to be processed at time zero, the problem is usually represented as 1jbatch; sj ; comptjPwjTj . These problems are still poorly explored in the literature and in addition, cover a large number of variant forms. There are few studies involving the application of exact methods for solving both. Only one mathematical formulation was identi ed in the literature for these problems. Hence, four time-indexed formulations were developed to solve the aforementioned problems, one of which is capable of dealing with both problems. The results achieved by the developed models were compared between themselves and with the results of the model available in the literature. These computational results reveal that two of the proposed models obtained higher performance both in terms of quality of the solution, particularly regarding the achieved lower bounds, and in numbers of open nodes and of proven optimal solutions. / O problema de sequenciamento de lotes da produ c~ao em uma m aquina, comprovadamente tido como NP-dif cil, consiste na de ni c~ao do agrupamento de tarefas em lotes e da sequ^encia em que estes ser~ao processados em uma m aquina. Cada tarefa est a associada a uma data de libera c~ao, um tempo de processamento, uma data de entrega, um n vel de prioridade em rela c~ao as demais, e um tamanho. A m aquina e capaz de processar um conjunto de tarefas (lote) simultaneamente, contanto que a soma dos tamanhos das tarefas pertencentes ao referido lote respeite a capacidade da m aquina. Cada tarefa deve ser processada apenas uma vez e somente um lote e processado por vez na m aquina. Neste trabalho, considera-se como objetivo a minimiza c~ao do total de atrasos ponderados, onde o atraso de uma tarefa e igual ao seu tempo de t ermino menos a sua data de entrega, caso o processamento da tarefa seja nalizado ap os a sua data da entrega e, portanto, em atraso, e e igual a zero, caso contr ario. Na literatura, este problema e geralmente referenciado como 1jbatch; rj ; sj ; comptjPwjTj . Quando todas as tarefas est~ao dispon veis para serem processadas no instante de tempo zero, o problema e usualmente representado por 1jbatch; sj ; comptjPwjTj . Estes s~ao problemas ainda pouco investigados na literatura e, al em disso, abordam uma grande quantidade de variantes. Existem poucos trabalhos envolvendo a aplica c~ao de m etodos exatos para a resolu c~ao de ambos. Apenas uma formula c~ao matem atica foi identi cada na literatura para estes problemas. Dessa forma, quatro formula c~oes matem aticas com vari aveis indexadas no tempo foram desenvolvidas para resolver os problemas mencionados anteriormente, das quais uma e capaz de tratar de ambos os problemas. Os resultados alcan cados por meio dos modelos desenvolvidos foram comparados entre si e com os resultados do modelo dispon vel na literatura. Tais resultados computacionais demonstram que dois dos modelos propostos obtiveram desempenho superior tanto em termos de qualidade da solu c~ao, em especial em rela c~ao aos limites inferiores alcan cados, quanto em n umeros de n os abertos e quantidade de solu c~oes otimas comprovadas.