Wire Bonder and Molding are the most costive equipments in the investment of IC packaging; and the packaging quality, cost and delivery are concerned most in the assembly processes. An inappropriate process scheduling may result in the wastes of resources and assembly bottleneck. Manager must allocate the resources appropriately to adapt the changeable products and production lines. We would introduce several heuristic search methods, especially the Tabu search. Tabu search is one of the most popular methods of heuristic search. We also use Tabu list to record several latest moves and avoid to the duplication of the paths or loops. It starts from an initial solution and keep moving the solution to the best neighborhood without stock by Tabu. The iterations would be repeated until the terminating condition is reached. At last of the report, an example will be designed to approach the best wire bonding and molding scheduling by Tabu search; and verify the output volume is more than those with FIFO in the same period of production time. Tabu search will be then confirmed to be effective for flexible flow shop.

No description available.

Markov decision processes (MDPs) are a general framework used by Artificial Intelligence (AI) researchers to model decision theoretic planning problems. Solving real world MDPs has been a major and challenging research topic in the AI literature. This paper discusses two main groups of approaches in solving MDPs. The first group of approaches combines the strategies of heuristic search and dynamic programming to expedite the convergence process. The second makes use of graphical structures in MDPs to decrease the effort of classic dynamic programming algorithms. Two new algorithms proposed by the author, MBLAO* and TVI, are described here.

The one- and two-sided bipartite graph drawing problem alms to find a layout of a bipartite graph, with vertices of the two parts placed on parallel imaginary lines, that has the minimum number of edge-crossings. Vertices of one part are in fixed positions for the one-sided problem, whereas all vertices are free to move along their lines in the two-sided version. Many different heuristics exist for finding approximations to these problems, which are NP-hard. New sequential and parallel methods for producing drawings with low edgecrossings are investigated and compared to existing algorithms, notably Penalty Minimisation and Sifting, the current leaders. For the one-sided problem, new methods that include those based on simple stochastic hillclimbing, simulated annealing and genet.ic algorithms were tested. The new block-crossover genetic algorithm produced very good results with lower crossings than existing methods, although it tended to be slower. However, time was a secondary aim, the priority being to achieve low numbers of crossings. This algorithm can also be seeded with the output of an existing algorithm to improve results; combining with Penalty Minimisation in this way improved both the speed and number of crossings. Four parallel methods for the one-sided problem have been created, although two were abandoned because they gave bad results for even simple graphs. The other two methods, based on stochastic hill-climbing, produced acceptable results in faster times than similar sequential methods. PVM was used as the parallel communication system. Two new heuristics were studied for the two-sided problem, for which the only known existing method is to apply one-sided algorithms iteratively. The first is based on a heuristic for the linear arrangment problem; the second is a method of performing stochastic hill-climbing on two sides. A way of applying anyone-sided algorithm iteratively was also created. The linear arrangement method based on the Koren-Harel multi-scale algorithm achieved the best results, outperforming iterative Barycentre (previously the best method) and iterative Penalty Minimisation. Another area of this work created three new heuristics for the k-planar drawing problem where k > 1. These are the first known practical algorithms to solve this problem. A sequential genetic algorithm based on TimGA is devised to work on k-planar graphs. Two parallel algorithms, one island model and the other a 'mesh' model, are also given. Comparison of results for k = 2 indicate that the parallel island method is better than the other two methods. MPI was used for the parallel communication. Overall, 14 new methods are introduced, of which 10 were developed into working algorithms. For the one-sided bipartite graph drawing problem the new block-crossover genetic algorithm can produce drawings with lower crossings than the current best available algorithms. The parallel methods do not perform as well as the sequential ones, although they generally achieved the same results faster. All of the new two-sided methods worked well; the weighted two-sided swap stochastic hill-climbing method was comparable to the existing best method, iterative Barycentre, and generally produced drawings with lower crossings, although it suffered with needing a good termination condition. The new methods based on the linear arrangement problem consistently produced drawings with lower crossings than iterative Barycentre, although they were nearly always slower. A new parallel algorithm for the k-planar drawing problem, based on the island model, generally created drawings with the lowest edge-crossings, although no algorithms were known to exist to make comparisons.

Many single-agent search algorithms have parameters that need to be tuned. Although settings found by offline tuning will exhibit strong average performance, properly selecting parameter settings for each problem can result in substantially reduced search effort. We consider the use of dovetailing as a way to deal with this issue. This procedure performs search with multiple parameter settings simultaneously. We present results testing the use of dovetailing with the weighted A*, weighted IDA*, weighted RBFS, and BULB algorithms on the sliding tile and pancake puzzle domains. Dovetailing will be shown to significantly improve weighted IDA*, often by several orders of magnitude, and generally enhance weighted RBFS. In the case of weighted A* and BULB, dovetailing will be shown to be an ineffective addition to these algorithms. A trivial parallelization of dovetailing will also be shown to decrease the search time in all considered domains.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-09-09T18:25:14Z No. of bitstreams: 1 texto completo.pdf: 2101606 bytes, checksum: c4227b09a3bae62b835f5aabafc917b3 (MD5) / Made available in DSpace on 2016-09-09T18:25:14Z (GMT). No. of bitstreams: 1 texto completo.pdf: 2101606 bytes, checksum: c4227b09a3bae62b835f5aabafc917b3 (MD5) Previous issue date: 2016-05-25 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho apresentamos um modelo computacional baseado em teorias de design para gerar mapas de jogos de plataforma visualmente agradáveis. Nós estudamos o problema de geração de mapas como um problema de otimização e provamos que uma versão simplificada do problema é computacionalmente difícil. Em seguida, propomos uma abordagem de busca heurística para resolver o problema de geração de mapas e utilizamos ela para gerar níveis de um clone do Super Mario Bros (SMB), chamado Infinite Mario Bros (IMB). Antes de avaliar os níveis de IMB gerados pelo nosso sistema, realizamos um estudo detalhado das abordagens comumente utilizadas para avaliar o conteúdo gerado por programas de computador. A avaliação utilizada em trabalhos anteriores utiliza apenas métricas computacionais. Embora esses indicadores são importantes para uma avaliação inicial e exploratória do conteúdo gerado, não é claro se são capazes de capturar a percepção do jogador sobre o conteúdo gerado. Neste trabalho, comparamos os conhecimentos adquiridos a partir de um estudo com seres humanos usando níveis de IMB gerados por diferentes sistemas, com os conhecimentos adquiridos a partir de análise dos valores de métricas computacionais. Os nossos resultados sugerem que as m ́etricas computacionais atuais não devem substituir estudos com seres humanos para avaliar o conteúdo gerado por programas de computador. Usando os conhecimentos adquiridos em nosso experimento anterior, foi realizado outro estudo com seres humanos para avaliar os níveis de IMB gerados pelo nosso método. Os resultados mostram a vantagem do nosso método em relação a outras abordagens em termos de estética visual e diversão. Finalmente, foi realizado outro estudo com seres humanos, mostrando que o nosso método é capaz de gerar níveis de IMB semelhantes aos níveis de SMB criados por designers profissionais. / In this work we introduce a computational model based on theories of graphical design to generate visually pleasing video game maps. We cast the problem of map generation as an optimization problem and prove it to be computationally hard. Then, we propose a heuristic search approach to solve the map generation problem and use it to generate levels of a clone of Super Mario Bros (SMB) called Infinite Mario Bros (IMB). Before evaluating the levels of IMB generated by our system, we perform a detailed study of the approaches commonly used to evaluate the content generated by computer programs. The evaluation used in previous works often relies on computational metrics. While these metrics are important for an initial exploratory evaluation of the content generated, it is not clear whether they are able to capture the player’s perception of the content generated. In this work we compare the insights gained from a user study with IMB levels generated by different systems with the insights gained from analyzing computational metric values. Our results suggest that current computational metrics should not be used in lieu of user studies for evaluating content generated by computer programs. Using the insights gained in our previous experiment, we performed another user study to evaluate the IMB levels generated by our method. The results show the advantage of our method over other approaches in terms of visual aesthetics and enjoyment. Finally, we performed one last user study that showed that our method is able to generate IMB levels with striking similarity to SMB levels created by professional designers. / Autor sem Lattes e arquivo PDF não criptografou

Orientador: Fernando Antonio Campos Gomide / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-10T00:48:57Z (GMT). No. of bitstreams: 1 Tazoniero_Alexandre_M.pdf: 2202986 bytes, checksum: eac2bab1d27c5baaf56ef296663e1cef (MD5) Previous issue date: 2007 / Resumo: O transporte ferroviário tem grande participação no transporte de cargas e passageiros em todo o mundo. No Brasil a malha ferroviária sofreu um processo de abandono e deterioração no período de 1960 a 1990. A partir de 1990 a privatização da rede ferroviária nacional iniciou uma retomada de investimentos e nos últimos anos à demanda por transporte ferroviário vem crescendo significativamente. É necessário, então, que os recursos da ferrovia sejam utilizados de maneira eficiente para atender a crescente demanda, o que exige planejamento estratégico, táctico e operacional. No nível operacional uma das principais etapas e também umas das mais carentes de ferramentas computacionais é o Planejamento de Circulação de trens. O processo operacional de uma ferrovia é dinâmico, sujeito a inúmeras interferências imprevisíveis e uma ferramenta computacional para o apoio ao planejamento de circulação de trens deve fornecer soluções com tempo de processamento compatível com essa realidade. Este trabalho propõe algoritmos para o planejamento de circulação de trens em tempo real, utilizando metodologias de inteligência computacional e conjuntos nebulosos. Um algoritmo objetiva decidir localmente a preferência entre trens concorrendo pelo uso de um segmento de linha singela de modo a seguir uma referência de percurso fornecida por algum algoritmo de otimização ou por um especialista. Outro algoritmo decide, além da preferência entre trens, a velocidade de percurso dos trens para mantê-los o mais próximo possível de suas referências. O terceiro algoritmo usa elementos de busca em árvore para obter uma solução para o planejamento de circulação de trens. É feito um estudo comparativo dos algoritmos aqui propostos e de algoritmos existentes na literatura. O estudo comparativo é feito a pm1ir de instâncias pequenas de problema de planejamento de circulação e uma instância que considera dados reais de uma ferrovia brasileira. Os resultados mostram que os algoritmos propostos obtêm soluções próximas às ótimas para as instâncias pequenas e soluções satisfatórias para o caso real / Abstract: Railways plays a major role in freight and passenger transportation in the whole world. The Brazilian railway system has suffered a process of abandon and deterioration from 1960 to 1990. Since 1990 the privatization of the national railways brought new investments and in the last years the demand for railway transportation has increased significantly. Railway resources must be efficiently managed to match the increasingly transportation demand. This requires efficient strategic, tactical and operational planning. One of the main tasks at the operational planning level concerns train circulation and associated tools. Railway operation is a very dynamic process because trains are subject to many unexpected interferences. Computational tools to help trains circulation planning must provide solutions in a time range consistent with real-time needs. This work suggests algorithms for real-time train movement planning, using computational intelligence and fuzzy set theory methodology. One of the algorithms decides the preference between trains competing for a single line track at the same moment. The aim is to drive train circulation as dose as possible to reference trajectories supplied by human experts, global optimization algorithms or both. Other algorithm decides preference between trains and chose the velocity with which trains must travel to remain as dose as possible to its references. The third algorithm uses depth search algorithm to obtain a solution for train circulation problems. A comparative study considering the algorithms proposed herein and algorithms suggested in the literature. The comparative study is done using small railway system instances. Data of a major Brazilian railway is adopted to illustrate how the algorithms behave to solve larger instances. Results show that the algorithms here proposed obtain near optimal solutions for small instances and satisfactory solutions for the real case / Mestrado / Automação / Mestre em Engenharia Elétrica

There are two symmetrical resolution rules applicable to logic programs - SL-resolution which yields a top-down refutation and unit-resolution which yields a bottom-up refutation. Both resolution principles need to be coupled with a search rule before they can be used in practice. The search rule determines in which order program clauses are used in the refutation and affects both performance, completeness and quality of solutions. The thesis surveys exhaustive and heuristic search rules for SL-resolution and transformation techniques for (general) logic programs that makes unit-resolution goal oriented. The search rules were implemented as meta-interpreters for Prolog and were benchmarked on a suite of programs incorporating both deterministic and nondeterministic code. Whenever deemed applicable benchmark programs were permuted with respect to clause and goal ordering to see if it affected the interpreters performance and termination. With the help of the evaluation the conclusion was that alternative search rules for SL-resolution should not be used for performance gains but can in some cases greatly improve the quality of solutions, e.g. in planning or other applications where the quality of an answer correlates with the length of the refutation. It was also established that A* is more flexible than exhaustive search rules since its behavior can be fine-tuned with weighting, and can in some cases be more efficient than both iterative deepening and breadth-first search. The bottom-up interpreter based on unit-resolution and magic transformation had several advantages over the top-down interpreters. Notably for programs where subgoals are recomputed many times. The great disparity in implementation techniques made direct performance comparisons hard however, and it is not clear if even an optimized bottom-up interpreter is competitive against a top-down interpreter with tabling of answers.

A large class of practical planning problems that require reasoning about uncertain outcomes, as well as tradeoffs among competing goals, can be modeled as Markov decision processes (MDPs). This model has been studied for over 60 years, and has many applications that range from stochastic inventory control and supply-chain planning, to probabilistic model checking and robotic control. Standard dynamic programming algorithms solve these problems for the entire state space. A more efficient heuristic search approach focuses computation on solving these problems for the relevant part of the state space only, given a start state, and using heuristics to identify irrelevant parts of the state space that can be safely ignored. This dissertation considers the heuristic search approach to this class of problems, and makes three contributions that advance this approach. The first contribution is a novel algorithm for solving MDPs that integrates the standard value iteration algorithm with branch-and-bound search. Called branch-and-bound value iteration, the new algorithm has several advantages over existing algorithms. The second contribution is the integration of recently-developed suboptimality bounds in heuristic search algorithm for MDPs, making it possible for iterative algorithms for solving these planning problems to detect convergence to a bounded-suboptimal solution. The third contribution is the evaluation and analysis of some techniques that are widely-used by state-of-the-art planning algorithms, the identification of some weaknesses of these techniques, and the development of a more efficient implementation of one of these techniques -- a solved-labeling procedure that speeds converge by leveraging a decomposition of the state-space graph of a planning problem into strongly-connected components. The new algorithms and techniques introduced in this dissertation are experimentally evaluated on a range of widely-used planning benchmarks.

Tesis por compendio / [EN] Automated planning is a centralized process in which a single planning entity, or agent, synthesizes a course of action, or plan, that satisfies a desired set of goals from an initial situation. A Multi-Agent System (MAS) is a distributed system where a group of autonomous agents pursue their own goals in a reactive, proactive and social way. Multi-Agent Planning (MAP) is a novel research field that emerges as the integration of automated planning in MAS. Agents are endowed with planning capabilities and their mission is to find a course of action that attains the goals of the MAP task. MAP generalizes the problem of automated planning in domains where several agents plan and act together by combining their knowledge, information and capabilities. In cooperative MAP, agents are assumed to be collaborative and work together towards the joint construction of a competent plan that solves a set of common goals. There exist different methods to address this objective, which vary according to the typology and coordination needs of the MAP task to solve; that is, to which extent agents are able to make their own local plans without affecting the activities of the other agents. The present PhD thesis focuses on the design, development and experimental evaluation of a general-purpose and domain-independent resolution framework that solves cooperative MAP tasks of different typology and complexity. More precisely, our model performs a multi-agent multi-heuristic search over a plan space. Agents make use of an embedded search engine based on forward-chaining Partial Order Planning to successively build refinement plans starting from an initial empty plan while they jointly explore a multi-agent search tree. All the reasoning processes, algorithms and coordination protocols are fully distributed among the planning agents and guarantee the preservation of the agents' private information. The multi-agent search is guided through the alternation of two state-based heuristic functions. These heuristic estimators use the global information on the MAP task instead of the local projections of the task of each agent. The experimental evaluation shows the effectiveness of our multi-heuristic search scheme, obtaining significant results in a wide variety of cooperative MAP tasks adapted from the benchmarks of the International Planning Competition. / [ES] La planificación automática es un proceso centralizado en el que una única entidad de planificación, o agente, sintetiza un curso de acción, o plan, que satisface un conjunto deseado de objetivos a partir de una situación inicial. Un Sistema Multi-Agente (SMA) es un sistema distribuido en el que un grupo de agentes autónomos persiguen sus propias metas de forma reactiva, proactiva y social. La Planificación Multi-Agente (PMA) es un nuevo campo de investigación que surge de la integración de planificación automática en SMA. Los agentes disponen de capacidades de planificación y su propósito consiste en generar un curso de acción que alcance los objetivos de la tarea de PMA. La PMA generaliza el problema de planificación automática en dominios en los que diversos agentes planifican y actúan conjuntamente mediante la combinación de sus conocimientos, información y capacidades. En PMA cooperativa, se asume que los agentes son colaborativos y trabajan conjuntamente para la construcción de un plan competente que resuelva una serie de objetivos comunes. Existen distintos métodos para alcanzar este objetivo que varían de acuerdo a la tipología y las necesidades de coordinación de la tarea de PMA a resolver; esto es, hasta qué punto los agentes pueden generar sus propios planes locales sin afectar a las actividades de otros agentes. La presente tesis doctoral se centra en el diseño, desarrollo y evaluación experimental de una herramienta independiente del dominio y de propósito general para la resolución de tareas de PMA cooperativa de distinta tipología y nivel de complejidad. Particularmente, nuestro modelo realiza una búsqueda multi-agente y multi-heurística sobre el espacio de planes. Los agentes hacen uso de un motor de búsqueda embebido basado en Planificación de Orden Parcial de encadenamiento progresivo para generar planes refinamiento de forma sucesiva mientras exploran conjuntamente el árbol de búsqueda multiagente. Todos los procesos de razonamiento, algoritmos y protocolos de coordinación están totalmente distribuidos entre los agentes y garantizan la preservación de la información privada de los agentes. La búsqueda multi-agente se guía mediante la alternancia de dos funciones heurísticas basadas en estados. Estos estimadores heurísticos utilizan la información global de la tarea de PMA en lugar de las proyecciones locales de la tarea de cada agente. La evaluación experimental muestra la efectividad de nuestro esquema de búsqueda multi-heurístico, que obtiene resultados significativos en una amplia variedad de tareas de PMA cooperativa adaptadas a partir de los bancos de pruebas de las Competición Internacional de Planificación. / [CA] La planificació automàtica és un procés centralitzat en el que una única entitat de planificació, o agent, sintetitza un curs d'acció, o pla, que satisfau un conjunt desitjat d'objectius a partir d'una situació inicial. Un Sistema Multi-Agent (SMA) és un sistema distribuït en el que un grup d'agents autònoms persegueixen les seues pròpies metes de forma reactiva, proactiva i social. La Planificació Multi-Agent (PMA) és un nou camp d'investigació que sorgeix de la integració de planificació automàtica en SMA. Els agents estan dotats de capacitats de planificació i el seu propòsit consisteix en generar un curs d'acció que aconseguisca els objectius de la tasca de PMA. La PMA generalitza el problema de planificació automàtica en dominis en què diversos agents planifiquen i actúen conjuntament mitjançant la combinació dels seus coneixements, informació i capacitats. En PMA cooperativa, s'assumeix que els agents són col·laboratius i treballen conjuntament per la construcció d'un pla competent que ressolga una sèrie d'objectius comuns. Existeixen diferents mètodes per assolir aquest objectiu que varien d'acord a la tipologia i les necessitats de coordinació de la tasca de PMA a ressoldre; és a dir, fins a quin punt els agents poden generar els seus propis plans locals sense afectar a les activitats d'altres agents. La present tesi doctoral es centra en el disseny, desenvolupament i avaluació experimental d'una ferramenta independent del domini i de propòsit general per la resolució de tasques de PMA cooperativa de diferent tipologia i nivell de complexitat. Particularment, el nostre model realitza una cerca multi-agent i multi-heuristica sobre l'espai de plans. Els agents fan ús d'un motor de cerca embegut en base a Planificació d'Ordre Parcial d'encadenament progressiu per generar plans de refinament de forma successiva mentre exploren conjuntament l'arbre de cerca multiagent. Tots els processos de raonament, algoritmes i protocols de coordinació estan totalment distribuïts entre els agents i garanteixen la preservació de la informació privada dels agents. La cerca multi-agent es guia mitjançant l'aternança de dues funcions heurístiques basades en estats. Aquests estimadors heurístics utilitzen la informació global de la tasca de PMA en lloc de les projeccions locals de la tasca de cada agent. L'avaluació experimental mostra l'efectivitat del nostre esquema de cerca multi-heurístic, que obté resultats significatius en una ampla varietat de tasques de PMA cooperativa adaptades a partir dels bancs de proves de la Competició Internacional de Planificació. / Torreño Lerma, A. (2016). Cooperative planning in multi-agent systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/65815 / Premios Extraordinarios de tesis doctorales / Compendio