New Bounds for the Identical Parallel Processor Weighted Flow Time Problem

In 1964, Eastman, Even, and Isaacs (EEI) presented a polynomial time lower bound for the NP-hard problem of scheduling n jobs on m available and identical processors to minimize weighted flow time. A general bound, of which the EEI bound is a special case, is proposed. Four new bounds for the identical processor problem are given. All of the new bounds can be applied to problems with variable processor ready times. The EEI bound is limited to problems where all processors are initially available at the same time. Two of the four new bounds are shown to dominate the EEI bound. The two other bounds are found to be effective for a particular problem class. Two polynomial time lower bounds for problems with nonidentical processors are introduced. One bound is applicable to the uniform processor problem, the other bound can be applied to the general processor problem. No bounds have previously been proposed for these problems.