New Bounds for the Identical Parallel Processor Weighted Flow Time Problem
针对NP难的相同并行处理器加权流程时间调度问题，提出了四个新的下界，其中两个优于1964年EEI下界，另两个对特定问题类有效；还首次给出了非相同处理器问题的多项式时间下界。
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.