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.

A mathematical excursion: From the three-door problem to a Cantor-type perfect set

We start with a generalization of the well-known three-door problem:the n-door problem. The solution of this new problem leads us toa beautiful representation system for real numbers in (0,1] as alternated series, known in the literature as Pierce expansions. A closer look to Pierce expansions will take us to some metrical properties of sets defined through the Pierce expansions of its elements. Finally, these metrical properties will enable us to present 'strange' sets, similar to the classical Cantor set.

Locating emergency services with priority rules: The priority queuing covering location problem

One of the assumptions of the Capacitated Facility Location Problem (CFLP) is thatdemand is known and fixed. Most often, this is not the case when managers take somestrategic decisions such as locating facilities and assigning demand points to thosefacilities. In this paper we consider demand as stochastic and we model each of thefacilities as an independent queue. Stochastic models of manufacturing systems anddeterministic location models are put together in order to obtain a formula for thebacklogging probability at a potential facility location.Several solution techniques have been proposed to solve the CFLP. One of the mostrecently proposed heuristics, a Reactive Greedy Adaptive Search Procedure, isimplemented in order to solve the model formulated. We present some computationalexperiments in order to evaluate the heuristics performance and to illustrate the use ofthis new formulation for the CFLP. The paper finishes with a simple simulationexercise.

A multi-objective model for a multi-period distribution management problem

The problems arising in commercial distribution are complex and involve several players and decision levels. One important decision is relatedwith the design of the routes to distribute the products, in an efficient and inexpensive way.This article deals with a complex vehicle routing problem that can beseen as a new extension of the basic vehicle routing problem. The proposed model is a multi-objective combinatorial optimization problemthat considers three objectives and multiple periods, which models in a closer way the real distribution problems. The first objective is costminimization, the second is balancing work levels and the third is amarketing objective. An application of the model on a small example, with5 clients and 3 days, is presented. The results of the model show the complexity of solving multi-objective combinatorial optimization problems and the contradiction between the several distribution management objective.

Multiparametric brainstem segmentation using a modified multivariate mixture of Gaussians

The human brainstem is a densely packed, complex but highly organised structure. It not only serves as a conduit for long projecting axons conveying motor and sensory information, but also is the location of multiple primary nuclei that control or modulate a vast array of functions, including homeostasis, consciousness, locomotion, and reflexive and emotive behaviours. Despite its importance, both in understanding normal brain function as well as neurodegenerative processes, it remains a sparsely studied structure in the neuroimaging literature. In part, this is due to the difficulties in imaging the internal architecture of the brainstem in vivo in a reliable and repeatable fashion. A modified multivariate mixture of Gaussians (mmMoG) was applied to the problem of multichannel tissue segmentation. By using quantitative magnetisation transfer and proton density maps acquired at 3 T with 0.8 mm isotropic resolution, tissue probability maps for four distinct tissue classes within the human brainstem were created. These were compared against an ex vivo fixated human brain, imaged at 0.5 mm, with excellent anatomical correspondence. These probability maps were used within SPM8 to create accurate individual subject segmentations, which were then used for further quantitative analysis. As an example, brainstem asymmetries were assessed across 34 right-handed individuals using voxel based morphometry (VBM) and tensor based morphometry (TBM), demonstrating highly significant differences within localised regions that corresponded to motor and vocalisation networks. This method may have important implications for future research into MRI biomarkers of pre-clinical neurodegenerative diseases such as Parkinson's disease.

Minimax lower bounds for the two-armed bandit problem

We obtain minimax lower bounds on the regret for the classicaltwo--armed bandit problem. We provide a finite--sample minimax version of the well--known log $n$ asymptotic lower bound of Lai and Robbins. Also, in contrast to the log $n$ asymptotic results on the regret, we show that the minimax regret is achieved by mere random guessing under fairly mild conditions on the set of allowable configurations of the two arms. That is, we show that for {\sl every} allocation rule and for {\sl every} $n$, there is a configuration such that the regret at time $n$ is at least 1 -- $\epsilon$ times the regret of random guessing, where $\epsilon$ is any small positive constant.

Simultaneous determination of antidementia drugs in human plasma: Procedure transfer from HPLC-MS to UPLC-MS/MS.

A previously developed high performance liquid chromatography mass spectrometry (HPLC-MS) procedure for the simultaneous determination of antidementia drugs, including donepezil, galantamine, memantine, rivastigmine and its metabolite NAP 226-90, was transferred to an ultra performance liquid chromatography system coupled to a tandem mass spectrometer (UPLC-MS/MS). The drugs and their internal standards ([(2)H(7)]-donepezil, [(13)C,(2)H(3)]-galantamine, [(13)C(2),(2)H(6)]-memantine, [(2)H(6)]-rivastigmine) were extracted from 250μL human plasma by protein precipitation with acetonitrile. Chromatographic separation was achieved on a reverse phase column (BEH C18 2.1mm×50mm; 1.7μm) with a gradient elution of an ammonium acetate buffer at pH 9.3 and acetonitrile at a flow rate of 0.4mL/min and an overall run time of 4.5min. The analytes were detected on a tandem quadrupole mass spectrometer operated in positive electrospray ionization mode, and quantification was performed using multiple reaction monitoring. The method was validated according to the recommendations of international guidelines over a calibration range of 1-300ng/mL for donepezil, galantamine and memantine, and 0.2-50ng/mL for rivastimgine and NAP 226-90. The trueness (86-108%), repeatability (0.8-8.3%), intermediate precision (2.3-10.9%) and selectivity of the method were found to be satisfactory. Matrix effects variability was inferior to 15% for the analytes and inferior to 5% after correction by internal standards. A method comparison was performed with patients' samples showing similar results between the HPLC-MS and UPLC-MS/MS procedures. Thus, this validated UPLC-MS/MS method allows to reduce the required amount of plasma, to use a simplified sample preparation, and to obtain a higher sensitivity and specificity with a much shortened run-time.

Modeling the forensic two-trace problem with Bayesian networks

The forensic two-trace problem is a perplexing inference problem introduced by Evett (J Forensic Sci Soc 27:375-381, 1987). Different possible ways of wording the competing pair of propositions (i.e., one proposition advanced by the prosecution and one proposition advanced by the defence) led to different quantifications of the value of the evidence (Meester and Sjerps in Biometrics 59:727-732, 2003). Here, we re-examine this scenario with the aim of clarifying the interrelationships that exist between the different solutions, and in this way, produce a global vision of the problem. We propose to investigate the different expressions for evaluating the value of the evidence by using a graphical approach, i.e. Bayesian networks, to model the rationale behind each of the proposed solutions and the assumptions made on the unknown parameters in this problem.

The TetR-type MfsR protein of the integrative and conjugative element (ICE) ICEclc controls both a putative efflux system and initiation of ICE transfer.

Integrative and conjugating elements (ICE) are self-transferable DNAs widely present in bacterial genomes, which often carry a variety of auxiliary genes of potential adaptive benefit. One of the model ICE is ICEclc, an element originally found in Pseudomonas knackmussii B13 and known for its propensity to provide its host with the capacity to metabolize chlorocatechols and 2-aminophenol. In this work, we studied the mechanism and target of regulation of MfsR, a TetR-type repressor previously found to exert global control on ICEclc horizontal transfer. By using a combination of ICEclc mutant and transcriptome analysis, gene reporter fusions, and DNA binding assays, we found that MfsR is a repressor of both its own expression and that of a gene cluster putatively coding for a major facilitator superfamily efflux system on ICEclc (named mfsABC). Phylogenetic analysis suggests that mfsR was originally located immediately adjacent to the efflux pump genes but became displaced from its original cis target DNA by a gene insertion. This resulted in divergence of the original bidirectional promoters into two separated individual regulatory units. Deletion of mfsABC did not result in a strong phenotype, and despite screening a large number of compounds and conditions, we were unable to define the precise current function or target of the putative efflux pump. Our data reconstruct how the separation of an ancestor mfsR-mfsABC system led to global control of ICEclc transfer by MfsR.

LIF and sIL-2R plasma concentrations in IVF patients on the day of embryo transfer: predictive markers of IVF outcome.

Successful implantation is still the limiting step in IVF. We hypothesized that maternal plasma concentrations of certain cytokines at the time of embryo transfer could predict the likelihood of successful implantation and pregnancy. sIL-2R, IL-6, LIF, and MMP2 concentrations were measured in plasma from 160 IVF patients (natural and stimulated IVF cycles) on the morning of the embryo transfer (ET0) and 14days later (ET+14). Patients were ultimately subdivided into four groups depending on the IVF treatment outcome (pregnancy failure, biochemical pregnancy, first-trimester miscarriage and normal term delivery). In natural and stimulated IVF cycles at ET0, sIL-2R concentrations were threefold higher in biochemical pregnancies than in pregnancy failures (P=0.020), and in natural cycles only, 2.5-fold higher in normal term deliveries than in pregnancy failures (P=0.023). Conversely, in natural and stimulated IVF cycles at ET0, LIF concentrations were one third lower in biochemical pregnancies/first-trimester miscarriages compared with pregnancy failures (P=0.042). We suggest that high sIL-2R and low LIF concentrations in maternal plasma on the morning of the embryo transfer might be associated with increased risks of early pregnancy loss, while a basal level of sIL-2R is necessary for normal term delivery outcome. Both cytokine measurements might therefore be useful in the management of IVF patients, and modulation of their concentrations could be investigated as a therapeutic alternative for women with abnormal concentrations at the time of embryo transfer.