Semi-on-line multiprocessor scheduling with given total processing time

被引：36

作者：

Cheng, TCE

Kellerer, H

Kotov, V

机构：

[1] Graz Univ, Inst Stat & Operat Res, A-8010 Graz, Austria

[2] Hong Kong Polytech Univ, Dept Logist, Kowloon, Hong Kong, Peoples R China

[3] Belarusian State Univ, Fac Appl Math & Comp Sci, Minsk 220050, BELARUS

来源：

THEORETICAL COMPUTER SCIENCE | 2005年 / 337卷 / 1-3期

关键词：

on-line algorithms; semi-on-line algorithms; bin stretching; multiprocessor scheduling; approximation algorithms;

D O I：

10.1016/j.tcs.2004.11.018

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We are given a set of identical machines and a sequence of jobs, the sum of whose weights is known in advance. The jobs are to be assigned on-line to one of the machines and the objective is to minimize the makespan. An algorithm with performance ratio 1.6 and a lower bound of 1.5 is presented. These results improve on the recent results by Azar and Regev, who proposed an algorithm with performance ratio 1.625 for the less general problem that the optimal makespan is known in advance. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：134 / 146

页数：13

共 10 条

[1] On-line bin-stretching
Azar, Y
Regev, O
[J]. THEORETICAL COMPUTER SCIENCE, 2001, 268 (01) : 17 - 41
[2] Bin stretching revisited
Epstein, L
[J]. ACTA INFORMATICA, 2003, 39 (02) : 97 - 117
[3] Faigle U., 1989, Acta Cybernetica, V9, P107
[4] Fleischer R., 2000, Journal of Scheduling, V3, P343, DOI 10.1002/1099-1425(200011/12)3:6<343::AID-JOS54>3.0.CO
[5] 2-2
[6] Gormley T, 2000, PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P564
[7] Graham R L., 1969, SIAM J APPL MATH, V17, P263
[8] BOUNDS FOR CERTAIN MULTIPROCESSING ANOMALIES
GRAHAM, RL
[J]. BELL SYSTEM TECHNICAL JOURNAL, 1966, 45 (09): : 1563 - +
[9] Semi on-line algorithms for the partition problem
Kellerer, H
Kotov, V
Speranza, MC
Tuza, Z
[J]. OPERATIONS RESEARCH LETTERS, 1997, 21 (05) : 235 - 242
[10] Sgall J, 1998, LECT NOTES COMPUT SC, V1442, P196, DOI 10.1007/BFb0029570

← 1 →