Scheduling stochastic jobs with due dates on parallel machines (Q750283)

Jobs with random processing times, random due dates, and weights are to be scheduled on parallel machines so as to minimize the expected total weight of tardy jobs. Under various assumptions, optimal policies are presented both for static lists and dynamic schedules, preemptive and non-preemptive. It was found that the assumption of i.i.d. job processing times is generally necessary to obtain analytic results. However, results that can be achieved for identical processors usually extend to uniform processors. When the jobs do not have different weights, it often becomes possible to allow their processing time distributions to differ.