A new formulation for scheduling unrelated processor under precedence constraints

被引：3

作者：

Maculan, N

Porto, SCS

Ribeiro, CC

de Souza, CC

机构：

[1] Univ Fed Rio de Janeiro, COPPE, BR-21945970 Rio De Janeiro, Brazil

[2] Univ Fed Fluminense, Dept Telecommun Engn, BR-24210 Niteroi, RJ, Brazil

[3] Pontificia Univ Catolica Rio de Janeiro, Dept Informat, BR-22453900 Rio De Janeiro, Brazil

[4] Univ Estadual Campinas, Dept Ciencia Comp, BR-13081 Campinas, Brazil

来源：

RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH | 1999年 / 33卷 / 01期

关键词：

parallel processing; scheduling; unrelated processors; precedence constraints; makespan;

D O I：

10.1051/ro:1999106

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We give a new formulation for the problem of task scheduling into unrelated processors under precedence constraints. This formulation has a polynomial number of variables variables and does not require that the processing times be integer valued.

引用

页码：87 / 92

页数：6

共 13 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

Bertsekas Dimitri P., 1989, PARALLEL DISTRIBUTED

[3]

Bla~zewicz J, 1986, ANN OPER RES

[4]

BLAZEWICZ J, 1993, COMMUNICATION

[5]

Coffman Edward Grady, 1973, Operating Systems Theory

[6] STRONG NP-COMPLETENESS RESULTS - MOTIVATION, EXAMPLES, AND IMPLICATIONS [J].

GAREY, MR ;

JOHNSON, DS .

JOURNAL OF THE ACM, 1978, 25 (03) :499-508

[7]

LASSERRE JB, P 2 INT PROGR COMB O, P136

[8]

LAWLER EL, 1989, 118903 NFI EINDH I T

[9]

Menasce D. A., 1992, Proceedings. Sixth International Parallel Processing Symposium (Cat. No.92TH0419-2), P186, DOI 10.1109/IPPS.1992.223049

[10]

Nemhauser GL, 1988, INTEGER COMBINATORIA

← 1 2 →