PPGCC - Mestrado (Dissertações)

URI permanente para esta coleçãohttp://www.hml.repositorio.ufop.br/handle/123456789/597

Navegar

Filtrar resultados informando as primeiras letras
Agora exibindo 1 - 2 de 2
  • Nenhuma Miniatura Disponível
    Item
    Algoritmos heurísticos híbridos para o problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes da sequência.
    (Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Haddad, Matheus Nohra; Souza, Marcone Jamilson Freitas
    Este trabalho aborda o problema de sequenciamento em máquinas paralelas não- relacionadas com tempos de preparação dependentes da sequência, dó inglês Unre- lated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, ou apenas UPMSPST. Neste problema há um conjunto de tarefas e máquinas e a cada tarefa está associado um tempo de processamento, que é diferente para cada máquina. Dadas duas tarefas, também existe um tempo de preparação dependente da sequência de lase da máquina utilizada. O objetivo considerado neste problema é minimizar o tempo máximo de conclusão do sequenciamento, o chamado makes pan. OUPMSPST é muito encontrado no âmbito industrial e pertence à classe NP- difícil. Visando a sua resolução, são propostos três algoritmos heurísticos híbridos. O primeiro, nomeado VP, combina os procedimentos heurísticos Iterated Local Search (ILS), Variable Neighborhood Descent (VND)e Path Relinking(PR). O segundo, nomeado GIVP, difere do primeiro pelo fato de gerar a solução inicial pela fase de construção Greedy Randomized AdaptiveS earch Procedure(GRASP), e não por um procedimento guloso. O terceiro algoritmo, nomeado GIVMP, diferedos outros em três estratégias: a fase PR utiliza a estratégia mix edrelinking ao invés de backward relinking, as vizinhanças que formam o VND são usada sem ordem aleatória a cada chamada e não em ordem previamente de nida; por m,o GIVMP inclui um módulo de busca local feita pelo resolvedor CPLEX12.1 de programação matemática. Este resolvedor é aplicado apenas à máquina gargalo do problema e utiliza um modelo de programação inteira mista base a dono problemado Caixeiro Viajante Assimétrico. Para explorar o espaço de soluções são utilizados movimentos de inserção e troca de tarefas entre máquinas. Para testar os algoritmos foram utilizados dois conjuntos de problemas-teste da literatura. Inicialmente eles foram comparados entre si em um conjunto reduzido de instâncias ,tendo- severi cado a superioridade do algoritmo GIVMP. Em seguida, este algoritmo foi compara do com outros seis da literatura, sendo dois no primeiro conjunto de problemas- teste e outros quatro no Segundo. No primeiro conjunto veri cou-se a superiorida de absoluta do GIVMP sobre os dois algoritmos genéticos da literatura, tendo-se encontra do desvios percentuais relativos médios menores e novas melhores soluções.No segundo conjunto de problemas-teste vericou-se que o GIVMP tem desempenho inferior a um dos algoritmos, mas superior em relação aos outros três. Observa-se,no entanto,que neste segundo conjunto de problemas, não foram disponibilizados os desvios percentuais relativos médios dos algoritmos, mas apenas os desvios dos melhores valores encontrados,impedindo uma comparação de robustez dos algoritmos.
  • Nenhuma Miniatura Disponível
    Item
    Certified virtual machine-based regular expression parsing.
    (2019) Delfino, Thales Antônio; Ribeiro, Rodrigo Geraldo; Ribeiro, Rodrigo Geraldo; Malaquias, José Romildo; Reis, Leonardo Vieira dos Santos
    Regular expressions (REs) are pervasive in computing. We use REs in text editors, string search tools (like GNU-Grep) and lexical analyzers generators. Most of these tools rely on converting REs to its corresponding finite state machine or use REs derivatives for directly parse an input string. In this work, we investigated the suitability of another approach: instead of using derivatives or generating a finite state machine for a given RE, we developed a certified virtual machine-based algorithm (VM) for parsing REs, in such a way that a RE is merely a program executed by the VM over the input string. First, we developed a small-step operational semantics for the algorithm, implemented it in Haskell, tested it using QuickCheck and provided proof sketches of its correctness with respect to RE standard inductive semantics. After that, we developed a big-step operational semantics, an evolution of the small-step one. Unlike the small-step, the bigstep semantics can deal with problematic REs. We showed that the big-step semantics for our VM is also sound and complete with regard to a standard inductive semantics for REs and that the evidence produced by it denotes a valid parsing result. All of our results regarding the big-step semantics are formalized in Coq proof assistant and, from it, we extracted a certified algorithm, which we used to build a RE parsing tool using Haskell programming language. Experiments comparing the efficiency of our algorithm with another Haskell tool are reported.