A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems

The problem of scheduling n jobs with known process times on m identical parallel machines with an objective of minimizing weighted flow time is NP-hard. However, when job weights are identical, it is well known that the problem is easily solved using the shortest processing time rule. In this paper, we show that a generalization of the shortest processing time rule minimizes weighted flow time in a class of problems where job weights are not identical.