Abstract
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.
Original language | English (US) |
---|---|
Pages (from-to) | 327-334 |
Number of pages | 8 |
Journal | European Journal of Operational Research |
Volume | 70 |
Issue number | 3 |
DOIs | |
State | Published - Nov 12 1993 |
Externally published | Yes |
Keywords
- Parallel machines
- Priority rule
- Scheduling
ASJC Scopus subject areas
- General Computer Science
- Modeling and Simulation
- Management Science and Operations Research
- Information Systems and Management