SOCIALLY AND INDIVIDUALLY OPTIMAL ROUTING OF STOCHASTIC JOBS IN PARALLEL PROCESSOR SYSTEMS
成果类型：
Article
署名作者：
XU, SH
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.40.2.367
发表日期：
1992
页码：
367-375
关键词：
摘要：
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.