Scheduling jobs with exponentially distributed processing times and intree precedence constraints on two parallel machines. (English) Zbl 0581.90036

Pinedo, Michael; Weiss, Gideon

Oper. Res. 33, 1381-1388 (1985).

A set of jobs with independent exponentially distributed processing times is to be processed on two identical parallel machines, subject to intree precedence constraints. A job is said to be at level \(\ell\) if its successor is at level \(\ell -1\), while the job without successor is at level 0. If all jobs at level \(\ell\) have independent and identically exponentially distributed processing times with mean \(1/\mu_{\ell}\), then the ’highest level first’ policy is shown to minimize expected makespan. This generalizes a previous result of Chandy and Reynolds.

Reviewer: J.K.Lenstra

MSC:

90B35

Deterministic scheduling theory in operations research

Keywords:

highest level first policy; stochastic scheduling; independent exponentially distributed processing times; two identical parallel machines; intree precedence constraints; expected makespan