PCB assembly line assignment:a genetic algorithm approach

Purpose – This paper sets out to study a production-planning problem for printed circuit board (PCB) assembly. A PCB assembly company may have a number of assembly lines for production of several product types in large volume. Design/methodology/approach – Pure integer linear programming models are formulated for assigning the product types to assembly lines, which is the line assignment problem, with the objective of minimizing the total production cost. In this approach, unrealistic assignment, which was suffered by previous researchers, is avoided by incorporating several constraints into the model. In this paper, a genetic algorithm is developed to solve the line assignment problem. Findings – The procedure of the genetic algorithm to the problem and a numerical example for illustrating the models are provided. It is also proved that the algorithm is effective and efficient in dealing with the problem. Originality/value – This paper studies the line assignment problem arising in a PCB manufacturing company in which the production volume is high.

The influence of memory in a threshold model for distributed task assignment

A nature inspired decentralised multi-agent algorithm is proposed to solve a problem of distributed task selection in which cities produce and store batches of different mail types. Agents must collect and process the mail batches, without a priori knowledge of the available mail at the cities or inter-agent communication. In order to process a different mail type than the previous one, agents must undergo a change-over during which it remains inactive. We propose a threshold based algorithm in order to maximise the overall efficiency (the average amount of mail collected). We show that memory, i.e. the possibility for agents to develop preferences for certain cities, not only leads to emergent cooperation between agents, but also to a significant increase in efficiency (above the theoretical upper limit for any memoryless algorithm), and we systematically investigate the influence of the various model parameters. Finally, we demonstrate the flexibility of the algorithm to changes in circumstances, and its excellent scalability.

An alternative formulation for the fuzzy assignment problem

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit measured as crisp. However, in many real applications, costs are not deterministic numbers. This paper develops a procedure based on Data Envelopment Analysis method to solve the assignment problems with fuzzy costs or fuzzy profits for each possible assignment. It aims to obtain the points with maximum membership values for the fuzzy parameters while maximizing the profit or minimizing the assignment cost. In this method, a discrete approach is presented to rank the fuzzy numbers first. Then, corresponding to each fuzzy number, we introduce a crisp number using the efficiency concept. A numerical example is used to illustrate the usefulness of this new method. © 2012 Operational Research Society Ltd. All rights reserved.

Molecular identification of 26 syntaxin genes and their assignment to the different trafficking pathways in Paramecium

SNARE proteins have been classified as vesicular (v)- and target (t)-SNAREs and play a central role in the various membrane interactions in eukaryotic cells. Based on the Paramecium genome project, we have identified a multigene family of at least 26 members encoding the t-SNARE syntaxin (PtSyx) that can be grouped into 15 subfamilies. Paramecium syntaxins match the classical build-up of syntaxins, being 'tail-anchored' membrane proteins with an N-terminal cytoplasmic domain and a membrane-bound single C-terminal hydrophobic domain. The membrane anchor is preceded by a conserved SNARE domain of approximately 60 amino acids that is supposed to participate in SNARE complex assembly. In a phylogenetic analysis, most of the Paramecium syntaxin genes were found to cluster in groups together with those from other organisms in a pathway-specific manner, allowing an assignment to different compartments in a homology-dependent way. However, some of them seem to have no counterparts in metazoans. In another approach, we fused one representative member of each of the syntaxin isoforms to green fluorescent protein and assessed the in vivo localization, which was further supported by immunolocalization of some syntaxins. This allowed us to assign syntaxins to all important trafficking pathways in Paramecium.

Genetic Algorithm Approach for Solving the Task Assignment Problem

This research was partially supported by the Serbian Ministry of Science and Ecology under project 144007. The authors are grateful to Ivana Ljubić for help in testing and to Vladimir Filipović for useful suggestions and comments.

Solving the Task Assignment Problem with a Variable Neighborhood Search

In this paper a variable neighborhood search (VNS) approach for the task assignment problem (TAP) is considered. An appropriate neighborhood scheme along with a shaking operator and local search procedure are constructed specifically for this problem. The computational results are presented for the instances from the literature, and compared to optimal solutions obtained by the CPLEX solver and heuristic solutions generated by the genetic algorithm. It can be seen that the proposed VNS approach reaches all optimal solutions in a quite short amount of computational time.

On axiomatizations of the Shapley value for assignment games

We consider the problem of axiomatizing the Shapley value on the class of assignment games. We first show that several axiomatizations of the Shapley value on the class of all TU-games do not characterize this solution on the class of assignment games by providing alternative solutions that satisfy these axioms. However, when considering an assignment game as a communication graph game where the game is simply the assignment game and the graph is a corresponding bipartite graph buyers are connected with sellers only, we show that Myerson's component efficiency and fairness axioms do characterize the Shapley value on the class of assignment games. Moreover, these two axioms have a natural interpretation for assignment games. Component efficiency yields submarket efficiency stating that the sum of the payoffs of all players in a submarket equals the worth of that submarket, where a submarket is a set of buyers and sellers such that all buyers in this set have zero valuation for the goods offered by the sellers outside the set, and all buyers outside the set have zero valuations for the goods offered by sellers inside the set. Fairness of the graph game solution boils down to valuation fairness stating that only changing the valuation of one particular buyer for the good offered by a particular seller changes the payoffs of this buyer and seller by the same amount.

Stable sets in one-seller assignment games

We consider von Neumann -- Morgenstern stable sets in assignment games with one seller and many buyers. We prove that a set of imputations is a stable set if and only if it is the graph of a certain type of continuous and monotone function. This characterization enables us to interpret the standards of behavior encompassed by the various stable sets as possible outcomes of well-known auction procedures when groups of buyers may form bidder rings. We also show that the union of all stable sets can be described as the union of convex polytopes all of whose vertices are marginal contribution payoff vectors. Consequently, each stable set is contained in the Weber set. The Shapley value, however, typically falls outside the union of all stable sets.

Lexicographic allocations and extreme core payoffs: the case of assignment games

We consider various lexicographic allocation procedures for coalitional games with transferable utility where the payoffs are computed in an externally given order of the players. The common feature of the methods is that if the allocation is in the core, it is an extreme point of the core. We first investigate the general relationship between these allocations and obtain two hierarchies on the class of balanced games. Secondly, we focus on assignment games and sharpen some of these general relationship. Our main result is the coincidence of the sets of lemarals (vectors of lexicographic maxima over the set of dual coalitionally rational payoff vectors), lemacols (vectors of lexicographic maxima over the core) and extreme core points. As byproducts, we show that, similarly to the core and the coalitionally rational payoff set, also the dual coalitionally rational payoff set of an assignment game is determined by the individual and mixed-pair coalitions, and present an efficient and elementary way to compute these basic dual coalitional values. This provides a way to compute the Alexia value (the average of all lemacols) with no need to obtain the whole coalitional function of the dual assignment game.

Assignment Games with Externalities

We examine assignment games, wherematched pairs of firms and workers create some monetary value to distribute among themselves and the agents aim to maximize their payoff. In the majority of this literature, externalities - in the sense that a pair’s value depends on the pairing of the others - have been neglected. However, inmost applications a firm’s success depends on, say, the success of its rivals and suppliers. Thus, it is natural to ask how the classical results on assignment games are affected by the introduction of externalities? The answer is – dramatically. We find that (i) a problem may have no stable outcome, (ii) stable outcomes can be inefficient (not maximize total value), (iii) efficient outcomes can be unstable, and (iv) the set of stable outcomes may not form a lattice. We show that stable outcomes always exist if agents are "pessimistic." This is a knife-edge result: there are problems in which the slightest optimism by a single pair erases all stable outcomes.

A case study of the assignment of withdrawal codes for reporting dropout in two disciplinary alternative schools

Dropout rates are major issues facing any nation's continued economic and social progress. The seriousness of this issue in the United States is evidenced by the recent legislation of the 2001 No Child Left Behind Act. The purpose of this study was to use the richness of qualitative methodology to analyze inaccuracies in the assignment of withdrawal codes by school administrators in two different disciplinary alternative schools. The primary codes examined were Code 05, any students over the age of 16 who leaves school voluntarily with no intention of returning; Code 15, any PK–12 student who is withdrawn from school due to nonattendance; Code 22, whereabouts unknown; Code 23, no other code can be used to identify the student's reason for leaving school, and Code 26, entering an adult program. ^ The cross-case method was used for this study. The participants were comprised of 19 school personnel and 25 students from two disciplinary alternative schools, designated X and Y, in the Miami-Dade County Public School system, Miami, FL. Data collection procedures included semi-structured interview, observations, field notes, and district documents. With a matrix, these data were analyzed to compare patterns and themes that emerged within both schools. ^ Results indicated that withdrawal codes were assigned inaccurately for two distinct reasons. At School Y, withdrawal codes were inaccurately assigned intentionally to keep the students from returning to a regular school without notification. At School X, withdrawal codes were inaccurately assigned due to lack of ability to properly track students and ascertain the real circumstances for their departure from school. The end result in both cases was that the school systems were not accurately identifying the whereabouts of students. It was recommended that further investigation be conducted to compare the accuracy of reporting dropouts among traditional/regular high schools and disciplinary alternative schools. ^