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.
- Parallel machines
- Priority rule
ASJC Scopus subject areas
- General Computer Science
- Modeling and Simulation
- Management Science and Operations Research
- Information Systems and Management