Parallel task scheduling problem

In theoretical computer science, the parallel task scheduling problem is an NP-hard optimization problem. A given set of ${\displaystyle n}$ parallel tasks, also called jobs, need to be scheduled on ${\displaystyle m}$ identical machines, sometimes called processors, minimizing the latest completion time. In Veltman et al.[1] and Drozdowski[2], this problem is denoted by ${\displaystyle P|size_{j}|C_{\max }}$ in the tree field notation introduced by Graham et al [3]. The origins of this problem formulation can be traced back to 1960[4]. For this problem, there exists no polynomial time approximation algorithm with a ratio smaller than ${\displaystyle 3/2}$ unless ${\displaystyle P=NP}$.

Definition

In this problem, we are given a set ${\displaystyle {\mathcal {J}}}$ of ${\displaystyle n}$ jobs as well as ${\displaystyle m}$ identical machines. Each job ${\displaystyle j\in {\mathcal {J}}}$ has a processing time ${\displaystyle p_{j}\in \mathbb {N} }$ and requires the simultaneous use of ${\displaystyle q_{j}\in \mathbb {N} }$ machines during its execution. A schedule assigns each job ${\displaystyle j\in {\mathcal {J}}}$ to a starting time ${\displaystyle s_{j}\in \mathbb {N} _{0}}$ and a set ${\displaystyle m_{j}\subseteq \{1,\dots ,m\}}$ of ${\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 ${\displaystyle P|size_{j}|C_{\max }}$ is to find a schedule with minimum length ${\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

${\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 string time starting with time ${\displaystyle t=0}$.[5][6]. Furthermore, the number of machine intervals used by jobs and idle intervals at each time step can be bounded by ${\displaystyle |{\mathcal {J}}|+1}$[5]. 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.

Hardness

This problem is NP-hard even for a constant number of machines due to the fact that ${\displaystyle P2||C_{\max }}$ corresponds to the partition problem. Furthermore, Du and Leung[7] showed that this problem is strongly NP-hard when the number of machines is at least ${\displaystyle m=5}$, and that there exists a pseudo-polynomial time algorithm, which solves the problem exactly if the number of machines is at most ${\displaystyle m=3}$. Later Henning et al.[8] showed that the problem is also strongly NP-hard when the number of machines is ${\displaystyle m=4}$. If the number of machines is not bounded by a constant, there can be no approximation algorithm with an approximation ratio smaller than ${\displaystyle 3/2}$ unless ${\displaystyle P=NP}$ because this problem contains the bin packing problem as a subcase, i.e., when all the jobs have processing time ${\displaystyle p_{j}=1}$.

Variants

There are several variants of this problem that have been studied[2]. The following variants also have been considered in combination with each other.

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

Moldable jobs: In this variant each job ${\displaystyle j\in {\mathcal {J}}}$ has a set of feasible machine numbers ${\displaystyle D\subseteq \{1,\dots m\}}$ and for each of these numbers ${\displaystyle d\in D}$ it has a processing time ${\displaystyle p_{j,d}}$. To schedule a job ${\displaystyle j\in {\mathcal {J}}}$, an algorithm has to choose a machine number ${\displaystyle d\in D}$ and assign it to a starting time ${\displaystyle s_{j}}$ and to ${\displaystyle d}$ machines during the time interval ${\displaystyle [s_{j},s_{j}+p_{j,d}).}$ A usual assumption for this kind of problem is that the work of a job, which is defined as ${\displaystyle d\cdot p_{j,d}}$ is non-increasing for an increasing number of machines.

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.

Algorithms

The list scheduling algorithm by Garey and Graham[9] has an absolute ratio ${\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 ${\displaystyle (2-1/m)}$ times the optimum preemptive makespan. A polynomial-time approximation scheme (PTAS) for the case when the number ${\displaystyle m}$ of processors is constant, denoted by ${\displaystyle Pm|size_{j}|C_{\max }}$, was presented by Amoura et al.[13] and Jansen et al.[14] Later, Jansen and Thöle [6] 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 ${\displaystyle (3/2+\varepsilon )}$-approximation was given by Jansen[15], which closes the gap to the lower bound of ${\displaystyle 3/2}$ exept for an arbitrarily small ${\displaystyle \varepsilon }$.

Differences between contiguous and non-contiguous jobs

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 ${\displaystyle n=8}$ tasks, ${\displaystyle m=23}$ processors, ${\displaystyle C_{\max }^{nc}=17}$, and ${\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 ${\displaystyle q_{j}>1.}$
• For a c/nc-difference to arise, there must be at least three tasks with ${\displaystyle p_{j}>1.}$
• For a c/nc-difference to arise, at least ${\displaystyle m=4}$ processors are required (and there exists an instance with a c/nc-difference with ${\displaystyle m=4}$).
• For a c/nc-difference to arise, the non-contiguous schedule length must be at least ${\displaystyle C_{\max }^{nc}=4.}$
• The maximal c/nc-difference ${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)}$ is at least ${\displaystyle 5/4}$ and at most ${\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 ${\displaystyle n=7}$ tasks are required.
• ${\displaystyle \sup _{I}C_{\max }^{c}(I)/C_{\max }^{nc}(I)=5/4}$

References

1. Veltman, B; Lageweg, B. J; Lenstra, J. K (1990-12-01). "Multiprocessor scheduling with communication delays". Parallel Computing. 16 (2): 173–182. doi:10.1016/0167-8191(90)90056-F. ISSN 0167-8191.
2. Drozdowski, Maciej (2009). "Scheduling for Parallel Processing". Computer Communications and Networks. doi:10.1007/978-1-84882-310-5. ISSN 1617-7975.
3. Graham, R. L.; Lawler, E. L.; Lenstra, J.K.; Rinnooy Kan, A.H.G. (1979). "Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey" (PDF). Proceedings of the Advanced Research Institute on Discrete Optimization and Systems Applications of the Systems Science Panel of NATO and of the Discrete Optimization Symposium. Elsevier. pp. (5) 287–326.
4. F, CoddE (1960-06-01). "Multiprogram scheduling". Communications of the ACM. doi:10.1145/367297.367317.
5. Johannes, Berit (2006-10-01). "Scheduling parallel jobs to minimize the makespan". Journal of Scheduling. 9 (5): 433–452. doi:10.1007/s10951-006-8497-6. ISSN 1099-1425.
6. Jansen, Klaus.; Thöle, Ralf. (2010-01-01). "Approximation Algorithms for Scheduling Parallel Jobs". SIAM Journal on Computing. 39 (8): 3571–3615. doi:10.1137/080736491. ISSN 0097-5397.
7. Du, Jianzhong.; Leung, Joseph Y.-T. (1 November 1989). "Complexity of Scheduling Parallel Task Systems". SIAM Journal on Discrete Mathematics. 2 (4): 473–487. doi:10.1137/0402042. ISSN 0895-4801.
8. Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars (1 January 2020). "Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing". Theory of Computing Systems. 64 (1): 120–140. arXiv:1705.04587. doi:10.1007/s00224-019-09910-6. ISSN 1433-0490.
9. Garey, M. R.; Graham, R. L. (1 June 1975). "Bounds for Multiprocessor Scheduling with Resource Constraints". SIAM Journal on Computing. 4 (2): 187–200. doi:10.1137/0204015. ISSN 0097-5397.
10. Turek, John; Wolf, Joel L.; Yu, Philip S. "Approximate algorithms scheduling parallelizable tasks | Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures". dl.acm.org. doi:10.1145/140901.141909.
11. Ludwig, Walter; Tiwari, Prasoon (1994). "Scheduling malleable and nonmalleable parallel tasks | Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms". Fifth Annual {ACM-SIAM} Symposium on Discrete Algorithms (SODA): 167--176.
12. Feldmann, Anja; Sgall, Jiří; Teng, Shang-Hua (1 August 1994). "Dynamic scheduling on parallel machines". Theoretical Computer Science. 130 (1): 49–72. doi:10.1016/0304-3975(94)90152-X. ISSN 0304-3975.
13. Amoura, Abdel Krim; Bampis, Evripidis; Kenyon, Claire; Manoussakis, Yannis (1 February 2002). "Scheduling Independent Multiprocessor Tasks". Algorithmica. 32 (2): 247–261. doi:10.1007/s00453-001-0076-9. ISSN 1432-0541.
14. Jansen, Klaus; Porkolab, Lorant (1 March 2002). "Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks". Algorithmica. 32 (3): 507–520. doi:10.1007/s00453-001-0085-8. hdl:11858/00-001M-0000-0014-7B6C-D. ISSN 1432-0541.
15. Jansen, Klaus (2012). "A(3/2+ε) approximation algorithm for scheduling moldable and non-moldable parallel tasks | Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures". 24th {ACM} Symposium on Parallelism in Algorithms and Architectures,{SPAA}. doi:10.1145/2312005.2312048.
16. "Approximate algorithms scheduling parallelizable tasks | Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures". dl.acm.org. doi:10.1145/140901.141909. Retrieved 2020-01-25.
17. Błądek, Iwo; Drozdowski, Maciej; Guinand, Frédéric; Schepler, Xavier (1 October 2015). "On contiguous and non-contiguous parallel task scheduling". Journal of Scheduling. 18 (5): 487–495. doi:10.1007/s10951-015-0427-z. ISSN 1099-1425.