Socially and Individually Optimal Routing of Stochastic Jobs in Parallel Processor Systems

Susan H. Xu
Additional contact information
Susan H. Xu: The Pennsylvania State University, University Park, Pennsylvania

Operations Research, 1992, vol. 40, issue 2, 367-375

Abstract: This paper considers a stochastic system where a fixed number of nonpreemptive jobs (no new jobs arrive) are to be processed on multiple nonidentical processors. Each processor has an increasing hazard rate processing time distribution and the processors are ordered in ascending order of their expected processing times. It is shown that the policy which minimizes the total expected delay of all the jobs (flowtime) has a threshold structure. This policy would utilize the fastest available processor only if its mean processing time is less than a critical number. Furthermore, a previously rejected processor must never be utilized at later times. This policy is also individually optimal in the sense that it minimizes the delay of each job subject to the constraint that processor preference is given to jobs at the head of the buffer. This result proves the conjecture of P. R. Kumar and J. Walrand regarding socially and individually optimal policies in parallel routing systems.

Keywords: production/scheduling; sequencing; stochastic: multiple; uniform processor scheduling (search for similar items in EconPapers)
Date: 1992
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.40.2.367 (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:40:y:1992:i:2:p:367-375

Access Statistics for this article

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