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:The objectives of this study were to develop an efficient algorithm for calculating prediction error variances (PEVs) for genomic best linear unbiased prediction (GBLUP) models using the Algorithm for Proven and Young (APY), extend it to single-step GBLUP (ssGBLUP), and apply this algorithm for approximating the theoretical reliabilities for single- and multiple-trait models in ssGBLUP. The PEV with APY was calculated by block sparse inversion, efficiently exploiting the sparse structure of the inverse of the genomic relationship matrix with APY. Single-step GBLUP reliabilities were approximated by combining reliabilities with and without genomic information in terms of effective record contributions. Multi-trait reliabilities relied on single-trait results adjusted using the genetic and residual covariance matrices among traits. Tests involved two datasets provided by the American Angus Association. A small dataset (Data1) was used for comparing the approximated reliabilities with the reliabilities obtained by the inversion of the left-hand side of the mixed model equations. A large dataset (Data2) was used for evaluating the computational performance of the algorithm. Analyses with both datasets used single-trait and three-trait models. The number of animals in the pedigree ranged from 167,951 in Data1 to 10,213,401 in Data2, with 50,000 and 20,000 genotyped animals for single-trait and multiple-trait analysis, respectively, in Data1 and 335,325 in Data2. Correlations between estimated and exact reliabilities obtained by inversion ranged from 0.97 to 0.99, whereas the intercept and slope of the regression of the exact on the approximated reliabilities ranged from 0.00 to 0.04 and from 0.93 to 1.05, respectively. For the three-trait model with the largest dataset (Data2), the elapsed time for the reliability estimation was 11 min. The computational complexity of the proposed algorithm increased linearly with the number of genotyped animals and with the number of traits in the model. This algorithm can efficiently approximate the theoretical reliability of genomic estimated breeding values in ssGBLUP with APY for large numbers of genotyped animals at a low cost.
| S-EPMC8827023 | biostudies-literature
Project description:Although a wide range of literature has investigated the network-level highway maintenance plans and policies, few of them focused on the maintenance scheduling problem. This study proposes a methodology framework to model and compare two different maintenance scheduling strategies for highway networks, i.e., minimal makespan strategy (MMS) and minimal increased travel delay strategy (MITDS). We formulate MMS as a mixed integer linear programming model subject to the constraints of the quantity of manpower and the worst-first maintenance sequence. A bi-level programming model is proposed to quantify and optimize MITDS. The upper level model determines the optimal scheduling to minimize the increased traffic delays during the maintenance makespan. In the lower level, a modified day-to-day traffic assignment model is put forward to reflect the traffic evolution dynamics by simulating travelers' route choice behaviors. A simulated annealing algorithm and augmented Lagrange algorithm are employed to solve the two proposed models, respectively. Finally, a numerical example using a highway network is developed. The two proposed strategies are tested considering different traffic demands, numbers of engineering teams, and travelers' sensitivities to traffic congestion. The experiment results reveal that compared with MMS, MITDS extends makespan by 2 days though, it reduces the total increased travel delays by 4% and both MMS and MITDS can obtain the minimum total increased travel delays when the number of engineering teams is 6. The sensitivity analysis indicates that both the two strategies have the maximum and minimum total increased travel delays when the weight of prediction in travelers' perception is 0.3 and 0.7, respectively. The proposed framework has the potential to provide reference in implementing highway maintenance activities reasonably.
| S-EPMC9176791 | biostudies-literature
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:We consider in this work a bicriteria scheduling problem on two different parallel machines with a periodic preventive maintenance policy. The two objectives considered involve minimization of job rejection costs and weighted sum of completion times. They are handled through a lexicographic approach, due to a natural hierarchy among the two objectives in the applications considered. The main contributions of this paper are first to present a new problem relevant to practice, second, to develop a mixed-integer-linear-program model for the problem, and third, to introduce two generalizable tabu-search metaheuristics relying on different neighborhood structures and solution spaces. Computational results for 120 instances (generated from a real case) are reported to empirically demonstrate the effectiveness of the proposed metaheuristics.
| S-EPMC8929393 | biostudies-literature
Project description:BackgroundDespite existing research on text mining and machine learning for title and abstract screening, the role of machine learning within systematic literature reviews (SLRs) for health technology assessment (HTA) remains unclear given lack of extensive testing and of guidance from HTA agencies. We sought to address two knowledge gaps: to extend ML algorithms to provide a reason for exclusion-to align with current practices-and to determine optimal parameter settings for feature-set generation and ML algorithms.MethodsWe used abstract and full-text selection data from five large SLRs (n = 3089 to 12,769 abstracts) across a variety of disease areas. Each SLR was split into training and test sets. We developed a multi-step algorithm to categorize each citation into the following categories: included; excluded for each PICOS criterion; or unclassified. We used a bag-of-words approach for feature-set generation and compared machine learning algorithms using support vector machines (SVMs), naïve Bayes (NB), and bagged classification and regression trees (CART) for classification. We also compared alternative training set strategies: using full data versus downsampling (i.e., reducing excludes to balance includes/excludes because machine learning algorithms perform better with balanced data), and using inclusion/exclusion decisions from abstract versus full-text screening. Performance comparisons were in terms of specificity, sensitivity, accuracy, and matching the reason for exclusion.ResultsThe best-fitting model (optimized sensitivity and specificity) was based on the SVM algorithm using training data based on full-text decisions, downsampling, and excluding words occurring fewer than five times. The sensitivity and specificity of this model ranged from 94 to 100%, and 54 to 89%, respectively, across the five SLRs. On average, 75% of excluded citations were excluded with a reason and 83% of these citations matched the reviewers' original reason for exclusion. Sensitivity significantly improved when both downsampling and abstract decisions were used.ConclusionsML algorithms can improve the efficiency of the SLR process and the proposed algorithms could reduce the workload of a second reviewer by identifying exclusions with a relevant PICOS reason, thus aligning with HTA guidance. Downsampling can be used to improve study selection, and improvements using full-text exclusions have implications for a learn-as-you-go approach.
| S-EPMC7734810 | 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