Stochastic scheduling problems II-set strategies-
[For part I see ibid. 28, 193-260 (1984; Zbl 0553.90059.] The paper introduces the finite class of set strategies for stochastic scheduling problems. It is shown that the known stable classes of strategies such as ES and MES strategies are of this type, as are list- scheduling strategies such as LEPT and SEPT and other, more complicated priority-type strategies. Roughly speaking, set strategies are characterized by the fact that the decision as to which jobs should be started at time t depends only on the knowledge of the two sets of jobs finished up to time t and being processed at time t. Contrary to list scheduling strategies, set strategies may involve deliberate idleness of machines, i.e. may not be greedy and can therefore not generally be induced by priority rules. It is demonstrated that set strategies have useful properties. They are e.g. \(\lambda^ n\)-almost everywhere continuous and therefore show satisfactory stability behaviour w.r.t. weak convergence of the joint distribution of job durations. Furthermore, the optimum w.r.t. all strategies is already attained on this class if job durations are independent and exponentially distributed and the performance measure fulfills a certain shift condition. This shift property is a quite natural concept and generalizes aspects of the notion of additivity in semi-Markov decision theory and stochastic dynamic optimization. Its complete analytical characterization is a major object of this paper. Typical additive cost criteria such as makespan and flowtime are of course covered, which yields simultaneously a first step towards generalization of opimality of LEPT and SEPT rules, as known for special cases. In fact, in view of the obtained optimality result, the question of when deliberate idleness of machines can be avoided, gains considerable interest, as it characterizes stochastic environments in which priority strategies are optimal. This provides a major link with current research on the analysis of networks of queues in the context of computer systems.
- Stochastic scheduling problems I — General strategies
- scientific article; zbMATH DE number 3906216
- On the scheduling of alternative stochastic jobs on a single machine
- scientific article; zbMATH DE number 4064442
- Scheduling jobs with stochastically ordered processing times on parallel machines to minimize expected flowtime
- Algorithmic approaches to preselective strategies for stochastic scheduling problems
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 3758087 (Why is no real title available?)
- scientific article; zbMATH DE number 3758089 (Why is no real title available?)
- scientific article; zbMATH DE number 3768969 (Why is no real title available?)
- scientific article; zbMATH DE number 3780553 (Why is no real title available?)
- scientific article; zbMATH DE number 3617891 (Why is no real title available?)
- scientific article; zbMATH DE number 3238721 (Why is no real title available?)
- scientific article; zbMATH DE number 3274494 (Why is no real title available?)
- scientific article; zbMATH DE number 3313523 (Why is no real title available?)
- scientific article; zbMATH DE number 3320878 (Why is no real title available?)
- scientific article; zbMATH DE number 3338194 (Why is no real title available?)
- scientific article; zbMATH DE number 3339023 (Why is no real title available?)
- scientific article; zbMATH DE number 3385032 (Why is no real title available?)
- Negative Dynamic Programming
- Preselective strategies for the optimization of stochastic project networks under resource constraints
- Scheduling tasks with exponential service times on non-identical processors to minimize various cost functions
- Stochastic optimal control. The discrete time case
- Stochastic scheduling problems I — General strategies
- Vorlesungen über Funktionalgleichungen und ihre Anwendungen
- New trends in machine scheduling
- Optimal match-up strategies in stochastic scheduling
- When greediness fails: examples from stochastic scheduling.
- Important classes of reactions for the proactive and reactive resource-constrained project scheduling problem
- Project scheduling under uncertainty: survey and research potentials
- Some concepts of stability analysis in combinatorial optimization
- Resource-constrained project scheduling: Notation, classification, models, and methods
- Advanced DSS for scheduling: Software engineering aspects and the role of eigenmodels
- Proactive policies for the stochastic resource-constrained project scheduling problem
- The proactive and reactive resource-constrained project scheduling problem
- On index policies for stochastic minsum scheduling
- Stochastic scheduling problems I — General strategies
- Worst‐case allocation algorithms in a complex of operations with interval parameters
- Nested Optimal Policies for Set Functions with Applications to Scheduling
- Greed works -- online algorithms for unrelated machine stochastic scheduling
- A tight 2-approximation for preemptive stochastic scheduling
- A novel hyper-heuristic based on surrogate genetic programming for the three-dimensional spatial resource-constrained project scheduling problem under uncertain environments
- Efficient priority rules for the stochastic resource-constrained project scheduling problem
- New directions in scheduling theory
- A classification of predictive-reactive project scheduling procedures
- When it is worthwhile to work with the stochastic RCPSP?
- A new heuristic for resource-constrained project scheduling in stochastic networks using critical chain concept
- Scheduling of project networks
This page was built for publication: Stochastic scheduling problems II-set strategies-
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3685553)