• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 11
  • 2
  • 1
  • Tagged with
  • 14
  • 10
  • 8
  • 5
  • 4
  • 4
  • 4
  • 4
  • 4
  • 3
  • 3
  • 3
  • 3
  • 3
  • 3
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Optimization of row spacing and nitrogen fertilization for cotton

Clawson, Ernest Leslie 30 September 2004 (has links)
Ultra-narrow row (UNR) cotton (Gossypium hirsutum L.) is a production system using high plant populations in reduced row spacings. The responses of this production system to nitrogen fertilizer have not been fully investigated. Evaluations of yield and earliness of harvest are also important. A three-year study was conducted at the Texas Agricultural Experiment Station farm, Burleson County, TX, on a Ships clay (very-fine, mixed, active, thermic Chromic Hapluderts) and a Weswood silty clay loam (fine-silty, mixed, superactive, thermic Udifluventic Haplustepts). A split plot design was used. Nitrogen fertilizer rates of 0, 50, 101, and 151 kg N ha-1 were applied as the whole plots and row spacings of 19, 38, and 76 cm were established as the split plots. Data included lint yield and yield components, as well as earliness of crop maturity and earliness-related parameters such as boll distribution. Lint yield was increased by higher nitrogen rate. There was no nitrogen rate by row spacing interaction on lint yield, implying fertilizer rates do not need to be changed for UNR systems. Reductions in row spacing did not significantly affect lint yield in any year. Responses such as reduced bolls per plant, increased plant populations, increased ginout, and decreased boll size were often significant and combined to allow the crop to maintain equivalent yields as row spacings were reduced. The slight UNR earliness advantages were probably due to changes in boll distribution. Based on these results, increases in lint yield and earliness may not reliably contribute to the profitability of UNR cotton.
2

Heurística para o problema estocástico de programação de máquina única com minimização de earliness e tardiness. / Heuristics for the stochastic single-machine problem with E/T costs.

Lemos, Rafael de Freitas 29 September 2014 (has links)
O presente trabalho aborda o problema de determinação de datas de entrega e o sequenciamento de tarefas com tempos de processamento estocásticos. O ambiente considerado constitui em uma máquina simples e tarefas com custos individuais e distintos de adiantamento e atraso de entrega (earliness e tardiness ou simplesmente E/T). O objetivo é determinar a sequência e as datas de entrega ótimas que simultaneamente minimizam o custo total esperado de E/T. Para a determinação de sequências candidatas, são apresentadas diversas heurísticas construtivas com tempo de execução polinomial baseadas em um método de inserção de tarefas. Considerando tarefas com distribuição normal, experimentos computacionais comprovam a eficácia dos algoritmos para problemas de menor porte, os quais fornecem soluções ótimas em 99,85% dos casos avaliados. Quando aplicadas a um conjunto com uma maior quantidade de tarefas, as heurísticas apresentaram resultados melhores do que o algoritmo disponível na literatura em mais de 80% dos casos. Consideradas tarefas com distribuição lognormal, obteve-se um percentual de otimalidade entre 93,87% e 96,45%, a depender da heurística aplicada. Demonstra-se ainda para o caso com distribuição normal que os métodos propostos são assintoticamente ótimos e, portanto, são indicados para a resolução de problemas de grande porte. / This work addresses the problem of concurrent due-date assignment and sequencing of a set of jobs on a stochastic single-machine environment with distinct job earliness and tardiness penalty costs. It is assumed that the jobs processing times are statistically independent and follow a normal distribution whose mean and variance are provided and they are not necessarily integer values. The objective is to determine the job sequence and the integer due dates which minimize the expected total earliness and tardiness costs. Several efficient insertion-based construction heuristics are proposed in order to find candidates for the optimal sequence with polynomial time complexity. For the normal distribution problem, numerical experiments show that the proposed heuristic methods are able to find the optimal solution in 99,85% when applied to problems with a smaller size. When applied to problems with a bigger size, the solutions found by the proposed heuristics had better costs than the solutions described in the literature in more than 80% of cases. For the lognormal distribution problem, the proposed heuristic methods provided solutions with a percentage of optimality between 93,87% and 96,45%. Furthermore, for the normal distribuition case, it was proven that the heuristics are asymptotically optimal, i.e., it can be used for problems of any size.
3

Heurística para o problema estocástico de programação de máquina única com minimização de earliness e tardiness. / Heuristics for the stochastic single-machine problem with E/T costs.

Rafael de Freitas Lemos 29 September 2014 (has links)
O presente trabalho aborda o problema de determinação de datas de entrega e o sequenciamento de tarefas com tempos de processamento estocásticos. O ambiente considerado constitui em uma máquina simples e tarefas com custos individuais e distintos de adiantamento e atraso de entrega (earliness e tardiness ou simplesmente E/T). O objetivo é determinar a sequência e as datas de entrega ótimas que simultaneamente minimizam o custo total esperado de E/T. Para a determinação de sequências candidatas, são apresentadas diversas heurísticas construtivas com tempo de execução polinomial baseadas em um método de inserção de tarefas. Considerando tarefas com distribuição normal, experimentos computacionais comprovam a eficácia dos algoritmos para problemas de menor porte, os quais fornecem soluções ótimas em 99,85% dos casos avaliados. Quando aplicadas a um conjunto com uma maior quantidade de tarefas, as heurísticas apresentaram resultados melhores do que o algoritmo disponível na literatura em mais de 80% dos casos. Consideradas tarefas com distribuição lognormal, obteve-se um percentual de otimalidade entre 93,87% e 96,45%, a depender da heurística aplicada. Demonstra-se ainda para o caso com distribuição normal que os métodos propostos são assintoticamente ótimos e, portanto, são indicados para a resolução de problemas de grande porte. / This work addresses the problem of concurrent due-date assignment and sequencing of a set of jobs on a stochastic single-machine environment with distinct job earliness and tardiness penalty costs. It is assumed that the jobs processing times are statistically independent and follow a normal distribution whose mean and variance are provided and they are not necessarily integer values. The objective is to determine the job sequence and the integer due dates which minimize the expected total earliness and tardiness costs. Several efficient insertion-based construction heuristics are proposed in order to find candidates for the optimal sequence with polynomial time complexity. For the normal distribution problem, numerical experiments show that the proposed heuristic methods are able to find the optimal solution in 99,85% when applied to problems with a smaller size. When applied to problems with a bigger size, the solutions found by the proposed heuristics had better costs than the solutions described in the literature in more than 80% of cases. For the lognormal distribution problem, the proposed heuristic methods provided solutions with a percentage of optimality between 93,87% and 96,45%. Furthermore, for the normal distribuition case, it was proven that the heuristics are asymptotically optimal, i.e., it can be used for problems of any size.
4

Dynamic Control for Batch Process Systems Using Stochastic Utility Evaluation

Park, Hongsuk 2011 August 1900 (has links)
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.
5

Programação de tarefas em máquinas paralelas não-relacionadas com tempos de setup dependentes da sequência

Etcheverry, Guilherme Vazquez January 2012 (has links)
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.
6

Um método heurístico para a resolução de uma classe de problemas de sequenciamento da produção envolvendo penalidades por antecipação e atraso

Kramen, Arthur Harry frederico Ribeiro 14 April 2015 (has links)
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.
7

Programação de tarefas em máquinas paralelas não-relacionadas com tempos de setup dependentes da sequência

Etcheverry, Guilherme Vazquez January 2012 (has links)
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.
8

Programação de tarefas em máquinas paralelas não-relacionadas com tempos de setup dependentes da sequência

Etcheverry, Guilherme Vazquez January 2012 (has links)
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.
9

Avaliação de diferentes porta-enxertos na produção de maracujazeiro (Passiflora edulis Sims) / Evaluation of different rootstocks in the production of passion fruit (Passiflora edulis Sims)

Salazar, Alejandro Hurtado 18 March 2013 (has links)
Made available in DSpace on 2015-03-26T13:39:55Z (GMT). No. of bitstreams: 1 texto completo.pdf: 5375296 bytes, checksum: c7ea1e4a6904287d34cf3114d66369d3 (MD5) Previous issue date: 2013-03-18 / Brazil is the largest producer of passion fruit, with 920.158 million tonnes achieved during the year 2010, an area of 62,243 ha (IBGE, 2012). The passion fruit is the most cultivated in Brazil, with over 90% of the planted area and volume sold across the country, 60% of this production is intended for the fresh market. However, the soil diseases reduces the life crop, forcing the crop traveling into practice. The genetic resistance may prevent the premature death of the plants, providing training to healthier crops, uniform and enduring. Among the alternatives to be fetched, we highlight the use of wild species as resistant rootstocks. This study aimed to quantify the influence on the agronomic characteristics of yellow passion fruit (Passiflora edulis Sims) rootstocks of wild P. mucronata and P. gibertii. The characteristics evaluated were: percentage of graft survival, plant height, height of first flowering, number of leaves, number of nodes, diameter of the rootstock and grafting, histological analysis of the graft region, rate of occurrence of us days to flowering, gas exchange and physical and chemical qualities of the fruit. It was observed that the rootstock P. mucronata showed better conformation anatomical and histological region exertia and positively influenced the number of leaves, number of nodes, the time of first flowering, number of flowers and the rate of occurrence of us. When wild species were used as rootstock, developed these early buds and fruits originated more elongated than the non-grafted, but within the standards of marketing. The species P. mucronata showed the best performance as a rootstock. / O Brasil é o maior produtor mundial de maracujá, com 920.158 mil toneladas alcançadas durante o ano de 2010, numa área de 62.243 ha (IBGE, 2012). O maracujá amarelo é o mais cultivado no Brasil, com mais de 90% de área plantada e volume comercializado em todo o país; 60% dessa produção se destinam ao mercado in natura. No entanto, as doenças do solo reduzem a vida útil das lavouras, forçando à prática do cultivo itinerante. A resistência genética pode evitar a morte prematura das plantas, fornecendo formação de lavouras mais sadias, uniformes e longevas. Entre as alternativas a serem buscadas, destaca-se a utilização de espécies silvestres resistentes como porta-enxertos. Este trabalho buscou quantificar a influência sobre as características agronômicas do maracujazeiro-amarelo (Passiflora edulis Sims) dos porta-enxertos silvestres P. mucronata e P. gibertii. As características avaliadas foram: porcentagem de sobrevivência dos enxertos, altura da planta, altura da primeira floração, número de folhas, número de nós, diâmetros do porta-enxerto e do enxerto, análise histológica da região do enxerto, taxa de ocorrência de nós, dias até a floração, trocas gasosas e qualidades físicas e químicas dos frutos. Foi observado que o porta enxerto P. mucronata apresentou melhor conformação anatômico-histológica da região da exertia e influenciou positivamente o número de folhas, o número de nós, a altura da primeira floração, o número de flores e a taxa de ocorrência de nós. Quando as espécies silvestres foram empregadas como porta-enxerto, essas desenvolveram botões florais mais precocemente e originou frutos mais alongados que os pés-francos, porém dentro dos padrões de comercialização. A espécie P. mucronata foi a que apresentou o melhor desempenho como porta-enxerto.
10

Programação de tarefas em um ambiente flow shop com m máquinas para a minimização do desvio absoluto total de uma data de entrega comum / Scheduling in a n-machine flow shop for the minimization of the total absolute deviation from a common due date

Vasquez, Julio Cesar Delgado 28 August 2017 (has links)
Neste trabalho abordamos o problema de programação de tarefas em um ambiente flow shop permutacional com mais de duas máquinas. Restringimos o estudo para o caso em que todas as tarefas têm uma data de entrega comum e restritiva, e onde o objetivo é minimizar a soma total dos adiantamentos e atrasos das tarefas em relação a tal data de entrega. É assumido também um ambiente estático e determinístico. Havendo soluções com o mesmo custo, preferimos aquelas que envolvem menos tempo de espera no buffer entre cada máquina. Devido à dificuldade de resolver o problema, mesmo para instâncias pequenas (o problema pertence à classe NP-difícil), apresentamos uma abordagem heurística para lidar com ele, a qual está baseada em busca local e faz uso de um algoritmo linear para atribuir datas de conclusão às tarefas na última máquina. Este algoritmo baseia-se em algumas propriedades analíticas inerentes às soluções ótimas. Além disso, foi desenvolvida uma formulação matemática do problema em programação linear inteira mista (PLIM) que vai permitir validar a eficácia da abordagem. Examinamos também o desempenho das heurísticas com testes padrões (benchmarks) e comparamos nossos resultados com outros obtidos na literatura. / In this work we approach the permutational flow shop scheduling problem with more than two machines. We restrict the study to the case where all the jobs have a common and restrictive due date, and where the objective is to minimize the total sum of the earliness and tardiness of jobs relative to the due date. A static and deterministic environment is also assumed. If there are solutions with the same cost, we prefer those that involve less buffer time between each machine. Due to the difficulty of solving the problem, even for small instances (the problem belongs to the NP-hard class), we present a heuristic approach to dealing with it, which is based on local search and makes use of a linear algorithm to assign conclusion times to the jobs on the last machine. This algorithm is based on some analytical properties inherent to optimal solutions. In addition, a mathematical formulation of the problem in mixed integer linear programming (MILP) was developed that will validate the effectiveness of the approach. We also examined the performance of our heuristics with benchmarks and compared our results with those obtained in the literature.

Page generated in 0.0667 seconds