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.

Made available in DSpace on 2015-04-11T14:02:41Z (GMT). No. of bitstreams: 1 rainer.pdf: 3537323 bytes, checksum: 46bd81628ce774393ea9334f7287a55f (MD5) Previous issue date: 2013-03-27 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This dissertation presents a study on scheduling problems with earliness and tardiness penalties on identical parallel machines, considering independent and weighted jobs with arbitrary processing times. An analysis of the major mathematical formulations in integer programming is given, and presented the main results from the literature. An integer mathematical formulation based on network flow model was also proposed for the problem, which can be applied on single and parallel machines without idle time. Exact methods of implicit enumeration were studied and applied for the problem through the integer linear programming solver CPLEX and the UFFLP library and, mainly, algorithmic strategies of global optimization based on local search heuristic and path-relinking technique were developed. The computational experiments shows that the proposed algorithmic strategies are competitive in relation to existing results from the literature for single-machine scheduling, involving instances based on OR-Library benchmark for 40, 50, 100, 150, 200 and 300 jobs, where all the optimal values were found, and, mainly, being the best algorithmic strategy for multiprocessor environments, involving 2, 4 and 10 identical parallel machines. / Esta dissertação apresenta um estudo sobre problemas de escalonamento com penalidades de antecipação e atraso em máquinas paralelas, considerando tarefas independentes, ponderadas e de tempos de execução arbitrários. Uma análise sobre as principais formulações matemáticas em programação inteira é dada, bem como apresentados os principais resultados da literatura. Uma formulação matemática de programação inteira baseada no modelo de fluxo em redes também foi proposta para o problema, que pode ser aplicada em ambientes mono e multiprocessado sem tempo ocioso. Métodos de enumeração implícita foram estudados e aplicados aos problemas em questão através do resolvedor de programação linear inteira CPLEX e da biblioteca UFFLP, principalmente, estratégias algorítmicas aproximadas de otimização global baseadas em heurísticas de busca local e técnica de reconexão de caminhos foram desenvolvidas. Os experimentos computacionais mostram que as estratégias propostas são competitivas em relação aos resultados existentes na literatura para ambientes de escalonamento monoprocessados, envolvendo instâncias baseadas no benchmark da OR-Library para 40, 50, 100, 150, 200 e 300 tarefas, onde todos os ótimos foram encontrados, e, principalmente, sendo a melhor estratégia apresentada para ambientes multiprocessados, envolvendo 2, 4 e 10 máquinas paralelas idênticas.