Paraphrase sparsity is an issue that complicates the training process of question answering systems: syntactically diverse but semantically equivalent sentences can have significant disparities in predicted output probabilities. We propose a method for generating an augmented paraphrase corpus for the visual question answering system to make it more robust to paraphrases. This corpus is generated by concatenating two sequence to sequence models. In order to generate diverse paraphrases, we sample the neural network using diverse beam search. We evaluate the results on the standard VQA validation set. Our approach results in a significantly expanded training dataset and vocabulary size, but has slightly worse performance when tested on the validation split. Although not as fruitful as we had hoped, our work highlights additional avenues for investigation into selecting more optimal model parameters and the development of a more sophisticated paraphrase filtering algorithm. The primary contribution of this work is the demonstration that decent paraphrases can be generated from sequence to sequence models and the development of a pipeline for developing an augmented dataset. / Master of Science

Nesta tese, dois diferentes problemas de programação da produção são abordados, o Flexible JobShop Scheduling Problem com Flexibilidade de sequenciamento e o Flowshop Scheduling Problem com tempos de espera e permutação de sequência. Para ambos, inicialmente um algoritmo list scheduling (LS) que explora características do problema é desenvolvido e então estendido para um método do tipo Beam Search (BS) que utiliza o LS em seus principais elementos: (1) expansão dos níveis, (2) avaliação local dos candidatos e (3) avaliação global dos candidatos. Todos os métodos propostos são determinísticos e seus pseudocódigos são cuidadosamente descritos para garantir a replicabilidade dos resultados reportados. O desempenho dos métodos propostos são avaliados utilizando instâncias e outros métodos heurísticos da literatura. Os resultados computacionais obtidos mostram a eficiência das heurísticas propostas que superaram os métodos da literatura utilizando pouco tempo computacional. / In this thesis two diferent scheduling problems were addressed, the Flexible Job Shop Scheduling Problem with sequence Flexibility and the Flowshop Scheduling Problem with waiting times and sequence permutation. For both problems, firstly, a list scheduling (LS) algorithm which exploit features of the problem was developed and then it was extedend to a Beam Search (BS) method which use the LS in his main features: (1) level expansion, (2) local evaluation and (3) global evaluation. All the proposed methods are deterministics and their pseudocodes are carefully described to ensure the replicability of the reported results. The performance of the proposed methods was evaluated using instances and other heuristic methods found in literature. The computational results show the eficiency of the proposed heuristics, which outperformed the literature methods while using low computational time.

O Job Shop Scheduling Problem é um problema NP-Difícil que chama a atenção de muitos pesquisadores devido seu desafio matemático e sua aplicabilidade em contextos reais. Geralmente, principalmente em cenários próximos aos de fábricas e indústrias, obter um escalonamento ótimo por meio de métodos computacionais exatos implica em um alto desprendimento de tempo. Em contrapartida, devido às exigências de um mercado cada vez mais competitivo, as decisões de onde, como, quando e com o que produzir devem ser tomadas rapidamente. O presente trabalho propõe o desenvolvimento de um método heurístico Beam Search para solucionar o Job Shop Scheduling Problem e o Flexible Job Shop Scheduling Problem. Para isso, inicialmente um algoritmo do tipo list scheduling é definido e então o método Beam Search é construído baseado neste algoritmo. Os métodos propostos foram avaliados em diferentes níveis de complexidade utilizando instâncias da literatura que retratam diferentes cenários de planejamento. Em linhas gerais, as soluções encontradas se mostraram bastante competitivas quando comparadas a outras soluções da literatura. / The Job Shop Scheduling Problem is a NP-Hard problem which draws the attention of researchers due to both its mathematical challenge and its applicability in real contexts. Usually, mainly in industry and factory environments, an optimal schedule got by the use of exact computational methods implies in a long spending time. On the other hand, due to a more and more competitive marketplace, the decisions on where, how, when and with which to produce must be taken quickly. The present work proposes the development of an heuristic Beam Search method to solve both the Job Shop Scheduling Problem and the Flexible Job Shop Scheduling Problem. To that end, at rst a list scheduling algorithm is dened and then the Beam Search method is built based on the list scheduling algorithm. The proposed methods were evaluated over dierent complexity levels using instances from the literature that report dierent planning environments. In general terms, the solutions implemented have been proved very competitive when compared against other solutions in the literature.

O Job Shop Scheduling Problem é um problema NP-Difícil que chama a atenção de muitos pesquisadores devido seu desafio matemático e sua aplicabilidade em contextos reais. Geralmente, principalmente em cenários próximos aos de fábricas e indústrias, obter um escalonamento ótimo por meio de métodos computacionais exatos implica em um alto desprendimento de tempo. Em contrapartida, devido às exigências de um mercado cada vez mais competitivo, as decisões de onde, como, quando e com o que produzir devem ser tomadas rapidamente. O presente trabalho propõe o desenvolvimento de um método heurístico Beam Search para solucionar o Job Shop Scheduling Problem e o Flexible Job Shop Scheduling Problem. Para isso, inicialmente um algoritmo do tipo list scheduling é definido e então o método Beam Search é construído baseado neste algoritmo. Os métodos propostos foram avaliados em diferentes níveis de complexidade utilizando instâncias da literatura que retratam diferentes cenários de planejamento. Em linhas gerais, as soluções encontradas se mostraram bastante competitivas quando comparadas a outras soluções da literatura. / The Job Shop Scheduling Problem is a NP-Hard problem which draws the attention of researchers due to both its mathematical challenge and its applicability in real contexts. Usually, mainly in industry and factory environments, an optimal schedule got by the use of exact computational methods implies in a long spending time. On the other hand, due to a more and more competitive marketplace, the decisions on where, how, when and with which to produce must be taken quickly. The present work proposes the development of an heuristic Beam Search method to solve both the Job Shop Scheduling Problem and the Flexible Job Shop Scheduling Problem. To that end, at rst a list scheduling algorithm is dened and then the Beam Search method is built based on the list scheduling algorithm. The proposed methods were evaluated over dierent complexity levels using instances from the literature that report dierent planning environments. In general terms, the solutions implemented have been proved very competitive when compared against other solutions in the literature.

Este trabalho apresenta procedimentos que podem ser utilizados na programação da produção em um ambiente JIT. Esses procedimentos deveriam ser utilizados em sistemas clássicos de programação, onde a utilização do sistema kanban é inviável. O caso estudado se baseia em uma única máquina, com datas de entrega múltiplas e com penalidades distintas de adiantamento e de atraso para cada ordem. O objetivo a ser alcançado é a minimização do custo total. Para isso, é utilizado um procedimento de busca denominado beam search, para gerar as seqüências, e um algoritmo de inserção de ociosidade, para definir os programas. O algoritmo utilizado é uma generalização do algoritmo de GAREY et al. (1988) onde as penalidades são distintas para adiantamento e para atraso. O procedimento e o algoritmo são testados em várias condições sendo comparados com regras de despacho e com a função EXP-ET. Quando a função EXP-ET é utilizada com a possibilidade de inserção de ociosidade, o período de ociosidade ótimo é determinado. Assume-se que a dificuldade de solução do problema é dependente de dois parâmetros clássicos: fator de atraso médio e amplitude relativa das datas de entrega. Testes empíricos comparativos são realizados através de simulação computacional, onde se mede o tempo de solução e o valor alcançado pela função objetivo. Os resultados indicam que o desempenho dos vários procedimentos testados é altamente dependente dos dois parâmetros, mostrando que para a escolha de um procedimento apropriado, deve-se primeiramente conhecer o valor dos parâmetros. São fornecidos os resultados encontrados e os códigos computacionais utilizados no estudo. / This work presents some procedures which can be used in production scheduling problems in JIT environments. These procedures may be used in cases of classical production scheduling where the use of the kanban system is infeasible. The case studied is based on a single machine, with multiple due dates, and distinct earliness and tardiness penalties for each job. The objective function is to minimize total cost. A heuristic search procedure known as beam search is used to construct sequences of jobs, and an idleness insertion algorithm is used to obtain schedules. The algorithm used is a generalization of the GAREY et al. (1988) algorithm, where penalties are distinct for earliness and tardiness. The procedure and algorithm are tested in many conditions involving comparisons with dispatching rules and the EXP-ET function. When EXP-ET function is applied with possibility of idleness insertion, the optimal idleness period is provided. It was assumed that problem hardness is dependent on two classical parameters: average tardiness factor and relative range of due dates. Empirical comparative tests are conducted with computational simulation, where computational solution time and objective function value are evaluated. Results indicate that procedures performance is highly dependent on both parameters, showing that is necessary to know parameters values before choosing an appropriate procedure. The detailed results and computational code used in this study are also provided.

Este trabalho apresenta procedimentos que podem ser utilizados na programação da produção em um ambiente JIT. Esses procedimentos deveriam ser utilizados em sistemas clássicos de programação, onde a utilização do sistema kanban é inviável. O caso estudado se baseia em uma única máquina, com datas de entrega múltiplas e com penalidades distintas de adiantamento e de atraso para cada ordem. O objetivo a ser alcançado é a minimização do custo total. Para isso, é utilizado um procedimento de busca denominado beam search, para gerar as seqüências, e um algoritmo de inserção de ociosidade, para definir os programas. O algoritmo utilizado é uma generalização do algoritmo de GAREY et al. (1988) onde as penalidades são distintas para adiantamento e para atraso. O procedimento e o algoritmo são testados em várias condições sendo comparados com regras de despacho e com a função EXP-ET. Quando a função EXP-ET é utilizada com a possibilidade de inserção de ociosidade, o período de ociosidade ótimo é determinado. Assume-se que a dificuldade de solução do problema é dependente de dois parâmetros clássicos: fator de atraso médio e amplitude relativa das datas de entrega. Testes empíricos comparativos são realizados através de simulação computacional, onde se mede o tempo de solução e o valor alcançado pela função objetivo. Os resultados indicam que o desempenho dos vários procedimentos testados é altamente dependente dos dois parâmetros, mostrando que para a escolha de um procedimento apropriado, deve-se primeiramente conhecer o valor dos parâmetros. São fornecidos os resultados encontrados e os códigos computacionais utilizados no estudo. / This work presents some procedures which can be used in production scheduling problems in JIT environments. These procedures may be used in cases of classical production scheduling where the use of the kanban system is infeasible. The case studied is based on a single machine, with multiple due dates, and distinct earliness and tardiness penalties for each job. The objective function is to minimize total cost. A heuristic search procedure known as beam search is used to construct sequences of jobs, and an idleness insertion algorithm is used to obtain schedules. The algorithm used is a generalization of the GAREY et al. (1988) algorithm, where penalties are distinct for earliness and tardiness. The procedure and algorithm are tested in many conditions involving comparisons with dispatching rules and the EXP-ET function. When EXP-ET function is applied with possibility of idleness insertion, the optimal idleness period is provided. It was assumed that problem hardness is dependent on two classical parameters: average tardiness factor and relative range of due dates. Empirical comparative tests are conducted with computational simulation, where computational solution time and objective function value are evaluated. Results indicate that procedures performance is highly dependent on both parameters, showing that is necessary to know parameters values before choosing an appropriate procedure. The detailed results and computational code used in this study are also provided.

The most popular methods for solving the shortest-path problem in Artificial Intelligence are heuristic search algorithms. The main contributions of this research are new heuristic search algorithms that are either faster or scale up to larger problems than existing algorithms. Our contributions apply to both online and offline tasks. For online tasks, existing real-time heuristic search algorithms learn better informed heuristic values and in some cases eventually converge to a shortest path by repeatedly executing the action leading to a successor state with a minimum cost-to-goal estimate. In contrast, we claim that real-time heuristic search converges faster to a shortest path when it always selects an action leading to a state with a minimum f-value, where the f-value of a state is an estimate of the cost of a shortest path from start to goal via the state, just like in the offline A* search algorithm. We support this claim by implementing this new non-trivial action-selection rule in FALCONS and by showing empirically that FALCONS significantly reduces the number of actions to convergence of a state-of-the-art real-time search algorithm. For offline tasks, we improve on two existing ways of scaling up best-first search to larger problems. First, it is known that the WA* algorithm (a greedy variant of A*) solves larger problems when it is either diversified (i.e., when it performs expansions in parallel) or committed (i.e., when it chooses the state to expand next among a fixed-size subset of the set of generated but unexpanded states). We claim that WA* solves even larger problems when it is enhanced with both diversity and commitment. We support this claim with our MSC-KWA* algorithm. Second, it is known that breadth-first search solves larger problems when it prunes unpromising states, resulting in the beam search algorithm. We claim that beam search quickly solves even larger problems when it is enhanced with backtracking based on limited discrepancy search. We support this claim with our BULB algorithm. We show that both MSC-KWA* and BULB scale up to larger problems than several state-of-the-art offline search algorithms in three standard benchmark domains. Finally, we present an anytime variant of BULB and apply it to the multiple sequence alignment problem in biology.

In this study, we address job sequencing and tool switching problem arising in Flexible Manufacturing Systems. We consider a single machine with limited tool slots on its tool magazine. The available tool slots cannot accommodate all the tools required by all jobs, therefore tool switches between jobs are required. A single tool transporter with limited capacity is used in transporting the tools from the storage area to the machine. Our aim is to minimize the number of tool transporter movements. We provide two mixed integer linear programming formulations of the problem, one of which is based on the traveling salesman problem. We develop a Branch-and-Bound algorithm powered with various lower and upper bounding techniques for optimal results. In order to obtain good solutions in reasonable times, we propose Beam Search algorithms. Our computational results reveal the satisfactory performance of the B&amp / B algorithm for moderate sized problems. Moreover, Beam Search techniques perform well for large-sized problems.

A number of problems in Computer Vision, Natural Language Processing, and Machine Learning produce structured outputs in high-dimensional space, which makes searching for the global optimal solution extremely expensive. Thus, greedy algorithms, making trade-offs between precision and efficiency, are widely used. Unfortunately, they in general lack theoretical guarantees. In this thesis, we prove that greedy algorithms are effective and efficient to search for multiple top-scoring hypotheses from structured (neural) models: 1) Entropy estimation. We aim to find deterministic samples that are representative of Gibbs distribution via a greedy strategy. 2) Searching for a set of diverse and high-quality bounding boxes. We formulate this problem as the constrained maximization of a monotonic sub-modular function such that there exists a greedy algorithm having near-optimal guarantee. 3) Fill-in-the-blank. The goal is to generate missing words conditioned on context given an image. We extend Beam Search, a greedy algorithm applicable on unidirectional expansion, to bidirectional neural models when both past and future information have to be considered. We test our proposed approaches on a series of Computer Vision and Natural Language Processing benchmarks and show that they are effective and efficient. / Ph. D.

A diferença entre estações de trabalho é considerada desprezível em linhas de montagem tradicionais. Por outro lado, linhas de montagem heterogêneas consideram o problema de indústrias nas quais os tempos das tarefas variam de acordo com alguma característica a ser selecionada para a tarefa. No Problema de Balanceamento e Atribuição de Trabalhadores em Linhas de Montagem (do inglês Assembly Line Worker Assignment and Balancing Problem, ALWABP), os trabalhadores são responsáveis por estações de trabalho e de acordo com as suas habilidades, eles executam as tarefas em diferentes quantidades de tempo. Em alguns casos, os trabalhadores podem até ser incapazes de executar algumas tarefas. No Problema de Balanceamento de Linhas de Montagem Robóticas (do inglês Robotic Assembly Line Balancing Problem, RALBP), há diferentes tipos de robôs e o conjunto de tarefas de cada estação deve ser executada por um robô. Robôs do mesmo tipo podem ser usados múltiplas vezes. Nós propomos métodos exatos e heurísticos para a minimização do tempo de ciclo destes dois problemas, para um número fixo de estações. Os problemas têm características similares que são exploradas para produzir limitantes inferiores, métodos inferiores, models de programação inteira mista, e regras de redução e dominância. Para a estratégia de ramificação do método de branch-and-bound, entretanto, as diferenças entre os problemas forçam o uso de dois algoritmos diferentes. Uma estratégia orientada a tarefas tem os melhores resultados para o ALWABP-2, enquanto uma estratégia orientada a estações tem os melhores resultados para o RALBP-2. Nós mostramos que os limitantes inferiores, heurísticas, modelos de programação inteira mista e algoritmos de branch-and-bound para estes dois problemas são competitivos com os métodos do estado da arte da literatura. / The difference among workstations is assumed to be negligible in traditional assembly lines. Heterogeneous assembly lines consider the problem of industries in which the task times vary according to some property to be selected for the task. In the Assembly Line Worker Assignment and Balancing Problem (ALWABP), workers are assigned to workstations and according to their abilities, they execute tasks in different amounts of time. In some cases they can even be incapable of executing some tasks. In the Robotic Assembly Line Balancing Problem (RALBP) there are different types of robots and each station must be executed by a robot. Multiple robots of the same type may be used. We propose exact and heuristic methods for minimizing the cycle time of these two problems, for a fixed number of stations. The problems have similar characteristics that are explored to produce lower bounds, heuristic methods, mixed-integer programming models, and reduction and dominance rules. For the branching strategy of the branch-and-bound method, however, the differences among the problem force the use of two different algorithms. A task-oriented strategy has the best results for the ALWABP-2 while a station-oriented strategy has the best results for the RALBP-2. The lower bounds, heuristics, MIP models and branch-and-bound algorithms for these two problems are shown to be competitive with the state-of-the-art methods in the literature.