A Constructive Genetic Algorithm for permutation flowshop scheduling

The general flowshop scheduling problem is a production problem where a set of n jobs have to be processed with identical flow pattern on in machines. In permutation flowshops the sequence of jobs is the same on all machines. A significant research effort has been devoted for sequencing jobs in a flowshop minimizing the makespan. This paper describes the application of a Constructive Genetic Algorithm (CGA) to makespan minimization on flowshop scheduling. The CGA was proposed recently as an alternative to traditional GA approaches, particularly, for evaluating schemata directly. The population initially formed only by schemata, evolves controlled by recombination to a population of well-adapted structures (schemata instantiation). The CGA implemented is based on the NEH classic heuristic and a local search heuristic used to define the fitness functions. The parameters of the CGA are calibrated using a Design of Experiments (DOE) approach. The computational results are compared against some other successful algorithms from the literature on Taillard`s well-known standard benchmark. The computational experience shows that this innovative CGA approach provides competitive results for flowshop scheduling; problems. (C) 2007 Elsevier Ltd. All rights reserved.

Hybrid Algorithms for Routing and Assignment Wavelengths in Optical Networks

This paper presents a strategy for the solution of the WDM optical networks planning. Specifically, the problem of Routing and Wavelength Allocation (RWA) in order to minimize the amount of wavelengths used. In this case, the problem is known as the Min-RWA. Two meta-heuristics (Tabu Search and Simulated Annealing) are applied to take solutions of good quality and high performance. The key point is the degradation of the maximum load on the virtual links in favor of minimization of number of wavelengths used; the objective is to find a good compromise between the metrics of virtual topology (load in Gb/s) and of the physical topology (quantity of wavelengths). The simulations suggest good results when compared to some existing in the literature.

New simple and efficient heuristics for the uncapacitated single allocation hub location problem

Hub-and-spoke networks are widely studied in the area of location theory. They arise in several contexts, including passenger airlines, postal and parcel delivery, and computer and telecommunication networks. Hub location problems usually involve three simultaneous decisions to be made: the optimal number of hub nodes, their locations and the allocation of the non-hub nodes to the hubs. In the uncapacitated single allocation hub location problem (USAHLP) hub nodes have no capacity constraints and non-hub nodes must be assigned to only one hub. In this paper, we propose three variants of a simple and efficient multi-start tabu search heuristic as well as a two-stage integrated tabu search heuristic to solve this problem. With multi-start heuristics, several different initial solutions are constructed and then improved by tabu search, while in the two-stage integrated heuristic tabu search is applied to improve both the locational and allocational part of the problem. Computational experiments using typical benchmark problems (Civil Aeronautics Board (CAB) and Australian Post (AP) data sets) as well as new and modified instances show that our approaches consistently return the optimal or best-known results in very short CPU times, thus allowing the possibility of efficiently solving larger instances of the USAHLP than those found in the literature. We also report the integer optimal solutions for all 80 CAB data set instances and the 12 AP instances up to 100 nodes, as well as for the corresponding new generated AP instances with reduced fixed costs. Published by Elsevier Ltd.

S/MIMO MC-CDMA Heuristic Multiuser Detectors Based on Single-Objective Optimization

This paper analyzes the complexity-performance trade-off of several heuristic near-optimum multiuser detection (MuD) approaches applied to the uplink of synchronous single/multiple-input multiple-output multicarrier code division multiple access (S/MIMO MC-CDMA) systems. Genetic algorithm (GA), short term tabu search (STTS) and reactive tabu search (RTS), simulated annealing (SA), particle swarm optimization (PSO), and 1-opt local search (1-LS) heuristic multiuser detection algorithms (Heur-MuDs) are analyzed in details, using a single-objective antenna-diversity-aided optimization approach. Monte- Carlo simulations show that, after convergence, the performances reached by all near-optimum Heur-MuDs are similar. However, the computational complexities may differ substantially, depending on the system operation conditions. Their complexities are carefully analyzed in order to obtain a general complexity-performance framework comparison and to show that unitary Hamming distance search MuD (uH-ds) approaches (1-LS, SA, RTS and STTS) reach the best convergence rates, and among them, the 1-LS-MuD provides the best trade-off between implementation complexity and bit error rate (BER) performance.

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines: therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and Coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising. (c) 2007 Elsevier Ltd. All rights reserved.

Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints

This article describes and compares three heuristics for a variant of the Steiner tree problem with revenues, which includes budget and hop constraints. First, a greedy method which obtains good approximations in short computational times is proposed. This initial solution is then improved by means of a destroy-and-repair method or a tabu search algorithm. Computational results compare the three methods in terms of accuracy and speed. (C) 2007 Elsevier B.V. All rights reserved.

Search for cytotoxic agents in multiple Laurencia complex seaweed species (Ceramiales, Rhodophyta) harvested from the Atlantic Ocean with emphasis on the Brazilian State of Espírito Santo

The development of new anti-cancer drugs of algal origin represents one of the least explored frontiers in medicinal chemistry. In this regard, the diversity of micro- and macroalgae found in Brazilian coastal waters can be viewed as a largely untapped natural resource. In this report, we describe a comparative study on the cytotoxic properties of extracts obtained from the Laurencia complex: Laurencia aldingensis, L. catarinensis, L. dendroidea, L. intricata, L. translucida, L. sp, and Palisada flagellifera. All of these species were collected in the coastal waters of the State of Espírito Santo, Brazil. Four out of the twelve samples initially investigated were found to show significant levels of toxicity towards a model tumor cell line (human uterine sarcoma, MES-SA). The highest levels of cytotoxicity were typically associated with non-polar (hexane) algal extracts, while the lowest levels of cytotoxicity were found with the corresponding polar (methanol) extracts. In this report, we also describe a biological model currently in development that will not only facilitate the search for new anti-cancer drug candidates of algal origin, but also permit the identification of compounds capable of inducing the destruction of multi-drug resistant tumors with greater efficiency than the pharmaceuticals currently in clinical use.

A SEARCH FOR FIELD HORIZONTAL-BRANCH STARS NEAR THE SOUTH GALACTIC POLE

Searches for field horizontal-branch (FHB) stars in the halo of the Galaxy in the past have been carried out by several techniques, such as objective-prism surveys and visual or infrared photometric surveys. By choosing adequate color criteria, it is possible to improve the efficiency of identifying bona fide FHB stars among the other objects that exhibit similar characteristics, such as main-sequence A-stars, blue stragglers, subdwarfs, etc. In this work, we report the results of a spectroscopic survey carried out near the south Galactic pole intended to validate FHB stars originally selected from the HK objective-prism survey of Beers and colleagues, based on near-infrared color indices. A comparison between the stellar spectra obtained in this survey with theoretical stellar atmosphere models allows us to determine T(eff), log g, and [Fe/H] for 13 stars in the sample. Stellar temperatures were calculated from measured (B-V)(o), when this measurement was available (16 stars). The color index criteria adopted in this work are shown to correctly classify 30% of the sample as FHB, 25% as non-FHB (main-sequence stars and subdwarfes), whereas 40% could not be distinguished between FHB and main-sequence stars. We compare the efficacy of different color criteria in the literature intended to select FHB stars, and discuss the use of the Mg II 4481 line to estimate the metallicity.

A SEARCH FOR UNRECOGNIZED CARBON-ENHANCED METAL-POOR STARS IN THE GALAXY

We have developed a new procedure to search for carbon-enhanced metal-poor (CEMP) stars from the Hamburg/ESO (HES) prism-survey plates. This method employs an extended line index for the CH G band, which we demonstrate to have superior performance when compared to the narrower G-band index formerly employed to estimate G-band strengths for these spectra. Although CEMP stars have been found previously among candidate metal-poor stars selected from the HES, the selection on metallicity undersamples the population of intermediate-metallicity CEMP stars (-2.5 <= [Fe/H] <= -1.0); such stars are of importance for constraining the onset of the s-process in metal-deficient asymptotic giant branch stars (thought to be associated with the origin of carbon for roughly 80% of CEMP stars). The new candidates also include substantial numbers of warmer carbon-enhanced stars, which were missed in previous HES searches for carbon stars due to selection criteria that emphasized cooler stars. A first subsample, biased toward brighter stars (B < 15.5), has been extracted from the scanned HES plates. After visual inspection (to eliminate spectra compromised by plate defects, overlapping spectra, etc., and to carry out rough spectral classifications), a list of 669 previously unidentified candidate CEMP stars was compiled. Follow-up spectroscopy for a pilot sample of 132 candidates was obtained with the Goodman spectrograph on the SOAR 4.1 m telescope. Our results show that most of the observed stars lie in the targeted metallicity range, and possess prominent carbon absorption features at 4300 angstrom. The success rate for the identification of new CEMP stars is 43% (13 out of 30) for [Fe/H] < -2.0. For stars with [Fe/H] < -2.5, the ratio increases to 80% (four out of five objects), including one star with [Fe/H] < -3.0.

A search for thermally emitting isolated neutron stars in the 2XMMp catalogue

The relatively large number of nearby radio-quiet and thermally emitting isolated neutron stars (INSs) discovered in the ROSAT All-Sky Survey, dubbed the ""Magnificent Seven"", suggests that they belong to a formerly neglected major component of the overall INS population. So far, attempts to discover similar INSs beyond the solar vicinity failed to confirm any reliable candidate. The good positional accuracy and soft X-ray sensitivity of the EPIC cameras onboard the XMM-Newton satellite allow us to efficiently search for new thermally emitting INSs. We used the 2XMMp catalogue to select sources with no catalogued candidate counterparts and with X-ray spectra similar to those of the Magnificent Seven, but seen at greater distances and thus undergoing higher interstellar absorptions. Identifications in more than 170 astronomical catalogues and visual screening allowed us to select fewer than 30 good INS candidates. In order to rule out alternative identifications, we obtained deep ESO-VLT and SOAR optical imaging for the X-ray brightest candidates. We report here on the optical follow-up results of our search and discuss the possible nature of 8 of our candidates. A high X-ray-to-optical flux ratio together with a stable flux and soft X-ray spectrum make the brightest source of our sample, 2XMM J104608.7-594306, a newly discovered thermally emitting INS. The X-ray source 2XMM J010642.3+005032 has no evident optical counterpart and should be further investigated. The remaining X-ray sources are most probably identified with cataclysmic variables and active galactic nuclei, as inferred from the colours and flux ratios of their likely optical counterparts. Beyond the finding of new thermally emitting INSs, our study aims at constraining the space density of this Galactic population at great distances and at determining whether their apparently high density is a local anomaly or not.

Search for Lorentz Invariance and CPT Violation with the MINOS Far Detector

We searched for a sidereal modulation in the MINOS far detector neutrino rate. Such a signal would be a consequence of Lorentz and CPT violation as described by the standard-model extension framework. It also would be the first detection of a perturbative effect to conventional neutrino mass oscillations. We found no evidence for this sidereal signature, and the upper limits placed on the magnitudes of the Lorentz and CPT violating coefficients describing the theory are an improvement by factors of 20-510 over the current best limits found by using the MINOS near detector.

Search for sterile neutrino mixing in the MINOS long-baseline experiment

A search for depletion of the combined flux of active neutrino species over a 735 km baseline is reported using neutral-current interaction data recorded by the MINOS detectors in the NuMI neutrino beam. Such a depletion is not expected according to conventional interpretations of neutrino oscillation data involving the three known neutrino flavors. A depletion would be a signature of oscillations or decay to postulated noninteracting sterile neutrinos, scenarios not ruled out by existing data. From an exposure of 3.18 x 10(20) protons on target in which neutrinos of energies between similar to 500 MeV and 120 GeV are produced predominantly as nu(mu), the visible energy spectrum of candidate neutral-current reactions in the MINOS far detector is reconstructed. Comparison of this spectrum to that inferred from a similarly selected near-detector sample shows that of the portion of the nu(mu) flux observed to disappear in charged-current interaction data, the fraction that could be converting to a sterile state is less than 52% at 90% confidence level (C. L.). The hypothesis that active neutrinos mix with a single sterile neutrino via oscillations is tested by fitting the data to various models. In the particular four-neutrino models considered, the mixing angles theta(24) and theta(34) are constrained to be less than 11 degrees and 56 degrees at 90% C. L., respectively. The possibility that active neutrinos may decay to sterile neutrinos is also investigated. Pure neutrino decay without oscillations is ruled out at 5.4 standard deviations. For the scenario in which active neutrinos decay into sterile states concurrently with neutrino oscillations, a lower limit is established for the neutrino decay lifetime tau(3)/m(3) > 2.1 x 10(-12) s/eV at 90% C.L.

Search for Muon-Neutrino to Electron-Neutrino Transitions in MINOS

This Letter reports on a search for nu(mu)->nu(e) transitions by the MINOS experiment based on a 3.14x10(20) protons-on-target exposure in the Fermilab NuMI beam. We observe 35 events in the Far Detector with a background of 27 +/- 5(stat)+/- 2(syst) events predicted by the measurements in the Near Detector. If interpreted in terms of nu(mu)->nu(e) oscillations, this 1.5 sigma excess of events is consistent with sin(2)(2 theta(13)) comparable to the CHOOZ limit when |Delta m(2)|=2.43x10(-3) eV(2) and sin(2)(2 theta(23))=1.0 are assumed.

Search for Active Neutrino Disappearance Using Neutral-Current Interactions in the MINOS Long-Baseline Experiment

We report the first detailed comparisons of the rates and spectra of neutral-current neutrino interactions at two widely separated locations. A depletion in the rate at the far site would indicate mixing between nu(mu) and a sterile particle. No anomalous depletion in the reconstructed energy spectrum is observed. Assuming oscillations occur at a single mass-squared splitting, a fit to the neutral- and charged-current energy spectra limits the fraction of nu(mu) oscillating to a sterile neutrino to be below 0.68 at 90% confidence level. A less stringent limit due to a possible contribution to the measured neutral-current event rate at the far site from nu(e) appearance at the current experimental limit is also presented.

Search for the rare decay K(L)->pi(0)pi(0)gamma

The KTeV E799 experiment has conducted a search for the rare decay K(L)->pi(0)pi(0)gamma via the topology K(L)->pi(0)pi(0)(D)gamma (where pi(0)(D)->gamma e(+)e(-)). Because of Bose statistics of the pi(0) pair and the real nature of the photon, the K(L)->pi(0)pi(0)gamma decay is restricted to proceed at lowest order by the CP conserving direct emission (DE) of an E2 electric quadrupole photon. The rate of this decay is interesting theoretically since chiral perturbation theory predicts that this process vanishes at level O(p(4)). Therefore, this mode probes chiral perturbation theory at O(p(6)). In this paper we report a determination of an upper limit of 2.43x10(-7) (90% CL) for K(L)->pi(0)pi(0)gamma. This is approximately a factor of 20 lower than previous results.