Minimizing Flow Time on Parallel Identical Processors with Variable Unit Processing Time

I. Meilijson and A. Tamir
Additional contact information
I. Meilijson: Tel-Aviv University, Tel-Aviv, Israel
A. Tamir: Tel-Aviv University, Tel-Aviv, Israel

Operations Research, 1984, vol. 32, issue 2, 440-448

Abstract: We show that minimizing total flow time on parallel identical processors with nonincreasing unit processing time is achieved with shortest processing time (SPT) scheduling: Sequence the tasks in an order of nondecreasing lengths. Following this order and starting with the shortest task, process any task by the first processor that becomes available. If the unit processing time is allowed to be increasing, e.g., quadratically, the problem becomes NP-hard.

Keywords: 581; processors; with; variable; processing; rate (search for similar items in EconPapers)
Date: 1984
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.32.2.440 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:32:y:1984:i:2:p:440-448

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().