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

Edwin Tai Chiu Cheng; Hans Kellerer; Vladimir Kotov

doi:10.1016/j.tcs.2004.11.018

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

Edwin Tai Chiu Cheng, Hans Kellerer, Vladimir Kotov

Research output: Journal article publication › Journal article › Academic research › peer-review

43 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	134-146
Number of pages	13
Journal	Theoretical Computer Science
Volume	337
Issue number	1-3
DOIs	https://doi.org/10.1016/j.tcs.2004.11.018
Publication status	Published - 9 Jun 2005

Keywords

Approximation algorithms
Bin stretching
Multiprocessor scheduling
On-line algorithms
Semi-on-line algorithms

ASJC Scopus subject areas

Computational Theory and Mathematics

More information

10.1016/j.tcs.2004.11.018

http://hdl.handle.net/10397/632

Cite this

@article{56413dc4888644389b0fd1c4aefc9183,

title = "Semi-on-line multiprocessor scheduling with given total processing time",

abstract = "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.",

keywords = "Approximation algorithms, Bin stretching, Multiprocessor scheduling, On-line algorithms, Semi-on-line algorithms",

author = "Cheng, {Edwin Tai Chiu} and Hans Kellerer and Vladimir Kotov",

year = "2005",

month = jun,

day = "9",

doi = "10.1016/j.tcs.2004.11.018",

language = "English",

volume = "337",

pages = "134--146",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

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

AU - Cheng, Edwin Tai Chiu

AU - Kellerer, Hans

AU - Kotov, Vladimir

PY - 2005/6/9

Y1 - 2005/6/9

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Bin stretching

KW - Multiprocessor scheduling

KW - On-line algorithms

KW - Semi-on-line algorithms

UR - http://www.scopus.com/inward/record.url?scp=18444407803&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2004.11.018

DO - 10.1016/j.tcs.2004.11.018

M3 - Journal article

SN - 0304-3975

VL - 337

SP - 134

EP - 146

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this