Dataset Information

Single machine scheduling and due date assignment with past-sequence-dependent setup time and position-dependent processing time.

ABSTRACT: This paper considers single machine scheduling and due date assignment with setup time. The setup time is proportional to the length of the already processed jobs; that is, the setup time is past-sequence-dependent (p-s-d). It is assumed that a job's processing time depends on its position in a sequence. The objective functions include total earliness, the weighted number of tardy jobs, and the cost of due date assignment. We analyze these problems with two different due date assignment methods. We first consider the model with job-dependent position effects. For each case, by converting the problem to a series of assignment problems, we proved that the problems can be solved in O(n(4)) time. For the model with job-independent position effects, we proved that the problems can be solved in O(n(3)) time by providing a dynamic programming algorithm.

SUBMITTER: Zhao CL

PROVIDER: S-EPMC4167446 | biostudies-other | 2014

REPOSITORIES: biostudies-other

ACCESS DATA

Similar Datasets

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.

Dataset Information

Single machine scheduling and due date assignment with past-sequence-dependent setup time and position-dependent processing time.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets