Parallel task scheduling

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 J 1 , J 2 , ..., 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. and Drozdowski denote this problem by 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; 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} instead. Note that the problem of parallel-machines scheduling is a special case of parallel-task scheduling where 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.…

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 J 1 , J 2 , ..., 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. and Drozdowski denote this problem by 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; 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} instead. Note that the problem of parallel-machines scheduling is a special case of parallel-task scheduling where 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 unless P=NP . A schedule assigns each job j \in \mathcal{J} to a starting time s_j \in \mathbb{N}_0 and a set m_j \subseteq \{1,\dots,m\} of |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|size_j|C_{\max} is to find a schedule with minimum length 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 \sum_{j \in \mathcal{J}, s_j \leq t . 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 . Furthermore, the number of machine intervals used by jobs and idle intervals at each time step can be bounded by |\mathcal{J}| + 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 (i.e., each job needs to run only on a single machine). This special case, denoted by 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 P2|size_j|C_{\max} and P3|size_j|C_{\max} , there exists a pseudo-polynomial time algorithm, which solves the problem exactly. In contrast, when the number of machines is at least 4, that is: for the variants Pm|size_j|C_{\max} for any m \geq 4 , the problem is also strongly NP-hard (this result improved a previous result showing strong NP-hardness for 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 unless P = NP . This holds even for the special case in which the processing time of all jobs is 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. The difference between contiguous and non-contiguous schedules has been first demonstrated in 1992 on an instance with n=8 tasks, m=23 processors, C^{nc}_{\max}=17 , and C^c_{\max}=18 . Błądek et al. 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. For a c/nc-difference to arise, there must be at least three tasks with p_j>1. For a c/nc-difference to arise, at least m=4 processors are required (and there exists an instance with a c/nc-difference with m=4 ). For a c/nc-difference to arise, the non-contiguous schedule length must be at least C^{nc}_{\max}=4. The maximal c/nc-difference \sup_{I}C^{c}_{\max}(I)/C^{nc}_{\max}(I) is at least 5/4 and at most 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 tasks are required. \sup_{I}C^{c}_{\max}(I)/C^{nc}_{\max}(I) = 5/4 ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1353108015 under CC BY-SA 4.0; modifications have been made.