Algorithm optimization for solving crew scheduling problems

In this paper, we are proposing a methodology to determine the most efficient and least costly way of crew pairing optimization. We are developing a methodology based on algorithm optimization on Eclipse opensource IDE using the Java programming language to solve the crew scheduling problems.

Energy partitioning for "fuzzy" atoms

The total energy of molecule in terms of 'fuzzy atoms' presented as sum of one- and two-atomic energy components is described. The divisions of three-dimensional physical space into atomic regions exhibit continuous transition from one to another. The energy components are on chemical energy scale according to proper definitions. The Becke's integration scheme and weight function determines realization of method which permits effective numerical integrations

One- and two-center physical space partitioning of the energy in the density functional theory

A conceptually new approach is introduced for the decomposition of the molecular energy calculated at the density functional theory level of theory into sum of one- and two-atomic energy components, and is realized in the "fuzzy atoms" framework. (Fuzzy atoms mean that the three-dimensional physical space is divided into atomic regions having no sharp boundaries but exhibiting a continuous transition from one to another.) The new scheme uses the new concept of "bond order density" to calculate the diatomic exchange energy components and gives them unexpectedly close to the values calculated by the exact (Hartree-Fock) exchange for the same Kohn-Sham orbitals

Partitioning of genetic (Rapd) variability among sexes and populations of the Barn Owl (Tyto alba) in Europe

The white Barn Owl subspecies (Tyto alba alba) is found in southern Europe and the reddish-brown subspecies (T a. guttata) in northern and eastern Europe. In central Europe, the two subspecies interbreed producing a large range of phenotypic variants. Because of the different ratios of the subspecies in different geographic regions, we predict that genetic variation should be greater in Switzerland than in Hungary. We tested this hypothesis by measuring genetic variation with the RAPD method. As predicted, the genetic differentiation within a Swiss population of Barn Owls was significantly greater than the variation within a Hungarian population. This suggests that gene flow is greater in central Europe than at the eastern limit of the Barn Owl distribution in Hungary. In both countries genetic variation was more pronounced in females than in males. As in other birds, this is probably because female Barn Owls are less philopatric than males. The number of migrants between Hungary and Switzerland is ca. 1 individual per generation; if calculated separately for the sexes, then 0.525 for males and ca. I for females (Nm values). The difference in the number of migrants between genders again is likely a consequence of higher male philopatry. The sexual differentiation is greater in the Swiss population than in the Hungarian and the genetic substructuring of the populations of the species is substantial. The reason for the considerable population substructuring could be the nonmigratory behavior and socially monogamous pairing of the species, as well as the geographical barriers (Alps) between the populations examined.

Development and validation of AMANDA, a new algorithm for selecting highly relevant regions in Molecular Interaction Fields

Descriptors based on Molecular Interaction Fields (MIF) are highly suitable for drug discovery, but their size (thousands of variables) often limits their application in practice. Here we describe a simple and fast computational method that extracts from a MIF a handful of highly informative points (hot spots) which summarize the most relevant information. The method was specifically developed for drug discovery, is fast, and does not require human supervision, being suitable for its application on very large series of compounds. The quality of the results has been tested by running the method on the ligand structure of a large number of ligand-receptor complexes and then comparing the position of the selected hot spots with actual atoms of the receptor. As an additional test, the hot spots obtained with the novel method were used to obtain GRIND-like molecular descriptors which were compared with the original GRIND. In both cases the results show that the novel method is highly suitable for describing ligand-receptor interactions and compares favorably with other state-of-the-art methods.

A systolic array for linear MIMO detection based on an all-swap lattice reduction algorithm

A systolic array to implement lattice-reduction-aided lineardetection is proposed for a MIMO receiver. The lattice reductionalgorithm and the ensuing linear detections are operated in the same array, which can be hardware-efficient. All-swap lattice reduction algorithm (ASLR) is considered for the systolic design.ASLR is a variant of the LLL algorithm, which processes all lattice basis vectors within one iteration. Lattice-reduction-aided linear detection based on ASLR and LLL algorithms have very similarbit-error-rate performance, while ASLR is more time efficient inthe systolic array, especially for systems with a large number ofantennas.

Silver space-time trellis-coded modulation

Silver Code (SilC) was originally discovered in [1–4] for 2×2 multiple-input multiple-output (MIMO) transmission. It has non-vanishing minimum determinant 1/7, slightly lower than Golden code, but is fast-decodable, i.e., it allows reduced-complexity maximum likelihood decoding [5–7]. In this paper, we present a multidimensional trellis-coded modulation scheme for MIMO systems [11] based on set partitioning of the Silver Code, named Silver Space-Time Trellis Coded Modulation (SST-TCM). This lattice set partitioning is designed specifically to increase the minimum determinant. The branches of the outer trellis code are labeled with these partitions. Viterbi algorithm is applied for trellis decoding, while the branch metrics are computed by using a sphere-decoding algorithm. It is shown that the proposed SST-TCM performs very closely to the Golden Space-Time Trellis Coded Modulation (GST-TCM) scheme, yetwith a much reduced decoding complexity thanks to its fast-decoding property.

ILS-ESP An efficient, simple, and parameter-free algorithm for solving the permutation flow-shop problem

From a managerial point of view, the more effcient, simple, and parameter-free (ESP) an algorithm is, the more likely it will be used in practice for solving real-life problems. Following this principle, an ESP algorithm for solving the Permutation Flowshop Sequencing Problem (PFSP) is proposed in this article. Using an Iterated Local Search (ILS) framework, the so-called ILS-ESP algorithm is able to compete in performance with other well-known ILS-based approaches, which are considered among the most effcient algorithms for the PFSP. However, while other similar approaches still employ several parameters that can affect their performance if not properly chosen, our algorithm does not require any particular fine-tuning process since it uses basic "common sense" rules for the local search, perturbation, and acceptance criterion stages of the ILS metaheuristic. Our approach defines a new operator for the ILS perturbation process, a new acceptance criterion based on extremely simple and transparent rules, and a biased randomization process of the initial solution to randomly generate different alternative initial solutions of similar quality -which is attained by applying a biased randomization to a classical PFSP heuristic. This diversification of the initial solution aims at avoiding poorly designed starting points and, thus, allows the methodology to take advantage of current trends in parallel and distributed computing. A set of extensive tests, based on literature benchmarks, has been carried out in order to validate our algorithm and compare it against other approaches. These tests show that our parameter-free algorithm is able to compete with state-of-the-art metaheuristics for the PFSP. Also, the experiments show that, when using parallel computing, it is possible to improve the top ILS-based metaheuristic by just incorporating to it our biased randomization process with a high-quality pseudo-random number generator.

Partitioning of reproduction in mother-daughter versus sibling associations : a test of optimal skew theory

A critical feature of cooperative animal societies is the reproductive skew, a shorthand term for the degree to which a dominant individual monopolizes overall reproduction in the group. Our theoretical analysis of the evolutionarily stable skew in matrifilial (i.e., mother-daughter) societies, in which relatednesses to offspring are asymmetrical, predicts that reproductive skews in such societies should tend to be greater than those of semisocial societies (i.e., societies composed of individuals of the same generation, such as siblings), in which relatednesses to offspring are symmetrical. Quantitative data on reproductive skews in semisocial and matrifilial associations within the same species for 17 eusocial Hymenoptera support this prediction. Likewise, a survey of reproductive partitioning within 20 vertebrate societies demonstrates that complete reproductive monopoly is more likely to occur in matrifilial than in semisocial societies, also as predicted by the optimal skew model.

ParA2, a Vibrio cholerae chromosome partitioning protein, forms left-handed helical filaments on DNA.

Most bacterial chromosomes contain homologs of plasmid partitioning (par) loci. These loci encode ATPases called ParA that are thought to contribute to the mechanical force required for chromosome and plasmid segregation. In Vibrio cholerae, the chromosome II (chrII) par locus is essential for chrII segregation. Here, we found that purified ParA2 had ATPase activities comparable to other ParA homologs, but, unlike many other ParA homologs, did not form high molecular weight complexes in the presence of ATP alone. Instead, formation of high molecular weight ParA2 polymers required DNA. Electron microscopy and three-dimensional reconstruction revealed that ParA2 formed bipolar helical filaments on double-stranded DNA in a sequence-independent manner. These filaments had a distinct change in pitch when ParA2 was polymerized in the presence of ATP versus in the absence of a nucleotide cofactor. Fitting a crystal structure of a ParA protein into our filament reconstruction showed how a dimer of ParA2 binds the DNA. The filaments formed with ATP are left-handed, but surprisingly these filaments exert no topological changes on the right-handed B-DNA to which they are bound. The stoichiometry of binding is one dimer for every eight base pairs, and this determines the geometry of the ParA2 filaments with 4.4 dimers per 120 A pitch left-handed turn. Our findings will be critical for understanding how ParA proteins function in plasmid and chromosome segregation.

A polynomial algorithm for special case of the one-machine scheduling problem with time-lags

The standard one-machine scheduling problem consists in schedulinga set of jobs in one machine which can handle only one job at atime, minimizing the maximum lateness. Each job is available forprocessing at its release date, requires a known processing timeand after finishing the processing, it is delivery after a certaintime. There also can exists precedence constraints between pairsof jobs, requiring that the first jobs must be completed beforethe second job can start. An extension of this problem consistsin assigning a time interval between the processing of the jobsassociated with the precedence constrains, known by finish-starttime-lags. In presence of this constraints, the problem is NP-hardeven if preemption is allowed. In this work, we consider a specialcase of the one-machine preemption scheduling problem with time-lags, where the time-lags have a chain form, and propose apolynomial algorithm to solve it. The algorithm consist in apolynomial number of calls of the preemption version of the LongestTail Heuristic. One of the applicability of the method is to obtainlower bounds for NP-hard one-machine and job-shop schedulingproblems. We present some computational results of thisapplication, followed by some conclusions.

Speed of convergence of recursive least squares learning with ARMA perceptions

This paper fills a gap in the existing literature on least squareslearning in linear rational expectations models by studying a setup inwhich agents learn by fitting ARMA models to a subset of the statevariables. This is a natural specification in models with privateinformation because in the presence of hidden state variables, agentshave an incentive to condition forecasts on the infinite past recordsof observables. We study a particular setting in which it sufficesfor agents to fit a first order ARMA process, which preserves thetractability of a finite dimensional parameterization, while permittingconditioning on the infinite past record. We describe how previousresults (Marcet and Sargent [1989a, 1989b] can be adapted to handlethe convergence of estimators of an ARMA process in our self--referentialenvironment. We also study ``rates'' of convergence analytically and viacomputer simulation.

Recursive contracts

We obtain a recursive formulation for a general class of contractingproblems involving incentive constraints. Under these constraints,the corresponding maximization (sup) problems fails to have arecursive solution. Our approach consists of studying the Lagrangian.We show that, under standard assumptions, the solution to theLagrangian is characterized by a recursive saddle point (infsup)functional equation, analogous to Bellman's equation. Our approachapplies to a large class of contractual problems. As examples, westudy the optimal policy in a model with intertemporal participationconstraints (which arise in models of default) and intertemporalcompetitive constraints (which arise in Ramsey equilibria).

On the efficiency and sensitivity of a pyramidal classification algorithm

In this paper we propose a Pyramidal Classification Algorithm,which together with an appropriate aggregation index producesan indexed pseudo-hierarchy (in the strict sense) withoutinversions nor crossings. The computer implementation of thealgorithm makes it possible to carry out some simulation testsby Monte Carlo methods in order to study the efficiency andsensitivity of the pyramidal methods of the Maximum, Minimumand UPGMA. The results shown in this paper may help to choosebetween the three classification methods proposed, in order toobtain the classification that best fits the original structureof the population, provided we have an a priori informationconcerning this structure.