Heuristic algorithm for computing reversal distance with multigene families via binary integer programming

Hannenhalli and Pevzner developed the first polynomial-time algorithm for the combinatorial problem of sorting of signed genomic data. Their algorithm solves the minimum number of reversals required for rearranging a genome to another when gene duplication is nonexisting. In this paper, we show how to extend the Hannenhalli-Pevzner approach to genomes with multigene families. We propose a new heuristic algorithm to compute the reversal distance between two genomes with multigene families via the concept of binary integer programming without removing gene duplicates. The experimental results on simulated and real biological data demonstrate that the proposed algorithm is able to find the reversal distance accurately. ©2005 IEEE

An integrated scheduling problem of PCB components on sequential pick-and-place machines:mathematical models and heuristic solutions

This paper formulates several mathematical models for determining the optimal sequence of component placements and assignment of component types to feeders simultaneously or the integrated scheduling problem for a type of surface mount technology placement machines, called the sequential pick-andplace (PAP) machine. A PAP machine has multiple stationary feeders storing components, a stationary working table holding a printed circuit board (PCB), and a movable placement head to pick up components from feeders and place them to a board. The objective of integrated problem is to minimize the total distance traveled by the placement head. Two integer nonlinear programming models are formulated first. Then, each of them is equivalently converted into an integer linear type. The models for the integrated problem are verified by two commercial packages. In addition, a hybrid genetic algorithm previously developed by the authors is adopted to solve the models. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total traveling distance.

A heuristic approach for component scheduling on a high-speed PCB assembly machine

The collect-and-place machine is one of the most widely used placement machines for assembling electronic components on the printed circuit boards (PCBs). Nevertheless, the number of researches concerning the optimisation of the machine performance is very few. This motivates us to study the component scheduling problem for this type of machine with the objective of minimising the total assembly time. The component scheduling problem is an integration of the component sequencing problem, that is, the sequencing of component placements; and the feeder arrangement problem, that is, the assignment of component types to feeders. To solve the component scheduling problem efficiently, a hybrid genetic algorithm is developed in this paper. A numerical example is used to compare the performance of the algorithm with different component grouping approaches and different population sizes.

Majority versus minority influence:when, not whether, source status instigates heuristic or systematic processing

Two experiments investigated the extent of message processing of a persuasive communication proposed by either a numerical majority or minority. Both experiments crossed source status (majority versus minority) with message quality (strong versus weak arguments) to determine which source condition is associated with systematic processing. The first experiment showed a reliable difference between strong and weak messages, indicating systematic processing had occurred, for a minority irrespective of message direction (pro- versus counter-attitudinal), but not for a majority. The second experiment showed that message outcome moderates when a majority or a minority leads to systematic processing. When the message argued for a negative personal outcome, there was systematic processing only for the majority source; but when the message did not argue for a negative personal outcome, there was systematic processing only for the minority source. Thus one key moderator of whether a majority or minority source leads to message processing is whether the topic induces defensive processing motivated by self-interest.

Systematic and heuristic processing of majority and minority-endorsed messages:the effects of varying outcome relevance and levels of orientation on attitude and message processing

Two experiments investigated the conditions under which majority and minority sources instigate systematic processing of their messages. Both experiments crossed source status (majority vs. minority) with message quality (strong vs. weak arguments). In each experiment, message elaboration was manipulated by varying either motivational (outcome relevance, Experiment 1) or cognitive (orientating tasks, Experiment 2) factors. The results showed that when either motivational or cognitive factors encouraged low message elaboration, there was heuristic acceptance of the majority position without detailed message processing. When the level of message elaboration was intermediate, there was message processing only for the minority source. Finally, when message elaboration was high, there was message processing for both source conditions. These results show that majority and minority influence is sensitive to motivational and cognitive factors that constrain or enhance message elaboration and that both sources can lead to systematic processing under specific circumstances. © 2007 by the Society for Personality and Social Psychology, Inc.

Rapid heuristic projection on simplicial cones

A very fast heuristic iterative method of projection on simplicial cones is presented. It consists in solving two linear systems at each step of the iteration. The extensive experiments indicate that the method furnishes the exact solution in more then 99.7 percent of the cases. The average number of steps is 5.67 (we have not found any examples which required more than 13 steps) and the relative number of steps with respect to the dimension decreases dramatically. Roughly speaking, for high enough dimensions the absolute number of steps is independent of the dimension.

Implementation of a Heuristic Method of Decomposition of Partial Boolean Functions

An original heuristic algorithm of sequential two-block decomposition of partial Boolean functions is researched. The key combinatorial task is considered: finding of suitable partition on the set of arguments, i. e. such one, on which the function is separable. The search for suitable partition is essentially accelerated by preliminary detection of its traces. Within the framework of the experimental system the efficiency of the algorithm is evaluated, the boundaries of its practical application are determined.

A new VRPPD model and a hybrid heuristic solution approach for e-tailing

We analyze a business model for e-supermarkets to enable multi-product sourcing capacity through co-opetition (collaborative competition). The logistics aspect of our approach is to design and execute a network system where “premium” goods are acquired from vendors at multiple locations in the supply network and delivered to customers. Our specific goals are to: (i) investigate the role of premium product offerings in creating critical mass and profit; (ii) develop a model for the multiple-pickup single-delivery vehicle routing problem in the presence of multiple vendors; and (iii) propose a hybrid solution approach. To solve the problem introduced in this paper, we develop a hybrid metaheuristic approach that uses a Genetic Algorithm for vendor selection and allocation, and a modified savings algorithm for the capacitated VRP with multiple pickup, single delivery and time windows (CVRPMPDTW). The proposed Genetic Algorithm guides the search for optimal vendor pickup location decisions, and for each generated solution in the genetic population, a corresponding CVRPMPDTW is solved using the savings algorithm. We validate our solution approach against published VRPTW solutions and also test our algorithm with Solomon instances modified for CVRPMPDTW.

Women’s adaptation to STEM domains promotes resilience and a lesser reliance on heuristic thinking

Experiences that compel people to challenge social stereotypes can promote enhanced cognitive flexibility on a range of judgmental domains. Women in STEM (science, technology, engineering, and math) fields are chronically exposed to such experiences and may therefore also demonstrate these benefits. Two studies examined the differential effects of counterstereotypical experiences on women from STEM and non-STEM fields. Results showed that imagining or recollecting these experiences led women from STEM fields to exhibit a lesser reliance on heuristic thinking compared to women from non-STEM fields, and this difference was mediated by self-perceived resilience to the negative impact of gender stereotyping. Implications for psychologists’ and educators’ understanding of the relationship between counterstereotypical experiences and heuristic thinking are discussed.

Some extended psychological benefits of challenging social stereotypes:decreased dehumanization and a reduced reliance on heuristic thinking

One way to promote equality is to encourage people to generate counterstereotypic role models. In two experiments, we demonstrate that such interventions have much broader benefits than previously thoughtreducing a reliance on heuristic thinking and decreasing tendencies to dehumanize outgroups. In Experiment 1, participants who thought about a gender counterstereotype (e.g., a female mechanic) demonstrated a generalized decrease in dehumanization towards a range of unrelated target groups (including asylum seekers and the homeless). In Experiment 2 we replicated these findings using alternative targets and measures of dehumanization. Furthermore, we found the effect was mediated by a reduced reliance on heuristic thinking. The findings suggest educational initiatives that aim to challenge social stereotypes may not only have societal benefits (generalized tolerance), but also tangible benefits for individuals (enhanced cognitive flexibility).

An order batching and processing heuristic to address aisle congestion in a manual order picking warehouse with order due dates

A heuristic for batching orders in a manual order-picking warehouse has been developed. It prioritizes orders based on due time to prevent mixing of orders of different priority levels. The order density of aisles criterion is used to form batches. It also determines the number of pickers required and assigns batches to pickers such that there is a uniform workload per unit of time. The effectiveness of the heuristic was studied by observing computational time and aisle congestion for various numbers of total orders and number of orders that form a batch. An initial heuristic performed well for small number of orders, but for larger number of orders, a partitioning technique is computationally more efficient, needing only minutes to solve for thousands of orders, while preserving 90% of the batch quality obtained with the original heuristic. Comparative studies between the heuristic and other published heuristics are needed. ^

Intuition and its component parts in the heuristic processing of deception detection: Hunch, *evidence, and reliance on intuitive efficacy

Rated trust in intuitive efficacy (measured as trust, belief, use, accuracy and weighting of intuition) was investigated as a predictor of self-designated use of intuitive (hunch and hunch plus evidential belief) vs. deliberative (evidential belief and evidential belief plus hunch) deception detection judgments and actual accuracy. Twenty-nine student participants were filmed as they made true and deceptive statements about their everyday activities on a given evening (last Friday night), and college students (N=238) judged 20 (10=true, 10=deceptive) of these filmed statements as truthful or deceptive. Participants provided ratings of reliance on hunches vs. evidential belief, confidence in film judgments, intuitive efficacy, accuracy in deception detection, reliance on cues to deception, and experiences with intuition. Generalized estimated equation modeling using binary logistics demonstrated accuracy in identifying true vs. deceptive statements was predicted by film number, hunch-evidence ratings, weighting of intuition, and total cues cited. Weighting of intuition was predictive of accuracy across participants, with higher weighting predictive of higher accuracy in general. Participants who cited evidential belief plus hunch and moderate to high weighting incorrectly reversed their true vs. deceptive judgments. Accuracy for true statements was higher for hunches and hunch plus evidential belief, whereas accuracy for deceptive statements was higher for evidential belief Accuracy for participants who relied on evidential belief plus hunch was at chance. Subjective experiences underlying judgments differed by participant and type of film viewed (true vs. deceptive) and were predicted by hunch-evidence ratings, trust, use, intuitive accuracy, and total cues cited. Trust predicted increases in judging films to be true, whereas use and accuracy predicted increases in judging films as deceptive; none were predictive of accuracy. Increased number of cues cited predicted judgments of deception, whereas decreased number of cues cited predicted truth. The study concluded that participants have the capacity to self-define their judgments as subjectively vs. deliberately based, provide subjective assessments of the influence of intuitive vs. objective information on their judgments, and can apply this self-knowledge, through effective weighting of intuition vs. other types of information, in making accurate judgments of true and deceptive everyday statements.

A heuristic algorithm to generate test program sequences for moving probe electronic test equipment

The electronics industry, is experiencing two trends one of which is the drive towards miniaturization of electronic products. The in-circuit testing predominantly used for continuity testing of printed circuit boards (PCB) can no longer meet the demands of smaller size circuits. This has lead to the development of moving probe testing equipment. Moving Probe Test opens up the opportunity to test PCBs where the test points are on a small pitch (distance between points). However, since the test uses probes that move sequentially to perform the test, the total test time is much greater than traditional in-circuit test. While significant effort has concentrated on the equipment design and development, little work has examined algorithms for efficient test sequencing. The test sequence has the greatest impact on total test time, which will determine the production cycle time of the product. Minimizing total test time is a NP-hard problem similar to the traveling salesman problem, except with two traveling salesmen that must coordinate their movements. The main goal of this thesis was to develop a heuristic algorithm to minimize the Flying Probe test time and evaluate the algorithm against a "Nearest Neighbor" algorithm. The algorithm was implemented with Visual Basic and MS Access database. The algorithm was evaluated with actual PCB test data taken from Industry. A statistical analysis with 95% C.C. was performed to test the hypothesis that the proposed algorithm finds a sequence which has a total test time less than the total test time found by the "Nearest Neighbor" approach. Findings demonstrated that the proposed heuristic algorithm reduces the total test time of the test and, therefore, production cycle time can be reduced through proper sequencing.

A simulation-based heuristic for fleet assignment

Integer programming, simulation, and rules of thumb have been integrated to develop a simulation-based heuristic for short-term assignment of fleet in the car rental industry. It generates a plan for car movements, and a set of booking limits to produce high revenue for a given planning horizon. Three different scenarios were used to validate the heuristic. The heuristic's mean revenue was significant higher than the historical ones, in all three scenarios. Time to run the heuristic for each experiment was within the time limits of three hours set for the decision making process even though it is not fully automated. These findings demonstrated that the heuristic provides better plans (plans that yield higher profit) for the dynamic allocation of fleet than the historical decision processes. Another contribution of this effort is the integration of IP and rules of thumb to search for better performance under stochastic conditions.