Parallel task scheduling (also called parallel job scheduling or parallel processing scheduling) is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. 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 makespan - 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 three-field notation 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 parallel-machines scheduling 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} .
Definition There is a set J {\displaystyle {\mathcal {J}}} of n {\displaystyle n} jobs, and m {\displaystyle m} identical machines. Each job j ∈ J {\displaystyle j\in {\mathcal {J}}} has a processing time p j ∈ N {\displaystyle p_{j}\in \mathbb {N} } (also called the length of j), and requires the simultaneous use of q j ∈ N {\displaystyle q_{j}\in \mathbb {N} } machines during its execution (also called the size or the width of j). A schedule assigns each job j ∈ J {\displaystyle j\in {\mathcal {J}}} to a starting time s j ∈ N 0 {\displaystyle s_{j}\in \mathbb {N} _{0}} and a set m j ⊆ { 1 , … , m } {\displaystyle m_{j}\subseteq \{1,\dots ,m\}} of | m j | = q j {\displaystyle |m_{j}|=q_{j}} machines to be processed on. A schedule is feasible if each processor executes at most one job at any given time. The objective of the problem denoted by P | s i z e j | C max {\displaystyle P|size_{j}|C_{\max }} is to find a schedule with minimum length C max = max j ∈ J ( s j + p j ) {\displaystyle C_{\max }=\max _{j\in {\mathcal {J}}}(s_{j}+p_{j})} , also called the makespan of the schedule. A sufficient condition for the feasibility of a schedule is the following
… excerpt ends here. Continue reading the full article.
