Semi-on-line multiprocessor scheduling with given total processing time (Q557814): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / author | |||
Property / author: Cheng, T. C. Edwin / rank | |||
Normal rank | |||
Property / review text | |||
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. | |||
Property / review text: 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. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jacek Błażewicz / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68M20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68W40 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90B35 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 2184050 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
on-line algorithms | |||
Property / zbMATH Keywords: on-line algorithms / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
multiprocessor scheduling | |||
Property / zbMATH Keywords: multiprocessor scheduling / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
approximation algorithms | |||
Property / zbMATH Keywords: approximation algorithms / rank | |||
Normal rank |
Revision as of 15:09, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Semi-on-line multiprocessor scheduling with given total processing time |
scientific article |
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