International Telemetering Conference Proceedings / October 18-21, 2004 / Town & Country Resort, San Diego, California / The Broadcast Scheduling Problem (BSP) is a well known NP-complete problem that arises in the study of wireless networks. In the BSP, a finite set of stations are to be scheduled in a time division multiple access (TDMA) frame. The objective is a collision free transmission schedule with the minimum number of TDMA slots and maximal slot utilization. Such a schedule will minimize the total system delay. We present variations of a Greedy Randomized Adaptive Search Procedure (GRASP) for the BSP. Path-relinking, a post-optimization strategy is applied. Also, a reactivity method is used to balance GRASP parameters. Numerical results of our research are reported and compared with other heuristics from the literature.

In this thesis, we study time-sensitive applications where it is important to minimize the completion time, i.e., time passing between receiving the instance and finishing the implementation of the solution. Different from the traditional approach, we are directly focusing on the minimization of the computation time as well as finding the optimal solution to the problem. The conventional approach to these conflicting objectives is generally to trade off one for the other. As an alternative, we propose a new approach called Computation-Implementation Parallelization (CIP), and develop methods to embed the computation time into the solution-implementation to minimize the total completion time. We implement our CIP approach and show its effectiveness on a type of TSP we call the TSP Race problem, where the goal is to minimize the time between receiving the instance and finishing the travel. We demonstrate a method for determining a priori when CIP will be effective. We also implement our CIP approach on Computation-Time Limited Capacitated Vehicle Routing (CTL-CVRP) problems, and show that it is possible to decrease the computation-only time while maintaining the solution quality. By this means, some of the computation time can be set free and used to improve the customer service either by delaying the order cutoff time or dispatching the trucks earlier. As a tangential study, we develop a new TSP tour length estimation model. Our model is distribution-free, and is shown to produce very accurate estimates on many different node dispersions.

This thesis uses a grounded theory methodology to reveal the processes by which cognitive heuristics are used by senior managers to make decisions in a large UK local authority. The thesis is based on primary data, organisational documentation and an extensive and critical review of the pertinent literature. Primary data was generated over four years and involved detailed observation of 156 senior managers making a total of 513 decisions, together with formal interviews and informal discussions with these managers. The organisation under study provided an ideal context for this research since it offered a rich insight into management decision-making practices in diverse contexts such as social work and highways, and with varying degrees of urgency ranging from procurement decisions lasting several months to instant decisions concerning child protection. Furthermore, UK local government has been subject to drastic change in recent years, such as the introduction of private sector management practices and increased competition. This has been exacerbated by an austerity programme which means that local authorities, in common with much of the world, have to do a lot more with a lot less. The turbulent context of local government is, in Yin’s (2009) terms, an ‘exemplifying’ case study, and hence the issues raised in this study resonate far beyond the scope of this thesis. This thesis makes a number of significant contributions to knowledge. Firstly, original flow charts are developed that allow the underlying processes of heuristic decision-making to be identified, and these reveal that, whereas the academic literature treats heuristics as discrete entities, there is actually considerable interplay between them. Further, a new definition of the moral heuristic is developed, which allows researchers to view this heuristic at a higher, more conceptual level than has hitherto been possible. The thesis also extends the work of Daniel Kahneman and demonstrates that the role of the unconscious in decision-making is more complex than previously thought. For instance, intuitive heuristics can be used consciously and choice-based heuristics can be used unconsciously. It is also argued that the underlying processes of ‘classical’ theory are better explained by the degree of consciousness involved when making a decision, and not by the commonly accepted normative/behavioural distinction made by Herbert Simon and others. As such, this thesis represents an important contribution to the decision-making literature.

Many real-world optimisation problems are discrete in nature. Although recent rapid developments in computer technologies are steadily increasing the speed of computations, the size of an instance of a hard discrete optimisation problem solvable in prescribed time does not increase linearly with the computer speed. This calls for the development of new solution methodologies for solving larger instances in shorter time. Furthermore, large instances of discrete optimisation problems are normally impossible to solve to optimality within a reasonable computational time/space and can only be tackled with a heuristic approach. In this thesis the development of so called matheuristics, the heuristics which are based on the mathematical formulation of the problem, is studied and employed within the variable neighbourhood search framework. Some new variants of the variable neighbourhood searchmetaheuristic itself are suggested, which naturally emerge from exploiting the information from the mathematical programming formulation of the problem. However, those variants may also be applied to problems described by the combinatorial formulation. A unifying perspective on modern advances in local search-based metaheuristics, a so called hyper-reactive approach, is also proposed. Two NP-hard discrete optimisation problems are considered: 0-1 mixed integer programming and clustering with application to colour image quantisation. Several new heuristics for 0-1 mixed integer programming problem are developed, based on the principle of variable neighbourhood search. One set of proposed heuristics consists of improvement heuristics, which attempt to find high-quality near-optimal solutions starting from a given feasible solution. Another set consists of constructive heuristics, which attempt to find initial feasible solutions for 0-1 mixed integer programs. Finally, some variable neighbourhood search based clustering techniques are applied for solving the colour image quantisation problem. All new methods presented are compared to other algorithms recommended in literature and a comprehensive performance analysis is provided. Computational results show that the methods proposed either outperform the existing state-of-the-art methods for the problems observed, or provide comparable results. The theory and algorithms presented in this thesis indicate that hybridisation of the CPLEX MIP solver and the VNS metaheuristic can be very effective for solving large instances of the 0-1 mixed integer programming problem. More generally, the results presented in this thesis suggest that hybridisation of exact (commercial) integer programming solvers and some metaheuristic methods is of high interest and such combinations deserve further practical and theoretical investigation. Results also show that VNS can be successfully applied to solving a colour image quantisation problem.

<p>Individuals have the tendency to believe that they have complete information when making decisions. In many contexts this propensity allows for swift, efficient, and generally effective decision making. However, individuals cannot always see a representative picture of the world in which they operate. This paper examines judgment in censored environments where a constraint, the censorship point, systematically distorts the sample observed by a decision maker. Random instances beyond the censorship point are observed at the censorship point, while instances below the censorship point are observed at their true value. Many important managerial decisions occur in censored environments, such as inventory, risk-taking, and employee evaluation decisions. This empirical work demonstrates a censorship bias - individuals tend to rely too heavily on the observed censored sample, biasing their beliefs about the underlying population. Further, the censorship bias is exacerbated for higher rates of censorship, higher variance in the population, and higher variability in the censorship points. Evidence from four studies demonstrates how the censorship bias can cause managers to underestimate demand for their goods, over-estimate risk in their environments, and underappreciate the capabilities of their employees, which can lead to undesirable outcomes for organizations.</p> / Dissertation

The areas of machine learning, data mining, and knowledge representation have many different formats used to represent information. Decision rules, amongst these formats, are the most expressive and easily-understood by humans. In this thesis, we use dynamic programming to design decision rules and analyze them. The use of dynamic programming allows us to work with decision rules in ways that were previously only possible for brute force methods. Our algorithms allow us to describe the set of all rules for a given decision table. Further, we can perform multi-stage optimization by repeatedly reducing this set to only contain rules that are optimal with respect to selected criteria. One way that we apply this study is to generate small systems with short rules by simulating a greedy algorithm for the set cover problem. We also compare maximum path lengths (depth) of deterministic and non-deterministic decision trees (a non-deterministic decision tree is effectively a complete system of decision rules) with regards to Boolean functions. Another area of advancement is the presentation of algorithms for constructing Pareto optimal points for rules and rule systems. This allows us to study the existence of “totally optimal” decision rules (rules that are simultaneously optimal with regards to multiple criteria). We also utilize Pareto optimal points to compare and rate greedy heuristics with regards to two criteria at once. Another application of Pareto optimal points is the study of trade-offs between cost and uncertainty which allows us to find reasonable systems of decision rules that strike a balance between length and accuracy.

Doctor of Philosophy / Department of Psychological Sciences / Gary L. Brase / Risky decision making occurs in both humans and non-human animals. For a large portion of the history of scientific investigation into human judgment and decision making, risky behavior has been viewed as flawed and irrational. However, the past several decades have seen advances in the view of human rationality. Scientists have suggested that, rather than using probability theory as the metric by which humans are judged as rational or irrational, human minds should be evaluated with respect to specific ecologies (e.g., Gigerenzer & Selten, 2001) with some scientists going further and specifying the ecologies as those which our ancestors evolved; essentially, our minds and their decision processes are adapted to solve specific recurring problems, and to solve those problems in specific environments. Within the domain of risky decision making there are a number of theories and models which are consistent with the hypothesis that human (and non-human) minds are molded for specific behavioral patterns based on environmental cues. One example is the priority heuristic. The priority heuristic is based in the ecological rationality approach—that heuristics are designed for specific ecologies. However, the ecological rationality of the priority heuristic is underspecified. Studies One and Two of the present dissertation compared predictions made by two models of risk-taking from evolutionary biology and behavioral ecology (dominance theory and risk-sensitive foraging) with a variety of predictions made by the priority heuristic. Data clearly showed that risk-sensitive foraging outperforms the priority heuristic (Study One) and that the priority heuristic cannot account for the motivation to acquire a minimum number of resources. Study Two showed mixed results for the priority heuristic when compared to dominance theory. Specifically, choice patterns were consistent with the priority heuristic, but process data in the form of decision times were not consistent with the priority heuristic. Also, the data pointed to a strong effect for desiring higher status when competing against others of varying status. Study Three compared four potential models of risky decision making in an attempt to extend the pattern of results from Studies One and Two showing general risk-sensitivity when attempting to achieve a specified need level (Money for Study One; Status for Study Two). Also, Study Three attempted to clarify the scope of the pattern of general risk-sensitivity by examining differential patterns of results based on whether the models predicted motivations to achieve need levels for money, status, or both. Results from Study Three were consistent with a general model of risk-sensitivity which operated on both monetary need levels and status need levels. This effect was additionally ubiquitous for males and females, contrary to predictions by dominance theory. The data from three studies showed support for a general model of risk-sensitivity consistent with those proposed by others (Mishra, 2010). The concept and implications of this general risk-sensitivity model are discussed, as well as future directions to understand the finer details and potential scope of this particular general risk-sensitivity model.

The target of this thesis is to explain the Travelling Salesman Problem and also create a special program, which will be able to make calculations using the heuristics GENIUS. The Travelling Salesman Problem will be described from two different points of view. The first one is the historical description of the idea of the Travelling Salesman Problem and later will be the problem will be described with some of the very wide number of the calculation methods. For the explanation of the methods, in the thesis there has been chosen some of the algorithms which belong to that methods. The heuristics and also the exact algorithms will be explained. The focus of this thesis is on the heuristics called GENIUS and also in the creation of the program which can calculate it. The program works first with the GENI algorithm and after that it works with US post-optimization algorithm. The program will be described from the point of view of the user and the manual will be written as well. The program will be tested on two different examples and will be compared with the exact algorithm.

Este trabalho lida com o problema de balanceamento e sequenciamento de linhas de produção multi-modelo com trabalhadores deficientes, uma generalização de dois importantes problemas da literatura de linhas de produção: o Problema de Balanceamento de Linhas de Produção Multi-Modelo (MALBP) e o Problema de Balanceamento e Designação de Trabalhadores em Linhas de Produção (ALWABP). O MALBP tem sido particularmente importante nas últimas décadas, onde, em um cenário de maior competividade, cresce a necessidade de produção em larga escala de produtos customizados. O ALWABP, por sua vez, é de grande importância em Centros de Trabalhadores com Deficiências (CTDs), onde é necessário considerar as competências individuais de cada trabalhador, que se revelam nos diferentes tempos de execução de uma tarefa, segundo o trabalhador escolhido. Ao nosso conhecimento, nenhum estudo se dedicou a resolver estes dois problemas conjuntamente. Nesta dissertação, propomos modelos lineares para os problemas de balanceamento e sequenciamento de linhas de produção multi-modelo em CTDs. Para o problema de sequenciamento, limitantes inferiores e superiores e métodos heurísticos de resolução são desenvolvidos e discutidos. Testes computacionais foram efetuados e os resultados sugerem que os métodos desenvolvidos são eficientes / This study addresses the Mixed Assembly Line and Worker Assignment Balancing Problem, which generalizes two classical problems in the assembly line literature: the Mixed Assembly Line Balancing Problem (MALBP) and the Assembly Line Worker Assignment and Balacing Problem (ALWABP). The MALBP has been considered particularly important in the last two decades, when, in the context of more competitive scenarios, there is a growing need of producing customized products in large scale. On the other hand, the ALWABP is of interest in Sheltered Work centers for the Disabled (SWD). In this situation, we must consider each worker individual abilities, which results in task duration times that are dependent on the workers selected for their execution. To the best of our knowledge, there has been no effort to solve these problems jointly. We propose linear models for both balancing and sequencing multimodels assembly lines commonly found in SWD. Lower and upper bounds and also heuristic methods are proposed and discussed for the sequencing problem. The results obtained by computational experiments suggest the heuristic methods can efficiently solve the MALWABP

Submitted by Sandro Camargo (sandro.camargo@unipampa.edu.br) on 2015-05-09T18:28:47Z No. of bitstreams: 1 107110006.pdf: 2090462 bytes, checksum: 5fecbc3cc993bd7ac1637e41b7b2be41 (MD5) / Made available in DSpace on 2015-05-09T18:28:47Z (GMT). No. of bitstreams: 1 107110006.pdf: 2090462 bytes, checksum: 5fecbc3cc993bd7ac1637e41b7b2be41 (MD5) Previous issue date: 2012-10-19 / Com a total dependência pela energia elétrica em todos os setores da sociedade e a consequente regulamentação, é necessário que as concessionárias se preocupem em manter a continuidade do seu fornecimento, além de atender aos padrões que remetem à qualidade. A continuidade do fornecimento de energia elétrica é algo fundamental tanto para os consumidores quanto para a concessionária, a qual deixa de vender energia elétrica e ainda pode ser penalizada por interrupções muito longas ou em áreas críticas (hospitais ou indústrias, por exemplo). Como nem sempre é possível manter a continuidade do fornecimento devido a diversos fatores, sendo os defeitos permanentes os mais críticos, as empresas concessionárias são levadas a procurar novas metodologias e tecnologias para diminuir o tempo que o fornecimento de energia elétrica é interrompido. Nesse trabalho é descrita uma metodologia para o restabelecimento da energia em redes de distribuição de maneira automática. Essa metodologia se baseia no uso de tecnologias de comunicação e na automação dos equipamentos de manobras das redes. Com isso é possível obter os dados do estado da rede em tempo real, e é possível enviar os comandos para tais equipamentos de forma direta, sem a necessidade de intervenção humana. A metodologia aqui apresentada tem como objetivo detectar a localização de um defeito na rede através de leituras dos estados dos equipamentos, e então procurar as melhores manobras que restabeleçam o fornecimento ao máximo de consumidores sem que isso coloque todo sistema de distribuição, ou mesmo parte dele, em sobrecarga. Também é considerado que a rede pode ter sofrido alterações em equipamentos não automatizados (chaves manuais), e que as características de carga mudam no decorrer do tempo. Assim, a topologia deve ser atualizada antes de executar simulações e que os dados para tais simulações devem prever o comportamento da carga para o tempo que a contingência possa durar. Como teste da metodologia, foram executadas simulações em dados de redes reais de distribuição com diferentes topologias e diferentes cenários de defeitos. Os resultados obtidos foram satisfatórios na medida que tais soluções de restabelecimento eram viáveis em termos de carregamento da rede e foram calculadas em um curto espaço de tempo (poucos segundos). Essa agilidade traz vantagens tanto para os clientes quanto para a própria concessionária. / With the total dependency for electric power in all society sectors and the following regumen-tation, is necessary that the utilities worry in maintaining the continuity of power supply, in addition to meeting the standards that refer to quality. The continuity of power supply is fun- damental both for consumers and for the utility, which stops selling electricity and can still be penalized for too long interruptions or in critical areas (hospitals or industries, for example). As it is not allways possible to maintain the continuity of power supply due several factors, being the most critical the permanets defects, the utilities are driven to seek new methods and tecnologies to reduce the time that power supply is interrupted. In this work we describe a methodology for automatic restoration in power grids. This methodology is based on the use of communication technologies and automation equipment maneuvers networks. With this is possible to get the data status from the grid in real time, and also can send commands to these devices directly, without the need for human intervention. The methodology presented here tries to detect the location of a fault on the grid, through readings of the equipments status, and then search for the best maneuvers to restores supply to maximum consumers without putting the entire distribution system, or portion thereof, in overload . It is also considered that the grid may have changed in non-automated equipment (manual keys), and that the load characteristics change over time. Thus, the topology must be updated before running simulations and data for such simulations should predict the behavior of the load for time that can last contingency. As a test of the methodology, simulations were performed on real power grids data with different topologies and different scenarios defects. The results were satisfactory as such restoration solutions were viable in terms of network loading and were calculated in a short time (few seconds). This agility has benefits both for customers and for the own utility.