This thesis contributes to theoretical and quantitative aspects of machine scheduling. In fact, it is dedicated to the issue of scheduling n jobs on one single machine. The scope is limited to deterministic problems - i.e. those with all data available and known with certainty in advance - with tardiness involved objectives; hence, the common denominator of all problems addressed are jobs with a predetermined due date assigned to. A job is finished on time as long as it is completed before its due date, otherwise it is said to be tardy. Since the single machine utilized is assumed to be restricted to process at most one job at a time, the aim is to find a proper sequence - a schedule - of how to process the jobs in order to best fulfill a certain objective. The contribution of this thesis aims at giving a state of the art survey and detailed review of research effort considering the objectives "minimizing the number of tardy jobs" and "minimizing the weighted number of tardy jobs". Further, the objectives of "minimizing the total tardiness", "minimizing the total weighted tardiness" and "minimizing the maximum tardiness" are adumbrated but reduced to a rough overview of research effort made.

Most research studies in the batch process control problem are focused on optimizing system performance. The methods address the problem by minimizing single criterion such as cycle time and tardiness, or bi-criteria such as cycle time and tardiness, and earliness and tardiness. This research demonstrates the use of Stochastic Utility Evaluation (SUE) function approach to optimize system performance using multiple criteria. In long production cycles, the earliness and tardiness weight (utility) of products vary depending on the time. As the time approaches the due-date, it affects contractual penalties, loss of customer goodwill and the storage period for the completed products. It is necessary to reflect the weight of products for earliness and tardiness at decision epochs to decide on the optimal strategy. This research explores how stochastic utility function using stochastic information can be derived and used to strategically improve existing approaches for the batch process control problem. This research first explores how SUE function can be applied to existing model for bi-objective problem such as cycle time and tardiness. Benchmark strategies using SUE function (NACH-SUE, MBS-SUE, No idle and full batch) are compared to each other. The experimental results show that NACH-SUE effectively improves mean cycle time and tardiness performance respectively than other benchmark strategies. Next, SUE function for earliness and tardiness is used in an existing model to develop a tri-objective problem. Typically, this problem is very complex to solve due to its trade-off relationship. However SUE function makes it relatively easy to solve the tri-objective problem since SUE function can be incorporated in an existing model. It is observed that SUE function can be effectively used for solving a tri-objective problem. Performance improvement for averaged value of cycle time, earliness and tardiness is observed under a comprehensive set of experimental conditions.

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.

O presente trabalho aborda o ambiente de produção conhecido como flowshop híbrido. Devido a crescente complexidade dos sistemas de produção, este ambiente é frequentemente encontrado em situações reais de manufatura. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Os tempos de processamento em cada estágio são dependentes da tarefa, já a rota através do sistema é a mesma para todas as tarefas. O objetivo é minimizar o atraso total, ou seja, a soma do atraso de todas as tarefas. Um modelo de programação linear inteira mista é apresentado para este problema e, dada a sua complexidade, ele é abordado através de uma meta-heurística relativamente nova e que, conforme revisão da literatura, nunca foi aplicada a este problema. Conhecida por BRKGA (Biased Random-Key Genetic Algorithm), este método codifica as soluções de maneira a obter um melhor desempenho em comparação com algoritmos genéticos tradicionais. Com o objetivo de avaliar a melhor estratégia, são propostas diversas versões de BRKGA para o problema considerado. Estas versões buscam explorar características das melhores heurísticas construtivas da literatura, dentre estas: ordens direta e inversa de programação das tarefas dentro do ambiente produtivo, identificação do estágio gargalo e diferenciação da programação do gargalo dos demais estágios. Experimentos computacionais foram realizados com 432 problemas teste de grande porte. Os métodos apresentados são comparados entre si e os resultados mostraram que uma versão do BRKGA se destaca frente às demais, visto que ela atingiu o melhor resultado em 61% dos problemas. Destaca-se que o método de melhor desempenho da literatura obteve a melhor solução em apenas 15% dos problemas. Devido às dimensões dos problemas teste da literatura, não foi possível encontrar suas soluções ótimas. Deste modo, este trabalho propõe um novo limitante inferior para o mínimo atraso total. Além disso, 576 novos problemas teste de menores dimensões são propostos e seus resultados ótimos são utilizados para aprofundar as comparações. Os resultados deste experimento indicaram que o BRKGA proposto apresentou um bom desempenho visto que, na média, seus resultados estão apenas a 2,4% dos resultados ótimos. / This work addresses a scheduling problem in hybrid flowshops. Due to the increasing complexity of production systems, this production environment is often encountered in real manufacturing situations. In hybrid flowshops, there are stages in series and, in each stage, a number of similar parallel machines. Processing times in each stage are dependent on the job, and the route through the system is the same for all jobs. The objective is to minimize the total tardiness, that is, the sum of all jobs tardiness. A mixed integer linear programming model is presented for the problem considered. Given its complexity, this problem is approached by a relatively new meta-heuristic, known as BRKGA (Biased Random-Key Genetic Algorithm). A literature review showed that BRKGA had never been applied to this problem. The BRKGA codes solutions in order to obtain a better performance compared with traditional genetic algorithms. Several versions of BRKGA were developed in order to evaluate the best strategy to solve the problem considered. These versions aim to exploit features of the best constructive heuristic from the literature, among them: scheduling jobs in direct and inverse order within the production environment, identification of the bottleneck stage and distinction of the bottleneck stage schedule from the others. Computational experiments were conducted with 432 large instances. The methods were compared and the results showed that one of these versions stood out against the others. This version achieved better results in 61% of instances, while the best heuristic from the literature achieved 15%. Due to the size of these instances, optimal solutions were not found. Therefore, this work develops a new lower bound for the minimum total tardiness. Additionally, in order to find optimal results, a set of 576 new instances is proposed. This experiment indicated that the BRKGA proposed performed well since, on average, their results are only 2.4% away from the optimal results.

Submitted by Maike Costa (maiksebas@gmail.com) on 2016-04-27T14:06:26Z No. of bitstreams: 1 arquivo total.pdf: 1831708 bytes, checksum: edf5d3b8c2b5483f249063f565ba3024 (MD5) / Made available in DSpace on 2016-04-27T14:06:26Z (GMT). No. of bitstreams: 1 arquivo total.pdf: 1831708 bytes, checksum: edf5d3b8c2b5483f249063f565ba3024 (MD5) Previous issue date: 2015-04-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work proposes a uni ed heuristic algorithm for a large class of earlinesstardiness (E-T) scheduling problems. We consider single/parallel machine E-T problems that may or may not consider some additional features such as idle time, setup times and release dates. In addition, we also consider those problems whose objective is to minimize either the total (average) weighted completion time or the total (average) weighted ow time, which arise as particular cases when the due dates of all jobs are either set to zero or to their associated release dates, respectively. The developed local search based metaheuristic framework is quite simple, but at the same time relies on sophisticated procedures for e ciently performing local search according to the characteristics of the problem. The algorithm was tested in hundreds of instances of several E-T problems and particular cases. The results obtained show that our general heuristic is capable of producing high quality solutions when compared to the best ones available in the literature that were obtained by speci c methods. Moreover, the algorithm was tested on a new set of instances proposed for the most general case (Rjrj ; sk ij jPw0j Ej + wjTj) of the class of problems considered, in order to validate the method. / Esta disserta c~ao prop~oe uma heur stica uni cada para uma classe de problemas de sequenciamento da produ c~ao com penalidades por antecipa c~ao e atraso. S~ao considerados problemas que envolvem uma ou m ultiplas m aquinas e que podem, ou n~ao, considerar algumas particularidades, tais como: a inser c~ao de tempos ociosos entre as tarefas, tempos de setup e datas de libera c~ao distintas. Al em desses problemas, tamb em s~ao considerados os em que a fun c~ao objetivo e de minimizar tanto o a soma (ponderada) dos tempos de t ermino das tarefas, quanto a soma (ponderada) dos tempos de uxo das tarefas, que surgem como casos particulares quando as datas de entrega de todas as tarefas s~ao de nidas com zero ou iguais a suas respectivas datas de libera c~ao, respectivamente. A meta-heur stica baseada em busca local proposta e simples, mas cont em procedimentos so sticados que possibilitam uma execu c~ao e ciente da busca local, de acordo com as caracter sticas do problema. O algoritmo foi testado em centenas de inst^ancias de problemas envolvendo penalidades por antecipa c~ao e atraso e em casos particulares. Os resultados obtidos mostram que a heur stica proposta e capaz de produzir solu c~oes de alta qualidade quando comparadas com os melhores dispon veis na literatura, os quais foram obtidos por m etodos espec cos. Al em disso, o algoritmo foi testado em um novo conjunto de inst^ancias propostas para caso mais geral (Rjrj ; sk ij jPw0j Ej +wjTj) da classe de problemas considerados, com o intuito de validar o m etodo.

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.

Neste trabalho será estudado um ambiente de produção que é freqüentemente encontrado na prática: o flowshop com múltiplos processadores. No caso estudado existem estágios em série e em cada estágio existe um número de máquinas idênticas em paralelo. Todas as tarefas devem ser processadas por todos os estágios. O objetivo é minimizar o atraso das tarefas. Primeiramente o problema foi abordado através de um método que programa as tarefas por estágio e em ordem direta, ou seja, do primeiro para o último estágio. Em seguida, foram desenvolvidas duas novas regras que utilizam o mesmo método de programação, porém consideram o ambiente como uma série de problemas de máquinas em paralelo. Uma das regras desenvolvidas tem como característica principal considerar estados futuros do sistema. Também foi desenvolvido um novo método de programação em ordem inversa, no qual as tarefas são programadas do último para o primeiro estágio. Este método apresenta melhor desempenho se comparado com o método de programação em ordem inversa da literatura. Por último foi desenvolvido um método de programação com foco no estágio gargalo, visto que este estágio pode impedir um bom fluxo das tarefas pelo sistema e resultar em uma conclusão tardia das mesmas. Este método é mais simples, rápido e tem resultados competitivos frente ao método com foco no gargalo da literatura. / This work considers a production environment that is frequently found in practice: the flexible flowshop. In the case studied, there are stages in series and in each stage there are a number of identical parallel machines. All jobs must be processed by all stages. The objective is to minimize the tardiness of jobs. First the problem was addressed by a method in which jobs are schedule forward, that is, from first to last stage. Two new rules were developed using this same method, but considering the environment as a series of parallel machines problems. One of the rules is able to consider future states of the system. It was also developed a new method in which jobs are scheduled backward, i.e., from last to first stage. This method shows better performance compared to the literature method. At last, it was developed a method that focus on the bottleneck stage scheduling (since this stage may prevent a good flow of jobs throughout the system and result in late completions). This method is simpler, faster and competitive next to the literature method.

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.

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.

No description available.