Best possible approximation algorithms for single machine scheduling with increasing linear maintenance durations.
Ontology highlight
ABSTRACT:
SUBMITTER: Shi X
PROVIDER: S-EPMC3950368 | biostudies-other | 2014
REPOSITORIES: biostudies-other
Similar Datasets
Project description:We investigate a common due-date assignment scheduling problem with a variable maintenance on a single machine. The goal is to minimize the total earliness, tardiness, and due-date cost. We derive some properties on an optimal solution for our problem. For a special case with identical jobs we propose an optimal polynomial time algorithm followed by a numerical example.
| S-EPMC4132401 | biostudies-other
Project description:BackgroundStochastic fluctuations in molecular numbers have been in many cases shown to be crucial for the understanding of biochemical systems. However, the systematic study of these fluctuations is severely hindered by the high computational demand of stochastic simulation algorithms. This is particularly problematic when, as is often the case, some or many model parameters are not well known. Here, we propose a solution to this problem, namely a combination of the linear noise approximation with optimisation methods. The linear noise approximation is used to efficiently estimate the covariances of particle numbers in the system. Combining it with optimisation methods in a closed-loop to find extrema of covariances within a possibly high-dimensional parameter space allows us to answer various questions. Examples are, what is the lowest amplitude of stochastic fluctuations possible within given parameter ranges? Or, which specific changes of parameter values lead to the increase of the correlation between certain chemical species? Unlike stochastic simulation methods, this has no requirement for small numbers of molecules and thus can be applied to cases where stochastic simulation is prohibitive.ResultsWe implemented our strategy in the software COPASI and show its applicability on two different models of mitogen-activated kinases (MAPK) signalling -- one generic model of extracellular signal-regulated kinases (ERK) and one model of signalling via p38 MAPK. Using our method we were able to quickly find local maxima of covariances between particle numbers in the ERK model depending on the activities of phospho-MKKK and its corresponding phosphatase. With the p38 MAPK model our method was able to efficiently find conditions under which the coefficient of variation of the output of the signalling system, namely the particle number of Hsp27, could be minimised. We also investigated correlations between the two parallel signalling branches (MKK3 and MKK6) in this model.ConclusionsOur strategy is a practical method for the efficient investigation of fluctuations in biochemical models even when some or many of the model parameters have not yet been fully characterised.
| S-EPMC3814289 | biostudies-literature
Project description:Memory-related activity in the Dentate Gyrus (DG) is characterized by sparsity. Memory representations are seen as activated neuronal populations of granule cells, the main encoding cells in DG, which are estimated to engage 2-4% of the total population. This sparsity is assumed to enhance the ability of DG to perform pattern separation, one of the most valuable contributions of DG during memory formation. In this work, we investigate how features of the DG such as its excitatory and inhibitory connectivity diagram can be used to develop theoretical algorithms performing Sparse Approximation, a widely used strategy in the Signal Processing field. Sparse approximation stands for the algorithmic identification of few components from a dictionary that approximate a certain signal. The ability of DG to achieve pattern separation by sparsifing its representations is exploited here to improve the performance of the state of the art sparse approximation algorithm "Iterative Soft Thresholding" (IST) by adding new algorithmic features inspired by the DG circuitry. Lateral inhibition of granule cells, either direct or indirect, via mossy cells, is shown to enhance the performance of the IST. Apart from revealing the potential of DG-inspired theoretical algorithms, this work presents new insights regarding the function of particular cell types in the pattern separation task of the DG.
| S-EPMC4312091 | biostudies-literature
Project description:When the optimal treatment duration is uncertain, a randomized trial may allocate patients to receive active treatment for different durations. We use an example where patients receive treatment for 0, 24, or 52 weeks. In this trial, patients in the 24-weeks and 52-weeks arms receive the same treatment during the first 24 weeks. This overlap allows for more powerful analyses than conventional pair-wise comparisons of arms. When the outcome is the time-to-event, the power for the 0-weeks versus 24-weeks comparison can be increased by including patients in the 52-weeks arm as patients in the 24-weeks arm for the first 24 weeks and censoring at 24 weeks. Furthermore, differences observed between the 24-weeks and 52-weeks arms during the first 24 weeks can only reflect noise. Hence, the comparison of these two arms should be restricted to only patients who remain on the study at 24 weeks and include only the events after 24 weeks. Through simulation, we show that modified analyses accounting for these considerations increase study power substantially. Moreover, if patients were allocated equally to the arms, then events or discontinuations during the first 24 weeks will reduce the number of patients available for the 24-weeks versus 52-weeks comparison, and hence the power of this analysis will be lower than that for the 0-weeks versus 24-weeks comparison. We present a sample size calculation procedure for equalizing the power of these two analyses. Typically, this allocation requires much larger sample sizes in the 24-weeks and 52-weeks arms than in the 0-week arm.
| S-EPMC7322686 | biostudies-literature
Project description:Cell culturing is a basic experimental technique in cell biology and medical science. However, culturing high-quality cells with a high degree of reproducibility relies heavily on expert skills and tacit knowledge, and it is not straightforward to scale the production process due to the education bottleneck. Although many automated culture systems have been developed and a few have succeeded in mass production environments, very few robots are permissive of frequent protocol changes, which are often required in basic research environments. LabDroid is a general-purpose humanoid robot with two arms that performs experiments using the same tools as humans. Combining our newly developed AI software with LabDroid, we developed a variable scheduling system that continuously produces subcultures of cell lines without human intervention. The system periodically observes the cells on plates with a microscope, predicts the cell growth curve by processing cell images, and decides the best times for passage. We have succeeded in developing a system that maintains the cultures of two HEK293A cell plates with no human intervention for 192 h.
| S-EPMC7985857 | biostudies-literature
Project description:Volcanoes constitute dissipative systems with many degrees of freedom. Their eruptions are the result of complex processes that involve interacting chemical-physical systems. At present, due to the complexity of involved phenomena and to the lack of precise measurements, both analytical and numerical models are unable to simultaneously include the main processes involved in eruptions thus making forecasts of volcanic dynamics rather unreliable. On the other hand, accurate forecasts of some eruption parameters, such as the duration, could be a key factor in natural hazard estimation and mitigation. Analyzing a large database with most of all the known volcanic eruptions, we have determined that the duration of eruptions seems to be described by a universal distribution which characterizes eruption duration dynamics. In particular, this paper presents a plausible global power-law distribution of durations of volcanic eruptions that holds worldwide for different volcanic environments. We also introduce a new, simple and realistic pipe model that can follow the same found empirical distribution. Since the proposed model belongs to the family of the self-organized systems it may support the hypothesis that simple mechanisms can lead naturally to the emergent complexity in volcanic behaviour.
| S-EPMC4772095 | biostudies-literature
Project description:The presence of protein-DNA binding reactions often leads to analytically intractable models of stochastic gene expression. Here we present the linear-mapping approximation that maps systems with protein-promoter interactions onto approximately equivalent systems with no binding reactions. This is achieved by the marriage of conditional mean-field approximation and the Magnus expansion, leading to analytic or semi-analytic expressions for the approximate time-dependent and steady-state protein number distributions. Stochastic simulations verify the method's accuracy in capturing the changes in the protein number distributions with time for a wide variety of networks displaying auto- and mutual-regulation of gene expression and independently of the ratios of the timescales governing the dynamics. The method is also used to study the first-passage time distribution of promoter switching, the sensitivity of the size of protein number fluctuations to parameter perturbation and the stochastic bifurcation diagram characterizing the onset of multimodality in protein number distributions.
| S-EPMC6098115 | biostudies-literature
Project description:BackgroundWireless links are fast becoming the key communication mode. However, as compared to the wired link, their characteristics make the traffic prone to time- and location-dependent signal attenuation, noise, fading, and interference that result in time varying channel capacities and link error rate. Scheduling algorithms play an important role in wireless links to guarantee quality of service (QoS) parameters such as throughput, delay, jitter, fairness and packet loss rate. The scheduler has vital importance in current as well as future cellular communications since it assigns resource block (RB) to different users for transmission. Scheduling algorithm makes a decision based on the information of link state, number of sessions, reserved rates and status of the session queues. The information required by a scheduler implemented in the base station can easily be collected from the downlink transmission.MethodsThis paper reflects on the importance of schedulers for future wireless communications taking LTE-A networks as a case study. It compares the performance of four well-known scheduling algorithms including round robin (RR), best channel quality indicator (BCQI), proportional fair (PF), and fractional frequency reuse (FFR). The performance of these four algorithms is evaluated in terms of throughput, fairness index, spectral efficiency and overall effectiveness. System level simulations have been performed using a MATLAB based LTE-A Vienna downlink simulator.ResultsThe results show that the FFR scheduler is the best performer among the four tested algorithms. It also exhibits flexibility and adaptability for radio resource assignment.
| S-EPMC8157178 | biostudies-literature
Project description:This paper develops a likelihood-based approach to analyze quantile regression (QR) models for continuous longitudinal data via the asymmetric Laplace distribution (ALD). Compared to the conventional mean regression approach, QR can characterize the entire conditional distribution of the outcome variable and is more robust to the presence of outliers and misspecification of the error distribution. Exploiting the nice hierarchical representation of the ALD, our classical approach follows a Stochastic Approximation of the EM (SAEM) algorithm in deriving exact maximum likelihood estimates of the fixed-effects and variance components. We evaluate the finite sample performance of the algorithm and the asymptotic properties of the ML estimates through empirical experiments and applications to two real life datasets. Our empirical results clearly indicate that the SAEM estimates outperforms the estimates obtained via the combination of Gaussian quadrature and non-smooth optimization routines of the Geraci and Bottai (2014) approach in terms of standard errors and mean square error. The proposed SAEM algorithm is implemented in the R package qrLMM().
| S-EPMC5667718 | biostudies-literature
Project description:BackgroundFluorescent and luminescent gene reporters allow us to dynamically quantify changes in molecular species concentration over time on the single cell level. The mathematical modeling of their interaction through multivariate dynamical models requires the development of effective statistical methods to calibrate such models against available data. Given the prevalence of stochasticity and noise in biochemical systems inference for stochastic models is of special interest. In this paper we present a simple and computationally efficient algorithm for the estimation of biochemical kinetic parameters from gene reporter data.ResultsWe use the linear noise approximation to model biochemical reactions through a stochastic dynamic model which essentially approximates a diffusion model by an ordinary differential equation model with an appropriately defined noise process. An explicit formula for the likelihood function can be derived allowing for computationally efficient parameter estimation. The proposed algorithm is embedded in a Bayesian framework and inference is performed using Markov chain Monte Carlo.ConclusionThe major advantage of the method is that in contrast to the more established diffusion approximation based methods the computationally costly methods of data augmentation are not necessary. Our approach also allows for unobserved variables and measurement error. The application of the method to both simulated and experimental data shows that the proposed methodology provides a useful alternative to diffusion approximation based methods.
| S-EPMC2774326 | biostudies-literature