# Inapproximability and Polynomial-Time Approximation Algorithm  for UET Tasks on Structured  Processor Networks

Authors: M. Bouznif; R. Giroudeau
Journal: Advances in Operations Research
 (2011)

---

## Abstract

We investigate  complexity and approximation results on a processor networks  where the communication delay depends on the distance between the processors performing tasks. We then prove
that there is no heuristic with a performance guarantee smaller than 4/3 for  makespan minimization for precedence graph on a large class of processor networks  like hypercube, grid,
torus, and so forth, with a fixed diameterδ∈ℕ. We extend complexity results when the  precedence graph is a bipartite graph. We also design an efficient  polynomial-time O(δ2)-approximation algorithm for the makespan minimization on processor networks with diameter δ.


---

## Body

## 1. Introduction

### 1.1. Problem Statement

In this paper, we consider the processor network model, which is a generalization of thehomogeneous scheduling delay model in which task allocation on the processors does not have any influence over the length of scheduling.  Indeed, since the graph of processors (denoted hereafter G*=(V*,E*) where V*={π1,…,πm} is a set of m processors and E* is the set relationship between them) is fully connected, the starting of a task i depends only on the potential communication delay, given by precedence graph between i and its own predecessors.In the processor network model, this assumption is relaxed in order to take into account the fact that the processor graph may not be fully connected. Thus, task allocation on the processors can be expressed by its essential and fundamentals characteristics. We consider a model in which a distance function (which is defined hereafter), denotedd(πl,πh) between two processors πl and πh in the graph of processors impacts computation of the communication delay between two tasks i and j (subject to a precedence constraint) and consequently on the starting time of task j. The communication time, using ci,πl,j,πh for computing the starting time of a task (this notation indicates that the value of the communication delay between task i, which is allotted to processor πl and task j which will be executed on the processor πh), is assumed as cijd(πl,πh), where cij is the communication delay given by the precedence graph.Formally, the processor network model may be defined as(1.1)∀(i,j)∈E,tj≥ti+pi+cijd(πl,πh),
where πℓ (resp. πh) represents the processor on which task i (resp. task j) is scheduled, ti represents the starting time of task i, pi represents the processing time of task i, d(πℓ,πh) represents the shortest path in graph G* (the graph of processor G*=(V*,E*)) between πℓ and πh, and cij represents the communication delay if two tasks are executed on two neighboring processors (this value is given by the precedence graph).We consider the classic scheduling UET-UCT (Unit Execution Time-Unit Communication Time, i.e.,∀i∈V, pi=1, and ∀(i,j)∈E,cij=1) problem on a bounded number of processors such that the processor network is a structured graph with a diameter δ. In these topologies, processors are numbered as π1,π2,…,πm and processor πh may be communicated with processor πl with a communication cost equal to d(πh,πl) where d(πh,πl) represents the shortest path on graph G* between processors πh and πl. The communication delay is therefore the distance function proposed above.In scheduling theory, a problem type is categorized by its machine environment, job characteristic, and objective function. Thus, using thethree fields notation scheme α|β|γ,(where α designates the environment processors, β the characteristics of the job, and γ the criteria.) proposed by Graham et al. [1], we consider the problem of makespan minimization (denoted in follows by Cmax) with unitary task and unitary communication delay (UET-UCT) in presence of a precedence graph G on a processors network having a graph G* such that the communication delay depends on the shortest path on graph G*. This problem is denoted by (P,G*)|prec;cij=d(πℓ,πk);pi=1|Cmax.Example 1.1.
Figure1 shows the difference between the two problems P|prec;cij=1;pi=1|Cmax and (P,grid2×2)|prec;cij=d(πℓ,πk);pi=1|Cmax.  (The relationship between processors is as follows: π0 and π3 are connected to π1 and π2.)  The processing time of the tasks and the communication delay between the tasks are unitary (UET-UCT problem). Gantt diagram G1 represents an optimal solution for the P|prec;cij=1;pi=1|Cmax problem. We can notice that task z can be executed on any processor at t=2. Moreover, Gantt diagram G2 represents an optimal solution for the problem (P,grid2×2)|prec;cij=d(πℓ,πk);pi=1|Cmax. In order to obtain an optimal solution, the task a must be delayed by one unit of time and must be processed on the same processor π2 as task c at t=1. Thus, task e may be executed at t=2 only on the processor π2.Figure 1
Difference between the problemP|prec;cij=1;pi=1|Cmax and (P,grid2×2)|prec;cij=d(πi,πj);pi=1|Cmax.


### 1.2. Organization of the Paper

This paper is organized as follows: the next section is devoted to the related works. In Section3, after defining the class graph 𝒢 we propose a general nonapproximability result for a nonspecified precedence graph. We also extend the previous result when the precedence graph is a bipartite graph and when the duplication is allowed. In the last section, we design a polynomial-time approximation algorithm with a performance ratio within O(δ).


## 1.1. Problem Statement

In this paper, we consider the processor network model, which is a generalization of thehomogeneous scheduling delay model in which task allocation on the processors does not have any influence over the length of scheduling.  Indeed, since the graph of processors (denoted hereafter G*=(V*,E*) where V*={π1,…,πm} is a set of m processors and E* is the set relationship between them) is fully connected, the starting of a task i depends only on the potential communication delay, given by precedence graph between i and its own predecessors.In the processor network model, this assumption is relaxed in order to take into account the fact that the processor graph may not be fully connected. Thus, task allocation on the processors can be expressed by its essential and fundamentals characteristics. We consider a model in which a distance function (which is defined hereafter), denotedd(πl,πh) between two processors πl and πh in the graph of processors impacts computation of the communication delay between two tasks i and j (subject to a precedence constraint) and consequently on the starting time of task j. The communication time, using ci,πl,j,πh for computing the starting time of a task (this notation indicates that the value of the communication delay between task i, which is allotted to processor πl and task j which will be executed on the processor πh), is assumed as cijd(πl,πh), where cij is the communication delay given by the precedence graph.Formally, the processor network model may be defined as(1.1)∀(i,j)∈E,tj≥ti+pi+cijd(πl,πh),
where πℓ (resp. πh) represents the processor on which task i (resp. task j) is scheduled, ti represents the starting time of task i, pi represents the processing time of task i, d(πℓ,πh) represents the shortest path in graph G* (the graph of processor G*=(V*,E*)) between πℓ and πh, and cij represents the communication delay if two tasks are executed on two neighboring processors (this value is given by the precedence graph).We consider the classic scheduling UET-UCT (Unit Execution Time-Unit Communication Time, i.e.,∀i∈V, pi=1, and ∀(i,j)∈E,cij=1) problem on a bounded number of processors such that the processor network is a structured graph with a diameter δ. In these topologies, processors are numbered as π1,π2,…,πm and processor πh may be communicated with processor πl with a communication cost equal to d(πh,πl) where d(πh,πl) represents the shortest path on graph G* between processors πh and πl. The communication delay is therefore the distance function proposed above.In scheduling theory, a problem type is categorized by its machine environment, job characteristic, and objective function. Thus, using thethree fields notation scheme α|β|γ,(where α designates the environment processors, β the characteristics of the job, and γ the criteria.) proposed by Graham et al. [1], we consider the problem of makespan minimization (denoted in follows by Cmax) with unitary task and unitary communication delay (UET-UCT) in presence of a precedence graph G on a processors network having a graph G* such that the communication delay depends on the shortest path on graph G*. This problem is denoted by (P,G*)|prec;cij=d(πℓ,πk);pi=1|Cmax.Example 1.1.
Figure1 shows the difference between the two problems P|prec;cij=1;pi=1|Cmax and (P,grid2×2)|prec;cij=d(πℓ,πk);pi=1|Cmax.  (The relationship between processors is as follows: π0 and π3 are connected to π1 and π2.)  The processing time of the tasks and the communication delay between the tasks are unitary (UET-UCT problem). Gantt diagram G1 represents an optimal solution for the P|prec;cij=1;pi=1|Cmax problem. We can notice that task z can be executed on any processor at t=2. Moreover, Gantt diagram G2 represents an optimal solution for the problem (P,grid2×2)|prec;cij=d(πℓ,πk);pi=1|Cmax. In order to obtain an optimal solution, the task a must be delayed by one unit of time and must be processed on the same processor π2 as task c at t=1. Thus, task e may be executed at t=2 only on the processor π2.Figure 1
Difference between the problemP|prec;cij=1;pi=1|Cmax and (P,grid2×2)|prec;cij=d(πi,πj);pi=1|Cmax.


## 1.2. Organization of the Paper

This paper is organized as follows: the next section is devoted to the related works. In Section3, after defining the class graph 𝒢 we propose a general nonapproximability result for a nonspecified precedence graph. We also extend the previous result when the precedence graph is a bipartite graph and when the duplication is allowed. In the last section, we design a polynomial-time approximation algorithm with a performance ratio within O(δ).


## 2. Related Works

### 2.1. Complexity Results

To the best of our knowledge, the first complexity result was given by Picouleau [2]. The considered problem was to schedule unit execution time tasks with a precedence graph on an unbounded number of processors and on a chain or star (a star is a tree of depth one)  topology. Picouleau proved that this problem is 𝒩𝒫-complete if the precedence graph is a tree or an outtree. Recently in [3], the authors proved that there is no heuristic with a performance guarantee smaller than 6/5 for minimizing the makespan on a processor network represented by a star. This model is closest to the master-slave architecture. In [4], the authors proved that there is no hope to finding a polynomial-time approximation algorithm with a ratio ρ>4/3 for the problem to schedule a set of tasks on a ring or a chain as processors network (see Table 1).Table 1
Previous complexity results on the processors network model.
TopologyPrecedence graphComplexityReferenceUnbounded chainTree𝒩𝒫-complete[2]Antitree𝒩𝒫-completeStarTree𝒩𝒫-complete[2]Cycle/chainPrecρ≥4/3[4]StarPrecρ≥6/5[3]


#### 2.1.1. Approximation Results

In ring topology, Lahlou developed, in [5], using the list scheduling proposed by Rayward-Smith [6], a ρ-approximation algorithm with ⌈m⌉≤ρ≤1+(3/8)m-1/2m where m is the number of processors.Moreover, Hwang et al. [7] studied approximation list algorithms for scheduling problems where the communication times depend on contention and a distance function for the tasks involved and on the processors that execute the tasks. The authors examined a simple strategy called extended list scheduling, ELS, which is a straightforward extension of list scheduling. They proved that the ELS strategy is unsatisfactory, but improved a strategy called earliest task first.Recently, in [3] the authors proposed a sophisticated polynomial-time approximation algorithm with a ratio equal to four based on three steps for the problem for the makespan minimization problem on a processor networks as a star forms. In [4] the authors develop two polynomial-time approximation algorithms for processor networks with limited or unlimited resources.


### 2.2. Our Contributions

In this paper, we answer the following interesting question:is there a large class of graphs, for which it exists a polynomial-time reduction fromn-PARTITION, to show the𝒩𝒫-completeness? Therefore, it is sufficient to show if the graphGis belonging to this class, in order to prove the nonexistence of𝒫𝒯𝒜𝒮? In order to complete the study of processor networks, we design a polynomial-time approximation algorithm within a ratio at most ((δ+1)2/3)+1 where δ designates the diameter of the graph G*.


## 2.1. Complexity Results

To the best of our knowledge, the first complexity result was given by Picouleau [2]. The considered problem was to schedule unit execution time tasks with a precedence graph on an unbounded number of processors and on a chain or star (a star is a tree of depth one)  topology. Picouleau proved that this problem is 𝒩𝒫-complete if the precedence graph is a tree or an outtree. Recently in [3], the authors proved that there is no heuristic with a performance guarantee smaller than 6/5 for minimizing the makespan on a processor network represented by a star. This model is closest to the master-slave architecture. In [4], the authors proved that there is no hope to finding a polynomial-time approximation algorithm with a ratio ρ>4/3 for the problem to schedule a set of tasks on a ring or a chain as processors network (see Table 1).Table 1
Previous complexity results on the processors network model.
TopologyPrecedence graphComplexityReferenceUnbounded chainTree𝒩𝒫-complete[2]Antitree𝒩𝒫-completeStarTree𝒩𝒫-complete[2]Cycle/chainPrecρ≥4/3[4]StarPrecρ≥6/5[3]


### 2.1.1. Approximation Results

In ring topology, Lahlou developed, in [5], using the list scheduling proposed by Rayward-Smith [6], a ρ-approximation algorithm with ⌈m⌉≤ρ≤1+(3/8)m-1/2m where m is the number of processors.Moreover, Hwang et al. [7] studied approximation list algorithms for scheduling problems where the communication times depend on contention and a distance function for the tasks involved and on the processors that execute the tasks. The authors examined a simple strategy called extended list scheduling, ELS, which is a straightforward extension of list scheduling. They proved that the ELS strategy is unsatisfactory, but improved a strategy called earliest task first.Recently, in [3] the authors proposed a sophisticated polynomial-time approximation algorithm with a ratio equal to four based on three steps for the problem for the makespan minimization problem on a processor networks as a star forms. In [4] the authors develop two polynomial-time approximation algorithms for processor networks with limited or unlimited resources.


## 2.1.1. Approximation Results

In ring topology, Lahlou developed, in [5], using the list scheduling proposed by Rayward-Smith [6], a ρ-approximation algorithm with ⌈m⌉≤ρ≤1+(3/8)m-1/2m where m is the number of processors.Moreover, Hwang et al. [7] studied approximation list algorithms for scheduling problems where the communication times depend on contention and a distance function for the tasks involved and on the processors that execute the tasks. The authors examined a simple strategy called extended list scheduling, ELS, which is a straightforward extension of list scheduling. They proved that the ELS strategy is unsatisfactory, but improved a strategy called earliest task first.Recently, in [3] the authors proposed a sophisticated polynomial-time approximation algorithm with a ratio equal to four based on three steps for the problem for the makespan minimization problem on a processor networks as a star forms. In [4] the authors develop two polynomial-time approximation algorithms for processor networks with limited or unlimited resources.


## 2.2. Our Contributions

In this paper, we answer the following interesting question:is there a large class of graphs, for which it exists a polynomial-time reduction fromn-PARTITION, to show the𝒩𝒫-completeness? Therefore, it is sufficient to show if the graphGis belonging to this class, in order to prove the nonexistence of𝒫𝒯𝒜𝒮? In order to complete the study of processor networks, we design a polynomial-time approximation algorithm within a ratio at most ((δ+1)2/3)+1 where δ designates the diameter of the graph G*.


## 3. Computational Complexity for a Large Class of Graph

### 3.1. The Class Graph𝒢

We propose a large class of graph𝒢 for which the problem of deciding whether an instance (P,G*)|prec;cij=d(πℓ,πk);pi=1|Cmax≤3 is 𝒩𝒫-complete.We present now a graph class for which we may apply the same polynomial-time transformation mechanism from  3-PARTITION problem to show that our scheduling problem when processor networks belong to this class is𝒩𝒫-complete. Hereafter, we give the definition of the prism graph.Definition 3.1.
A prismP=(VP,EP) of size k and length L (k,L∈ℕ) is a connected undirected graph for that  (i)
there are two sets of verticesK and K′ such as K⊂VP, K′⊂VP∖{K}, and |K|=|K′|=k. The vertices are denoted s1,…,sk (resp. s1′,…,sk′);(ii)
it exists an order onK and K′ vertices such that (∀si∈K,si′∈K,1≤i≤k) there is a path of length L denoted Ci between si and si′;(iii)
(i≠j)∧x∈Ci∖{si,si′}∧y∈Cj∖{sj,sj′}⇒(x,y)∉EP.Moreover, the size of a prism is polynomial ink. An illustration is given in Figure 2.Figure 2
An example of a prism of sizek and length L.Definition 3.2.
Let𝒢 be a collection of graphs. 𝒢 possess the prism property if and only if ∀n0,∀n1∈ℕ∃G∈𝒢, such that G contains a unique subgraph G1=(V1,E1) of G induced by vertices V1⊂V with a prism of size k=n0 and length L=n1.Lemma 3.3.
The class graph𝒢 is not empty.Proof.
In particular we will see in Section3.2 classic structured graph like torus, grid, complete binary tree, and so forth, belonging to this class graph.Theorem 3.4.
The problem of deciding whether an instance of(P,G*)|β;cij=d(πℓ,πk);pi=1|Cmax has a schedule of length at most two is polynomial with β∈{prec,bipartite} and G*∈𝒢.Proof.
No communication is allowed between two pairs of tasks.The remainder of this section is devoted to proving Theorem3.5.Theorem 3.5.
The problem of deciding whether an instance of(P,G*)|prec;cij=d(πk,πl);pi=1|Cmax has a schedule of length at most three is 𝒩𝒫-complete with G*∈𝒢.Proof.
The proof is established by a reduction of the  3-PARTITION problem [8].
Instance
A finite set𝒜 of 3M elements {a1,…,a3M}, a bound B∈ℕ+, and a size s(a)∈ℕ for each a∈𝒜 such that each s(a) satisfies B/4<s(a)<B/2 and such that ∑a∈𝒜s(a)=MB.Question 1.
CanA be partitioned into M disjoint sets 𝒜1,…,𝒜M of 𝒜 such that for all i∈[1,…,M],B=∑a∈𝒜is(a)=∑a∈𝒜s(a)/M∈ℕ?
3-PARTITION is known to be𝒩𝒫-complete in the strong sense [8]. (Even if B is polynomially bounded by the instance size, the problem is still 𝒩𝒫-complete.)
It is easy to see that(P,G*)|prec,cij=d(πl,πk)=1,pi=1|Cmax≤3∈𝒩𝒫.
Given an instanceℐ of the  3- PARTITION problem, we construct an instance ℐ′ of the scheduling problem (P,G*)|prec;cij=d(πℓ,πk);pi=1|Cmax≤3 with G*∈𝒢, in the following way.
The precedence graphG̃=𝒲+𝒵, which will be scheduled on the processors network G*, is decomposed into two disjointed graphs, denoted as follows by 𝒲 and 𝒵 (the graph 𝒵 is a collection of graphs Zs(aj), i.e., 𝒵=∪aj∈𝒜Zs(aj)). Hereafter, graphs 𝒵 and 𝒲 are characterized.GraphZi
Leti be an integer such that i>1. Graph Zi consists of 4×i vertices denoted by Zi[k,0], Zi[k,1], where 0≤k<2i. The precedence constraints between these tasks are defined as follows: (i)
arcsZi[j,0]→Zi[j,1] for any j, 0≤j≤2i-1,(ii)
arcsZi[2j,0]→Zi[2j+1,1] for any j, 0≤j≤i-1,(iii)
arcsZi[2j,0]→Zi[2j-1,1] for any j, 1≤j≤i-1.Remark 3.6.
Valid scheduling of length three for the case where the precedence graph isZi in a path of 2i processors is as follows, for any j, 0≤j≤2i-1,  (i)
tasksZi[j,0] and Zi[j,1] are executed on πj,(ii)
tasksZi[j,ℓ] are executed at time ℓ, for any ℓ∈{0,1}, if j is even,(iii)
tasksZi[j,ℓ] are otherwise executed at time ℓ+1, for any ℓ∈{0,1}.
See Figure3 for graph Z2 and Figure 4 for the valid scheduling described in Remark 3.6.Figure 3
GraphZ2.Figure 4
Valid schedule of length three for graphZ2.Graph𝒲
Remark 3.7.
A path of lengthl admits l+1 vertices.
The𝒲=(𝒱∪𝒱′;E𝒲) graph will be defined as follows. Let G*=(V*,E*) be a graph such that G*∈𝒢, with V*={v1*,…,vn**}. By Definition 3.2, we know that it exists a unique subgraph G=(V⊂V*,E⊂E*) of size k and length L with desired properties. In the following we set k=n and L=2B+1 and the size of G*=(V*,E*) is polynomial in k. Note that n*≫2B.
The𝒲-graph is defined by polynomial-time transformations from the G*-graph. The graph given in Figure 5 will be used to illustrated the following construction. (i)
The paths of length three are created and precedence constraints are added (see Figure6). The two sets of tasks 𝒱1 and 𝒱′ are created.(ii)
The tasks are partitioned into three subsets𝒱′, 𝒦, and 𝒱 (see Figure 7).(iii)
The𝒱1-tasks are now partitioned into two subsets 𝒦 and 𝒱. We consider the subgraph induced by the 𝒱∪𝒱′-tasks (see Figure 8) as the 𝒲-graph.
The purpose of removing these tasks is to allow the tasks of𝒦-graph when the tasks of 𝒲-graph, deprived of these tasks, will be executed on the graph of processors.
The set of verticesV* is partitioned into two sets V*=V′∪V:  (i)
V={v1*,…,v2n(B+1)*} the vertices of G, and defined the vertices of the n unique paths of length (2B+1) respecting the characteristics given by Definition 3.1,(ii)
V′={v2n(B+1)+1*,…,vn**}, the set of an other vertices. Note that these vertices do not belong to G graph.
The definition of the𝒲 graph is given below.  (i)
∀i∈{1,…,2n(B+1)}, we create a path of length three vi*[0],vi*[1], and vi*[2], with edges vi*[0]→vi*[1]→vi*[2]. The set of tasks will be denoted 𝒱1={vi*[j]|∀i∈{1,…,2n(B+1)},j∈{0,1,2}}. The cardinality of 𝒱1 is 6n(B+1) (see Figure 6).(ii)
∀i∈{2n(B+1)+1,…,n*}, we create a path of length three vi*[0]→vi*[1]→vi*[2]. This set of tasks will be denoted 𝒱′. The number of tasks is 3(n*-2n(B+1)) with n*=|V*|.(iii)
(k,l)∈E*, we add the edges vk*[0]→vl*[2] and vl*[0]→vk*[2] (see Figure 6).
Now,4nB tasks are removed from 𝒲-graph. (In order to clarify the polynomial-time transformation, we give priority to create tasks and remove some ones instead of enumerating all precedence constraints.) Therefore,  we consider the following index sets: (i)
J0={2i(B+1)∣i={1,2,…,n}},(ii)
J1={2i(B+1)+1∣i∈{0,1,2,…,n-1},(iii)
I0={k∈{1,…,2n(B+1)}∖{J0∪J1}and|kiseven},(iv)
I1={k∈{1,…,2n(B+1)}∖{J0∪J1}and|kisodd}.
We remove from the𝒱1-set the following tasks vk*[0], vk*[1] with k∈I0, (resp. vk*[1], vk*[2] with k∈I1). 𝒦 denotes the set of removed tasks (see Figure 7). Finally, we put 𝒱=𝒱1∖𝒦 with |𝒱|=2nB+6n (see Figure 8).
Figures5, 6, 7, and 8 describe the construction of 𝒲-graph from G*∈𝒢.
E𝒲 is the set of arcs as described above.
Lastly, the number of processors ism=n*, and they are numbered as πi with i∈[1,n*].
In summary the precedence graphG̃=𝒲+𝒵 is composed by 𝒲=(𝒱∪𝒱′,E𝒲) with 3n*-4nB tasks and the precedence constraints given before and the graph 𝒵={⋃aj∈𝒜Zs(ai)} with 4nB tasks.
The transformation is computed in polynomial time.(i)
Let us assume that𝒜={a1,…,a3M} can be partitioned into M disjoint subsets 𝒜1,…,𝒜M with each summing up to B. We will then prove that there is a schedule of length three at most.
Let us construct this schedule.
First, the taskvi*[j]∈𝒱′∪𝒱 is executed on the processors πi to t=j with j∈{0,1,2} (if this task exists).
Consider the processors on which the set of𝒱-tasks are scheduled. By the previous allocation, these processors are numbered as π1,…,π2n(B+1).
Let{𝒜1,…,𝒜n} be a partition of 𝒜. Consider 𝒜i={ai1,ai2,ai3} with a fixed i. The tasks of Zs(aj), aj∈𝒜i are executed between processors π1+2(i-1)(B+1) and π2i(B+1). Moreover, the tasks Zs(aj)[l,k], k∈{0,1}, l∈J0 (resp., k∈{1,2}, l∈J1) are scheduled on 2s(aij) processors in succession in order to respect a schedule of length three.
Thus without loss of generality, we suppose that the tasks ofZs(ai1) are scheduled between processors π1+2(i-1)(B+1) and π2(i-1)(B+1)+2s(ai1). In similar way, the tasks Zs(ai2) (resp., Zs(ai3)) are executed between processors π2+2(i-1)(B+1)+2s(ai1) and π1+2(i-1)(B+1)+2s(ai1)+2s(ai2) (resp. π2+2(i-1)(B+1)+2s(ai1)+2s(ai2) and π2i(B+1)).
(ii)
Let us assume now that there is a scheduleS of length at most three. We will prove that 𝒜={a1,…,a3M} can be partitioned into M disjoint subsets 𝒜1,…,𝒜M with each summing up to B.Figure 5
The beginning of the construction of𝒲 graph from G*∈𝒢.Figure 6
Next step of the construction of𝒲 graph. Path of length three is created and precedence constraints between tasks are added.Figure 7
Partition ofG* graph into tasks sets 𝒱, 𝒦, and 𝒱.Figure 8
The final𝒲 graph issue from several transformations.Lemma 3.8.
In any valid schedule of length three there is no idle time.Proof.
The number of processors ism=n* and the number of tasks is 3n* (4nB for 𝒵-graph and 3n*-4nB for 𝒲 graph).Lemma 3.9.
In any valid schedule of length three, the subgraph induced by𝒱 tasks must be executed on 2(B+1) processors in succession.Proof.
Consider the subgraph induced by the𝒱 tasks. This precedence graph admits paths of length two and these paths must be executed on the same processor (no communication delay is allowed).
Consider the tasks of path of length one. Letvi*[0]∈𝒱 be a task without predecessor. By construction vi*[0] admits one successor denoted by  vi+1*[2]∈𝒱.
Suppose that these two tasks are allotted on the same processorπl. Since that vi+1*[2] admits another predecessor denoted by vi+2*[0]∈𝒱 then vi+1*[2] is allotted at t=2.
The taskvi+2*[0] cannot be executed at t=1 on πl since this task admits another successor as vi+1*[2]. Therefore, it exists an idle slot at t=1 on the processor πl. By construction there is no independent task and since the 𝒵 graph admits only path of length one, then no task can be allotted on this idle slot. This is impossible
In conclusion, the subgraph induced by𝒱 tasks must be executed on 2(B+1) processors in succession.Lemma 3.10.
In any valid schedule of length three, two subgraphs induced by the𝒱 tasks from two disjoint paths of length 2(B+1) cannot be allotted on the same processors.Proof.
Consider the𝒱 tasks which are elements of two disjoints paths of length 2(B+1). A task without predecessor of one path cannot be allotted on the same processor as a task without successor of other path since there is no isolated task to schedule.Lemma 3.11.
In any valid valid schedule of length three theZs(aj) tasks must be executed on the same processors as the 𝒱 tasks.Proof.
LetΠ={πl∣𝒱 tasks allotted on πl} be the set of processors on which the 𝒱 tasks are executed.
Suppose that theZs(aj)-tasks are executed on processors πk∉Π. By Lemma 3.8, there is no idle slot, then the tasks on the path of length three are necessarily allotted on processor π*∈Π. This is impossible by Lemma 3.9.With previous lemmas, we know that6n(B+1) tasks (the 𝒱 tasks and the Zs(aj)-tasks) are executed on the n disjoints paths of length 2B+1. By Definition 3.2, we know that the graph G* admits a unique set of n disjoints paths of length 2B+1 with desired properties. Moreover with the precedence constraints, these tasks are allotted on a processor path of length (2B+1). Without loss of generality, we suppose that a task vlß𝒱 is executed on the processor πl with l∈{2n(B+1)+1,…,n*}.Building the partition{𝒜1,…,𝒜n} with desired property from S schedule of length three, we know that two tasks of the same subgraph Zs(aj) (see Lemma 3.11) cannot be executed on two different paths. The edge distance between these two processors is at least two.We define𝒜ℓ such that aj∈𝒜ℓ if and only if the tasks of the graph Zs(aj) are executed between the processors numbered as π1+(j-1)2(B+1) to π2j(B+1) with a fixed j.Now, we will compute∑ai∈𝒜ℓs(ai).Using previous remarks, without loss of generality, we suppose thatvi*[k] with i∈{1,…,2n(B+1)} and k∈{0,1,2} (if it exists) are executed on πl with l∈{1,…,2n(B+1)}. Consider the Zs(aj)-tasks which are scheduled between processors π1+(j-1)2(B+1) and π2j(B+1) for a fixed j∈{1,…,2n(B+1)} except the index such that paths of length three constituted by tasks from 𝒱, are allotted on πl.Using Lemma3.9, we know that the number of 𝒱 tasks executed on processors π1+(j-1)2(B+1) and π2j(B+1) for a fixed j is 6+2B.In conclusion we have{𝒜1,…,𝒜n} which forms a 𝒜 with desired properties.The construction suggested previously can be easily adapted to obtain a bipartite graph of depth one. Moreover, from the proof of Theorem3.5, we can derive the following theorem.Theorem 3.12.
The problem of deciding whether an instance of(P,G*)|β,cij=d(πℓ,πk)=1,pi=1|Cmax has a schedule of length at most three is 𝒩𝒫-complete with β∈{prec,bipartite}.Proof.
The proof is similar as the proof of Theorem3.5 by considering the graph G̃′ instead of widget G̃. Nevertheless each path of length two induced by the 𝒱 tasks is transformed into two paths of length one.
We use the same construction as it is proposed for the proof of Theorem3.5. Nevertheless, all paths of length three are transformed into two paths in the following way: vi*[0]→vi*[1] and vi*[0]→vi*[2]. These three must be executed on the same processors. Indeed, if vi*[2] admits several predecessors, it is obvious. Otherwise, suppose that vi*[0] is allotted on a processor π. So vi*[1] must be executed at t=1 on π. The task vi*[2] is scheduled at t=2 on a neighborhood processor. Therefore no task from the graphs 𝒵 and G̃′ can be executed on processor π at t=2. Now using the same arguments as previously there is a schedule of length three if and only if the set 𝒜={a1,…,a3n} can be partitioned into n disjoint subsets 𝒜1,…,𝒜n each summing up to B.The proof of Theorem3.5 therefore implies that the problem where the tasks can be duplicated is also 𝒩𝒫-complete.Corollary 3.13.
The problem of deciding whether an instance of(P,G*)|β;cij=d(πℓ,πk);pi=1,dup|Cmax with G*∈𝒢 has a schedule of length at most three is 𝒩𝒫-complete with β∈{prec,bipartite}.Proof.
The proof comes directly from Theorems3.5 and 3.12. In fact, Lemma 3.8 implies that no task can be duplicated (the number of the tasks is equal to the number of processors times 3).Moreover,  nonapproximability results can be deduced.Corollary 3.14.
No polynomial-time algorithm exists with a performance bound less than 4/3 unless𝒫=𝒩𝒫 for the problems (P,G*)|β;cij=d(πℓ,πk); pi=1|Cmaxand(P,G*)|β;cij=d(πℓ,πk); pi=1,dup|Cmaxβ∈{prec,bipartite} with G*∈𝒢.Proof.
The proof of Corollary3.14 is an immediate consequence of the impossibility theorem; see [9, page 4].


### 3.2. Discussion

In the previous section, we propose a class graph𝒢 for which the problem of deciding whether an instance of (P,G*)|β;cij=d(πℓ,πk);pi=1|Cmax has a schedule of length at most three is 𝒩𝒫-complete with β∈{prec,bipartite} and G*∈𝒢.Hereafter, we will exhibit the parameters(L,k) for some classic structured graphs in order to prove that the class graph 𝒢 is not empty.(i)
For a gridG*=Grid(m,p) (m,p∈ℕ, where the couple (i,j) designates the  j the position in the i the line; 1≤i≤m,1≤j≤p) (or torus) topology, we need k=2n+1 lines and L=2B+2 columns. The set of vertices for the graph G a subgraph of G* with the desired properties given by Definition 3.2 is V={(i,j),2≤i≤2n,ieven,2≤j≤2B+3} and V′={(i,1),1≤i≤2n+1}∪{(i,j),1≤i≤2n+1,iodd;1≤j≤2B+3}.(ii)
For the complete binary tree, it is sufficient to consider a tree with height of⌈log(n)⌉+2B+1.(iii)
For the HypercubeH(d) topology (or cube connected cycles), it is sufficient to have d=2⌈log(n)⌉+B+2.(iv)
….


## 3.1. The Class Graph𝒢

We propose a large class of graph𝒢 for which the problem of deciding whether an instance (P,G*)|prec;cij=d(πℓ,πk);pi=1|Cmax≤3 is 𝒩𝒫-complete.We present now a graph class for which we may apply the same polynomial-time transformation mechanism from  3-PARTITION problem to show that our scheduling problem when processor networks belong to this class is𝒩𝒫-complete. Hereafter, we give the definition of the prism graph.Definition 3.1.
A prismP=(VP,EP) of size k and length L (k,L∈ℕ) is a connected undirected graph for that  (i)
there are two sets of verticesK and K′ such as K⊂VP, K′⊂VP∖{K}, and |K|=|K′|=k. The vertices are denoted s1,…,sk (resp. s1′,…,sk′);(ii)
it exists an order onK and K′ vertices such that (∀si∈K,si′∈K,1≤i≤k) there is a path of length L denoted Ci between si and si′;(iii)
(i≠j)∧x∈Ci∖{si,si′}∧y∈Cj∖{sj,sj′}⇒(x,y)∉EP.Moreover, the size of a prism is polynomial ink. An illustration is given in Figure 2.Figure 2
An example of a prism of sizek and length L.Definition 3.2.
Let𝒢 be a collection of graphs. 𝒢 possess the prism property if and only if ∀n0,∀n1∈ℕ∃G∈𝒢, such that G contains a unique subgraph G1=(V1,E1) of G induced by vertices V1⊂V with a prism of size k=n0 and length L=n1.Lemma 3.3.
The class graph𝒢 is not empty.Proof.
In particular we will see in Section3.2 classic structured graph like torus, grid, complete binary tree, and so forth, belonging to this class graph.Theorem 3.4.
The problem of deciding whether an instance of(P,G*)|β;cij=d(πℓ,πk);pi=1|Cmax has a schedule of length at most two is polynomial with β∈{prec,bipartite} and G*∈𝒢.Proof.
No communication is allowed between two pairs of tasks.The remainder of this section is devoted to proving Theorem3.5.Theorem 3.5.
The problem of deciding whether an instance of(P,G*)|prec;cij=d(πk,πl);pi=1|Cmax has a schedule of length at most three is 𝒩𝒫-complete with G*∈𝒢.Proof.
The proof is established by a reduction of the  3-PARTITION problem [8].
Instance
A finite set𝒜 of 3M elements {a1,…,a3M}, a bound B∈ℕ+, and a size s(a)∈ℕ for each a∈𝒜 such that each s(a) satisfies B/4<s(a)<B/2 and such that ∑a∈𝒜s(a)=MB.Question 1.
CanA be partitioned into M disjoint sets 𝒜1,…,𝒜M of 𝒜 such that for all i∈[1,…,M],B=∑a∈𝒜is(a)=∑a∈𝒜s(a)/M∈ℕ?
3-PARTITION is known to be𝒩𝒫-complete in the strong sense [8]. (Even if B is polynomially bounded by the instance size, the problem is still 𝒩𝒫-complete.)
It is easy to see that(P,G*)|prec,cij=d(πl,πk)=1,pi=1|Cmax≤3∈𝒩𝒫.
Given an instanceℐ of the  3- PARTITION problem, we construct an instance ℐ′ of the scheduling problem (P,G*)|prec;cij=d(πℓ,πk);pi=1|Cmax≤3 with G*∈𝒢, in the following way.
The precedence graphG̃=𝒲+𝒵, which will be scheduled on the processors network G*, is decomposed into two disjointed graphs, denoted as follows by 𝒲 and 𝒵 (the graph 𝒵 is a collection of graphs Zs(aj), i.e., 𝒵=∪aj∈𝒜Zs(aj)). Hereafter, graphs 𝒵 and 𝒲 are characterized.GraphZi
Leti be an integer such that i>1. Graph Zi consists of 4×i vertices denoted by Zi[k,0], Zi[k,1], where 0≤k<2i. The precedence constraints between these tasks are defined as follows: (i)
arcsZi[j,0]→Zi[j,1] for any j, 0≤j≤2i-1,(ii)
arcsZi[2j,0]→Zi[2j+1,1] for any j, 0≤j≤i-1,(iii)
arcsZi[2j,0]→Zi[2j-1,1] for any j, 1≤j≤i-1.Remark 3.6.
Valid scheduling of length three for the case where the precedence graph isZi in a path of 2i processors is as follows, for any j, 0≤j≤2i-1,  (i)
tasksZi[j,0] and Zi[j,1] are executed on πj,(ii)
tasksZi[j,ℓ] are executed at time ℓ, for any ℓ∈{0,1}, if j is even,(iii)
tasksZi[j,ℓ] are otherwise executed at time ℓ+1, for any ℓ∈{0,1}.
See Figure3 for graph Z2 and Figure 4 for the valid scheduling described in Remark 3.6.Figure 3
GraphZ2.Figure 4
Valid schedule of length three for graphZ2.Graph𝒲
Remark 3.7.
A path of lengthl admits l+1 vertices.
The𝒲=(𝒱∪𝒱′;E𝒲) graph will be defined as follows. Let G*=(V*,E*) be a graph such that G*∈𝒢, with V*={v1*,…,vn**}. By Definition 3.2, we know that it exists a unique subgraph G=(V⊂V*,E⊂E*) of size k and length L with desired properties. In the following we set k=n and L=2B+1 and the size of G*=(V*,E*) is polynomial in k. Note that n*≫2B.
The𝒲-graph is defined by polynomial-time transformations from the G*-graph. The graph given in Figure 5 will be used to illustrated the following construction. (i)
The paths of length three are created and precedence constraints are added (see Figure6). The two sets of tasks 𝒱1 and 𝒱′ are created.(ii)
The tasks are partitioned into three subsets𝒱′, 𝒦, and 𝒱 (see Figure 7).(iii)
The𝒱1-tasks are now partitioned into two subsets 𝒦 and 𝒱. We consider the subgraph induced by the 𝒱∪𝒱′-tasks (see Figure 8) as the 𝒲-graph.
The purpose of removing these tasks is to allow the tasks of𝒦-graph when the tasks of 𝒲-graph, deprived of these tasks, will be executed on the graph of processors.
The set of verticesV* is partitioned into two sets V*=V′∪V:  (i)
V={v1*,…,v2n(B+1)*} the vertices of G, and defined the vertices of the n unique paths of length (2B+1) respecting the characteristics given by Definition 3.1,(ii)
V′={v2n(B+1)+1*,…,vn**}, the set of an other vertices. Note that these vertices do not belong to G graph.
The definition of the𝒲 graph is given below.  (i)
∀i∈{1,…,2n(B+1)}, we create a path of length three vi*[0],vi*[1], and vi*[2], with edges vi*[0]→vi*[1]→vi*[2]. The set of tasks will be denoted 𝒱1={vi*[j]|∀i∈{1,…,2n(B+1)},j∈{0,1,2}}. The cardinality of 𝒱1 is 6n(B+1) (see Figure 6).(ii)
∀i∈{2n(B+1)+1,…,n*}, we create a path of length three vi*[0]→vi*[1]→vi*[2]. This set of tasks will be denoted 𝒱′. The number of tasks is 3(n*-2n(B+1)) with n*=|V*|.(iii)
(k,l)∈E*, we add the edges vk*[0]→vl*[2] and vl*[0]→vk*[2] (see Figure 6).
Now,4nB tasks are removed from 𝒲-graph. (In order to clarify the polynomial-time transformation, we give priority to create tasks and remove some ones instead of enumerating all precedence constraints.) Therefore,  we consider the following index sets: (i)
J0={2i(B+1)∣i={1,2,…,n}},(ii)
J1={2i(B+1)+1∣i∈{0,1,2,…,n-1},(iii)
I0={k∈{1,…,2n(B+1)}∖{J0∪J1}and|kiseven},(iv)
I1={k∈{1,…,2n(B+1)}∖{J0∪J1}and|kisodd}.
We remove from the𝒱1-set the following tasks vk*[0], vk*[1] with k∈I0, (resp. vk*[1], vk*[2] with k∈I1). 𝒦 denotes the set of removed tasks (see Figure 7). Finally, we put 𝒱=𝒱1∖𝒦 with |𝒱|=2nB+6n (see Figure 8).
Figures5, 6, 7, and 8 describe the construction of 𝒲-graph from G*∈𝒢.
E𝒲 is the set of arcs as described above.
Lastly, the number of processors ism=n*, and they are numbered as πi with i∈[1,n*].
In summary the precedence graphG̃=𝒲+𝒵 is composed by 𝒲=(𝒱∪𝒱′,E𝒲) with 3n*-4nB tasks and the precedence constraints given before and the graph 𝒵={⋃aj∈𝒜Zs(ai)} with 4nB tasks.
The transformation is computed in polynomial time.(i)
Let us assume that𝒜={a1,…,a3M} can be partitioned into M disjoint subsets 𝒜1,…,𝒜M with each summing up to B. We will then prove that there is a schedule of length three at most.
Let us construct this schedule.
First, the taskvi*[j]∈𝒱′∪𝒱 is executed on the processors πi to t=j with j∈{0,1,2} (if this task exists).
Consider the processors on which the set of𝒱-tasks are scheduled. By the previous allocation, these processors are numbered as π1,…,π2n(B+1).
Let{𝒜1,…,𝒜n} be a partition of 𝒜. Consider 𝒜i={ai1,ai2,ai3} with a fixed i. The tasks of Zs(aj), aj∈𝒜i are executed between processors π1+2(i-1)(B+1) and π2i(B+1). Moreover, the tasks Zs(aj)[l,k], k∈{0,1}, l∈J0 (resp., k∈{1,2}, l∈J1) are scheduled on 2s(aij) processors in succession in order to respect a schedule of length three.
Thus without loss of generality, we suppose that the tasks ofZs(ai1) are scheduled between processors π1+2(i-1)(B+1) and π2(i-1)(B+1)+2s(ai1). In similar way, the tasks Zs(ai2) (resp., Zs(ai3)) are executed between processors π2+2(i-1)(B+1)+2s(ai1) and π1+2(i-1)(B+1)+2s(ai1)+2s(ai2) (resp. π2+2(i-1)(B+1)+2s(ai1)+2s(ai2) and π2i(B+1)).
(ii)
Let us assume now that there is a scheduleS of length at most three. We will prove that 𝒜={a1,…,a3M} can be partitioned into M disjoint subsets 𝒜1,…,𝒜M with each summing up to B.Figure 5
The beginning of the construction of𝒲 graph from G*∈𝒢.Figure 6
Next step of the construction of𝒲 graph. Path of length three is created and precedence constraints between tasks are added.Figure 7
Partition ofG* graph into tasks sets 𝒱, 𝒦, and 𝒱.Figure 8
The final𝒲 graph issue from several transformations.Lemma 3.8.
In any valid schedule of length three there is no idle time.Proof.
The number of processors ism=n* and the number of tasks is 3n* (4nB for 𝒵-graph and 3n*-4nB for 𝒲 graph).Lemma 3.9.
In any valid schedule of length three, the subgraph induced by𝒱 tasks must be executed on 2(B+1) processors in succession.Proof.
Consider the subgraph induced by the𝒱 tasks. This precedence graph admits paths of length two and these paths must be executed on the same processor (no communication delay is allowed).
Consider the tasks of path of length one. Letvi*[0]∈𝒱 be a task without predecessor. By construction vi*[0] admits one successor denoted by  vi+1*[2]∈𝒱.
Suppose that these two tasks are allotted on the same processorπl. Since that vi+1*[2] admits another predecessor denoted by vi+2*[0]∈𝒱 then vi+1*[2] is allotted at t=2.
The taskvi+2*[0] cannot be executed at t=1 on πl since this task admits another successor as vi+1*[2]. Therefore, it exists an idle slot at t=1 on the processor πl. By construction there is no independent task and since the 𝒵 graph admits only path of length one, then no task can be allotted on this idle slot. This is impossible
In conclusion, the subgraph induced by𝒱 tasks must be executed on 2(B+1) processors in succession.Lemma 3.10.
In any valid schedule of length three, two subgraphs induced by the𝒱 tasks from two disjoint paths of length 2(B+1) cannot be allotted on the same processors.Proof.
Consider the𝒱 tasks which are elements of two disjoints paths of length 2(B+1). A task without predecessor of one path cannot be allotted on the same processor as a task without successor of other path since there is no isolated task to schedule.Lemma 3.11.
In any valid valid schedule of length three theZs(aj) tasks must be executed on the same processors as the 𝒱 tasks.Proof.
LetΠ={πl∣𝒱 tasks allotted on πl} be the set of processors on which the 𝒱 tasks are executed.
Suppose that theZs(aj)-tasks are executed on processors πk∉Π. By Lemma 3.8, there is no idle slot, then the tasks on the path of length three are necessarily allotted on processor π*∈Π. This is impossible by Lemma 3.9.With previous lemmas, we know that6n(B+1) tasks (the 𝒱 tasks and the Zs(aj)-tasks) are executed on the n disjoints paths of length 2B+1. By Definition 3.2, we know that the graph G* admits a unique set of n disjoints paths of length 2B+1 with desired properties. Moreover with the precedence constraints, these tasks are allotted on a processor path of length (2B+1). Without loss of generality, we suppose that a task vlß𝒱 is executed on the processor πl with l∈{2n(B+1)+1,…,n*}.Building the partition{𝒜1,…,𝒜n} with desired property from S schedule of length three, we know that two tasks of the same subgraph Zs(aj) (see Lemma 3.11) cannot be executed on two different paths. The edge distance between these two processors is at least two.We define𝒜ℓ such that aj∈𝒜ℓ if and only if the tasks of the graph Zs(aj) are executed between the processors numbered as π1+(j-1)2(B+1) to π2j(B+1) with a fixed j.Now, we will compute∑ai∈𝒜ℓs(ai).Using previous remarks, without loss of generality, we suppose thatvi*[k] with i∈{1,…,2n(B+1)} and k∈{0,1,2} (if it exists) are executed on πl with l∈{1,…,2n(B+1)}. Consider the Zs(aj)-tasks which are scheduled between processors π1+(j-1)2(B+1) and π2j(B+1) for a fixed j∈{1,…,2n(B+1)} except the index such that paths of length three constituted by tasks from 𝒱, are allotted on πl.Using Lemma3.9, we know that the number of 𝒱 tasks executed on processors π1+(j-1)2(B+1) and π2j(B+1) for a fixed j is 6+2B.In conclusion we have{𝒜1,…,𝒜n} which forms a 𝒜 with desired properties.The construction suggested previously can be easily adapted to obtain a bipartite graph of depth one. Moreover, from the proof of Theorem3.5, we can derive the following theorem.Theorem 3.12.
The problem of deciding whether an instance of(P,G*)|β,cij=d(πℓ,πk)=1,pi=1|Cmax has a schedule of length at most three is 𝒩𝒫-complete with β∈{prec,bipartite}.Proof.
The proof is similar as the proof of Theorem3.5 by considering the graph G̃′ instead of widget G̃. Nevertheless each path of length two induced by the 𝒱 tasks is transformed into two paths of length one.
We use the same construction as it is proposed for the proof of Theorem3.5. Nevertheless, all paths of length three are transformed into two paths in the following way: vi*[0]→vi*[1] and vi*[0]→vi*[2]. These three must be executed on the same processors. Indeed, if vi*[2] admits several predecessors, it is obvious. Otherwise, suppose that vi*[0] is allotted on a processor π. So vi*[1] must be executed at t=1 on π. The task vi*[2] is scheduled at t=2 on a neighborhood processor. Therefore no task from the graphs 𝒵 and G̃′ can be executed on processor π at t=2. Now using the same arguments as previously there is a schedule of length three if and only if the set 𝒜={a1,…,a3n} can be partitioned into n disjoint subsets 𝒜1,…,𝒜n each summing up to B.The proof of Theorem3.5 therefore implies that the problem where the tasks can be duplicated is also 𝒩𝒫-complete.Corollary 3.13.
The problem of deciding whether an instance of(P,G*)|β;cij=d(πℓ,πk);pi=1,dup|Cmax with G*∈𝒢 has a schedule of length at most three is 𝒩𝒫-complete with β∈{prec,bipartite}.Proof.
The proof comes directly from Theorems3.5 and 3.12. In fact, Lemma 3.8 implies that no task can be duplicated (the number of the tasks is equal to the number of processors times 3).Moreover,  nonapproximability results can be deduced.Corollary 3.14.
No polynomial-time algorithm exists with a performance bound less than 4/3 unless𝒫=𝒩𝒫 for the problems (P,G*)|β;cij=d(πℓ,πk); pi=1|Cmaxand(P,G*)|β;cij=d(πℓ,πk); pi=1,dup|Cmaxβ∈{prec,bipartite} with G*∈𝒢.Proof.
The proof of Corollary3.14 is an immediate consequence of the impossibility theorem; see [9, page 4].


## 3.2. Discussion

In the previous section, we propose a class graph𝒢 for which the problem of deciding whether an instance of (P,G*)|β;cij=d(πℓ,πk);pi=1|Cmax has a schedule of length at most three is 𝒩𝒫-complete with β∈{prec,bipartite} and G*∈𝒢.Hereafter, we will exhibit the parameters(L,k) for some classic structured graphs in order to prove that the class graph 𝒢 is not empty.(i)
For a gridG*=Grid(m,p) (m,p∈ℕ, where the couple (i,j) designates the  j the position in the i the line; 1≤i≤m,1≤j≤p) (or torus) topology, we need k=2n+1 lines and L=2B+2 columns. The set of vertices for the graph G a subgraph of G* with the desired properties given by Definition 3.2 is V={(i,j),2≤i≤2n,ieven,2≤j≤2B+3} and V′={(i,1),1≤i≤2n+1}∪{(i,j),1≤i≤2n+1,iodd;1≤j≤2B+3}.(ii)
For the complete binary tree, it is sufficient to consider a tree with height of⌈log(n)⌉+2B+1.(iii)
For the HypercubeH(d) topology (or cube connected cycles), it is sufficient to have d=2⌈log(n)⌉+B+2.(iv)
….


## 4. An Approximation Algorithm for Processor Networks with a Fixed Diameter

### 4.1. Description and Correctness of an Algorithm

In order to design an efficient polynomial-time approximation algorithm, the classic strategy consists of taking an instance of the combinatorial optimization problem and applying some transformations and/or using polynomial-time algorithms as subroutines (shortest path, spanning tree, maximum matching, etc.). Afterwards, it is sufficient to evaluate the best lower bound for any optimal solution, and this lower bound may be compared to the feasible solution for the combinatorial optimization problem in order to determine the ratio of an approximation algorithm.Here, instead of considering an instanceI and trying to directly develop a feasible solution for the (P,G*)|prec;cij=d(πk,πl)=1;pi=1|Cmax problem, we consider a partial instance of I of our scheduling problem (An instance I is constituted by a precedence graph with unit execution time and unit communication time, m processors in G graph form, with the distance function.), denoted I*. (The partial instance I* of I is constituted only by the precedence graph with unitary tasks and unitary communication time) For any instance I*, we use the classic approximation algorithm proposed by Munier and König [10] for the P¯|prec;cij=1; pi=1|Cmax problem. We obtain a feasible schedule, denoted S (we omit consideration of the processor graph for the moment) for the previous problem. Nevertheless, this solution is not feasible for our scheduling problem.We proceed with polynomial-time chain of transformations, from scheduleS to a schedule S′′, in order to get a feasible schedule. It is only in the last step, only for schedule S′′, that we guarantee a feasible schedule for the problem (P,G*)|prec;cij=d(πk,πl)=1;pi=1|Cmax.This chain is defined as follows:I*→fS→gS′→hS′′ (The schedule S′ is a feasible solution for the{P¯,G}|prec;cij=d(πk,πl)=1;pi=1|Cmax  problem.), where f is the Munier-König algorithm [10], g the dilatation algorithm (see [11] for details or Appendix A) and h the folding algorithm (see [12] for details or Appendix B).Subsequently, we will consider the three following scheduling problems:(i)
P¯|prec;cij=1; pi=1|Cmax,(ii)
P¯|prec;cij≥2; pi=1|Cmax,(iii)
and finally(P,G*)|prec;cij=d(πk,πl)=1;pi=1|Cmax.The principal steps of the algorithm are described below.An approximation algorithm uses three steps. In each step we apply an algorithm for a specified scheduling problem [10–12]. In the two first steps, a schedule is produced (these schedules are not feasible for our problem).(i)
In the first step of an algorithm, a schedule (denotedS on an unbounded number of processors), for the scheduling problem P¯|prec;cij=1;pi=1|Cmax is produced. For this problem, Munier and König [10] presented a (4/3)-approximation algorithm that is based on an integer linear programming formulation. They use the following procedure: an integrity constraint is relaxed, and a feasible schedule is produced by rounding.(ii)
The second step of an algorithm produces a schedule (denotedS′, also on an unbounded number of processors) from S by applying the dilatation principle proposed by [11] for the problem P¯|prec;cij≥2;pi=1|Cmax (this algorithm produces a feasible schedule for the large communication delay problem from unitary communication delay. We therefore have S′=g(S) where g is the dilatation algorithm.(iii)
The third step produces a scheduleS′′ (feasible for the (P,G*)|prec,cij=d(πk,πl)=1,pi=1|Cmax problem) on the G topology from S′ using the folding principle [12]. The folding procedure constructs a feasible schedule on restricted number of processors from a feasible schedule on an unbounded number of processors. Thus, S′′=h(S′) with h being the folding algorithm.Note that the length of scheduleS is less than S′, which is less than S′′. The three steps are summarized in Figure 9. The notation description is given in the proof of Theorem 4.2.Figure 9
Description of chain of polynomial-time transformations.Theorem 4.1.
The previous algorithm leads a feasible schedule for the problem(P,G*|prec;cij=d(πk,πl)=1;pi=1|Cmax.Proof.
Proof is clear from the previous discussion concerning the description of an algorithm. Indeed, the communication delay is preserved and the precedence constraint is respected. Moreover, at mostm tasks are executed at any time.


### 4.2. Relative Performance Analysis

Theorem 4.2.
The problem(P,G*)|prec;cij=d(πk,πl)=1;pi=1|Cmax may be approximable within a factor of ((δ+1)2/3)+1 using the previous algorithm.Proof.
We denote usingCmaxx,y,z with x∈{opt,∅}, y∈{UET-UCT,UET-LCT(c=δ),G*}, and z∈{m,∞} the length of the schedule.     Moreover ρG*,m (resp., ρG*,∞) designates the performance ratio on a G processor network model with a bounded (resp., unbounded) number of processors.
Now let us examine the relative performance of this algorithm.(i)
According to an algorithm, the first step deals with the problemP¯|prec;cij=1;pi=1|Cmax.
First of all theSchedule (UET-UCT,∞) is not optimal. Using the algorithm from [10] gives us a 4/3 relative performance. And so, by [10], we know that
(4.1)Cmax⁡UET-UCT,∞≤43Cmax⁡opt,UET-UCT,∞.(ii)
In the second step, a feasible solution for a large communication delayc=δ (recall that δ stands for the diameter of processors network) is created. This solution comes from using the dilatation algorithm. Then, the expansion coefficient is (δ+1)/2 ([11]). And so,(4.2)Cmax⁡UET-LCT(c=δ),∞≤δ+12⋅43Cmax⁡opt,UET-LCT(c=δ),∞,(4.3)Cmax⁡UET-LCT(c=δ),∞≤2(δ+1)3Cmax⁡opt,UET-LCT(c=δ),∞.
Thus, we have a schedule on a UET-LCT task system with a communication delay equal to δ and an infinite number of processors.
By definition it is obvious that(4.4)Cmax⁡G*,∞≤Cmax⁡UET-LCT(c=δ),∞,(4.5)Cmax⁡opt,UET-UCT,∞≤Cmax⁡opt,UET-LCT(c=δ),∞.
It is necessary to evaluate the gap between the optimal length for the schedule on a fully connected processor graph and a processor graph with a diameter of length K. For this, we consider unitary tasks subject to precedence constraints and an unbounded number of processors.Lemma 4.3.
The gap between a schedule on a fully connected graph of processors with a large communication delayc, for all pairs of tasks, and a schedule on a graph of processors with a diameter of length K∈ℕ, is at most (c+1)/2.Proof.
We need to compare first the relative performance of this schedule on our model with network processor. The relative performance for the UET-LCT task system is not valid for our model. We need to compute a new bound for this schedule on our model.
Letp={x1,x2,…,xn}be a critical path of the schedule (i.e., a path that gives the length of the schedule). Suppose that there is a communication delay between each pair of tasks (xi,xi+1) with 1≤i<n. In the UET-LCT task system ( with a communication delay equal to c for all pair of tasks) the length of the schedule would be (1+c)n-c units of time. In the graph of processors with a diameter of length k, the same path allows a length of (k/2)(n-1)+n units of time. The worst case of the length for this path is n+(n-1)k and the best case is 2n-1. So, the ratio is (n(1+c)-c)/(2n-1). For the large n, we obtain the desired result.By applying Lemma4.3, which is valid for all schedules, and in particular for the optimum, with c=δ, we obtain(4.6)Cmax⁡opt,UET-LCT(c=δ),∞≤(δ+1)2Cmax⁡opt,G*,∞
and so(4.7)Cmax⁡G*,∞≤Cmax⁡UET-LCT(c=δ),∞by(4.4)(4.8)Cmax⁡G*,∞≤2(δ+1)3Cmax⁡opt,UET-LCT(c=δ),∞using(4.3)(4.9)Cmax⁡G*,∞≤(δ+1)23Cmax⁡opt,G,∞using(4.6)(4.10)ρG*,∞≤(δ+1)23.
Now we have to transform this schedule using an infinite number of processors into a schedule with a bounded number of processors. This can be done easily using the method from [12]. The new worst-case relative performance is just increased by one. Thus we have(4.11)ρG*,m≤ρG*,∞+1≤(δ+1)23+1.Remark 4.4.
Note that the order of the operations may be modified. Nevertheless, the ratio becomes7/6×(δ+1)2. Indeed, the folding principle may be used just after the solution given by an algorithm proposed by Munier and König [10]. We then obtain a schedule on m processors. Afterwards, we apply the dilation principle. This order yields a polynomial-time approximation algorithm with a ratio bounded by 7/6×(δ+1)2.Remark 4.5.
we may recall two classic results in scheduling problems for which the performance ratio increases by one between the unbounded and bounded versions.(1)  When the number of processors is unlimited, the problem of scheduling a set ofn tasks under precedence constraints with noncommunication delay is polynomial. It is sufficient to use the classical algorithm given by Bellman [13] as well as the two techniques widely used in project management: CPM (Critical Path Method) and PERT (Project/Program Evaluation and Review Technique). In contrast, when the number of processors is limited, the problem becomes 𝒩𝒫-complete and a (2-1/m)-approximation is developed by Graham, see [14], where m designates the number of processors based on a list scheduling in which no order on tasks is specified.(2)  The second illustration is given by the transition to UET-UCT on unrestricted version to the restricted variant. In [10], we know the existence of a 4/3-approximation algorithm. Using the previous result Munier and Hanen in [15] design a 7/3-approximation for the restricted version.


## 4.1. Description and Correctness of an Algorithm

In order to design an efficient polynomial-time approximation algorithm, the classic strategy consists of taking an instance of the combinatorial optimization problem and applying some transformations and/or using polynomial-time algorithms as subroutines (shortest path, spanning tree, maximum matching, etc.). Afterwards, it is sufficient to evaluate the best lower bound for any optimal solution, and this lower bound may be compared to the feasible solution for the combinatorial optimization problem in order to determine the ratio of an approximation algorithm.Here, instead of considering an instanceI and trying to directly develop a feasible solution for the (P,G*)|prec;cij=d(πk,πl)=1;pi=1|Cmax problem, we consider a partial instance of I of our scheduling problem (An instance I is constituted by a precedence graph with unit execution time and unit communication time, m processors in G graph form, with the distance function.), denoted I*. (The partial instance I* of I is constituted only by the precedence graph with unitary tasks and unitary communication time) For any instance I*, we use the classic approximation algorithm proposed by Munier and König [10] for the P¯|prec;cij=1; pi=1|Cmax problem. We obtain a feasible schedule, denoted S (we omit consideration of the processor graph for the moment) for the previous problem. Nevertheless, this solution is not feasible for our scheduling problem.We proceed with polynomial-time chain of transformations, from scheduleS to a schedule S′′, in order to get a feasible schedule. It is only in the last step, only for schedule S′′, that we guarantee a feasible schedule for the problem (P,G*)|prec;cij=d(πk,πl)=1;pi=1|Cmax.This chain is defined as follows:I*→fS→gS′→hS′′ (The schedule S′ is a feasible solution for the{P¯,G}|prec;cij=d(πk,πl)=1;pi=1|Cmax  problem.), where f is the Munier-König algorithm [10], g the dilatation algorithm (see [11] for details or Appendix A) and h the folding algorithm (see [12] for details or Appendix B).Subsequently, we will consider the three following scheduling problems:(i)
P¯|prec;cij=1; pi=1|Cmax,(ii)
P¯|prec;cij≥2; pi=1|Cmax,(iii)
and finally(P,G*)|prec;cij=d(πk,πl)=1;pi=1|Cmax.The principal steps of the algorithm are described below.An approximation algorithm uses three steps. In each step we apply an algorithm for a specified scheduling problem [10–12]. In the two first steps, a schedule is produced (these schedules are not feasible for our problem).(i)
In the first step of an algorithm, a schedule (denotedS on an unbounded number of processors), for the scheduling problem P¯|prec;cij=1;pi=1|Cmax is produced. For this problem, Munier and König [10] presented a (4/3)-approximation algorithm that is based on an integer linear programming formulation. They use the following procedure: an integrity constraint is relaxed, and a feasible schedule is produced by rounding.(ii)
The second step of an algorithm produces a schedule (denotedS′, also on an unbounded number of processors) from S by applying the dilatation principle proposed by [11] for the problem P¯|prec;cij≥2;pi=1|Cmax (this algorithm produces a feasible schedule for the large communication delay problem from unitary communication delay. We therefore have S′=g(S) where g is the dilatation algorithm.(iii)
The third step produces a scheduleS′′ (feasible for the (P,G*)|prec,cij=d(πk,πl)=1,pi=1|Cmax problem) on the G topology from S′ using the folding principle [12]. The folding procedure constructs a feasible schedule on restricted number of processors from a feasible schedule on an unbounded number of processors. Thus, S′′=h(S′) with h being the folding algorithm.Note that the length of scheduleS is less than S′, which is less than S′′. The three steps are summarized in Figure 9. The notation description is given in the proof of Theorem 4.2.Figure 9
Description of chain of polynomial-time transformations.Theorem 4.1.
The previous algorithm leads a feasible schedule for the problem(P,G*|prec;cij=d(πk,πl)=1;pi=1|Cmax.Proof.
Proof is clear from the previous discussion concerning the description of an algorithm. Indeed, the communication delay is preserved and the precedence constraint is respected. Moreover, at mostm tasks are executed at any time.


## 4.2. Relative Performance Analysis

Theorem 4.2.
The problem(P,G*)|prec;cij=d(πk,πl)=1;pi=1|Cmax may be approximable within a factor of ((δ+1)2/3)+1 using the previous algorithm.Proof.
We denote usingCmaxx,y,z with x∈{opt,∅}, y∈{UET-UCT,UET-LCT(c=δ),G*}, and z∈{m,∞} the length of the schedule.     Moreover ρG*,m (resp., ρG*,∞) designates the performance ratio on a G processor network model with a bounded (resp., unbounded) number of processors.
Now let us examine the relative performance of this algorithm.(i)
According to an algorithm, the first step deals with the problemP¯|prec;cij=1;pi=1|Cmax.
First of all theSchedule (UET-UCT,∞) is not optimal. Using the algorithm from [10] gives us a 4/3 relative performance. And so, by [10], we know that
(4.1)Cmax⁡UET-UCT,∞≤43Cmax⁡opt,UET-UCT,∞.(ii)
In the second step, a feasible solution for a large communication delayc=δ (recall that δ stands for the diameter of processors network) is created. This solution comes from using the dilatation algorithm. Then, the expansion coefficient is (δ+1)/2 ([11]). And so,(4.2)Cmax⁡UET-LCT(c=δ),∞≤δ+12⋅43Cmax⁡opt,UET-LCT(c=δ),∞,(4.3)Cmax⁡UET-LCT(c=δ),∞≤2(δ+1)3Cmax⁡opt,UET-LCT(c=δ),∞.
Thus, we have a schedule on a UET-LCT task system with a communication delay equal to δ and an infinite number of processors.
By definition it is obvious that(4.4)Cmax⁡G*,∞≤Cmax⁡UET-LCT(c=δ),∞,(4.5)Cmax⁡opt,UET-UCT,∞≤Cmax⁡opt,UET-LCT(c=δ),∞.
It is necessary to evaluate the gap between the optimal length for the schedule on a fully connected processor graph and a processor graph with a diameter of length K. For this, we consider unitary tasks subject to precedence constraints and an unbounded number of processors.Lemma 4.3.
The gap between a schedule on a fully connected graph of processors with a large communication delayc, for all pairs of tasks, and a schedule on a graph of processors with a diameter of length K∈ℕ, is at most (c+1)/2.Proof.
We need to compare first the relative performance of this schedule on our model with network processor. The relative performance for the UET-LCT task system is not valid for our model. We need to compute a new bound for this schedule on our model.
Letp={x1,x2,…,xn}be a critical path of the schedule (i.e., a path that gives the length of the schedule). Suppose that there is a communication delay between each pair of tasks (xi,xi+1) with 1≤i<n. In the UET-LCT task system ( with a communication delay equal to c for all pair of tasks) the length of the schedule would be (1+c)n-c units of time. In the graph of processors with a diameter of length k, the same path allows a length of (k/2)(n-1)+n units of time. The worst case of the length for this path is n+(n-1)k and the best case is 2n-1. So, the ratio is (n(1+c)-c)/(2n-1). For the large n, we obtain the desired result.By applying Lemma4.3, which is valid for all schedules, and in particular for the optimum, with c=δ, we obtain(4.6)Cmax⁡opt,UET-LCT(c=δ),∞≤(δ+1)2Cmax⁡opt,G*,∞
and so(4.7)Cmax⁡G*,∞≤Cmax⁡UET-LCT(c=δ),∞by(4.4)(4.8)Cmax⁡G*,∞≤2(δ+1)3Cmax⁡opt,UET-LCT(c=δ),∞using(4.3)(4.9)Cmax⁡G*,∞≤(δ+1)23Cmax⁡opt,G,∞using(4.6)(4.10)ρG*,∞≤(δ+1)23.
Now we have to transform this schedule using an infinite number of processors into a schedule with a bounded number of processors. This can be done easily using the method from [12]. The new worst-case relative performance is just increased by one. Thus we have(4.11)ρG*,m≤ρG*,∞+1≤(δ+1)23+1.Remark 4.4.
Note that the order of the operations may be modified. Nevertheless, the ratio becomes7/6×(δ+1)2. Indeed, the folding principle may be used just after the solution given by an algorithm proposed by Munier and König [10]. We then obtain a schedule on m processors. Afterwards, we apply the dilation principle. This order yields a polynomial-time approximation algorithm with a ratio bounded by 7/6×(δ+1)2.Remark 4.5.
we may recall two classic results in scheduling problems for which the performance ratio increases by one between the unbounded and bounded versions.(1)  When the number of processors is unlimited, the problem of scheduling a set ofn tasks under precedence constraints with noncommunication delay is polynomial. It is sufficient to use the classical algorithm given by Bellman [13] as well as the two techniques widely used in project management: CPM (Critical Path Method) and PERT (Project/Program Evaluation and Review Technique). In contrast, when the number of processors is limited, the problem becomes 𝒩𝒫-complete and a (2-1/m)-approximation is developed by Graham, see [14], where m designates the number of processors based on a list scheduling in which no order on tasks is specified.(2)  The second illustration is given by the transition to UET-UCT on unrestricted version to the restricted variant. In [10], we know the existence of a 4/3-approximation algorithm. Using the previous result Munier and Hanen in [15] design a 7/3-approximation for the restricted version.


## 5. Conclusion

We have sharpened the demarcation line between the polynomially solvable and𝒩𝒫-hard case of the central scheduling problem (UET-UCT) on a structured processor network by showing that its decision is polynomially solvable for Cmax≤2 while it is 𝒩𝒫-complete for Cmax≥3. This result is given for a large class of graph with a nonconstant diameter. This result implies there is no ρ-approximation algorithm with ρ<4/3. These results are extended to the case of precedence graph is a bipartite graph.Lastly, we complete our complexity results by developing a polynomial-time approximation algorithm for(P,G*)|prec,cij=d(πk,πl)=1,pi=1|Cmax with a worst-case relative performance of (δ+1)2/3+1, where δ designates the diameter of the graph. An interesting question for further research is to find a polynomial-time approximation algorithm with performance guarantee ρ with ρ∈ℝ.



---

*Source: 476939-2011-06-21.xml*