Abstract :
In this paper, a novel O(N2) algorithm is presented to minimize the weighted number of tardy jobs with unit processing times, integer ready times and deadlines, and M homogeneous parallel machines, where N is the number of jobs to be scheduled. wi is the weight reflecting job iʹs importance, and Ui is 1 if job i is tardy and 0 otherwise, so ΣwiUi is the measure of performance. (In standard notation, this is the P/ri, pi = 1/ΣwiUi problem.) This algorithm is extended to minimize weighted completion time ΣwiCi for some jobs, where completion time Ci is the time job i completes processing, and ΣwiUi for other jobs, at the same complexity. (The P/ri, pi = 1/ΣwiUi & ΣwiCi problem.) Complexity can be reduced to O(N log N) if all ready times are the same (with one additional constraint on weights). (P/pi = 1/ΣwiUi & ΣwiCi.) Finally, if one is trying to find the number of tardy jobs of each weight under optimal scheduling, but an actual schedule is not needed, this (P/ri, pi = 1/ΣwiUi) problem can be solved with an O(WN log N) algorithm, where W is the number of different weight values. In some cases, this can be done analytically.
