Parallel task scheduling

Parallel task scheduling (also called parallel job scheduling or parallel processing scheduling) is an <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a> in <a href="/facts/Computer_science/lN3pEyPz">computer science</a> and <a href="/facts/Operations_Research/H5yJkV5n">operations research</a>. It is a variant of <a href="/facts/Optimal_job_scheduling/XyUejB6y">optimal job scheduling</a>. In a general job scheduling problem, we are given n jobs J1, J2, ..., Jn of varying processing times, which need to be scheduled on m machines while trying to minimize the <a href="/facts/Makespan/w1HEjJaQ">makespan</a> - the total length of the schedule (that is, when all the jobs have finished processing). In the specific variant known as parallel-task scheduling, all machines are identical. Each job j has a length parameter pj and a size parameter qj, and it must run for exactly pj time-steps on exactly qj machines in parallel.
Veltman et al. and Drozdowski denote this problem by 
 
 
 
 P
 
 |
 
 s
 i
 z
 
 e
 
 j
 
 
 
 |
 
 
 C
 
 max
 
 
 
 
 {\displaystyle P|size_{j}|C_{\max }}
 
 in the <a href="/facts/Notation_for_theoretic_scheduling_problems/XyUejB6y">three-field notation</a> introduced by Graham et al. P means that there are several identical machines running in parallel; sizej means that each job has a size parameter; Cmax means that the goal is to minimize the maximum completion time. Some authors use 
 
 
 
 P
 
 |
 
 
 m
 
 j
 
 
 
 |
 
 
 C
 
 max
 
 
 
 
 {\displaystyle P|m_{j}|C_{\max }}
 
 instead. Note that the problem of <a href="/facts/Parallel-machines_scheduling/LFDtRUfD">parallel-machines scheduling</a> is a special case of parallel-task scheduling where 
 
 
 
 s
 i
 z
 
 e
 
 j
 
 
 =
 1
 
 
 {\displaystyle size_{j}=1}
 
 for all j, that is, each job should run on a single machine.
The origins of this problem formulation can be traced back to 1960. For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than 
 
 
 
 3
 
 /
 
 2
 
 
 {\displaystyle 3/2}
 
 unless 
 
 
 
 P
 =
 N
 P
 
 
 {\displaystyle P=NP}
 
.

Parallel task scheduling open-in-new

Parallel task scheduling