Exact and Approximation Algorithms for the Scheduling Tasks to Minimize the Number of Processors Natalia S. Grigoreva St.Petersburg State University Universitetskaj nab. 7/9, 199034 St.Petersburg, Russia n.s.grig@gmail.com Abstract 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 iden- tical processors. Any task can run on any processor and each processor can perform no more than one task at a time. Preemption is not al- lowed. 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 algo- rithm, 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 proces- sors. To illustrate the effectiveness of our algorithms we tested them on randomly generated set of tasks. 1 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. Copyright ⃝ c by the paper’s authors. Copying permitted for private and academic purposes. In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org 239 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 Problems Statement We consider a system of tasks U = {u1 u2 , . . . , 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 ). Length of schedule S is the quantity 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 vmin (ui ) ≤ τ (ui ) ≤ vmax (ui ), 240 τ (ui ) + t(ui ) ≤ τ (uj ), if ui ≺ uj . 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 Lower Bound of the Number of Processors Our target is to construct a feasible schedule for a fixed makespan Cmax with the minimum number of pro- cessors. We set Cmax = tcp or Cmax = Dmax . First we define∑ the lower bound of the number of processors n [Fernandez & Bussell, 1973]. We calculate lower bound LB1 = ⌈ i=1 t(ui )/Cmax ⌉. For problem MPRD we de- fine 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 ∑ M (t1 , t2 ) = min{L(x(ui )), L(y(ui ))}, ui ∈U where x(ui ) = [vmin (ui ), vmin (ui ) + t(ui )] ∩ [t1 , t2 ], y(ui ) = [vmax (ui ), vmax (ui ) + t(ui )] ∩ [t1 , t2 ]. Then LB2 = max{M (t1 , t2 )/Cmax |[t1 , t2 ] ∈ [0, Cmax ].} Let LB = max{LB1, LB2}. 4 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 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 . Definitoin 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 Approximate Algorithm MPELS/IIT 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. 241 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 Approximate Algorithm MPELS/ND 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 Algorithm SPELS/IIT 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 Algorithm for Constructing an Optimal Schedule 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 . 242 6 Branch and Bound Method for Constructing a Feasible Schedule BB(U, T, z; S, mS ) 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 ui ∈ U, the start time of its execution τ (ui ) satisfies the inequality vmin (ui ) ≤ τ (ui ) ≤ vmax (ui ). 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 TS for m processors, then n I = z · TS − i=1 t(ui ). For a partial solution σk we know idle(ui )— idle time of processor before start the task ui . At each level k will be allocated a set of tasks Uk , 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) − tmin (k) ≤ I − u∈σ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 = σk−1 ∪ uk exists, and max{tmin (k − 1), r(ucr ))} + t(ucr ) > vmax (uk ) 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 [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]})}. i=1 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 ∑ Mk (t1 , t2 ) = min{L(xk (ui )), L(y(ui ))}, ui ∈σ / k where x(ui ) = [vmin (ui ), vmin (ui ) + t(ui )] ∩ [t1 , t2 ], y(ui ) = [vmax (ui ), vmax (ui ) + t(ui )] ∩ [t1 , t2 ]. Let est(σk ) = max {Mk (t1 , t2 ) − M P (t1 , t2 ).} [t1 ,t2 ]∈[tmin (k),TS ] Lemma 5 If est(σk ) > 0 then a partial solution σk is unfeasible. 243 Table 1: Relative Error of the Minimum Number of Processors for Approximate Algorithms n MPELS/RD SPELS/RD MPND/RD MPELS/PC SPELS/PC MPED/PC 100 0.141 0.153 0.161 0.132 0.171 0.153 100 0.152 0.174 0.213 0.141 0.231 0.142 100 0.136 0.201 0.222 0.151 0.246 0.171 300 0.158 0.197 0.198 0.173 0.137 0.156 300 0.163 0.155 0.221 0.162 0.163 0.210 300 0.175 0.186 0.193 0.210 0.165 0.221 Average 0.156 0.177 0.201 0.161 0.185 0.175 Table 2: Relative Error of the Minimum Number of Processors for MPELS/IIT Method. n Nopt mL ≤ LB + 2 RT ≤ 0.3 RT > 0.3 100 63.1 11.2 22.5 3.1 100 61.4 12.3 22.0 4.3 100 64.2 11.5 19.1 5.2 300 65.1 10.9 20.1 4.5 300 59.8 11.6 24.4 4.2 300 62.1 12.4 20.6 5.1 Average 62.60 11.63 21.44 4.37 7 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 exam- ples. 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. 244 Table 3: Relative Error of the Minimum Number of Processors for BB/IIT Method. n Nopt mL ≤ LB + 2 RT ≤ 0.3 RT > 0.3 100 70,1 10,3 16.7 2.9 100 67.4 13.1 15.4 4,1 100 71,2 14,1 9.8 4.9 300 72,1 13,8 10.2 3.9 300 63,3 13,2 20,4 3,1 300 67.4 14,3 13,6 4.7 Average 68.58 13.19 14.35 3.88 8 Conclusion In this work we proposed the new approximate algorithm and branch and bound method for solving the mul- tiprocessor 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. References [Graham et al., 1979] Graham,J.R.,Lawner, E.L. and R. Kan.(1979). Optimization and approximation in deter- ministic sequencing and scheduling: A survey, Ann. of Disc. Math. 5 (10), 287-326. [Brucker, 2007] Brucker,P.(2007). Scheduling Algorithms.Springer,Berlin. [Ullman, 1975] Ullman,J. (1975). NP-complete scheduling problems J. Comp. Sys. Sci. ( 171), 394-394. [Baker, 1974] Baker,K.R.(1974.) Introduction to Sequencing. John Wiley & Son, New York. [Kanet & Sridharan, 2000] Kanet,J. & Sridharan, V. (2000). Scheduling with inserted idle time:problem taxon- omy and literature review, Oper.Res 48 (1), 99-110. [Grigoreva, 2014] Grigoreva,N.S.(2014). Branch and bound method for scheduling precedence constrained tasks on parallel identical processors, in Lecture Notes in Engineering and Computer Science: Proc. of The World Congress on Engineering 2014, WCE 2014, 2-4 July, 2014 ,(pp. 832–836). London, U.K. [Grigoreva, 2015] Grigoreva,N.S.(2015). Multiprocessor Scheduling with Inserted Idle Time to Minimize the Max- imum Lateness, Proceedings of the 7th Multidisciplinary International Conference of Scheduling:Theory and Applications. (pp.814–816). Prague,MISTA. [Fernandez & Bussell, 1973] Fernandez,E. & Bussell,B.(1973). Bounds the number of processor and time for multiprocessor optimal schedules, IEEE Tran. on Comp. 4 (11), 745-751. 245