Semi-on-line multiprocessor scheduling with given total processing time (Q557814): Difference between revisions

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.