A concorrência nos mercados mundiais impõe a necessidade de aumento da competitividade das empresas que desejam assumir posições de liderança nos segmentos em que atuam. Neste ínterim, a programação de tarefas contribui para que as empresas promovam a eficiente utilização dos recursos produtivos visando a realização de seus objetivos estratégicos. Esta dissertação enfoca a programação de tarefas em máquinas paralelas não-relacionadas e com tempos de setup dependentes da sequência de processamento. Primeiramente é abordado o objetivo de minimização do atraso total e do tempo total para a conclusão de um conjunto de tarefas, através de uma heurística de três etapas que (i) ordena as tarefas pelo WSPT (Weighted Shortest Processing Time), (ii) aloca as tarefas às máquinas e (iii) aprimora a solução proposta pela etapa (ii) através de Tabu Search. Quando aplicada em um ambiente de manufatura real composto por duas máquinas paralelas não-relacionadas no processo de metalização de filmes plásticos em alto vácuo, a heurística resulta em um desvio de 1,1% para o tempo total de processamento das tarefas e 4,6% para o atraso total, em comparação ao resultado ótimo obtido por enumeração. Na sequência, o objetivo passa a ser a minimização simultânea do atraso e do adiantamento das tarefas através de uma heurística de três etapas que (i) caracteriza o conjunto de tarefas por um conjunto de métricas, (ii) aloca as tarefas às máquinas através de uma versão modificada do ATCS (Apparent Tardiness Cost with Setup) de Lee e Pinedo (1997), e (iii) aprimora a solução final com Tabu Search. A aplicação em dados reais resulta em 14% de desvio em relação à solução ótima obtida por enumeração. Quando aplicada em cenários com data de entrega, tempos de processamento e setup simulados, a heurística resulta em desvio médio de 18% da solução ótima gerada por enumeração para pelo menos 70% das simulações. / The competition in worldwide markets lead the companies to increase the competitiveness in order to take leading positions in their industries. In this sense, scheduling plays an important role leading the companies to reach their strategic goals through efficient utilization of manufacturing resources. This dissertation focuses on the scheduling unrelated parallel machines with sequence dependent setup times. First goal is to minimize the completion time and total weighted tardiness, through a three phase heuristic which (i) sort the jobs with WSPT, (ii) allocate the jobs to the machines and (iii) improve final solution with Tabu Search. Once applied to a real manufacturing environment composed by two unrelated parallel machines, in high vacuum plastic films metallisation process, the heuristic results in 1.1% of deviation from total weighted completion time and 4.6% of deviation from weighted tardiness, in relation to the optimal solution obtained from total enumeration. Next goal is the simultaneous minimization of weighted earliness and tardiness, through a three phase heuristic which (i) characterize the jobs, (ii) allocate the jobs to the machines with a modified version of Lee and Pinedo’s (1997) ATCS and (iii) improve final solution with Tabu Search. The application in real data results in 14% of deviation from the optimal solution obtained by enumeration. When applied to simulated scenarios of due date, processing and setup time, the heuristic results in average deviation of 18% from optimal solution obtained by enumeration to at least 70% of the simulations.

A concorrência nos mercados mundiais impõe a necessidade de aumento da competitividade das empresas que desejam assumir posições de liderança nos segmentos em que atuam. Neste ínterim, a programação de tarefas contribui para que as empresas promovam a eficiente utilização dos recursos produtivos visando a realização de seus objetivos estratégicos. Esta dissertação enfoca a programação de tarefas em máquinas paralelas não-relacionadas e com tempos de setup dependentes da sequência de processamento. Primeiramente é abordado o objetivo de minimização do atraso total e do tempo total para a conclusão de um conjunto de tarefas, através de uma heurística de três etapas que (i) ordena as tarefas pelo WSPT (Weighted Shortest Processing Time), (ii) aloca as tarefas às máquinas e (iii) aprimora a solução proposta pela etapa (ii) através de Tabu Search. Quando aplicada em um ambiente de manufatura real composto por duas máquinas paralelas não-relacionadas no processo de metalização de filmes plásticos em alto vácuo, a heurística resulta em um desvio de 1,1% para o tempo total de processamento das tarefas e 4,6% para o atraso total, em comparação ao resultado ótimo obtido por enumeração. Na sequência, o objetivo passa a ser a minimização simultânea do atraso e do adiantamento das tarefas através de uma heurística de três etapas que (i) caracteriza o conjunto de tarefas por um conjunto de métricas, (ii) aloca as tarefas às máquinas através de uma versão modificada do ATCS (Apparent Tardiness Cost with Setup) de Lee e Pinedo (1997), e (iii) aprimora a solução final com Tabu Search. A aplicação em dados reais resulta em 14% de desvio em relação à solução ótima obtida por enumeração. Quando aplicada em cenários com data de entrega, tempos de processamento e setup simulados, a heurística resulta em desvio médio de 18% da solução ótima gerada por enumeração para pelo menos 70% das simulações. / The competition in worldwide markets lead the companies to increase the competitiveness in order to take leading positions in their industries. In this sense, scheduling plays an important role leading the companies to reach their strategic goals through efficient utilization of manufacturing resources. This dissertation focuses on the scheduling unrelated parallel machines with sequence dependent setup times. First goal is to minimize the completion time and total weighted tardiness, through a three phase heuristic which (i) sort the jobs with WSPT, (ii) allocate the jobs to the machines and (iii) improve final solution with Tabu Search. Once applied to a real manufacturing environment composed by two unrelated parallel machines, in high vacuum plastic films metallisation process, the heuristic results in 1.1% of deviation from total weighted completion time and 4.6% of deviation from weighted tardiness, in relation to the optimal solution obtained from total enumeration. Next goal is the simultaneous minimization of weighted earliness and tardiness, through a three phase heuristic which (i) characterize the jobs, (ii) allocate the jobs to the machines with a modified version of Lee and Pinedo’s (1997) ATCS and (iii) improve final solution with Tabu Search. The application in real data results in 14% of deviation from the optimal solution obtained by enumeration. When applied to simulated scenarios of due date, processing and setup time, the heuristic results in average deviation of 18% from optimal solution obtained by enumeration to at least 70% of the simulations.

A concorrência nos mercados mundiais impõe a necessidade de aumento da competitividade das empresas que desejam assumir posições de liderança nos segmentos em que atuam. Neste ínterim, a programação de tarefas contribui para que as empresas promovam a eficiente utilização dos recursos produtivos visando a realização de seus objetivos estratégicos. Esta dissertação enfoca a programação de tarefas em máquinas paralelas não-relacionadas e com tempos de setup dependentes da sequência de processamento. Primeiramente é abordado o objetivo de minimização do atraso total e do tempo total para a conclusão de um conjunto de tarefas, através de uma heurística de três etapas que (i) ordena as tarefas pelo WSPT (Weighted Shortest Processing Time), (ii) aloca as tarefas às máquinas e (iii) aprimora a solução proposta pela etapa (ii) através de Tabu Search. Quando aplicada em um ambiente de manufatura real composto por duas máquinas paralelas não-relacionadas no processo de metalização de filmes plásticos em alto vácuo, a heurística resulta em um desvio de 1,1% para o tempo total de processamento das tarefas e 4,6% para o atraso total, em comparação ao resultado ótimo obtido por enumeração. Na sequência, o objetivo passa a ser a minimização simultânea do atraso e do adiantamento das tarefas através de uma heurística de três etapas que (i) caracteriza o conjunto de tarefas por um conjunto de métricas, (ii) aloca as tarefas às máquinas através de uma versão modificada do ATCS (Apparent Tardiness Cost with Setup) de Lee e Pinedo (1997), e (iii) aprimora a solução final com Tabu Search. A aplicação em dados reais resulta em 14% de desvio em relação à solução ótima obtida por enumeração. Quando aplicada em cenários com data de entrega, tempos de processamento e setup simulados, a heurística resulta em desvio médio de 18% da solução ótima gerada por enumeração para pelo menos 70% das simulações. / The competition in worldwide markets lead the companies to increase the competitiveness in order to take leading positions in their industries. In this sense, scheduling plays an important role leading the companies to reach their strategic goals through efficient utilization of manufacturing resources. This dissertation focuses on the scheduling unrelated parallel machines with sequence dependent setup times. First goal is to minimize the completion time and total weighted tardiness, through a three phase heuristic which (i) sort the jobs with WSPT, (ii) allocate the jobs to the machines and (iii) improve final solution with Tabu Search. Once applied to a real manufacturing environment composed by two unrelated parallel machines, in high vacuum plastic films metallisation process, the heuristic results in 1.1% of deviation from total weighted completion time and 4.6% of deviation from weighted tardiness, in relation to the optimal solution obtained from total enumeration. Next goal is the simultaneous minimization of weighted earliness and tardiness, through a three phase heuristic which (i) characterize the jobs, (ii) allocate the jobs to the machines with a modified version of Lee and Pinedo’s (1997) ATCS and (iii) improve final solution with Tabu Search. The application in real data results in 14% of deviation from the optimal solution obtained by enumeration. When applied to simulated scenarios of due date, processing and setup time, the heuristic results in average deviation of 18% from optimal solution obtained by enumeration to at least 70% of the simulations.

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

Let there be m parallel machines and n jobs to be scheduled non-preemptively. A job j scheduled on machine i takes p_{i,j} time units to complete, where 1 ≤ i ≤ m and 1 ≤ j ≤ n. For a given schedule, the makespan is the completion time of a machine that finishes last. The goal is to produce a schedule of all n jobs with minimum makespan. This is known as the makespan problem on unrelated parallel machines (UPMs), denoted as R||C_{max}. In this thesis, we focus on subclasses of R||C_{max}. Our research consists of two components. First, a survey of theoretic results for R||C_{max} with a focus on approximation algorithms is presented. Second, we present exact polynomial-time algorithms and approximation algorithms for some subclasses of R||C_{max}. For instance, we present k-approximation algorithms on par with or better than the best known for certain subclasses of R||C_{max}.

本研究將探討非等效平行機台問題中具備順序相依整備時間及不同開始工作時間（Unequal ready-time）之情況，並以最小化總延遲工件權重數為目標值，其目的在改善非等效平行機台問題應用於實際產業中製造環境裡所面對的各項挑戰，如印刷電路板的鑽孔和半導體的測試製程。因本研究欲求解之問題是屬於NP - Hard problems 性質之尋優問題，故利用啟發式方法(heuristics)求解為合適的選擇。此外，本研究計畫開發混合式巨集啟發式方法來求解非等效平行機台問題，主要以禁忌搜尋法為主，在鄰域的搜尋上，也藉由變動鄰域尋優法能夠透過鄰域轉換的機制，進而找出更多好的解。由於啟發式方法對於尋優問題常需花費許多時間來計算才能獲得更好的解，為確保增進求解效率與品質，將針對問題特性開發數種初始解產生法，並也嘗試定義幾個能夠減少尋找鄰近解之鄰域。在後續求解改善的過程中，主要整合變動鄰域(VND)及禁忌(TS)巨集啟發式演算法搜尋最佳解。此外，為了評估本文推導之演算法效能，本研究利用設定之條件隨機產生適量模擬現場狀況的測試情境，進而比較本研究所提出之混合式巨集啟發式方法及標準禁忌搜尋法在不同情境下之表現。 / The problem considered in this paper is a set of independent jobs on unrelated parallel machines with sequence-dependent setup times and with unequal ready times so as to minimize total weighted tardy jobs. These problems can be found in real-life manufacturing environments, such as PCB fabrication drilling operations and semiconductor wafer manufacturing dicing. Since the problems are NP-hard in the strong sense, heuristics are an acceptable practice to finding good solutions. A hybrid meta-heuristics are proposed to solve this scheduling problem. The proposed heuristics belong to a type of solution improvement heuristic; therefore, the heuristics start with an effective initial feasible solution then a meta-heuristic is applied to improve the solution. To enhance both the efficiency and efficacy of the heuristics, several different initial solution generators, based on the characteristics of problems, are developed. The meta-heuristic is a hybrid heuristic integrating the principles of Variable Neighborhood Descent approach (VND) and Tabu Search (TS). In order to evaluate the performance of the proposed heuristics, two sets of large number test scenarios will be designed to simulate practical shop floor problems. Computational experiments will be performed to compare the performance of the proposed heuristics, and a basic tabu search algorithm. The results show the proposed heuristic perform better than the basic tabu search algorithm.