Introduction

In many applications of multiprocessor scheduling problem a set of tasks is performed on parallel identical processors. Any task can run on any processor and each processor can perform no more than one task at a time. The number of processors is known and the objective is to determine a feasible schedule S such that the maximum completion time is minimized [Brucker, 2007]. We consider two basic N P -hard [Ullman, 1975] models of multiprocessor scheduling.

The problem with release times and due dates while scheduling tasks to parallel identical processors is a classical combinatorial optimization problem. Following the 3-field classification scheme proposed by [Graham et al., 1979], this problem is denoted by P |r j |L max .

In another multiprocessor scheduling problem precedence constructions between tasks are represented by a directed acyclic task graph G = (U, E). The expression u i ≺ u j means that the task u j may be initiated only after completion of the task u i . The goal is to minimize the maximum completion time. For this models, we can consider two problems. In the first well-known problem the number of processors m is known and the goal is to minimize the maximum completion time. In the other one the completion time is known and the goal is to minimize the number of processors. Informally the first problem can be seen as a "dual" to the second one. We are interested in the problem where the goal is to minimize the number of processors.

A lot of research in scheduling has concentrated on the construction of nondelay schedule. A nondelay schedule has been defined by Baker [Baker, 1974] as a feasible schedule in which no processor is kept idle at a time when it could begin processing a task. An inserted idle time schedule (IIT) has been defined by J.Kanet and V.Sridharam [Kanet & Sridharan, 2000] as a feasible schedule in which a processor is kept idle at a time when it could begin processing a task.

In [Grigoreva, 2014] we considered scheduling with inserted idle time for m parallel identical processors with the objective of minimizing the makespan and proposed branch and bound algorithm for multiprocessor scheduling problem with precedence-constrained tasks.

The goal of this paper is to propose IIT schedule for two models with the objective of minimizing the number of processors. We propose an approximate IIT algorithm named MPELS/IIT (minimum processors earliest latest start/ inserted idle time) and branch and bound algorithm, which produces a feasible IIT(inserted idle time) schedule for a fixed completion time T S and m processors. The algorithm may be used in a binary search mode to find the smallest number of processors.

Problems Statement

We consider a system of tasks U = {u 1 u 2 , . . . , u n }. Each task is characterized by its execution time t(u i ). Set of tasks is performed on parallel identical processors. Any task can run on any processor and each processor can perform no more than one task at a time. Task preemption is not allowed.

We consider two problem. Problem MPRD. Each task is characterized by its execution time t(u i ), its release time r(u i ) and its due dates D(u i ). Release time r(u i ) -the time at which the task is ready for processing and due dates D(u i ) specifies the time limit by which should be completed. A schedule for a task set U is the mapping of each task u i ∈ U to a start time τ (u i ) and a processor num(u i ). In order to make the feasible schedule, it is necessary that the start time τ (u i ) of each task u i ∈ U , satisfies the inequality

r(u i ) ≤ τ (u i ) ≤ D(u i ) − t(u i ).

Length of schedule S is the quantity

T S = max{τ (u i ) + t(u i )|u i ∈ U }.

We need determine the minimum number of identical processors that are needed in order to execute all tasks in time. Then it is clear T S ≤ D max where D max = max{D(u i ) u i ∈ U }.

Problem MPPC. Precedence constructions between tasks are represented by a directed acyclic task graph G = ⟨U, E⟩. E is a set of directed arcs, an arc e = (u i , u j ) ∈ E if and only if u i ≺ u j . The expression u i ≺ u j means that the task u j may be initiated only after completion of the task u i . The critical path t cp is the maximal path in graph G from the initial vertex to the final vertex. We need determine the minimum number of identical processors that are needed in order to execute this set of tasks in a time not exceeding the time of the critical path t cp .

For each task u, we define the earliest starting time v min (u) and the latest start time v max (u). The earliest starting time is numerically equal to the length of the maximal path in the graph G from the initial vertex to the vertex u. The latest start timev max (u) of task u is numerically equal to the difference between the length of the critical path t cp and the length of the maximal path from the task u, to the final vertex. To schedule is feasible, it is necessary, that, for each task u i ∈ U, start time of its execution τ (u i ) satisfies the inequalities

v min (u i ) ≤ τ (u i ) ≤ v max (u i ), τ (u i ) + t(u i ) ≤ τ (u j ), if u i ≺ u j .

Subtask of these two problems is the task of constructing a feasible schedule for the given number of processors and the given execution time. To solve this problem we apply the branch and bound method in conjunction with binary search. Branch and bound method constructs a feasible schedule S of length T for m processors. The algorithm may be used in a binary search mode to find the smallest number of processors or the smallest makespan.

First, we propose an approximate IIT algorithm named MPELS/IIT. Then by combining the MPELS/IIT algorithm and B&B method this paper presents BB/IIT algorithm which can find optimal solutions for MPRD and MPPC scheduling problem.

Lower Bound of the Number of Processors

Our target is to construct a feasible schedule for a fixed makespan C max with the minimum number of processors. We set C max = t cp or C max = D max . First we define the lower bound of the number of processors [Fernandez & Bussell, 1973]. We calculate lower bound

LB1 = ⌈ ∑ n i=1 t(u i )/C max ⌉.

For problem MPRD we define for each task u i , the earliest starting time v min (u i ) = r(u i ) and the latest start time

v max (u i ) = D(u i )−t(u i ). We consider time intervals [t 1 , t 2 ] ⊆ [0, C max ]. Let L([t 1 , t 2 ]) be a length of time interval [t 1 , t 2 ].

Let M (t 1 , t 2 ) be the total minimal time of tasks in time interval [t 1 , t 2 ], then

M (t 1 , t 2 ) = ∑ ui∈U min{L(x(u i )), L(y(u i ))},

where

x(u i ) = [v min (u i ), v min (u i ) + t(u i )] ∩ [t 1 , t 2 ], y(u i ) = [v max (u i ), v max (u i ) + t(u i )] ∩ [t 1 , t 2 ]. Then LB2 = max{M (t 1 , t 2 )/C max |[t 1 , t 2 ] ∈ [0, C max ].} Let LB = max{LB1, LB2}.

Approximate Algorithms

We defined the lower bound of the number of processors. We set the number of processors smin = LB and construct a feasible schedule step by step.

We have to define how select a task, how select a processor. Let k tasks have been put in the schedule and partial schedule S k have been constructed. For each task u i , we know the earliest starting time v min (u i ) and the latest start time v max (u i ), which is a priority of task.

We know the completion time of processors time k [1 : smin]. Denote t min (k) = min{time k [i]|i ∈ 1 : smin} is the earliest time of ending all the tasks included in a partial solution S k .

Definitoin 1 The tasku cr / ∈ S k is called the delayed task for S k , if v max (u cr ) < t min (k), where v max (u cr ) = min{v max (u)|u / ∈ S k }.

Lemma 1 Let delayed task u cr for a partial solution S k exists, then a partial solution S k is unfeasible.

Approximate Algorithm MPELS/IIT

The approximate schedule is constructed by MPELS/IIT algorithm as follows:

1. Determine the processor l 0 such as t min (l 0 ) = min{time k [i]|i ∈ 1..smin}.

2. Select the task u 0 , such as

v max (u 0 ) = min{v max (u i )|v min (u i ) − t min (k) ≤ I k , u i / ∈ S k }.

3. If t min (l 0 ) > v max (u 0 ), then smin := smin + 1 and time[smin] := 0; go to 1.

6 Branch and Bound Method for Constructing a Feasible Schedule BB(U, T, z; S, m S )

The branch and bound algorithm produces a feasible IIT( inserted idle time) schedule for a fixed makespan T and the number of processors z.. In order to optimize over m we must iterate the scheduling process over possible values of m. We proposed the formal description of the branch and bound method in [Grigoreva, 2014].

In order to make the feasible schedule, it is necessary that each task u i ∈ U, the start time of its execution τ (u i ) satisfies the inequality

v min (u i ) ≤ τ (u i ) ≤ v max (u i ).

In order to describe the branch and bound method it is necessary to determine the set of tasks that we need to add to a partial solution, the order in which task will be chosen from this set and the rules that will be used for eliminating partial solutions.

Let I be the total idle time of processors in the feasible schedule S of length T S for m processors, then

I = z • T S −

∑ n i=1 t(u i ). For a partial solution σ k we know idle(u i )-idle time of processor before start the task u i . At each level k will be allocated a set of tasks U k , which we call the the ready tasks. These are tasks that need to add to a partial solution σ k−1 , so check all the possible continuation of the partial solutions.

Definitoin 2 Task u / ∈ σ k is called the ready task at the level k, if r(u) satisfies the inequality r(u) − t min (k) ≤ I − ∑ u∈σ k idle(u i ).

The main way of reducing of the exhaustive search will be the earliest possible identification unfeasible solutions. We formulated and proof the rules of deleting unfeasible solutions in [Grigoreva, 2015].

Lemma 2 Let delayed task u cr for a partial solution σ k exists, then a partial solution σ k is unfeasible.

Lemma 3 Let delayed task u cr for a partial solution σk = σ k−1 ∪ u k exists, then for any task u, such as max{t min (k − 1), r(u)} + t(u) > v max (u cr ) a partial solution σ k−1 ∪ u is unfeasible. Lemma 4 Let delayed task u cr for a partial solution σ k = σ k−1 ∪ u k exists, and max{t min (k − 1), r(u cr ))} + t(u cr ) > v max (u k ) then the partial solution σ k−1 is unfeasible.

Another method for determining unfeasible partial solutions based on a comparison of resource requirements of tasks and total processing power. In this case we propose to modify the algorithm for determining the interval of concentration [Fernandez & Bussell, 1973] for the complete schedule. We apply this algorithm to a partial schedule σ k and determine its admissibility.

We consider time intervals [t 1 , t 2 ] ⊆ [t min (k), T S ]. Let M P (t 1 , t 2 ) be the total time of free processors in time interval [t 1 , t 2 ] then

M P (t 1 , t 2 ) = m ∑ i=1 max{0, (t 2 − max{t 1 , time k [i]})}.

For all task u i / ∈ σ k we find minimal time of its begin:

v(u i ) = max{v min (u i ), t min (k)}. Let L([t 1 , t 2 ]) be a length of time interval [t 1 , t 2 ].

Let M k (t 1 , t 2 ) be the total minimal time of tasks in time interval [t 1 , t 2 ], then

M k (t 1 , t 2 ) = ∑ ui / ∈σ k min{L(x k (u i )), L(y(u i ))}, where x(u i ) = [v min (u i ), v min (u i ) + t(u i )] ∩ [t 1 , t 2 ], y(u i ) = [v max (u i ), v max (u i ) + t(u i )] ∩ [t 1 , t 2 ]. Let est(σ k ) = max [t1,t2]∈[tmin(k),TS ] {M k (t 1 , t 2 ) − M P (t 1 , t 2 ).} Lemma 5 If est(σ k ) > 0 then a partial solution σ k is unfeasible.

Computation Result

In this section we present numerical results for the proposed algorithms. To test the approximate M P ELS/IIT algorithm and BB/IIT algorithm, we conducted computational experiment. The quality of the solutions we estimated average ratio of the solution value over the lower bound of the minimum number of processors LB.

We restrict the number of iterations for a searching feasible solution by branch and bound method. If a feasible schedule S of the makespan T for m processors was not received for 20000 iterations, it was assumed that this does not exist and the number of processors m increased. This approach provided a schedule for all test problems, but whether or not the solutions obtained are exact or approximate remains an open question. Therefore, the quality of the solutions was estimated against to the lower bound of the minimum number of processors LB. We used tests from Standard Task Graph Set, which is available at http://www.kasahara.elec.waseda.ac.jp/schedule/.

Standard Task Graph Set is a kind of benchmark for evaluation of multiprocessor scheduling problem with precedence-constrained tasks, where optimal decisions are known. The each series of tests consists of 180 examples. We considered tests from Standard Task Graph Set with n = 100, and n = 300, where n is the number of tasks.

First, we tested approximate algorithms. The first column of all tables contains the number of tasks n.

In Table 1 average relative error RT = (mL − LB)/LB for three algorithms are presented. Results for model with release and due dates are presented in the first, second and three columns and results for model with precedence constrained tasks are presented in fourth, fifth and sixth columns. We see from table 1 that the best approximate schedules are created by approximate algorithm MPELS.

The average relative error RT = (mL − LB)/LB of schedules obtained by BB/IIT algorithm and M P ELS/IIT algorithm are presented in next tables.

Table 2 and table 3 shows the results for M P ELS/IIT algorithm and BB/IIT algorithm. The column N opt shows the cases (in percents) where optimal schedules were obtained by there methods. The next column shows the number of cases (in percents) in which approximate solutions with mL ≤ LB + 2 were obtained, but optimal solutions could not be obtained because of iterations limit. But an intermediate solution can be an optimal solution. The next two columns shows the number of cases in which RT ∈ (0.05, 0.3] and RT greater then 0.3.

Approximate solutions with the error RT of less then 10 percent were obtained by MPEST/IIT algorithm in 90 percent of the cases tested. It is seen from Table 2 that optimal solutions were obtained for 63 percent (in average) of the cases tested. It is seen from Table 3 that optimal solutions were obtained for 68,58 percent (in average) of the cases tested.

Conclusion

In this work we proposed the new approximate algorithm and branch and bound method for solving the multiprocessor scheduling problem with the objective of minimizing of the number of processors. We found that the minimum number processors problem can be solved within reasonable time for moderate-size systems. With an increasing number of tasks, branch and bound method requires more time to obtain the optimal solution.

Limiting the number of iterations seems justified and promising way to obtain a good approximate solution.