Parallel task scheduling

Parallel task scheduling (also called parallel job scheduling^[1][2] or parallel processing scheduling^[3]) 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 J₁, J₂, ..., J_n 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 p_j and a size parameter q_j, and it must run for exactly p_j time-steps on exactly q_j machines in parallel.

Veltman et al.^[4] and Drozdowski^[3] 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.^[5] P means that there are several identical machines running in parallel; size_j means that each job has a size parameter; C_max 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.^[1] 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.^[6] 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} .^{[citation needed]}

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

∑ j ∈ J , s j ≤ t < s j + p j q j ≤ m ∀ t ∈ { s 1 , … , s n } {\displaystyle \sum _{j\in {\mathcal {J}},s_{j}\leq t<s_{j}+p_{j}}q_{j}\leq m\,\forall t\in \{s_{1},\dots ,s_{n}\}} .

If this property is satisfied for all starting times, a feasible schedule can be generated by assigning free machines to the jobs at each time starting with time t = 0 {\displaystyle t=0} .^[1][2] Furthermore, the number of machine intervals used by jobs and idle intervals at each time step can be bounded by | J | + 1 {\displaystyle |{\mathcal {J}}|+1} .^[1] Here a machine interval is a set of consecutive machines of maximal cardinality such that all machines in this set are processing the same job. A machine interval is completely specified by the index of its first and last machine. Therefore, it is possible to obtain a compact way of encoding the output with polynomial size.

This problem is NP-hard even when there are only two machines and the sizes of all jobs are q j = 1 {\displaystyle q_{j}=1} (i.e., each job needs to run only on a single machine). This special case, denoted by P 2 | | C max {\displaystyle P2||C_{\max }} , is a variant of the partition problem, which is known to be NP-hard.

When the number of machines m is at most 3, that is: for the variants P 2 | s i z e j | C max {\displaystyle P2|size_{j}|C_{\max }} and P 3 | s i z e j | C max {\displaystyle P3|size_{j}|C_{\max }} , there exists a pseudo-polynomial time algorithm, which solves the problem exactly.^[7]

In contrast, when the number of machines is at least 4, that is: for the variants P m | s i z e j | C max {\displaystyle Pm|size_{j}|C_{\max }} for any m ≥ 4 {\displaystyle m\geq 4} , the problem is also strongly NP-hard^[8] (this result improved a previous result^[7] showing strong NP-hardness for m ≥ 5 {\displaystyle m\geq 5} ).

If the number of machines is not bounded by a constant, then there can be no approximation algorithm with an approximation ratio smaller than 3 / 2 {\displaystyle 3/2} unless P = N P {\displaystyle P=NP} . This holds even for the special case in which the processing time of all jobs is p j = 1 {\displaystyle p_{j}=1} , since this special case is equivalent to the bin packing problem: each time-step corresponds to a bin, m is the bin size, each job corresponds to an item of size q_j, and minimizing the makespan corresponds to minimizing the number of bins.

Several variants of this problem have been studied.^[3] The following variants also have been considered in combination with each other.

Contiguous jobs: In this variant, the machines have a fixed order ( M 1 , … , M m ) {\displaystyle (M_{1},\dots ,M_{m})} . Instead of assigning the jobs to any subset m j ⊆ { M 1 , … , M m } {\displaystyle m_{j}\subseteq \{M_{1},\dots ,M_{m}\}} , the jobs have to be assigned to a contiguous interval of machines. This problem corresponds to the problem formulation of the strip packing problem.

Multiple platforms: In this variant, the set of machines is partitioned into independent platforms. A scheduled job can only use the machines of one platform and is not allowed to span over multiple platforms when processed.

Moldable jobs: In this variant each job j ∈ J {\displaystyle j\in {\mathcal {J}}} has a set of feasible machine-counts D j ⊆ { 1 , … m } {\displaystyle D_{j}\subseteq \{1,\dots m\}} . For each count d ∈ D j {\displaystyle d\in D_{j}} , the job can be processed on d machines in parallel, and in this case, its processing time will be p j , d {\displaystyle p_{j,d}} . To schedule a job j ∈ J {\displaystyle j\in {\mathcal {J}}} , an algorithm has to choose a machine count d ∈ D j {\displaystyle d\in D_{j}} and assign j to a starting time s j {\displaystyle s_{j}} and to d {\displaystyle d} machines during the time interval [ s j , s j + p j , d ) . {\displaystyle [s_{j},s_{j}+p_{j,d}).} A usual assumption for this kind of problem is that the total workload of a job, which is defined as d ⋅ p j , d {\displaystyle d\cdot p_{j,d}} , is non-increasing for an increasing number of machines.

Release dates: In this variant, denoted by P | s i z e j , r j | C max {\displaystyle P|size_{j},r_{j}|C_{\max }} , not all jobs are available at time 0; each job j becomes available at a fixed and known time r_j. It must be scheduled after that time.

Preemption: In this variant, denoted by P | s i z e j , r j , pmtn | C max {\displaystyle P|size_{j},r_{j},{\text{pmtn}}|C_{\max }} , it is possible to interrupt jobs that are already running, and schedule other jobs that become available at that time.

The list scheduling algorithm by Garey and Graham^[9] has an absolute ratio 2 {\displaystyle 2} , as pointed out by Turek et al.^[10] and Ludwig and Tiwari.^[11] Feldmann, Sgall and Teng^[12] observed that the length of a non-preemptive schedule produced by the list scheduling algorithm is actually at most ( 2 − 1 / m ) {\displaystyle (2-1/m)} times the optimum preemptive makespan. A polynomial-time approximation scheme (PTAS) for the case when the number m {\displaystyle m} of processors is constant, denoted by P m | s i z e j | C max {\displaystyle Pm|size_{j}|C_{\max }} , was presented by Amoura et al.^[13] and Jansen et al.^[14] Later, Jansen and Thöle ^[2] found a PTAS for the case where the number of processors is polynomially bounded in the number of jobs. In this algorithm, the number of machines appears polynomially in the time complexity of the algorithm. Since, in general, the number of machines appears only in logarithmic in the size of the instance, this algorithm is a pseudo-polynomial time approximation scheme as well. A ( 3 / 2 + ε ) {\displaystyle (3/2+\varepsilon )} -approximation was given by Jansen,^[15] which closes the gap to the lower bound of 3 / 2 {\displaystyle 3/2} except for an arbitrarily small ε {\displaystyle \varepsilon } .

Given an instance of the parallel task scheduling problem, the optimal makespan can differ depending on the constraint to the contiguity of the machines. If the jobs can be scheduled on non-contiguous machines, the optimal makespan can be smaller than in the case that they have to be scheduled on contiguous ones. The difference between contiguous and non-contiguous schedules has been first demonstrated in 1992^[16] on an instance with n = 8 {\displaystyle n=8} tasks, m = 23 {\displaystyle m=23} processors, C max n c = 17 {\displaystyle C_{\max }^{nc}=17} , and C max c = 18 {\displaystyle C_{\max }^{c}=18} . Błądek et al.^[17] studied these so-called c/nc-differences and proved the following points:

• For a c/nc-difference to arise, there must be at least three tasks with q j > 1. {\displaystyle q_{j}>1.}
• For a c/nc-difference to arise, there must be at least three tasks with p j > 1. {\displaystyle p_{j}>1.}
• For a c/nc-difference to arise, at least m = 4 {\displaystyle m=4} processors are required (and there exists an instance with a c/nc-difference with m = 4 {\displaystyle m=4} ).
• For a c/nc-difference to arise, the non-contiguous schedule length must be at least C max n c = 4. {\displaystyle C_{\max }^{nc}=4.}
• The maximal c/nc-difference sup I C max c ( I ) / C max n c ( I ) {\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)} is at least 5 / 4 {\displaystyle 5/4} and at most 2. {\displaystyle 2.}
• To decide whether there is an c/nc-difference in a given instance is NP-complete.

Furthermore, they proposed the following two conjectures, which remain unproven:

• For a c/nc-difference to arise, at least n = 7 {\displaystyle n=7} tasks are required.
• sup I C max c ( I ) / C max n c ( I ) = 5 / 4 {\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)=5/4}

There are related scheduling problems in which each job consists of several operations, which must be executed in sequence (rather than in parallel). These are the problems of open shop scheduling, flow shop scheduling and job shop scheduling.