A hybrid algorithm combining metaheuristic with Monte Carlo simulation for solving the Stochastic Flow Shop problem

In this paper, a hybrid simulation-based algorithm is proposed for the StochasticFlow Shop Problem. The main idea of the methodology is to transform the stochastic problem into a deterministic problem and then apply simulation to the latter. In order to achieve this goal, we rely on Monte Carlo Simulation and an adapted version of a deterministic heuristic. This approach aims to provide flexibility and simplicity due to the fact that it is not constrained by any previous assumption and relies in well-tested heuristics.

A hybrid algorithm combining metaheuristic with Monte Carlo simulation for solving the Stochastic Flow Shop problem

In this paper, a hybrid simulation-based algorithm is proposed for the StochasticFlow Shop Problem. The main idea of the methodology is to transform the stochastic problem into a deterministic problem and then apply simulation to the latter. In order to achieve this goal, we rely on Monte Carlo Simulation and an adapted version of a deterministic heuristic. This approach aims to provide flexibility and simplicity due to the fact that it is not constrained by any previous assumption and relies in well-tested heuristics.

Local optima networks of hard combinatorial landscapes

Combinatorial optimization involves finding an optimal solution in a finite set of options; many everyday life problems are of this kind. However, the number of options grows exponentially with the size of the problem, such that an exhaustive search for the best solution is practically infeasible beyond a certain problem size. When efficient algorithms are not available, a practical approach to obtain an approximate solution to the problem at hand, is to start with an educated guess and gradually refine it until we have a good-enough solution. Roughly speaking, this is how local search heuristics work. These stochastic algorithms navigate the problem search space by iteratively turning the current solution into new candidate solutions, guiding the search towards better solutions. The search performance, therefore, depends on structural aspects of the search space, which in turn depend on the move operator being used to modify solutions. A common way to characterize the search space of a problem is through the study of its fitness landscape, a mathematical object comprising the space of all possible solutions, their value with respect to the optimization objective, and a relationship of neighborhood defined by the move operator. The landscape metaphor is used to explain the search dynamics as a sort of potential function. The concept is indeed similar to that of potential energy surfaces in physical chemistry. Borrowing ideas from that field, we propose to extend to combinatorial landscapes the notion of the inherent network formed by energy minima in energy landscapes. In our case, energy minima are the local optima of the combinatorial problem, and we explore several definitions for the network edges. At first, we perform an exhaustive sampling of local optima basins of attraction, and define weighted transitions between basins by accounting for all the possible ways of crossing the basins frontier via one random move. Then, we reduce the computational burden by only counting the chances of escaping a given basin via random kick moves that start at the local optimum. Finally, we approximate network edges from the search trajectory of simple search heuristics, mining the frequency and inter-arrival time with which the heuristic visits local optima. Through these methodologies, we build a weighted directed graph that provides a synthetic view of the whole landscape, and that we can characterize using the tools of complex networks science. We argue that the network characterization can advance our understanding of the structural and dynamical properties of hard combinatorial landscapes. We apply our approach to prototypical problems such as the Quadratic Assignment Problem, the NK model of rugged landscapes, and the Permutation Flow-shop Scheduling Problem. We show that some network metrics can differentiate problem classes, correlate with problem non-linearity, and predict problem hardness as measured from the performances of trajectory-based local search heuristics.

Repurposing Social Tagging Data for Extraction of Domain-level Concepts

The World Wide Web, the world¿s largest resource for information, has evolved from organizing information using controlled, top-down taxonomies to a bottom up approach that emphasizes assigning meaning to data via mechanisms such as the Social Web (Web 2.0). Tagging adds meta-data, (weak semantics) to the content available on the web. This research investigates the potential for repurposing this layer of meta-data. We propose a multi-phase approach that exploits user-defined tags to identify and extract domain-level concepts. We operationalize this approach and assess its feasibility by application to a publicly available tag repository. The paper describes insights gained from implementing and applying the heuristics contained in the approach, as well as challenges and implications of repurposing tags for extraction of domain-level concepts.

Programación de pedidos en una máquina de la vida real con tiempos de preparación dependientes de la secuencia

En este trabajo se evalúan algoritmos heurísticos de exploración de entornos(AED, ANED, SA, TS, GA y GRASP) en la programación de pedidos en unamáquina de la vida real, con el objetivo de minimizar la suma de retrasos . Elcaso estudiado se diferencia de los problemas convencionales en que lostiempos de preparación de las operaciones están separados de los tiempos deprocesamiento y son dependientes de la secuencia. Los resultadoscomputacionales revelan que la Búsqueda Tabú funciona mejor que los otrosalgoritmos aplicados.

Generating highly balanced sudoku problems as hard problems

Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold interesting area, in fact. On the one side Sudoku problems, being a variant of Gerechte Designs and Latin Squares, are being actively used for experimental design, as in [8, 44, 39, 9]. On the other hand, Sudoku problems, as simple as they seem, are really hard structured combinatorial search problems, and thanks to their characteristics and behavior, they can be used as benchmark problems for refining and testing solving algorithms and approaches. Also, thanks to their high inner structure, their study can contribute more than studies of random problems to our goal of solving real-world problems and applications and understanding problem characteristics that make them hard to solve. In this work we use two techniques for solving and modeling Sudoku problems, namely, Constraint Satisfaction Problem (CSP) and Satisfiability Problem (SAT) approaches. To this effect we define the Generalized Sudoku Problem (GSP), where regions can be of rectangular shape, problems can be of any order, and solution existence is not guaranteed. With respect to the worst-case complexity, we prove that GSP with block regions of m rows and n columns with m = n is NP-complete. For studying the empirical hardness of GSP, we define a series of instance generators, that differ in the balancing level they guarantee between the constraints of the problem, by finely controlling how the holes are distributed in the cells of the GSP. Experimentally, we show that the more balanced are the constraints, the higher the complexity of solving the GSP instances, and that GSP is harder than the Quasigroup Completion Problem (QCP), a problem generalized by GSP. Finally, we provide a study of the correlation between backbone variables – variables with the same value in all the solutions of an instance– and hardness of GSP.

An efficient solver for weighted Max-SAT

We present a new branch and bound algorithm for weighted Max-SAT, called Lazy which incorporates original data structures and inference rules, as well as a lower bound of better quality. We provide experimental evidence that our solver is very competitive and outperforms some of the best performing Max-SAT and weighted Max-SAT solvers on a wide range of instances.

How hard is a commercial puzzle: the eternity II challenge

Recently, edge matching puzzles, an NP-complete problem, have received, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.

Edge matching puzzles as hard SAT/CSP benchmarks

Recently, edge matching puzzles, an NP-complete problem, have rececived, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.

Säähavaintoaseman käytettävyyteen vaikuttavat tekijät

Diplomityön tarkoituksena on tuoda esiin tuotteen käytettävyyden kehittämisen tärkeyden osana uuden tuotteen kehittämistä. Tavoitteena on analysoida liikuteltavan säähavaintoaseman käytettävyyden nykytilanne ja löytää mahdollisia käytettävyyden kehittämisalueita. Työssä käydään läpi eri käytettävyyden määritteitä ja käytettävyyden testausta. Käytettävyyden tarkastelunäkökulmia ovat asiakkaiden vaatimukset tuotteelle ja yleinen käytettävyyden subjektiivinen analysointi perustuen hyväksi tunnettuihin suunnittelun perusteisiin, heuristiikkoihin. Säähavaintoasemat ovat valittu eri segmenteistä, jotta voidaan tutkia säähavaintokonseptia, jollaista ei tänäpäivänä vielä ole ja löytää käyttäjien mahdollisia tulevaisuuden tarpeita. Näin saadaan myös laaja näkökulma eri segmenteille suunnattujen säähavaintoasemien käytettävyydestä.Käytettävyyttä voidaan pitää tehokkaana myyntiargumenttina. Tämä edellyttää läheistä yhteistyötä käyttäjien kanssa ja tietoa tuotteen käyttöympäristöstä. Tuotteen tulisi tutkimusten perusteella olla yksinkertainen toiminnoiltaan ja luotettava, jotta se vastasi käyttäjien tarpeita. Työssä osoitetaan myös useita käytettävyyden kehittämisalueita, joita kehittämällä voidaan vastata käyttäjien tarpeita. Tutkimuksen perusteella tutkittavat säähavaintoasemat voisivat olla käyttäjäystävällisempiä ja vastata paremmin käyttäjän tarpeita.Jatkotoimenpiteinä ehdotetaan esille tulleiden säähavaintoseman käytettävyyden osa-alueiden tarkempaa kartoittamista ja erityisesti käyttäjien tomintaympäristöjen ymmärtämistä. Näin varmistetaan käyttäjäystävällisyyden huomioiminen aikaisessa tuotesuunnitteluprosessin vaiheessa. Tuotteen käytettävyyden huomioiminen aikaisessa suunnitteluvaiheessa on yleensä myös edullista yhtiölleDiplomityön tarkoituksena on tuoda esiin tuotteen käytettävyyden kehittämisen tärkeyden osana uuden tuotteen kehittämistä. Tavoitteena on analysoida liikuteltavan säähavaintoaseman käytettävyyden nykytilanne ja löytää mahdollisia käytettävyyden kehittämisalueita. Työssä käydään läpi eri käytettävyyden määritteitä ja käytettävyyden testausta. Käytettävyyden tarkastelunäkökulmia ovat asiakkaiden vaatimukset tuotteelle ja yleinen käytettävyyden subjektiivinen analysointi perustuen hyväksi tunnettuihin suunnittelun perusteisiin, heuristiikkoihin. Säähavaintoasemat ovat valittu eri segmenteistä, jotta voidaan tutkia säähavaintokonseptia, jollaista ei tänäpäivänä vielä ole ja löytää käyttäjien mahdollisia tulevaisuuden tarpeita. Näin saadaan myös laaja näkökulma eri segmenteille suunnattujen säähavaintoasemien käytettävyydestä.Käytettävyyttä voidaan pitää tehokkaana myyntiargumenttina. Tämä edellyttää läheistä yhteistyötä käyttäjien kanssa ja tietoa tuotteen käyttöympäristöstä. Tuotteen tulisi tutkimusten perusteella olla yksinkertainen toiminnoiltaan ja luotettava, jotta se vastasi käyttäjien tarpeita. Työssä osoitetaan myös useita käytettävyyden kehittämisalueita, joita kehittämällä voidaan vastata käyttäjien tarpeita. Tutkimuksen perusteella tutkittavat säähavaintoasemat voisivat olla käyttäjäystävällisempiä ja vastata paremmin käyttäjän tarpeita.Jatkotoimenpiteinä ehdotetaan esille tulleiden säähavaintoseman käytettävyyden osa-alueiden tarkempaa kartoittamista ja erityisesti käyttäjien tomintaympäristöjen ymmärtämistä. Näin varmistetaan käyttäjäystävällisyyden huomioiminen aikaisessa tuotesuunnitteluprosessin vaiheessa. Tuotteen käytettävyyden huomioiminen aikaisessa suunnitteluvaiheessa on yleensä myös edullista yhtiölle

The role of causal links in performance measurement models

Abstract Purpose: Several well-known managerial accounting performance measurement models rely on causal assumptions. Whilst users of the models express satisfaction and link them with improved organizational performance, academic research, of the realworld applications, shows few reliable statistical associations. This paper provides a discussion on the"problematic" of causality in a performance measurement setting. Design/methodology/approach: This is a conceptual study based on an analysis and synthesis of the literature from managerial accounting, organizational theory, strategic management and social scientific causal modelling. Findings: The analysis indicates that dynamic, complex and uncertain environments may challenge any reliance upon valid causal models. Due to cognitive limitations and judgmental biases, managers may fail to trace correct cause-and-effect understanding of the value creation in their organizations. However, even lacking this validity, causal models can support strategic learning and perform as organizational guides if they are able to mobilize managerial action. Research limitations/implications: Future research should highlight the characteristics necessary for elaboration of convincing and appealing causal models and the social process of their construction. Practical implications: Managers of organizations using causal models should be clear on the purposes of their particular models and their limitations. In particular, difficulties are observed in specifying detailed cause and effect relations and their potential for communicating and directing attention. They should therefore construct their models to suit the particular purpose envisaged. Originality/value: This paper provides an interdisciplinary and holistic view on the issue of causality in managerial accounting models.

Populating ACT-R's Declarative Memory with Internet Statistics

Decision situations are often characterized by uncertainty: we do not know the values of the different options on all attributes and have to rely on information stored in our memory to decide. Several strategies have been proposed to describe how people make inferences based on knowledge used as cues. The present research shows how declarative memory of ACT-R models could be populated based on internet statistics. This will allow to simulate the performance of decision strategies operating on declarative knowledge based on occurrences and co-occurrences of objects and cues in the environment.

Evolutionary Games in Networked Populations: Models and Experiments

Cooperation and coordination are desirable behaviors that are fundamental for the harmonious development of society. People need to rely on cooperation with other individuals in many aspects of everyday life, such as teamwork and economic exchange in anonymous markets. However, cooperation may easily fall prey to exploitation by selfish individuals who only care about short- term gain. For cooperation to evolve, specific conditions and mechanisms are required, such as kinship, direct and indirect reciprocity through repeated interactions, or external interventions such as punishment. In this dissertation we investigate the effect of the network structure of the population on the evolution of cooperation and coordination. We consider several kinds of static and dynamical network topologies, such as Baraba´si-Albert, social network models and spatial networks. We perform numerical simulations and laboratory experiments using the Prisoner's Dilemma and co- ordination games in order to contrast human behavior with theoretical results. We show by numerical simulations that even a moderate amount of random noise on the Baraba´si-Albert scale-free network links causes a significant loss of cooperation, to the point that cooperation almost vanishes altogether in the Prisoner's Dilemma when the noise rate is high enough. Moreover, when we consider fixed social-like networks we find that current models of social networks may allow cooperation to emerge and to be robust at least as much as in scale-free networks. In the framework of spatial networks, we investigate whether cooperation can evolve and be stable when agents move randomly or performing Le´vy flights in a continuous space. We also consider discrete space adopting purposeful mobility and binary birth-death process to dis- cover emergent cooperative patterns. The fundamental result is that cooperation may be enhanced when this migration is opportunistic or even when agents follow very simple heuristics. In the experimental laboratory, we investigate the issue of social coordination between indi- viduals located on networks of contacts. In contrast to simulations, we find that human players dynamics do not converge to the efficient outcome more often in a social-like network than in a random network. In another experiment, we study the behavior of people who play a pure co- ordination game in a spatial environment in which they can move around and when changing convention is costly. We find that each convention forms homogeneous clusters and is adopted by approximately half of the individuals. When we provide them with global information, i.e., the number of subjects currently adopting one of the conventions, global consensus is reached in most, but not all, cases. Our results allow us to extract the heuristics used by the participants and to build a numerical simulation model that agrees very well with the experiments. Our findings have important implications for policymakers intending to promote specific, desired behaviors in a mobile population. Furthermore, we carry out an experiment with human subjects playing the Prisoner's Dilemma game in a diluted grid where people are able to move around. In contrast to previous results on purposeful rewiring in relational networks, we find no noticeable effect of mobility in space on the level of cooperation. Clusters of cooperators form momentarily but in a few rounds they dissolve as cooperators at the boundaries stop tolerating being cheated upon. Our results highlight the difficulties that mobile agents have to establish a cooperative environment in a spatial setting without a device such as reputation or the possibility of retaliation. i.e. punishment. Finally, we test experimentally the evolution of cooperation in social networks taking into ac- count a setting where we allow people to make or break links at their will. In this work we give particular attention to whether information on an individual's actions is freely available to poten- tial partners or not. Studying the role of information is relevant as information on other people's actions is often not available for free: a recruiting firm may need to call a job candidate's refer- ences, a bank may need to find out about the credit history of a new client, etc. We find that people cooperate almost fully when information on their actions is freely available to their potential part- ners. Cooperation is less likely, however, if people have to pay about half of what they gain from cooperating with a cooperator. Cooperation declines even further if people have to pay a cost that is almost equivalent to the gain from cooperating with a cooperator. Thus, costly information on potential neighbors' actions can undermine the incentive to cooperate in dynamical networks.

Komposiittivaipan moderni optimisuunnittelu ja toteutus

Tavoitteena tällä tutkimuksella on soveltaa modernin optimisuunnittelun keinoja komposiittimuovisen nestesäiliön lieriömäisen vaipparakenteen suunnittelemiseksi optimaalisen tyydyttäviksi valmistustekniikan ja kustannusten kannalta. Kuormituksia on kahdenlaisia. Säiliön sisällä on neste, joka tuottaa hydrostaattisen painekuorman ja järjestelmään kytketty puhallin tuottaa ulkoisen ylipaineen. Säiliöt ovat pystysäiliöitä ja ne tukeutuvat alustaan suoran pohjalaatan avulla. FEM- malleissa kuoren alaosat ovat jäykästi kiinnitettyjä ja yläosissa säteensuuntaiset siirtymät ovat estettyjä. Materiaaleiksi kuoreen on valittu kahdella eri menetelmällä lujitetut komposiittimateriaalit. Kantavan kerroksen toimintona on kantaa kuormat. Sulkukerros toimii korroosiosuojana ja sen lujuus on kantavaa kerrosta pienempi. Keinoina käytetään ensin innovatiivista suunnittelua optimaalisten lähtövaihtoehtojen ideoimiseksi ja valitsemiseksi jatkokehittelyä varten. Tavoitteena on asiakkaan tyytyväisyyden maksimointi huomioiden tuotteen kustannukset ja kesto. Yhtenä suunnittelun keinona on käytetty kuoriteoriaa ja komposiittien materiaalimalleja. Kestoehtoina on sovellettu komposiiteille soveltuvia kriteerejä. Toisena keinona käytetään FEM-laskentaa. Elementtityypiksi on valittu kaksiulotteinen kuorielementti, jossa on ortotrooppisen ainemallin mukaiset materiaaliominaisuudet. Jännitystuloksien merkittävyys keston kannalta selvitettiin Tsai-Hillin kriteerillä. Tuloksina saatiin ensin innovoitua rakenteelle kaksi päävaihtoehtoa, joita alettiin optimoida. Valitussa ratkaisussa on huomioitu kokonaisuus ja eri yksityiskohdat, kuten paino, jäykisteet kustannustehokkuus, valmistusnopeus, laatu, hävikit, päästöt, lujuus ja kilpailukykyinen myyntihinta. Yhteenvetona voidaan todeta, että käytetyt keinot ovat hyvin tehokkaita ja niillä voidaan suunnitella ja toteuttaa komposiittirakenteita, jotka tyydyttävät optimaalisesti loppukäyttäjän teknis- taloudelliset vaatimukset. Lisäksi tulokset osoittavat, että standardin ja FEM-laskennan ennustukset ovat lähellä toisiaan sylinterimäisillä kuoriosilla, mutta standardit suosittavat suurempia mittoja itse jäykisteille.

A Method for Estimating Short-term Profitability, Case Stora Enso Packaging Boards

Tutkimuksen tavoitteena oli rakentaa case yritykselle malli lyhyen aikavälin kannattavuuden estimointia varten. Tutkimusmetodi on konstruktiivinen, ja malli kehitettiin laskentaihmisten avustuksella. Teoriaosassa käytiin kirjallisuuskatsauksen avulla läpi kannattavuutta, budjetointia sekä itse ennustamista. Teoriaosassa pyrittiin löytämään sellaisia menetelmiä, joita voitaisiin käyttää lyhyen aikavälin kannattavuuden estimoinnissa. Rakennettavalle mallille asetettujen vaatimusten mukaan menetelmäksi valittiin harkintaan perustuva menetelmä (judgmental). Tutkimuksen mukaan kannattavuuteen vaikuttaa myyntihinta ja –määrä, tuotanto, raaka-aineiden hinnat ja varaston muutos. Rakennettu malli toimii kohdeyrityksessä kohtalaisen hyvin ja huomattavaa on se, että eri tehtaiden ja eri koneiden väliset erot saattavat olla kohtuullisen suuret. Nämä erot johtuvat pääasiassa tehtaan koosta ja mallien erilaisuudesta. Mallin käytännön toimivuus tulee kuitenkin parhaiten selville silloin, kun se on laskentaihmisten käytössä. Ennustamiseen liittyy kuitenkin aina omat ongelmansa ja uudetkaan menetelmät eivät välttämättä poista näitä ongelmia.