Heuristics for unrelated machine scheduling with precedence constraints

被引：34

作者：

Herrmann, J ^{[1
]}

Proth, JM ^{[1
]}

Sauer, N ^{[1
]}

机构：

[1] INRIA LORRAINE, F-57070 METZ, FRANCE

来源：

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1997年 / 102卷 / 03期

关键词：

scheduling; parallel resources; makespan;

D O I：

10.1016/S0377-2217(96)00247-0

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we consider the problem of scheduling tasks on unrelated parallel machines. Precedence constraints between the tasks form chains of tasks. We propose a number of heuristics in order to find near optimal solutions to the problem. Empirical results show that the heuristics are able to find very good approximate solutions. (C) 1997 Elsevier Science B.V.

引用

收藏

页码：528 / 537

页数：10

相关论文

共 14 条

[1] A STATE-OF-THE-ART REVIEW OF PARALLEL-MACHINE SCHEDULING RESEARCH [J].

CHENG, TCE ;

SIN, CCS .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1990, 47 (03) :271-292

[2] PARALLEL ALGORITHMS FOR CHIP PLACEMENT BY SIMULATED ANNEALING [J].

DAREMA, F ;

KIRKPATRICK, S ;

NORTON, VA .

IBM JOURNAL OF RESEARCH AND DEVELOPMENT, 1987, 31 (03) :391-402

[3] ALGORITHMS FOR SCHEDULING TASKS ON UNRELATED PROCESSORS [J].

DAVIS, E ;

JAFFE, JM .

JOURNAL OF THE ACM, 1981, 28 (04) :721-736

[4] SCHEDULING CHAIN-STRUCTURED TASKS TO MINIMIZE MAKESPAN AND MEAN FLOW TIME [J].

DU, JZ ;

LEUNG, JYT ;

YOUNG, GH .

INFORMATION AND COMPUTATION, 1991, 92 (02) :219-236

[5] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES [J].

GRAHAM, RL .

BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09) :1563-+

[6] HEURISTICS FOR SCHEDULING UNRELATED PARALLEL MACHINES [J].

HARIRI, AMA ;

POTTS, CN .

COMPUTERS & OPERATIONS RESEARCH, 1991, 18 (03) :323-331

[7] Scheduling Jobs with Simple Precedence Constraints on Parallel Machines [J].

Hoitomt, Debra J. ;

Luh, Peter B. ;

Max, Eric ;

Pattipati, Krishna R. .

IEEE CONTROL SYSTEMS MAGAZINE, 1990, 10 (02) :34-40

[8]

IBARRA OH, 1977, J ASSOC COMPUT MACH, V24, P280, DOI DOI 10.1145/322003.322011

[9] OPTIMIZATION BY SIMULATED ANNEALING - AN EXPERIMENTAL EVALUATION .1. GRAPH PARTITIONING [J].

JOHNSON, DS ;

ARAGON, CR ;

MCGEOCH, LA ;

SCHEVON, C .

OPERATIONS RESEARCH, 1989, 37 (06) :865-892

[10] OPTIMIZATION BY SIMULATED ANNEALING [J].

KIRKPATRICK, S ;

GELATT, CD ;

VECCHI, MP .

SCIENCE, 1983, 220 (4598) :671-680