Optimal dynamic scheduling of a general class of parallel-processing queueing systems

被引：5

作者：

Gans, N ^{[1
]}

Van Ryzin, G

机构：

[1] Univ Penn, Wharton Sch, OPIM Dept, Philadelphia, PA 19104 USA

[2] Columbia Univ, Grad Sch Business, New York, NY 10027 USA

来源：

ADVANCES IN APPLIED PROBABILITY | 1998年 / 30卷 / 04期

关键词：

parallel processor queueing systems; dynamic nonpreemptive scheduling; optimal stochastic control;

D O I：

10.1017/S0001867800008831

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

In this paper we develop policies for scheduling dynamically arriving jobs to a broad class of parallel-processing queueing systems. We show that in heavy traffic the policies asymptotically minimize a measure of the expected system backlog, which we call system work. Our results yield succinct, closed-form expressions for optimal system work in heavy traffic.

引用

页码：1130 / 1156

页数：27

共 13 条

[1] SCHEDULING AND STABILITY ASPECTS OF A GENERAL-CLASS OF PARALLEL PROCESSING SYSTEMS [J].

BAMBOS, N ;

WALRAND, J .

ADVANCES IN APPLIED PROBABILITY, 1993, 25 (01) :176-202

[2]

BAZARAA MS, 1990, LINEAR PROGRAMMING N

[3] ON OPTIMAL PACKING OF RANDOMLY ARRIVING OBJECTS [J].

COURCOUBETIS, C ;

ROTHBLUM, UG .

MATHEMATICS OF OPERATIONS RESEARCH, 1991, 16 (01) :176-194

[4] STABILITY OF FLEXIBLE MANUFACTURING SYSTEMS [J].

COURCOUBETIS, C ;

WEBER, R .

OPERATIONS RESEARCH, 1994, 42 (05) :947-957

[5] BAHADUR REPRESENTATION OF SAMPLE QUANTILES [J].

DEHAAN, L ;

TACONISHAANTJES, E .

ANNALS OF THE INSTITUTE OF STATISTICAL MATHEMATICS, 1979, 31 (02) :299-308

[6]

Feller W., 1957, INTRO PROBABILITY TH, VI

[7] THE RATE OF CONVERGENCE TO OPTIMALITY OF THE LPT RULE [J].

FRENK, JBG ;

KAN, AHGR .

DISCRETE APPLIED MATHEMATICS, 1986, 14 (02) :187-197

[8] THE ASYMPTOTIC OPTIMALITY OF THE LPT RULE [J].

FRENK, JBG ;

KAN, AHGR .

MATHEMATICS OF OPERATIONS RESEARCH, 1987, 12 (02) :241-254

[9] Optimal control of a multiclass, flexible queueing system [J].

Gans, N ;

VanRyzin, G .

OPERATIONS RESEARCH, 1997, 45 (05) :677-693

[10]

Karlin S., 1981, 2 COURSE STOCHASTIC

← 1 2 →