scientific article; zbMATH DE number 3906216

From MaRDI portal
Publication:3683873





[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.











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)