Preemptive Scheduling to Minimize Maximum Completion Time on Uniform Processors with Memory Constraints

Charles Martel
Additional contact information
Charles Martel: University of California, Davis, California

Operations Research, 1985, vol. 33, issue 6, 1360-1380

Abstract: We consider the problem of preemptively scheduling n jobs on m processors. The i th job has a processing requirement p i and a memory requirement q i . The i th processor has a speed s i and a memory capacity c i . The i th job can be run on the j th processor whenever c j ≥ q i . When all jobs have a deadline D i we develop an O ( n log m ) time algorithm that finds a feasible schedule or determines that no such schedule exists. We then use this algorithm to find the minimum time by which all jobs can be completed in O ( nm log 2 m ) time.

Keywords: 64 preemptive scheduling of uniform processors; 581 uniform processors with memory constraints (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.33.6.1360 (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:33:y:1985:i:6:p:1360-1380

Access Statistics for this article

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