摘要
We consider scheduling problems with m machines in parallel and n jobs. Themachines are subject to breakdown and repair. Jobs have exponentially distributedprocessing times and possibly random release dates. For cost functions that onlydepend on the set of uncompleted jobs at time t we provide necessary and sufficientconditions for the LEPT rule to minimize the expected cost at all t within the class ofpreemptive policies. This encompasses results that are known for makespan, andprovides new results for the work remaining at time t. An application is that if the cyirule has the same priority assignment as the LEPT rule then it minimizes theexpected weighted number of jobs in the system for all t. Given appropriateconditions, we also show that the cy rule minimizes the expected value of otherobjective functions, such as weighted sum ofjob completion times, weighted numberof late jobs, or weighted sum of job tardinesses, when jobs have a common randomdue date.