Minimizing Total Weighted Completion Time on Uniform Machines with Unbounded Batch

摘要

In this paper,we consider the scheduling problem of minimizing total weighted com pletion time on uniform machines with unbounded batch.Each of the machine Ml (l=1.……,m) has a speed sl and can process up to B (≥n) jobs simultaneously as a batch. The processing time of a batch denoted by P(B) is given by the processing time of the longest job in it,and the running time of the batch on machine Ml is P(B)/sl.We present some useful properties of the optimal schedule,and then design an O(nm+2) time backward dynamic programming algorithm for the problem.