ON THE OPTIMALITY OF LEPT AND MU-C RULES FOR PARALLEL PROCESSORS AND DEPENDENT ARRIVAL PROCESSES

被引：11

作者：

HORDIJK, A

KOOLE, G

机构：

来源：

ADVANCES IN APPLIED PROBABILITY | 1993年 / 25卷 / 04期

关键词：

STOCHASTIC SCHEDULING; DYNAMIC PROGRAMMING; DEPENDENT ARRIVALS;

D O I：

10.2307/1427802

中图分类号：

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

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

In this paper we study scheduling problems of multiclass customers on identical parallel processors. A new type of arrival process, called a Markov decision arrival process, is introduced. This arrival process can be controlled and allows for an indirect dependence on the numbers of customers in the queues. As a special case we show the optimality of LEPT and the muc-rule in the last node of a controlled tandem network for various cost structures. A unifying proof using dynamic programming is given.

引用

收藏

页码：979 / 996

页数：18

相关论文

共 24 条

[1] MARKED POINT-PROCESSES AS LIMITS OF MARKOVIAN ARRIVAL STREAMS [J].

ASMUSSEN, S ;

KOOLE, G .

JOURNAL OF APPLIED PROBABILITY, 1993, 30 (02) :365-372

[2] K COMPETING QUEUES WITH GEOMETRIC SERVICE REQUIREMENTS AND LINEAR COSTS - THE MU-C-RULE IS ALWAYS OPTIMAL [J].

BARAS, JS ;

MA, DJ ;

MAKOWSKI, AM .

SYSTEMS & CONTROL LETTERS, 1985, 6 (03) :173-180

[3] 2 COMPETING QUEUES WITH LINEAR COSTS AND GEOMETRIC SERVICE REQUIREMENTS - THE MU-C-RULE IS OFTEN OPTIMAL [J].

BARAS, JS ;

DORSEY, AJ ;

MAKOWSKI, AM .

ADVANCES IN APPLIED PROBABILITY, 1985, 17 (01) :186-209

[4] SEQUENCING TASKS WITH EXPONENTIAL SERVICE TIMES TO MINIMIZE THE EXPECTED FLOW TIME OR MAKESPAN [J].

BRUNO, J ;

DOWNEY, P ;

FREDERICKSON, GN .

JOURNAL OF THE ACM, 1981, 28 (01) :100-113

[5] THE C-MU RULE REVISITED [J].

BUYUKKOC, C ;

VARAIYA, P ;

WALRAND, J .

ADVANCES IN APPLIED PROBABILITY, 1985, 17 (01) :237-238

[6] ON THE OPTIMALITY OF LEPT AND C-MU RULES FOR MACHINES IN PARALLEL [J].

CHANG, CS ;

CHAO, XL ;

PINEDO, M ;

WEBER, R .

JOURNAL OF APPLIED PROBABILITY, 1992, 29 (03) :667-681

[7]

Hordijk A., 1992, PROBAB ENG INFORM SC, V6, P495, DOI [10.1017/S0269964800002692, DOI 10.1017/S0269964800002692]

[8]

HORDIJK A, 1992, PROB ENG INF SCI, V24, P234

[9] OPTIMAL SCHEDULING OF JOBS WITH EXPONENTIAL SERVICE TIMES ON IDENTICAL PARALLEL PROCESSORS [J].

KAMPKE, T .

OPERATIONS RESEARCH, 1989, 37 (01) :126-133

[10]

KOOLE G, 1992, THESIS U LEIDEN