BEE COLONIES APPLIED TO MULTIPROCESSOR SCHEDULING

In order to achieve the high performance, we need to have an efficient scheduling of a parallelprogram onto the processors in multiprocessor systems that minimizes the entire executiontime. This problem of multiprocessor scheduling can be stated as finding a schedule for ageneral task graph to be executed on a multiprocessor system so that the schedule length can be minimize [10]. This scheduling problem is known to be NP- Hard.In multi processor task scheduling, we have a number of CPU’s on which a number of tasksare to be scheduled that the program’s execution time is minimized. According to [10], thetasks scheduling problem is a key factor for a parallel multiprocessor system to gain betterperformance. A task can be partitioned into a group of subtasks and represented as a DAG(Directed Acyclic Graph), so the problem can be stated as finding a schedule for a DAG to beexecuted in a parallel multiprocessor system so that the schedule can be minimized. Thishelps to reduce processing time and increase processor utilization. The aim of this thesis workis to check and compare the results obtained by Bee Colony algorithm with already generatedbest known results in multi processor task scheduling domain.

Train Dispatching: Heuristic Optimization

Train dispatchers faces lots of challenges due to conflicts which causes delays of trains as a result of solving possible dispatching problems the network faces. The major challenge is for the train dispatchers to make the right decision and have reliable, cost effective and much more faster approaches needed to solve dispatching problems. This thesis work provides detail information on the implementation of different heuristic algorithms for train dispatchers in solving train dispatching problems. The library data files used are in xml file format and deals with both single and double tracks between main stations. The main objective of this work is to build different heuristic algorithms to solve unexpected delays faced by train dispatchers and to help in making right decisions on steps to take to have reliable and cost effective solution to the problems. These heuristics algorithms proposed were able to help dispatchers in making right decisions when solving train dispatching problems.

Statistical bound of genetic solutions to quadratic assignment problems

Quadratic assignment problems (QAPs) are commonly solved by heuristic methods, where the optimum is sought iteratively. Heuristics are known to provide good solutions but the quality of the solutions, i.e., the confidence interval of the solution is unknown. This paper uses statistical optimum estimation techniques (SOETs) to assess the quality of Genetic algorithm solutions for QAPs. We examine the functioning of different SOETs regarding biasness, coverage rate and length of interval, and then we compare the SOET lower bound with deterministic ones. The commonly used deterministic bounds are confined to only a few algorithms. We show that, the Jackknife estimators have better performance than Weibull estimators, and when the number of heuristic solutions is as large as 100, higher order JK-estimators perform better than lower order ones. Compared with the deterministic bounds, the SOET lower bound performs significantly better than most deterministic lower bounds and is comparable with the best deterministic ones. 

On statistical bounds of heuristic solutions to location problems

Solutions to combinatorial optimization problems, such as problems of locating facilities, frequently rely on heuristics to minimize the objective function. The optimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. Pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small, almost dormant, branch of the literature suggests using statistical principles to estimate the minimum and its bounds as a tool to decide upon stopping and evaluating the quality of the solution. In this paper we examine the functioning of statistical bounds obtained from four different estimators by using simulated annealing on p-median test problems taken from Beasley’s OR-library. We find the Weibull estimator and the 2nd order Jackknife estimator preferable and the requirement of sample size to be about 10 being much less than the current recommendation. However, reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality and we give a simple statistic useful for checking the quality. We end the paper with an illustration on using statistical bounds in a problem of locating some 70 distribution centers of the Swedish Post in one Swedish region. 

A stopping rule while searching for optimal solution of facility-location

Solutions to combinatorial optimization, such as p-median problems of locating facilities, frequently rely on heuristics to minimize the objective function. The minimum is sought iteratively and a criterion is needed to decide when the procedure (almost) attains it. However, pre-setting the number of iterations dominates in OR applications, which implies that the quality of the solution cannot be ascertained. A small branch of the literature suggests using statistical principles to estimate the minimum and use the estimate for either stopping or evaluating the quality of the solution. In this paper we use test-problems taken from Baesley's OR-library and apply Simulated Annealing on these p-median problems. We do this for the purpose of comparing suggested methods of minimum estimation and, eventually, provide a recommendation for practioners. An illustration ends the paper being a problem of locating some 70 distribution centers of the Swedish Post in a region.

Confidence in heuristic solutions?

Solutions to combinatorial optimization problems frequently rely on heuristics to minimize an objective function. The optimum is sought iteratively and pre-setting the number of iterations dominates in operations research applications, which implies that the quality of the solution cannot be ascertained. Deterministic bounds offer a mean of ascertaining the quality, but such bounds are available for only a limited number of heuristics and the length of the interval may be difficult to control in an application. A small, almost dormant, branch of the literature suggests using statistical principles to derive statistical bounds for the optimum. We discuss alternative approaches to derive statistical bounds. We also assess their performance by testing them on 40 test p-median problems on facility location, taken from Beasley’s OR-library, for which the optimum is known. We consider three popular heuristics for solving such location problems; simulated annealing, vertex substitution, and Lagrangian relaxation where only the last offers deterministic bounds. Moreover, we illustrate statistical bounds in the location of 71 regional delivery points of the Swedish Post. We find statistical bounds reliable and much more efficient than deterministic bounds provided that the heuristic solutions are sampled close to the optimum. Statistical bounds are also found computationally affordable.

Hanteringen när medarbetares privata problem inverkar negativt på arbetsplatsen : En studie ur ett ledarskapsperspektiv

Uppsatsens syfte var att undersöka hur ledare hanterar situationer där medarbetares privata problem inverkar negativt på arbetet för både arbetsgivare och övriga medarbetare. För att få svar på det har vi inspirerats av vinjettstudie som utgår från diskussioner av fiktiva fall. Vi har genomfört studien med fyra enskilda semistrukturerade intervjuer och en fokusgruppsintervju där vi först introducerade respondenterna med vinjetterna. Deltagarna till undersökningen valdes ut genom ett subjektivt urval där vi riktade in oss på ledare, angående vilken organisation de tillhörde var av mindre vikt. I teoridelen introducerades teorierna ledarskap, medarbetarskap, individen i gruppen, ekonomi, hälsa, lagar, organisationskultur och föreskrifter samt försäkringskassans roll. Resultatet analyserades sedan mot teorierna och vi kan konstatera att respondenterna generellt menade att det var viktigt att prioritera kommunikation och relationer. Betydelsefullt var att relationerna etablerades innan problemen uppstår eftersom det anses vara svårt att skapa relationer i konfliktfyllda lägen. Tiden har betydelse vid hantering av problem av den orsaken att gränsen för vad som är acceptabelt förflyttas med tidens gång. Beroende på problem varierade graden av toleransnivå hos chefer och övriga medarbetare i vår undersökning. Resultatet visade att gränsen för privatlivets påverkan på arbetslivet går när arbetet blir misskött och när kunder och andra medarbetare påverkas. Utifrån ett genusperspektiv ansåg intervjupersonerna att det saknade betydelse om chefen var en man eller kvinna när det handlade om att hantera problem som uppkom, det ansågs vara personligt.

How do different densities in a network affect the optimal location of service centers?

The p-median problem is often used to locate p service centers by minimizing their distances to a geographically distributed demand (n). The optimal locations are sensitive to geographical context such as road network and demand points especially when they are asymmetrically distributed in the plane. Most studies focus on evaluating performances of the p-median model when p and n vary. To our knowledge this is not a very well-studied problem when the road network is alternated especially when it is applied in a real world context. The aim in this study is to analyze how the optimal location solutions vary, using the p-median model, when the density in the road network is alternated. The investigation is conducted by the means of a case study in a region in Sweden with an asymmetrically distributed population (15,000 weighted demand points), Dalecarlia. To locate 5 to 50 service centers we use the national transport administrations official road network (NVDB). The road network consists of 1.5 million nodes. To find the optimal location we start with 500 candidate nodes in the network and increase the number of candidate nodes in steps up to 67,000. To find the optimal solution we use a simulated annealing algorithm with adaptive tuning of the temperature. The results show that there is a limited improvement in the optimal solutions when nodes in the road network increase and p is low. When p is high the improvements are larger. The results also show that choice of the best network depends on p. The larger p the larger density of the network is needed. 

Does road network density matter in optimally locating facilities?

Optimal location on the transport infrastructure is the preferable requirement for many decision making processes. Most studies have focused on evaluating performances of optimally locate p facilities by minimizing their distances to a geographically distributed demand (n) when p and n vary. The optimal locations are also sensitive to geographical context such as road network, especially when they are asymmetrically distributed in the plane. The influence of alternating road network density is however not a very well-studied problem especially when it is applied in a real world context. This paper aims to investigate how the density level of the road network affects finding optimal location by solving the specific case of p-median location problem. A denser network is found needed when a higher number of facilities are to locate. The best solution will not always be obtained in the most detailed network but in a middle density level. The solutions do not further improve or improve insignificantly as the density exceeds 12,000 nodes, some solutions even deteriorate. The hierarchy of the different densities of network can be used according to location and transportation purposes and increase the efficiency of heuristic methods. The method in this study can be applied to other location-allocation problem in transportation analysis where the road network density can be differentiated. 

How does data quality in a network affect heuristic solutions?

To have good data quality with high complexity is often seen to be important. Intuition says that the higher accuracy and complexity the data have the better the analytic solutions becomes if it is possible to handle the increasing computing time. However, for most of the practical computational problems, high complexity data means that computational times become too long or that heuristics used to solve the problem have difficulties to reach good solutions. This is even further stressed when the size of the combinatorial problem increases. Consequently, we often need a simplified data to deal with complex combinatorial problems. In this study we stress the question of how the complexity and accuracy in a network affect the quality of the heuristic solutions for different sizes of the combinatorial problem. We evaluate this question by applying the commonly used p-median model, which is used to find optimal locations in a network of p supply points that serve n demand points. To evaluate this, we vary both the accuracy (the number of nodes) of the network and the size of the combinatorial problem (p). The investigation is conducted by the means of a case study in a region in Sweden with an asymmetrically distributed population (15,000 weighted demand points), Dalecarlia. To locate 5 to 50 supply points we use the national transport administrations official road network (NVDB). The road network consists of 1.5 million nodes. To find the optimal location we start with 500 candidate nodes in the network and increase the number of candidate nodes in steps up to 67,000 (which is aggregated from the 1.5 million nodes). To find the optimal solution we use a simulated annealing algorithm with adaptive tuning of the temperature. The results show that there is a limited improvement in the optimal solutions when the accuracy in the road network increase and the combinatorial problem (low p) is simple. When the combinatorial problem is complex (large p) the improvements of increasing the accuracy in the road network are much larger. The results also show that choice of the best accuracy of the network depends on the complexity of the combinatorial (varying p) problem.

Ensaio sobre o agente racional: esparadrapos para um paciente terminal?

The Rational Agent model have been a foundational basis for theoretical models such as Economics, Management Science, Artificial Intelligence and Game Theory, mainly by the ¿maximization under constraints¿ principle, e.g. the ¿Expected Utility Models¿, among them, the Subjective Expected Utility (SEU) Theory, from Savage, placed as most influence player over theoretical models we¿ve seen nowadays, even though many other developments have been done, indeed also in non-expected utility theories field. Having the ¿full rationality¿ assumption, going for a less idealistic sight ¿bounded rationality¿ of Simon, or for classical anomalies studies, such as the ¿heuristics and bias¿ analysis by Kahneman e Tversky, ¿Prospect Theory¿ also by Kahneman & Tversky, or Thaler¿s Anomalies, and many others, what we can see now is that Rational Agent Model is a ¿Management by Exceptions¿ example, as for each new anomalies¿s presentation, in sequence, a ¿problem solving¿ development is needed. This work is a theoretical essay, which tries to understand: 1) The rational model as a ¿set of exceptions¿; 2) The actual situation unfeasibility, since once an anomalie is identified, we need it¿s specific solution developed, and since the number of anomalies increases every year, making strongly difficult to manage rational model; 3) That behaviors judged as ¿irrationals¿ or deviated, by the Rational Model, are truly not; 4) That¿s the right moment to emerge a Theory including mental processes used in decision making; and 5) The presentation of an alternative model, based on some cognitive and experimental psychology analysis, such as conscious and uncounscious processes, cognition, intuition, analogy-making, abstract roles, and others. Finally, we present conclusions and future research, that claims for deeper studies in this work¿s themes, for mathematical modelling, and studies about a rational analysis and cognitive models possible integration. .

Essays on decision sciences: exploring cognition, information processing, and complexity

This thesis provides three original contributions to the field of Decision Sciences. The first contribution explores the field of heuristics and biases. New variations of the Cognitive Reflection Test (CRT--a test to measure "the ability or disposition to resist reporting the response that first comes to mind"), are provided. The original CRT (S. Frederick [2005] Journal of Economic Perspectives, v. 19:4, pp.24-42) has items in which the response is immediate--and erroneous. It is shown that by merely varying the numerical parameters of the problems, large deviations in response are found. Not only the final results are affected by the proposed variations, but so is processing fluency. It seems that numbers' magnitudes serve as a cue to activate system-2 type reasoning. The second contribution explores Managerial Algorithmics Theory (M. Moldoveanu [2009] Strategic Management Journal, v. 30, pp. 737-763); an ambitious research program that states that managers display cognitive choices with a "preference towards solving problems of low computational complexity". An empirical test of this hypothesis is conducted, with results showing that this premise is not supported. A number of problems are designed with the intent of testing the predictions from managerial algorithmics against the predictions of cognitive psychology. The results demonstrate (once again) that framing effects profoundly affect choice, and (an original insight) that managers are unable to distinguish computational complexity problem classes. The third contribution explores a new approach to a computationally complex problem in marketing: the shelf space allocation problem (M-H Yang [2001] European Journal of Operational Research, v. 131, pp.107--118). A new representation for a genetic algorithm is developed, and computational experiments demonstrate its feasibility as a practical solution method. These studies lie at the interface of psychology and economics (with bounded rationality and the heuristics and biases programme), psychology, strategy, and computational complexity, and heuristics for computationally hard problems in management science.

Heurísticas na decisão do consumidor

Decisões humanas foram a preocupação central de Herbert Simon em sua vasta produção acadêmica através da qual difundiu sua abordagem de racionalidade limitada pela economia. O reconhecimento do ambiente complexo e dos limites cognitivos do ser humano, levaram-no a propor mecanismos usados para facilitar o processo decisório. Dentre eles, salientou como o mais importante o uso de heurísticas, regras que simplificam a tomada de decisão. Em torno dessa ideia um novo e promissor caminho para o estudo das decisões humanas em economia tem se desenvolvido e inúmeros trabalhos têm se debruçado sobre o assunto. Mais atualmente o tema remete ao trabalho de Daniel Kahneman e Amos Tversky que analisaram comportamentos anômalos em relação à teoria da decisão mais tradicional devido ao uso de heurísticas. Essa abordagem chamada de heuristics and biases ganhou um grande espaço na academia sendo utilizada na análise de muitos eventos empíricos na administração, direito, economia e medicina. A presente tese está estruturada em três artigos. O primeiro artigo trata do uso de heurística na análise do comportamento do agente econômico a partir da contribuição de Simon, Kahneman e Tversky. A apresentação de críticas feitas às duas propostas jogam luz sobre o debate em torno de questões quanto a possível relação entre elas. A partir da análise da literatura, este trabalho propõe uma complementaridade promissora para a economia com a construção de uma teoria comportamental em torno de heurísticas. No segundo artigo, as contribuições de Herbert Simon, Daniel Kahneman e Amos Tversky são utilizadas na análise do comportamento do consumidor. Através de um modelo de simulação baseada em agentes são comparadas cinco heurísticas que representam diferentes regras utilizadas pelo consumidor na decisão de compra: Menor preço de 3, 4 e 5 alternativas pesquisadas, Take-The-Best (TTB), proposta por Gigerenzer e Goldstein, e Time-Is-Money (TIM). Os resultados obtidos se afastam da maximização mas podem ser interpretados como eficientes em função da redução do esforço de pesquisa e do preço obtido. Duas heurísticas mostram grande eficiência: a Menor preço de 3 alternativas e a TTB. A inclusão de custo crescente de pesquisa na análise torna muito eficientes os resultados da TIM e chama a atenção para a relevância da definição de custo na avaliação da eficiência da heurística. O terceiro artigo discute um mecanismo de adaptação do comportamento que objetiva melhorias do resultado obtido com a decisão. Através de simulação baseada em agentes são modelados consumidores de bens homogêneos que utilizam heurísticas para decidir sua compra. É desenvolvida uma heurística, a Take-The-Best adaptaviva (TTBA), que incorpora uma proposta de Simon de um mecanismo de adaptação como reação a performances recentes que pode alterar a aspiração em relação aos resultados futuros e, dessa forma, definir a extensão da pesquisa por alternativas. Os resultados alcançados com o uso da TTBA são comparados a três outras heurísticas: Procura Randômica, Menor de 3 alternativas e Take-The-Best (TTB). A simulação mostrou que a Menor de 3 continua obtendo bons resultados e que a incorporação à TTB do mecanismo de adaptação gera eficiência à TTBA.

Vieses do decisor que podem influenciar sua tomada de decisão

A pesquisa aqui representada teve por objetivo identificar quais vieses podem influenciar os tomadores de decisões estratégicas de organizações brasileiras localizadas no estado do Rio de Janeiro. O trabalho realizado apoiou-se em questionário adaptado de Bazerman (2004). A partir de estudos sobre o cognitivo, este autor apresenta as heurísticas e respectivos vieses, objetos desta dissertação. Os tipos de pesquisas utilizados foram a bibliográfica e a de campo. Esta pesquisa de campo foi realizada com presidentes e diretores executivos do ambiente corporativo. Em suas funções, são eles os responsáveis por decisões estratégicas de empresas brasileiras localizadas no Brasil. A pesquisa revelou que os vieses apresentados por Bazerman (2004) foram identificados nos executivos entrevistados.

A tomada de decisão dos sujeitos em projetos organizacionais e em seu cotidiano pessoal: um estudo no contexto de diferentes nacionalidades

Este trabalho tem por objetivo estudar a tomada de decisão dos indivíduos de diferentes nacionalidades, que atuam na gestão de projetos organizacionais, em sua vida fora do âmbito profissional. Dado que as metodologias existentes na área de gestão de projetos atentam para a necessidade de um processo decisório racional, lógico e objetivo, este estudo pretende explorar até que ponto os sujeitos organizacionais extrapolam este mesmo processo decisório linear, advindo do mundo profissional, para o seu cotidiano. Os estudos acadêmicos ao longo dos anos trataram de discutir esta temática da decisão racional, linear e lógica, os quais foram capazes de refutar esta hipótese com novas perspectivas para o julgamento cognitivo dos humanos. Portanto, além deste trabalho apresentar o campo de estudo da gerência de projetos e seus conceitos, ele também aborda as diversas evoluções teóricas acerca da tomada de decisão ao longo do tempo. A partir da consideração do caráter subjetivo nas teorias de decisão apresentadas, e a limitação cognitiva que muitas vezes se impõe, este estudo busca então explorar as diferentes heurísticas (estratégias simplificadoras, atalhos mentais) de julgamento e seus respectivos vieses cognitivos. As três principais meta-heurísticas, expostas por Tversky e Kahneman em seu trabalho acadêmico de 1974 e também foco deste estudo são, respectivamente: da representatividade, da disponibilidade e da ancoragem e ajustamento. Neste trabalho é realizada uma pesquisa quantitativa com sujeitos organizacionais que trabalham com gestão de projetos, ou que tiveram alguma experiência em algum projeto nas empresas em que trabalham. Ressalta-se que este estudo não se limita ao Brasil, extendendo-se também a outros países com o mesmo público-alvo de pesquisa. Os resultados da pesquisa revelaram que os profissionais que atuam em gestão de projetos estão sujeitos a vieses cognitivos fora do âmbito organizacional, sendo que os brasileiros são os menos propensos a estes vieses, em comparação com as demais nacionalidades estudadas. Também revelou-se que o tempo de experiência profissional não contribui de modo significante para uma tomada de decisão mais racional e lógica no cotidiano pessoal.