scientific article; zbMATH DE number 3906216
[For the entire collection see Zbl 0549.00028.] The paper gives a survey on recent developments in the theory of rather general non-preemptive stochastic scheduling problems. The general problem consists in the (on-line) non-preemptive scheduling of a set A of n activities (jobs) subject to arbitrary precedence constraints (represented by a partial order on A) and arbitrary time-independent resource constraints. Job processing times are random according to some arbitrary (but known) joint distribution P (permitting stochastic dependences), and the objective is to minimize the expected cost for some arbitrary regular performance measure (cost function) \(\kappa\), i.e. a nondecreasing function of the job completion times. This model covers most of the machine scheduling problems such as open shop, flow shop and job shop problems. The generality of the model requires a treatment as a dynamic optimization problem with finite horizon, but incountable state and action space, which leads to many new questions concerning stability and existence of optimal policies, measurability aspects etc. A main aspect in the paper is an equivalent interpretation of policies as functions from \({\mathbb{R}}^ n\) into \({\mathbb{R}}^ n\). This functional interpretation is characteristic for the non-preemptive model and a powerful tool for the development of the general theory. The theory is presented from three central viewpoints, viz optimality (existence of optimal policies), stability (which classes of policies have a satisfactory stability behaviour) and monotonicity (the monotinicity behaviour of classes of policies w.r.t. stochastically greater processing times). Main results covered are: optimality criteria; a sufficient condition for monotonicity of general policies in form of a separation condition of a stochastic process associated with the processing time distributions (covering the independence case); and a thourough discussion of new results for special classes of policies such as priority policies, ES- and MES-policies and set policies.
- Stochastic scheduling and forwards induction
- Bounds on optimal values in stochastic scheduling
- Linear preselective policies for stochastic project scheduling
- A concise survey of scheduling with time-dependent processing times
- When greediness fails: examples from stochastic scheduling.
- Some concepts of stability analysis in combinatorial optimization
- Rollout algorithms for stochastic scheduling problems
- An improved greedy algorithm for stochastic online scheduling on unrelated machines
- Stochastic scheduling problems I — General strategies
- A General Framework for Stochastic One-machine Scheduling Problems with Zero Release Times and No Partial Ordering
- scientific article; zbMATH DE number 5707114 (Why is no real title available?)
- Stochastic scheduling problems II-set strategies-
- scientific article; zbMATH DE number 4099021 (Why is no real title available?)
- scientific article; zbMATH DE number 4102843 (Why is no real title available?)
- Time complexity of single machine scheduling with stochastic precedence constraints
- Single-machine stochastic scheduling with dependent processing times
- A suboptimality bound for permutation policies in single machine stochastic scheduling
- Predetermined intervals for start times of activities in the stochastic project scheduling problem
- On a stochastic sequencing and scheduling problem
- Single-machine scheduling with general costs under compound-type distributions
- Stochastic scheduling in an in-forest
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3683873)