Spelling suggestions: "subject:"pesquisa operacional (otimização)"" "subject:"esquisa operacional (otimização)""
1 |
Programação de tarefas em um flow shop. / Flow shop job\' schedulingSouza, Eduardo Cordeiro de 22 May 2009 (has links)
Este trabalho trata de um problema de programação de tarefas em ambiente flow shop com algumas características específicas que, juntas, o diferenciam dos problemas usuais. Há N tarefas a serem processadas por M máquinas independentes e cada tarefa tem seu roteiro particular ao longo da oficina (shop), não passando necessariamente por todas as máquinas; cada tarefa deve ser concluída dentro de um respectivo intervalo de tempo, designado de janela de tempo, e há punições por adiantamento e atraso na conclusão da tarefa. O desempenho da programação é medido pela soma das punições por adiantamento e atraso. Trata-se de um problema de natureza combinatória, pertencente à classe NP-Difícil, para o qual, no limite, há (N !)^M alternativas. Neste trabalho, propõe-se um modelo matemático para representação do problema; para sua resolução é utilizado o pacote de programação linear mista inteira CPLEX; dada a dificuldade da obtenção de solução exata para as instâncias maiores, são propostas heurísticas para resolução do problema. São apresentados também procedimentos combinados, utilizando uma solução inicial gerada por heurística e o modelo matemático, quer usando a estrutura geral de ramificação do CPLEX, quer usando a técnica de ramificação local (Local Branching). / This study focuses a job scheduling problem in a flow shop with some specific features, which, all together, make it different from the usual flow shop scheduling problems. There are N jobs to be processed in M different machines and each job has a particular route, skipping, eventually, one or more machines; each job should be finished within a time interval, called time window, and there are penalties for earliness and tardiness. This is a combinatorial problem for which, in the extreme case, there are (N!)^M solutions, belonging to NP-Hard class. In this study, a mathematical model is proposed for representing the problem; the CPLEX solver is used for solving the mixed integer linear problem obtained. Given the computational complexity of the model, heuristic procedures are proposed in order to solve large- scale instances of this problem. Combined procedures, using an initial solution obtained by a proposed heuristic and the mathematical model, either using the general branching procedure of CPLEX or a specific local branching procedure, are also shown.
|
2 |
Programação de tarefas em um flow shop. / Flow shop job\' schedulingEduardo Cordeiro de Souza 22 May 2009 (has links)
Este trabalho trata de um problema de programação de tarefas em ambiente flow shop com algumas características específicas que, juntas, o diferenciam dos problemas usuais. Há N tarefas a serem processadas por M máquinas independentes e cada tarefa tem seu roteiro particular ao longo da oficina (shop), não passando necessariamente por todas as máquinas; cada tarefa deve ser concluída dentro de um respectivo intervalo de tempo, designado de janela de tempo, e há punições por adiantamento e atraso na conclusão da tarefa. O desempenho da programação é medido pela soma das punições por adiantamento e atraso. Trata-se de um problema de natureza combinatória, pertencente à classe NP-Difícil, para o qual, no limite, há (N !)^M alternativas. Neste trabalho, propõe-se um modelo matemático para representação do problema; para sua resolução é utilizado o pacote de programação linear mista inteira CPLEX; dada a dificuldade da obtenção de solução exata para as instâncias maiores, são propostas heurísticas para resolução do problema. São apresentados também procedimentos combinados, utilizando uma solução inicial gerada por heurística e o modelo matemático, quer usando a estrutura geral de ramificação do CPLEX, quer usando a técnica de ramificação local (Local Branching). / This study focuses a job scheduling problem in a flow shop with some specific features, which, all together, make it different from the usual flow shop scheduling problems. There are N jobs to be processed in M different machines and each job has a particular route, skipping, eventually, one or more machines; each job should be finished within a time interval, called time window, and there are penalties for earliness and tardiness. This is a combinatorial problem for which, in the extreme case, there are (N!)^M solutions, belonging to NP-Hard class. In this study, a mathematical model is proposed for representing the problem; the CPLEX solver is used for solving the mixed integer linear problem obtained. Given the computational complexity of the model, heuristic procedures are proposed in order to solve large- scale instances of this problem. Combined procedures, using an initial solution obtained by a proposed heuristic and the mathematical model, either using the general branching procedure of CPLEX or a specific local branching procedure, are also shown.
|
Page generated in 0.0777 seconds