Single machine scheduling and due date assignment with past-sequence-dependent setup time and position-dependent processing time.
Ontology highlight
ABSTRACT:
SUBMITTER: Zhao CL
PROVIDER: S-EPMC4167446 | 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:We consider a common due-window assignment scheduling problem jobs with variable job processing times on a single machine, where the processing time of a job is a function of its position in a sequence (i.e., learning effect) or its starting time (i.e., deteriorating effect). The problem is to determine the optimal due-windows, and the processing sequence simultaneously to minimize a cost function includes earliness, tardiness, the window location, window size, and weighted number of tardy jobs. We prove that the problem can be solved in polynomial time.
| S-EPMC4396807 | biostudies-other
Project description:We consider a single-machine two-agent problem where the objective is to minimize a weighted combination of the total completion time and the total tardiness of jobs from the first agent given that no tardy jobs are allowed for the second agent. A branch-and-bound algorithm is developed to derive the optimal sequence and two simulated annealing heuristic algorithms are proposed to search for the near-optimal solutions. Computational experiments are also conducted to evaluate the proposed branch-and-bound and simulated annealing algorithms.
| S-EPMC3915531 | biostudies-other
Project description:PURPOSE:Interfraction tumor setup variations in radiotherapy are often reduced with image guidance procedures. Clinical target volume (CTV)-planning target volume (PTV) margins are then used to deal with residual errors. We have investigated characterization of setup errors in patient populations with explicit modelling of occurring interfraction time trends. METHODS:The core of a "trendline characterization" of observed setup errors in a population is a distribution of trendlines, each obtained by fitting a straight line through a patient's daily setup errors. Random errors are defined as daily deviations from the trendline. Monte Carlo simulations were performed to predict the impact of offline setup correction protocols on residual setup errors in patient populations with time trends. A novel CTV-PTV margin recipe was derived that assumes that systematic underdosing of tumor edges in multiple consecutive fractions, as caused by trend motion, should preferentially be avoided. Similar to the well-known approach by van Herk et al. for conventional error characterization (no explicit modelling of trends), only a predefined percentage of patients (generally 10%) was allowed to have nonrandom (systematic + trend) setup errors outside the margin. Additionally, a method was proposed to avoid erroneous results in Monte Carlo simulations with setup errors, related to decoupling of error sources in characterizations. The investigations were based on a database of daily measured setup errors in 835 prostate cancer patients that were treated with 39 fractions, and on Monte Carlo-generated patient populations with time trends. RESULTS:With conventional characterization of setup errors in patient populations with time trends, predicted standard deviations of residual systematic errors ( ?res ) after application of an offline correction protocol could be underestimated by more than 50%, potentially resulting in application of too small margins. With the new trendline characterization this was avoided. With the novel CTV-PTV margin recipe with an allowed 10% of patients having nonrandom errors outside the margin, the observed percentage was 10.0% ± 0.2%. When using conventional characterization of errors and the van Herk margin recipe, on average 58.0% ± 24.3% of patients had errors outside the margin, while 10% was prescribed. For populations with no time trends, the novel recipe simplifies to the generally applied M=2.5?+0.7? formula proposed by van Herk et al. CONCLUSIONS: In populations with time trends in setup errors, the use of trendline characterizations in Monte Carlo simulations for establishment of residual errors after a setup correction protocol can avoid application of erroneous margins. The novel margin recipe can be used to accurately control the percentage of patients with nonrandom errors outside the margin. In case of daily image guidance of patients with multiple targets with differential motion, the recipe can be used to establish margins for the targets that are not the primary target for the image guidance (e.g., nodal regions). Probabilistic planning might be improved by using trendline characterization for modelling of setup errors. Population analyses of interfraction setup errors need to take into account potential time trends.
| S-EPMC7027586 | biostudies-literature
Project description:The idea of "date" and "party" hubs has been influential in the study of protein-protein interaction networks. Date hubs display low co-expression with their partners, whilst party hubs have high co-expression. It was proposed that party hubs are local coordinators whereas date hubs are global connectors. Here, we show that the reported importance of date hubs to network connectivity can in fact be attributed to a tiny subset of them. Crucially, these few, extremely central, hubs do not display particularly low expression correlation, undermining the idea of a link between this quantity and hub function. The date/party distinction was originally motivated by an approximately bimodal distribution of hub co-expression; we show that this feature is not always robust to methodological changes. Additionally, topological properties of hubs do not in general correlate with co-expression. However, we find significant correlations between interaction centrality and the functional similarity of the interacting proteins. We suggest that thinking in terms of a date/party dichotomy for hubs in protein interaction networks is not meaningful, and it might be more useful to conceive of roles for protein-protein interactions rather than for individual proteins.
| S-EPMC2887459 | biostudies-literature
Project description:Coordinating the charging scheduling of electric vehicles for dynamic dial-a-ride services is challenging considering charging queuing delays and stochastic customer demand. We propose a new two-stage solution approach to handle dynamic vehicle charging scheduling to minimize the costs of daily charging operations of the fleet. The approach comprises two components: daily vehicle charging scheduling and online vehicle-charger assignment. A new battery replenishment model is proposed to obtain the vehicle charging schedules by minimizing the costs of vehicle daily charging operations while satisfying vehicle driving needs to serve customers. In the second stage, an online vehicle-charger assignment model is developed to minimize the total vehicle idle time for charges by considering queuing delays at the level of chargers. An efficient Lagrangian relaxation algorithm is proposed to solve the large-scale vehicle-charger assignment problem with small optimality gaps. The approach is applied to a realistic dynamic dial-a-ride service case study in Luxembourg and compared with the nearest charging station charging policy and first-come-first-served minimum charging delay policy under different charging infrastructure scenarios. Our computational results show that the approach can achieve significant savings for the operator in terms of charging waiting times (-74.9%), charging times (-38.6%), and charged energy costs (-27.4%). A sensitivity analysis is conducted to evaluate the impact of the different model parameters, showing the scalability and robustness of the approach in a stochastic environment.
| S-EPMC8136635 | biostudies-literature
Project description:We consider a single machine scheduling problem with multiple maintenance activities, where the maintenance duration function is of the linear form f(t) = a+bt with a ≥ 0 and b > 1. We propose an approximation algorithm named FFD-LS2I with a worst-case bound of 2 for problem. We also show that there is no polynomial time approximation algorithm with a worst-case bound less than 2 for the problem with b ≥ 0 unless P = NP, which implies that the FFD-LS2I algorithm is the best possible algorithm for the case b > 1 and that the FFD-LS algorithm, which is proposed in the literature, is the best possible algorithm for the case b ≤ 1 both from the worst-case bound point of view.
| S-EPMC3950368 | biostudies-other
Project description:Microfluidic impedance flow cytometers enable high-throughput, non-invasive, and label-free detection of single-cells. Cytometers with coplanar electrodes are easy and cheap to fabricate, but are sensitive to positional differences of passing particles, owing to the inhomogeneous electric field. We present a novel particle height compensation method, which employs the dependence of measured electrical opacity on particle height. The measured electrical opacity correlates with the particle height as a result of the constant electrical double layer series capacitance of the electrodes. As an alternative to existing compensation methods, we use only two coplanar electrodes and multi-frequency analysis to determine the particle size of a mixture of 5, 6, and 7 µm polystyrene beads with an accuracy (CV) of 5.8%, 4.0%, and 2.9%, respectively. Additionally, we can predict the bead height with an accuracy of 1.5 µm (8% of channel height) using the measured opacity and we demonstrate its application in flow cytometry with yeast. The use of only two electrodes is of special interest for simplified, easy-to-use chips with a minimum amount of instrumentation and of limited size.
| S-EPMC8533872 | biostudies-literature
Project description:DNA sequence predicted from polyacrylamide gel-based technologies is inaccurate because of variations in the quality of the primary data due to limitations of the technology, and to sequence-specific variations due to nucleotide interactions within the DNA molecule and with the gel. The ability to recognize the probability of error in the primary data will be useful in reconstructing the target sequence of a DNA sequencing project, and in estimating the accuracy of the final sequence. This paper describes the use of linear discriminant analysis to assign position-specific probabilities of incorrect, over- and under-prediction of nucleotides for each predicted nucleotide position in primary sequence data generated by a gel-based DNA sequencing technology. Using this method, most of the error potential in primary sequence data can be assigned to a limited number of discrete positions. The use of probability values in the sequence reconstruction process, and in estimating the accuracy of consensus sequence determination is described.
| S-EPMC523653 | biostudies-other
Project description:BackgroundSelective serotonin reuptake inhibitors (SSRIs) have a wide and increasing use for the treatment of depression and anxiety. Previous studies have indicated an increased risk of hyponatremia during the first months of treatment. We aimed to investigate the detailed time-course of SSRI-associated hyponatremia with a high temporal resolution, using registry data encompassing the total Swedish population.MethodsThis was a population-based case control study using several national registers. Patients hospitalized with a principal diagnosis of hyponatremia (n = 11,213) were compared with matched controls (n = 44,801). Multivariable regression was applied to explore time-dependent associations between SSRIs and hospitalization due to hyponatremia.ResultsIndividuals initiating treatment with SSRIs were exposed to an immediately increased risk for hospitalization at week 1, reaching an adjusted odds ratio (aOR) (95% confidence interval) of 29 (19-46). The associations then gradually declined, reaching an aOR of 2.1 (1.0-4.2) by week 13. The aOR for individuals treated for longer than 13 weeks was 0.78 (0.71-0.85).ConclusionsThis study revealed a dramatically increased risk of hyponatremia exclusively related to newly initiated treatment. Consequently, even subtle symptoms consistent with hyponatremia during the first weeks of SSRI treatment should prompt analysis of sodium levels. In patients treated with SSRIs for several months or years, other causes should primarily be sought in the event of hyponatremia.
| S-EPMC8358543 | biostudies-literature