New Heuristics and Integer Programming Formulations for Schedulini! Divisible Load Tasks

被引：2

作者：

Abib, Elbio R. T. ^{[1
]}

Ribeiro, Celso C. ^{[2
]}

机构：

[1] Microsoft Corp, 1 Microsoft Way, Redmond, WA 98052 USA

[2] Univ Fed Fluminense, Dept Comp Sci, BR-24210 Niteroi, RJ, Brazil

来源：

2009 IEEE SYMPOSIUM ON COMPUTATIONAL INTELLIGENCE IN SCHEDULING: (CI-SCHED) | 2009年

关键词：

ALGORITHMS; JOBS;

D O I：

10.1109/SCIS.2009.4927015

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Divisible load applications occur in many fields of science and engineering. They can be parallelized in a master-worker fashion, but they pose several scheduling challenges. We propose single-round and multi-round integer programming formulations for scheduling divisible load applications with minimum makespan. An innovative linear-time exact algorithm improving the complexity of the best known algorithm to date is described for the special case in which the processor activation order is known beforehand. This algorithm is embedded within a greedy-with-feedback heuristic for finding good solutions for single-round problems. Numerical results illustrate the speed and the effectiveness of the proposed heuristic.

引用

页码：54 / +

页数：3

共 17 条

[1]

ALDA W, 1993, 9358 UMSI

[2]

Altilar DT, 2002, LECT NOTES COMPUT SC, V2400, P197

[3]

[Anonymous], COMMUNICATIONS ACM

[4]

[Anonymous], 1996, Scheduling divisible loads in parallel and distributed systems

[5] Scheduling divisible loads on star and tree networks: Results and open problems [J].

Beaumont, O ;

Casanova, H ;

Legrand, A ;

Robert, Y ;

Yang, Y .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (03) :207-218

[6]

BEAUMONT O, 2003, P 17 INT S PAR DISTR

[7]

BLANC JY, 1990, LECT NOTES COMPUT SC, V457, P467

[8] Scheduling divisible jobs on hypercubes [J].

Blazewicz, J ;

Drozdowski, M .

PARALLEL COMPUTING, 1995, 21 (12) :1945-1956

[9] Distributed processing of divisible jobs with communication startup costs [J].

Blazewicz, J ;

Drozdowski, M .

DISCRETE APPLIED MATHEMATICS, 1997, 76 (1-3) :21-41

[10] DISTRIBUTED COMPUTATION WITH COMMUNICATION DELAY [J].

CHENG, YC ;

ROBERTAZZI, TG .

IEEE TRANSACTIONS ON AEROSPACE AND ELECTRONIC SYSTEMS, 1988, 24 (06) :700-712

← 1 2 →