The multiprocessor scheduling problem is one of the classic NP-hard optimization problems. The goal of this paper is to prepare algorithms for scheduling problem where 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. Preemption is not allowed. The processing time of each task is known. We study both the case in which there exist precedence constrains among tasks and the case in which each task has a release time, when it becomes available for processing, and a due dates. The time by which all tasks need to be completed (makespan) is known. We have to find where and when each task will be executed.The goal is to minimize the number of processors. We compare the nondelay schedule, in which no processor is kept idle at a time when it could begin processing a task and an inserted idle time schedule in which a processor is kept idle at this time. We propose some approximate algorithms and branch and bound algorithm, which produces a feasible IIT( inserted idle time) schedule for a fixed makespan and the number of processors. The algorithm may be used in a binary search mode to find the smallest number of processors. To illustrate the effectiveness of our algorithms we tested them on randomly generated set of tasks.
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 |rj |Lmax.
In another multiprocessor scheduling problem precedence constructions between tasks are represented by a directed acyclic task graph G = (U; E). The expression ui ≺ uj means that the task uj may be initiated only after completion of the task ui. 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 TS and m processors. The algorithm may be used in a binary search mode to find the smallest number of processors. 2
We consider a system of tasks U = {u1u2; : : : ; un}. Each task is characterized by its execution time t(ui). 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(ui), its release time r(ui) and its due dates D(ui). Release time r(ui) - the time at which the task is ready for processing and due dates D(ui) specifies the time limit by which should be completed. A schedule for a task set U is the mapping of each task ui ∈ U to a start time (ui) and a processor num(ui). In order to make the feasible schedule, it is necessary that the start time (ui) of each task ui ∈ U , satisfies the inequality
r(ui) ≤
(ui) ≤ D(ui) − t(ui):
TS = max{ (ui) + t(ui)|ui ∈ 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 TS ≤ Dmax where Dmax = max{D(ui) ui ∈ 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 = (ui; uj ) ∈ E if and only if ui ≺ uj . The expression ui ≺ uj means that the task uj may be initiated only after completion of the task ui. The critical path tcp 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 tcp.
For each task u, we define the earliest starting time vmin(u) and the latest start time vmax(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 timevmax(u) of task u is numerically equal to the difference between the length of the critical path tcp 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 ui ∈ U; start time of its execution (ui) satisfies the inequalities
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. 3
Our target is to construct a feasible schedule for a fixed makespan Cmax with the minimum number of processors. We set Cmax = tcp or Cmax = Dmax. First we define the lower bound of the number of processors [Fernandez & Bussell, 1973]. We calculate lower bound LB1 = ⌈∑n i=1 t(ui)=Cmax⌉. For problem MPRD we define for each task ui, the earliest starting time vmin(ui) = r(ui) and the latest start time vmax(ui) = D(ui)−t(ui).
We consider time intervals [t1; t2] ⊆ [0; Cmax]: Let L([t1; t2]) be a length of time interval [t1; t2].
Let M (t1; t2) be the total minimal time of tasks in time interval [t1; t2]; then where
M (t1; t2) = ∑ min{L(x(ui)); L(y(ui))}; ui2U x(ui) = [vmin(ui); vmin(ui) + t(ui)] ∩ [t1; t2]; y(ui) = [vmax(ui); vmax(ui) + t(ui)] ∩ [t1; t2]: LB2 = max{M (t1; t2)=Cmax|[t1; t2] ∈ [0; Cmax]:} LB = max{LB1; LB2}: 4
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 Sk have been constructed. For each task ui, we know the earliest starting time vmin(ui) and the latest start time vmax(ui), which is a priority of task.
We know the completion time of processors timek[1 : smin]. Denote tmin(k) = min{timek[i]|i ∈ 1 : smin} is the earliest time of ending all the tasks included in a partial solution Sk.
De nitoin 1 The task ucr ∈= Sk is called the delayed task for Sk, if vmax(ucr) < tmin(k), where vmax(ucr) = min{vmax(u)|u ∈= Sk}: Lemma 1 Let delayed task ucr for a partial solution Sk exists, then a partial solution Sk is unfeasible. 4.1
The approximate schedule is constructed by MPELS/IIT algorithm as follows: 1. Determine the processor l0 such as tmin(l0) = min{timek[i]|i ∈ 1::smin}: 2. Select the task u0, such as vmax(u0) = min{vmax(ui)|vmin(ui) − tmin(k) ≤ Ik; ui ∈= Sk}: 3. If tmin(l0) > vmax(u0); then smin := smin + 1 and time[smin] := 0; go to 1. 4. If idle(u0) = vmin(u0) − tmin(l0) > 0 then select task u1 such as
vmax(u1) = min{vmax(ui)|vmin(ui) ≤ tmin; ui ∈= Sk}: 5. if idle(u0) > vmax(u1) − vmax(u0)) or tmin(k) + t(u1) ≤ vmax(u0)) then select u1 else select u0. 6. If idle(u0) > 0, and we select u0 then choose a task u ∈= Sk, which can be executed during the idle time of the processor l0 without increasing the start time of the task u0, namely vmax(u ) = min{vmax(ui)|vmin(ui) + t(ui) ≤ vmin(u0); ui ∈= Sk}: 7. If the task u is found, then we assign to the processor l0 the task u ; otherwise the task u0: We compare schedules which constructed by MPELS/IIT algorithm with schedules constructed by nondelay algorithm named MPELS/ND. 4.2
The approximate schedule is constructed by MPELS/ND algorithm as follows: 1. Determine the processor l0 such as tmin(l0) = min{timek[i]|i ∈ 1::smin}: 2. Select the task u0, such as vmax(u0) = min{vmax(ui)|vmin(u0) ≤ tmin(l0); ui ∈= Sk}: 3. If tmin(l0) > vmax(u0) then smin := smin + 1; time[smin] := 0, go to 1.
4. Assign the task u0 to the processor l0: MPELS/ND algorithm is a list algorithm and it selects a task, which can be executed without the idle of processor. If we find the task, which can begin at time tmin(l0), we set this task to processor l0.
We can select a processor by another way. At first we select a job, then select a processor for this job. 4.3
1. Select the task u0, such as vmax(u0) = min{vmax(ui)|ui ∈= Sk}: 2. If tmin(l0) > vmax(u0) then smin := smin + 1 and time[smin] := 0, go to 1. 3. Select a processor l1 such as timek[l1] = max{timek[i]|vmin(u0) ≤ time[i] ≤ vmax(u0); i ∈ 1 : smin}: 4. Assign the task u0 to the processor l1: 5
The branch and bound algorithm produces a feasible IIT schedule for a fixed makespan TS and a fixed number of processor m. In order to optimize over m we must iterate the scheduling process over possible values of m. Let mopt be minimum processors of optimal schedule. We defile interval (a; b] such as a < mopt ≤ b:
The preliminary step of the algorithm is a heuristic search for a good solution in order to have a good upper bound for the optimum number of processors.
The upper bound b = mL. Then mopt ∈ (a; b].
Select z = ⌈(a + b)=2⌉ and use branch and bound method for constructing a feasible schedule BB(U; D; m; S) a feasible schedule maximum lateness z. If we find a feasible schedule then we take interval (a; z], else we take interval (z; b] repeat .
Algorithm SCHEDU LE(U ; Sopt; mopt) 1. Calculate a = LB − 1 and b = mL: 2. While b − a > eps do 3. Set z := ⌈(a + b)=2⌉: 4. Use procedure BB(U; Cmax; z; S; mS) for constructing a feasible schedule. 5. If we find feasible schedule S , then Srec := S; mrec := mS and set b := mS, else set a := z: 6. Sopt := Srec; mopt := mrec:
BB(U; T ; z; S; mS )
De nitoin 2 Task u ∈= k is called the ready task at the level k, if r(u) satis es the inequality r(u) − tmin(k) ≤ I − ∑u2 k idle(ui):
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 ucr for a partial solution k exists, then a partial solution k is unfeasible. Lemma 3 Let delayed task ucr for a partial solution k = k 1 ∪ uk exists, then for any task u, such as max{tmin(k − 1); r(u)} + t(u) > vmax(ucr) a partial solution k 1 ∪ u is unfeasible.
Lemma 4 Let delayed task ucr for a partial solution k = t(ucr) > vmax(uk) then the partial solution k 1 is unfeasible. k 1 ∪ uk exists, and max{tmin(k − 1); r(ucr))} +
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 [t1; t2] ⊆ [tmin(k); TS ]. Let M P (t1; t2) be the total time of free processors in time interval [t1; t2] then
m
M P (t1; t2) = ∑ max{0; (t2 − max{t1; timek[i]})}: For all task ui ∈= k we find minimal time of its begin: v(ui) = max{vmin(ui); tmin(k)}. Let L([t1; t2]) be a length of time interval [t1; t2].
Let Mk(t1; t2) be the total minimal time of tasks in time interval [t1; t2]; then where
Let Lemma 5 If est( k) > 0 then a partial solution k is unfeasible.
i=1 ui2= k Mk(t1; t2) =
∑ min{L(xk(ui)); L(y(ui))}; x(ui) = [vmin(ui); vmin(ui) + t(ui)] ∩ [t1; t2]; y(ui) = [vmax(ui); vmax(ui) + t(ui)] ∩ [t1; t2]: est( k) = [t1;t2]2m[tmaixn(k);TS]{Mk(t1; t2) − M P (t1; t2):}
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 Nopt 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. 8
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.