Semi-on-line multiprocessor scheduling with given total processing time (Q557814)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2184050
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Semi-on-line multiprocessor scheduling with given total processing time |
scientific article; zbMATH DE number 2184050 |
Statements
Semi-on-line multiprocessor scheduling with given total processing time (English)
0 references
30 June 2005
0 references
In the paper, a classical multiprocessor scheduling problem is considered. A set of independent jobs is to be processed on \(m\) parallel, identical machines in order to minimize the makespan. The jobs arrive on-line, i.e., each job must be immediately assigned to one of the machines. A modification assumed in the paper is the knowledge of a sum of processing times of tasks which are supposed to arrive. The authors propose a new approximation algorithm with performance ratio 1.6.
0 references
on-line algorithms
0 references
multiprocessor scheduling
0 references
approximation algorithms
0 references
0.9384849667549132
0 references
0.925076425075531
0 references
0.8909432888031006
0 references
0.871408998966217
0 references
