An O(n) Time Algorithm for Scheduling UET-UCT of Bipartite Digraphs of Depth One on Two Processors

Ruzayn Quaddoura

Department of Computer Science, Faculty of Information Technology, Zarqa University, Zarqa, Jordan.

DOI: 10.4236/ajor.2016.61010                

Abstract

Given n unit execution time (UET) tasks whose precedence constraints form a directed acyclic graph, the arcs are associated with unit communication time (UCT) delays. The problem is to schedule the tasks on two identical processors in order to minimize the makespan. Several polynomial algorithms in the literature are proposed for special classes of digraphs, but the complexity of solving this problem in general case is still a challenging open question. We present in this paper an O(n) time algorithm to compute an optimal schedule for the class of bipartite digraphs of depth one.

Keywords

Scheduling, Makespan, Precedence Constraints, Bipartite Graph, Optimal Algorithm

Received 17 November 2015; accepted 24 January 2016; published 28 Janaury 2016

1. Introduction

The problem of scheduling a set of tasks on a set of identical processors under a precedence relation has been studied for a long time. A general description of the problem is the following. There are n tasks that have to be executed by m identical processors subject to precedence constraints and (may be without) communication delays. The objective is to schedule all the tasks on the processors such that the makespan is the minimum. Generally, this problem can be represented by a directed acyclic graph called a task graph. The set of vertices V corresponds to the set of tasks and the set of edges E corresponds to the set of precedence constrains. With every vertex i, a weight is associated that represents the execution time of the task i, and with every edge, a weight is associated that represents the communication time between the tasks i and j. If and the task i starts its execution at time t on a processor P, then either j starts its execution on P at time greater than or equal to, or j starts its execution on some other processor at time greater than or equal to.

According to the three field notation scheme introduced in [1] and extended in [2] for scheduling problems with communication delays, this problem is denoted as.

A large amount of work in the literature studies this problem with a restriction on its structure: the time of execution of every task is one unit execution time (UET), the number of processors m is fixed, the communication delays are neglected, constant or one unit (UCT), or special classes of task graph are considered. We find In this context, the problem, is polynomial [3] [4] , i.e. when the communication delays are not taken into account. On the contrary, the problem remains an open question [5] .

The problem of two processors scheduling with communication delays is extensively studied [6] [7] . In particular, it is proven in [8] that the problem is NP-hard where c is a large integer, whereas this problem is polynomial when the task graph is a complete binary tree.

A challenging open problem is the two processors scheduling with UET-UCT, i.e. the problem for which the complexity is unknown. However, several polynomial algorithms have been shown for special classes of task graphs, especially for trees [9] [10] , interval orders [11] and a sub- class of series parallel digraphs [12] . In this paper we present an time algorithm to compute an optimal algorithm for the class of bipartite digraphs of depth one, that is the digraphs for which every vertex is either a source (without predecessors) or a sink (without successors).

2. Scheduling UET-UCT for a Bipartite Digraph of Depth One on Two Processors

2.1. Preliminaries

A schedule UET-UCT on two processors for a general directed acyclic digraph is defined by a function, where is the time for which the task v is executed and the processor on which the task v is scheduled. A schedule is feasible if:

a), if then

b) If then if u and v are scheduled on the same processor, and if u and v are scheduled on distinct processors.

A time t of a schedule is said to be idle if one of the processors is idle during this time. The makespan or the length of a schedule is the last non-idle time of, that is:

A schedule is optimal if is the minimum among all feasible schedules.

Let be a bipartite digraph of depth one. Since every vertex of G is either a source or a sink, there exists always a feasible schedule such that the sources B are executed before executing the sinks W. Our algorithm for solving the problem under consideration produces an optimal schedule satisfies this condition and that we called a natural schedule defined as follows.

Definition 1 Let be a bipartite digraph of depth one. A natural schedule of G is obtained by scheduling first the sources B then the sinks W starting from the processor and alternating between and such that the resulting schedule is optimal.

The definition of a natural schedule of a bipartite digraph of depth one implies the following properties:

1) The number of sources executed on is and the number of sources executed on is.

2) If is even then:

a) contains at most 2 idle times, the first is at time, and the second is at time.

b) If is an idle time then is idle at this time (may be also).

3) If is odd then:

a) contains at most 3 idle times, the first is at time, the second is at time, and the third is at time.

b) If or is an idle time then is idle at this time and is non.

4).

Without loss of generality, we can suppose that both idle times and, if exist, are distinct. In this supposition, if and only if has at most the idle time otherwise.

Figure 1. Bipartite digraphs of depth one and their corresponding natural schedules.

. Figure 1 illustrates some bipartite digraphs of depth one and their corresponding natural schedules.

2.2. Scheduling Algorithm

The idea of solving the problem is to determine the necessary and sufficient conditions to exist idle times in a natural schedule of the task graph. In the following, we consider is a bipartite digraph of depth one where B is the set of sources and W is the set of sinks, and is a natural schedule for G. A vertex () is called universal if . We distinguish two cases, is even and is odd.

Lemma 2 Assume that is even.

1) The two processors and are idle at time if and only if G is a bipartite complete.

2) The processor only is idle at time if and only if one of the following holds:

a) Every vertex of B is universal except exactly one.

b) Every vertex of W is universal except exactly one.

Proof. 1) If G is a bipartite complete then obviously and must be idle at time. The inverse, let b and w be a source and a sink of G. If b is not adjacent to w, then we can schedule b on at time and w on at time, a contradiction. So b must be adjacent to w, therefore G is a bipartite complete.

2) Assume that only is idle at time and the conditions a and b are not hold. Then, there exist and such that and are all not universal. If is a stable set, i.e. no two vertices are adjacent, we can schedule on at time and on at time, a contradiction. If is not a stable set then we can suppose that. Since and are not universal, there exist and such that and. But now, we can schedule, b on respectively at time, and, w on respectively at time, a contradiction.

The inverse, suppose that every vertex of B is universal except exactly one. Since is even, there exist scheduled on at time. By 1, the two processors can’t be idle at time. If is not idle at time, then both and are not universal, a contradiction. In a similar way we prove the case b.

Notice that if B (or W) contains exactly one non-universal vertex b then the vertex of W which is independent of b is also non-universal but it is not necessary unique (see Figure 1). Algorithm Schedule_|B|_is_even (G) constructs a natural schedule for if is even, Lemma 2 proves its correctness.

Algorithm Schedule_|B|_is_even (G)

If and then

Schedule alternately on and at times

Schedule alternately on and at times

Else if or then

Let and such that

Schedule b on at time and w on at time

Schedule alternately on and at times

Schedule alternately on and at times

Else let and such that

Schedule on and on at time

Schedule on and on at time

Schedule alternately on and at times

Schedule alternately on and at times

Figure 1 shows the construction of natural schedules of the graphs and resulting from the algorithm Schedule_|B|_is_even (G).

Lemma 3 Assume that is odd.

1) The processor is idle at times and if and only if G is a bipartite complete.

2) The processor is idle at time and not idle at time if and only if

a) There is such that

b) For every, or.

3) The processor is idle at time and not idle at time if and only if

a) There is such that

b) For every for which and for every, where is the set of non-neighbors of w.

Proof. 1) If G is a bipartite complete then obviously is idle at times and. The inverse, let b and w be a source and a sink of G. If b is not adjacent to w, then we can schedule b on at time and w on at time or at time according to the adjacency relation between the source scheduled on at time and w, a contradiction. So b must be adjacent to w, therefore G is a bipartite complete.

2) Assume that is idle at time and not idle at time. The vertex scheduled on at time is of degree less than or equal to, since it must be independent of the vertex scheduled on at time. If there is a vertex such that, then we can schedule w on at time and two vertices from B independent of w on at times and, a contradiction.

The inverse, by 1, the processor is not idle at time or at time. If is not idle at time then the vertex scheduled at this time would be of degree less than or equal to, a contradiction.

3) Assume that is idle at time and not idle at time. The vertex scheduled on at time is of degree less than or equal to, since it must be independent of the two vertices scheduled on at times and. Let such that and let such that. Now, we can schedule on at time, b and another vertex independent of w on at time and respectively, and schedule a vertex independent of b on at time, a contradiction. The inverse, by 1 and 2, the processor can’t be idle at time and any vertex scheduled on at time must be of degree less than or equal to. The processor is idle at time, otherwise the vertex scheduled on at time is of degree less than or equal to, a contradiction.

To construct a natural schedule for G when is odd, we need to the Procedure Two_Vertices (G). This procedure return 1 if the condition 3.b of Lemma 3 holds, and return two vertices w, b such that, and if this condition is not hold.

Procedure Two_Vertices (G)

For to

For to k

If then Return

Return 1.

Algorithm Schedule_|B|_is_odd (G) constructs a natural schedule for if is odd. Lemma 3 proves its correctness.

Algorithm Schedule_|B|_is_odd (G)

If and then

Schedule a vertex on at time

Schedule a vertex on at time

Schedule alternately on and at times

Schedule alternately on and at times

Else if then

Let and such that

Schedule b on at time

Schedule w on at time

Schedule alternately on and at times

Schedule alternately on and at times

Else If Two_Vertices (G) = 1 then

Let and such that

Schedule on at times and

Schedule w on at time

Schedule alternately on and at times

Schedule a vertex on at time

Schedule alternately on and at times

Else let = Two_Vertices (G)

Let and such that

Schedule on at times and respectively

Schedule on at times and respectively

Schedule alternately on and at times

Schedule alternately on and at times

Figure 1 shows the construction of natural schedules of the graphs and resulting from the algorithm Schedule_|B|_is_odd (G).

2.3. Complexity

We assume that is represented by its adjacency lists, so the set of neighbors and the set of non neighbors of every vertex of G are known already. In this supposition, we can check easily that any step (except the step Two_Vertices (G)) of the two algorithms Schedule_|B|_is_even (G) and Schedule_|B|_is_ odd (G) can be executed either within a constant time or within an time where. Let’s prove that the Procedure Two_Vertices (G) runs within time.

The worst case of this Procedure occurs when its result is 1. In this case, for any,

, otherwise, a vertex b independent of and would be of degree less than or equal to. So the number of comparisons of if statement in this procedure is equal to at most. Therefore, the procedure Two_Vertices (G) runs within time and the total time of our scheduling algorithm is.

3. Conclusion

We have presented an time algorithm for the optimal schedule of bipartite digraphs of depth one with UET-UCT on two processors. The complexity of this problem for general directed acyclic graphs is still an open question. We believe that our algorithm can be used to solve this problem in general as follow: Consider a topological sort of a directed acyclic graph G. The linear ordering defined by this topological sort decomposes G into consecutives bipartite digraphs of depth one. The schedule obtained by the concatenation of the schedules of these bipartite digraphs is a feasible schedule or may be modified to a feasible schedule of G. Now, if we can determine the necessary and sufficient conditions to exist idle times in this feasible schedule then we can determine the complexity of this problem. This is a useful guide and foundation for future research.

Acknowledgements

This research is funded by the Deanship of Research and Graduate Studies in Zarqa University/Jordan. The author is grateful to anonymous referee’s suggestion and improvement of the presentation of this paper.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979) Optimization and Approximation in Deterministic Scheduling: A Survey. Annals of Discrete Mathematics, 5, 287-326. http://dx.doi.org/10.1016/S0167-5060(08)70356-X
[2]	Veltman, B., Lageweg, B.J. and Lenstra, L.K. (1990) Multiprocessor Scheduling with Communication Delays. Parallel Computing, 16, 173-182. http://dx.doi.org/10.1016/0167-8191(90)90056-F
[3]	Coffman Jr., E.G. and Graham, R.L. (1972) Optimal Scheduling for Two-Processor Systems. Acta Informatica, 1, 200-213. http://dx.doi.org/10.1007/BF00288685
[4]	Fujii, M., Kasami, T. and Ninomiya, K. (1969) Optimal Sequencing of Two Equivalent Processors. SIAM Journal on Applied Mathematics, 17, 784-789. http://dx.doi.org/10.1137/0117070
[5]	Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman.
[6]	Chrétienne, P. and Picouleau, C. (1995) Scheduling with Communication Delays: A Survey. In: Scheduling Theory and Its Applications, John Wiley & Sons.
[7]	Norman, M.G., Pelagatti, S. and Thanisch, P. (1995) On the Complexity of Scheduling with Communication Delay and Contention. Parallel Processing Letters, 5, 331-341. http://dx.doi.org/10.1142/S012962649500031X
[8]	Afrati, F., Bampis, E., Finta, L. and Mili, I. (2005) Scheduling Trees with Large Communication Delays on Two Identical Processors. Journal of Scheduling, 8, 179-190. http://dx.doi.org/10.1007/s10951-005-6366-3
[9]	Varvarigou, T., Roychowdhury, V.P., Kailath, T. and Lawler, E. (1996) Scheduling in and out Forests in the Presence of Communication Delays. IEEE Transactions on Parallel and Distributed Systems, 7, 1065-1074. http://dx.doi.org/10.1109/71.539738
[10]	Veldhorst, M. (1993) A Linear Time Algorithm to Schedule Trees with Communication Delays Optimally on Two Machines. Technical Report COSOR 93-07, Department of Math, and Computer Science, Eindhoven University of Technology, Eindhoven.
[11]	Ali, H. and El-Rewini, H. (1993) The Time Complexity of Scheduling Interval Orders with Communication Is Polynomial. Parallel Processing Letters, 3, 53-58. http://dx.doi.org/10.1142/S0129626493000083
[12]	Finta, L., Liu, Z., Mills, I. and Bampis, E. (1996) Scheduling UET-UCT Series Parallel Graphs on Two Processors. Theoretical Computer Science, 162, 323-340. http://dx.doi.org/10.1016/0304-3975(96)00035-7