Produto: Catálogo de heurísticas. / CNPq / A consciência da intensificação da concorrência global e os desafios sociais e ecológicos complexos ampliam a atenção e o interesse em inovação e tecnologia. Neste contexto, exige-se uma constante busca por novas fontes de inspiração, demandando que a geração de ideias e soluções de problemas inventivos sejam cada vez mais eficientes. Uma metodologia reconhecida pela sua eficiência, sistemática e estimula ao pensamento inventivo é a TRIZ (Theory of Inventive Problem Solving). A aplicação da TRIZ propõe a utilização de diversas ferramentas e conceitos que incluem princípios inventivos e combinados, padrões e templates, denominados neste estudo de heurísticas inventivas. As heurísticas são aplicadas como estratégia cognitiva que levam os projetistas para um espaço de soluções diversas explorando ideias mais criativas e de elevado potencial. No entanto, o número elevado de Heurísticas Inventivas da TRIZ demanda um tempo significativo para serem compreendidas selecionadas e aplicadas, representando um obstáculo para os recém-chegados à TRIZ. A fim de suprir esta lacuna, este estudo tem por objetivo desenvolver um catálogo a partir das heurísticas inventivas de TRIZ, previamente compiladas, exemplificando-as e indexando-as. O método de pesquisa dos exemplos ocorreu por meio de análise funcional e uso de palavras-chaves, com busca em banco de dados online, patentes, revistas, livros, entre outros. A seleção dos exemplos foi focada em situações, processos e produtos reais em que a criatividade ou a grande capacidade competitiva proveniente de inovação foram evidenciadas. A sua descrição ocorreu de modo textual e visual. O índice unificado proposto leva em consideração estudo de autores antecessores, além de funções e atributos de cada heurística. Após estruturação, o Catálogo de Heurísticas foi aplicado em estudos de caso, que evidenciaram a relevância deste na sistematização das heurísticas compiladas, demonstrando o seu potencial no processo de ideação e geração de soluções criativas com potencial inovador. / Awareness of the intensifying global competition and complex social and ecological challenges increased the attention and interest in innovation and technology. In this context, it is required a constant search for new sources of inspiration, demanding generation of increasingly efficient ideas and inventive problem solving. A methodology recognized for its efficiency, systematic and stimulating inventive thinking is the TRIZ (Theory of Inventive Problem Solving). This methodology proposes the use of several tools and concepts, including, inventive and combined principles, standard solutions and templates, referred as inventive heuristics in this study. Heuristics are applied as cognitive strategy that leads designers to a place of diverse solutions, exploring more creative and high-potential ideas. However, the high quantity of Inventive Heuristics of TRIZ demands significant time to be understood, selected and applied, representing an obstacle for newcomers to TRIZ. In order to fill this gap, this study aims to develop a catalog, based on the Inventive Heuristics of TRIZ previously compiled, exemplifying and indexing them. The research method of examples occurred through functional analysis and generation of keywords, surveyed by means of online database, patents, journals, books, and more. The selection of examples was focused on cases, processes and real products where creativity and great competitiveness from innovation were evidenced. The proposed unified index takes into account the study from previous authors, as well as functions and attributes of each heuristic. The study provided a more didactic view of heuristics and the mapping of examples in order to make a more practical application, improving the process of tranfer of ideas to generate creative solutions with great innovative potential.

In this thesis we investigate the application of two heuristic methods, genetic algorithms and tabu/scatter search, to the optimisation of realistic portfolios. The model is based on the classical mean-variance approach, but enhanced with floor and ceiling constraints, cardinality constraints and nonlinear transaction costs which include a substantial illiquidity premium, and is then applied to a large I 00-stock portfolio. It is shown that genetic algorithms can optimise such portfolios effectively and within reasonable times, without extensive tailoring or fine-tuning of the algorithm. This approach is also flexible in not relying on any assumed or restrictive properties of the model and can easily cope with extensive modifications such as the addition of complex new constraints, discontinuous variables and changes in the objective function. The results indicate that that both floor and ceiling constraints have a substantial negative impact on portfolio performance and their necessity should be examined critically relative to their associated administration and monitoring costs. Another insight is that nonlinear transaction costs which are comparable in magnitude to forecast returns will tend to diversify portfolios; the effect of these costs on portfolio risk is, however, ambiguous, depending on the degree of diversification required for cost reduction. Generally, the number of assets in a portfolio invariably increases as a result of constraints, costs and their combination. The implementation of cardinality constraints is essential for finding the bestperforming portfolio. The ability of the heuristic method to deal with cardinality constraints is one of its most powerful features. / Decision Sciences / M. Sc. (Operations Research)

Nesta tese, nós estudamos a classe de problemas de blocos-móveis. Um problema de blocos-móveis consiste em k blocos móveis dispostos em um labirinto em grade quadrangular onde há um bloco móvel adicional chamado de o homem, que é o único bloco que pode ser movido diretamente. Em particular, cada problema de blocos-móveis é definido pelo conjunto de movimentos disponíveis, pela descrição do objetivo e pelo o que acontece quando o homem tenta mover um bloco. Sokoban é o problema de blocos-móveis mais conhecido e pesquisado. Nós investigamos a complexidade computacional de problemas de blocos-móveis. Antes desta tese, a maior parte da literatura cientifica abordou problemas de blocos-móveis apenas com movimentos de EMPURRAR, na maioria dos casos provando que esses problemas são PSPACE-complete. Nós consideramos dois conjuntos de problemas: apenas movimentos de PUXAR, e movimentos de EMPURRAR e PUXAR combinados. Nossas reduções usam a Lógica de Restrições Não Determinística. Nós provamos que muitos problemas apenas com movimentos de PUXAR são PSPACE-complete. Além disso, nós provamos que o conjunto de problemas com movimentos de EMPURRAR e PUXAR é PSPACE-complete. A nossa contribuição nessa linha de pesquisa é aprimorar o conhecimento sobre o panorama da complexidade de problemas de blocos-móveis. Nosso principal objetivo com essa tese é resolver otimamente problemas de blocos-móveis com foco em Sokoban. Métodos baseados em busca heurística e heurísticas de abstrações como banco de dados de padrões são as abordagens mais efetivas para resolver otimamente esses problemas. Nós fazemos muitas contribuições nessa linha de pesquisa. Nós introduzimos novas funções heurísticas usando bancos de dados padrão com a ideia de estados objetivos intermediários. Propomos uma técnica baseada em bancos de dados padrão para detectar impasses. Propomos regras de desempate que exploram a estrutura do problema. Usando estas funções heurísticas e regras de desempate nós aumentamos o número de instâncias resolvidas de forma ótima de Sokoban e outros problemas em comparação com os métodos anteriores. / In this thesis, we study the class of moving-blocks problems. A moving-blocks problem consists of k movable blocks placed on a grid-square maze where there is an additional movable block called the man, which is the only block that can be moved directly. In particular, each moving-blocks problem is defined by the set of moves available, by the goal description and by what happens when the man attempts to move a block. Sokoban is the best known and researched moving-blocks problem. We study moving-blocks problems in theory and practice. We investigate the computational complexity of problems of moving-blocks. Prior to this thesis, most of the scientific literature addressed moving-blocks problems with PUSH moves only, in most of the cases proving that these problems are PSPACE-complete. We consider two sets of problems: PULL moves only, and PUSH and PULL moves combined. Our reductions are from Nondeterministic Constraint Logic. We prove that many problems with PULL moves only are PSPACE-complete. In addition, we prove that the entire set of PUSH and PULL moves is PSPACE-complete. Our contribution in this research line is to enhance the knowledge on the complexity landscape of moving-blocks problems. Our main objective in this thesis is to optimally solve moving-blocks problems with a focus on Sokoban. Methods based on heuristic search and abstraction heuristics such as pattern databases are the most effective approaches to optimally solve these problems. We make many contributions in this research line. We introduce novel heuristic functions using pattern databases with the idea of intermediate goal states. We propose a technique based on pattern databases to detect deadlocks. We propose tie-breaking rules that exploit the structure of the problem. Using these heuristic functions and tie-breaking rules we increase the number of optimally solved instances of Sokoban and other problems compared to previous methods.

Nesta tese, nós estudamos a classe de problemas de blocos-móveis. Um problema de blocos-móveis consiste em k blocos móveis dispostos em um labirinto em grade quadrangular onde há um bloco móvel adicional chamado de o homem, que é o único bloco que pode ser movido diretamente. Em particular, cada problema de blocos-móveis é definido pelo conjunto de movimentos disponíveis, pela descrição do objetivo e pelo o que acontece quando o homem tenta mover um bloco. Sokoban é o problema de blocos-móveis mais conhecido e pesquisado. Nós investigamos a complexidade computacional de problemas de blocos-móveis. Antes desta tese, a maior parte da literatura cientifica abordou problemas de blocos-móveis apenas com movimentos de EMPURRAR, na maioria dos casos provando que esses problemas são PSPACE-complete. Nós consideramos dois conjuntos de problemas: apenas movimentos de PUXAR, e movimentos de EMPURRAR e PUXAR combinados. Nossas reduções usam a Lógica de Restrições Não Determinística. Nós provamos que muitos problemas apenas com movimentos de PUXAR são PSPACE-complete. Além disso, nós provamos que o conjunto de problemas com movimentos de EMPURRAR e PUXAR é PSPACE-complete. A nossa contribuição nessa linha de pesquisa é aprimorar o conhecimento sobre o panorama da complexidade de problemas de blocos-móveis. Nosso principal objetivo com essa tese é resolver otimamente problemas de blocos-móveis com foco em Sokoban. Métodos baseados em busca heurística e heurísticas de abstrações como banco de dados de padrões são as abordagens mais efetivas para resolver otimamente esses problemas. Nós fazemos muitas contribuições nessa linha de pesquisa. Nós introduzimos novas funções heurísticas usando bancos de dados padrão com a ideia de estados objetivos intermediários. Propomos uma técnica baseada em bancos de dados padrão para detectar impasses. Propomos regras de desempate que exploram a estrutura do problema. Usando estas funções heurísticas e regras de desempate nós aumentamos o número de instâncias resolvidas de forma ótima de Sokoban e outros problemas em comparação com os métodos anteriores. / In this thesis, we study the class of moving-blocks problems. A moving-blocks problem consists of k movable blocks placed on a grid-square maze where there is an additional movable block called the man, which is the only block that can be moved directly. In particular, each moving-blocks problem is defined by the set of moves available, by the goal description and by what happens when the man attempts to move a block. Sokoban is the best known and researched moving-blocks problem. We study moving-blocks problems in theory and practice. We investigate the computational complexity of problems of moving-blocks. Prior to this thesis, most of the scientific literature addressed moving-blocks problems with PUSH moves only, in most of the cases proving that these problems are PSPACE-complete. We consider two sets of problems: PULL moves only, and PUSH and PULL moves combined. Our reductions are from Nondeterministic Constraint Logic. We prove that many problems with PULL moves only are PSPACE-complete. In addition, we prove that the entire set of PUSH and PULL moves is PSPACE-complete. Our contribution in this research line is to enhance the knowledge on the complexity landscape of moving-blocks problems. Our main objective in this thesis is to optimally solve moving-blocks problems with a focus on Sokoban. Methods based on heuristic search and abstraction heuristics such as pattern databases are the most effective approaches to optimally solve these problems. We make many contributions in this research line. We introduce novel heuristic functions using pattern databases with the idea of intermediate goal states. We propose a technique based on pattern databases to detect deadlocks. We propose tie-breaking rules that exploit the structure of the problem. Using these heuristic functions and tie-breaking rules we increase the number of optimally solved instances of Sokoban and other problems compared to previous methods.

This study investigates the refinement of an evaluation framework for e-Government websites. The aim of the research was to determine how an existing evaluation framework, which recommends the use of multiple usability techniques, could be used to obtain usability data that would indicate how to improve e-Government websites and satisfy users' needs. The framework describes how common techniques, such as heuristic testing and user testing, can be used with the emerging discipline of web analytics to provide a comprehensive and detailed view of users' interactions on e-Government websites. The original framework was refined in the light of the findings and the refined framework should facilitate the improvement of e-Government websites depending on users' demands and interactions. The work involved implementing the original multi-dimensional framework in e-Government websites in Saudi Arabia. A case study method was used over two implementations. In the former implementation, the evaluation methods consisted of heuristic evaluation followed by usability testing then web analytic tools. However, in the later implementation, refinements to the evaluation framework were proposed and the order of methods was amended: web analytics was used first, followed by heuristic evaluation then usability testing. The framework recommends specific usability methods for evaluating specific issues. The conclusions of this study illustrate the potential benefits of using a multidimensional evaluation framework for e-Government websites and it was found that each usability method had its own particular benefits and limitations. The research concludes by illustrating the potential usefulness of the designed evaluation framework in raising awareness of usability methods for evaluating e-Government websites in Saudi Arabia.

Denna text är delvis en dokumentation av min egna resa inom datorbaserat tonsättande, specifikt inom algoritmisk komposition. Det är även ett utforskande av den tankevärld som finns i anknytning till dessa metoder – där estetiska koncept och konsekvenser diskuteras. Texten kommer huvudsakligen att beröra metoder som gynnas av eller möjliggörs av teknologi. Jag har försökt att närma mig dessa ämnen holistiskt genom att diskutera allt från estetik, teknik, till konkreta realiseringar av särskilda musikaliska idéer. Till detta tillkommer även många notexempel, lite kod, och illustrationer – specifikt för att stödja förklaringarna av, för många musikstudenter, främmande utommusikaliska koncept.

Rotary planing, and moulding, machining operations have been employed within the woodworking industry for a number of years. Due to the rotational nature of the machining process, cuttermarks, in the form of waves, are created on the machined timber surface. It is the nature of these cuttermarks that determine the surface quality of the machined timber. It has been established that cutting tool inaccuracies and vibrations are a prime factor in the form of the cuttermarks on the timber surface. A principal aim of this thesis is to create a control architecture that is suitable for the adaptive operation of a wood planing machine in order to improve the surface quality of the machined timber. In order to improve the surface quality, a thorough understanding of the principals of wood planing is required. These principals are stated within this thesis and the ability to manipulate the rotary wood planing process, in order to achieve a higher surface quality, is shown. An existing test rig facility is utilised within this thesis, however upgrades to facilitate higher cutting and feed speeds, as well as possible future implementations such as extended cutting regimes, the test rig has been modified and enlarged. This test rig allows for the dynamic positioning of the centre of rotation of the cutterhead during a cutting operation through the use of piezo electric actuators, with a displacement range of ±15μm. A new controller for the system has been generated. Within this controller are a number of tuneable parameters. It was found that these parameters were dependant on a high number external factors, such as operating speeds and run‐out of the cutting knives. A novel approach to the generation of these parameters has been developed and implemented within the overall system. Both cutterhead inaccuracies and vibrations can be overcome, to some degree, by the vertical displacement of the cutterhead. However a crucial information element is not known, the particular displacement profile. Therefore a novel approach, consisting of a subtle change to the displacement profile and then a pattern matching approach, has been implemented onto the test rig. Within the pattern matching approach the surface profiles are simplified to a basic form. This basic form allows for a much simplified approach to the pattern matching whilst producing a result suitable for the subtle change approach. In order to compress the data levels a Principal Component Analysis was performed on the measured surface data. Patterns were found to be present in the resultant data matrix and so investigations into defect classification techniques have been carried out using both K‐Nearest Neighbour techniques and Neural Networks. The application of these novel approaches has yielded a higher system performance, for no additional cost to the mechanical components of the wood planing machine, both in terms of wood throughput and machined timber surface quality.

published_or_final_version / Mathematics / Master / Master of Philosophy

This research is an effort to improve the performance of successive approximation algorithm with a prime aim of solving finite states and actions, infinite horizon, stationary, discrete and discounted Markov Decision Processes (MDPs). Successive approximation is a simple and commonly used method to solve MDPs. Successive approximation often appears to be intractable for solving large scale MDPs due to its computational complexity. Action elimination, one of the techniques used to accelerate solving MDPs, reduces the problem size through identifying and eliminating sub-optimal actions. In some cases successive approximation is terminated when all actions but one per state are eliminated. The bounds on value functions are the key element in action elimination. New terms (action gain, action relative gain and action cumulative relative gain) were introduced to construct tighter bounds on the value functions and to propose an improved action elimination algorithm. When span semi-norm is used, we show numerically that the actual convergence of successive approximation is faster than the known theoretical rate. The absence of easy-to-compute bounds on the actual convergence rate motivated the current research to try a heuristic action elimination algorithm. The heuristic utilizes an estimated convergence rate in the span semi-norm to speed up action elimination. The algorithm demonstrated exceptional performance in terms of solution optimality and savings in computational time. Certain types of structured Markov processes are known to have monotone optimal policy. Two special action elimination algorithms are proposed in this research to accelerate successive approximation for these types of MDPs. The first algorithm uses the state space partitioning and prioritize iterate values updating in a way that maximizes temporary elimination of sub-optimal actions based on the policy monotonicity. The second algorithm is an improved version that includes permanent action elimination to improve the performance of the algorithm. The performance of the proposed algorithms are assessed and compared to that of other algorithms. The proposed algorithms demonstrated outstanding performance in terms of number of iterations and omputational time to converge.

The importance of evaluating the usability of e-commerce websites is well recognised and this area has attracted research attention for more than a decade. Nearly all the studies that evaluated the usability of e-commerce websites employed either user-based (i.e. user testing) or evaluator-based (i.e. heuristic evaluation) usability evaluation methods; but no research has employed softwarebased (i.e. Google Analytics software) in the evaluation of such sites. Furthermore, the studies which employed user testing and/or heuristic evaluation methods in the evaluation of the usability of e-commerce websites did not offer detail about the benefits and drawbacks of these methods with respect to the identification of specific types of usability problems. This research developed a methodological framework for the usability evaluation of e-commerce websites which involved user testing and heuristic evaluation methods together with Google Analytics software. The framework was developed by comparing the benefits and drawbacks of these methods in terms of the specific areas of usability problems that they could or could not identify on ecommerce websites. The framework involves Google Analytics software as a preliminary step to provide a quick, easy and cheap indication of general potential usability problem areas on an e-commerce website and its specific pages. Then, the framework enables evaluators to choose other methods to provide in-depth detail about specific iv problems on the site. For instance, the framework suggests that user testing is good for identifying specific major usability problems related to four areas: navigation, design, the purchasing process and accessibility and customer service, while the heuristic evaluation is good for identifying a large number of specific minor usability problems related to eight areas including: navigation, internal search, the site architecture, the content, the design, accessibility and customer service, inconsistency and missing capabilities. The framework also suggests that the heuristic evaluation is good at identifying major security and privacy problems. The framework was developed based on an extensive evaluation of the effectiveness of the three methods in identifying specific usability problems in three case studies (e-commerce websites) in Jordan. This highlighted the usefulness of the methods and therefore helps e-commerce retailers to determine the usability method that best matches their needs. The framework was tested and the results indicated the usefulness of the suggested framework in raising awareness of usability and usability evaluation methods among e-commerce retailers in Jordan. This will help them address usability in the design of their websites, thus helping them to survive, grow and achieve success.