 American Journal of Operations Research, 2013, 3, 589-600 Published Online November 2013 (http://www.scirp.org/journal/ajor) http://dx.doi.org/10.4236/ajor.2013.36056 Open Access AJOR Energetic Extended Edge Finding Filtering Algorithm for Cumulative Resource Constraints Roger Kameugne1,2, Sévérine Betmbe Fetgo3, Laure Pauline Fotso3 1Department of Mathematics, Higher Teachers’ Training College, University of Maroua, Maroua, Cameroon 2Department of Mathematics, Faculty of Sciences, University of Yaounde I, Yaoundé, Cameroon 3Department of Computer Sciences, Faculty of Sciences, University of Yaounde I, Yaoundé, Cameroon Email: rkameugne@yahoo.fr, rkameugne@gmail.com, betmbe2000@yahoo.fr, lpfotso@ballstate.bsu.edu Received September 28, 2013; revised October 28, 2013; accepted November 5, 2013 Copyright © 2013 Roger Kameugne et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. ABSTRACT Edge-finding and energetic reasoning are well known filtering rules used in constraint based disjunctive and cumulative scheduling during the propagation of the resource constraint. In practice, however, edge-finding is most used (because it has a low running time complexity) than the energetic reasoning which needs 2 n time-intervals to be considered (where n is the number of tasks). In order to reduce the number of time-intervals in the energetic reasoning, the maxi- mum density and the minimum slack notions are used as criteria to select the time-intervals. The paper proposes a new filtering algorithm for cumulative resource constraint, titled energetic extended edge finder of complexity 3 n. The new algorithm is a hybridization of extended edge-finding and energetic reasoning: more powerful than the extended edge-finding and faster than the energetic reasoning. It is proven that the new algorithm subsumes the extended edge-finding algorithm. Results on Resource Constrained Project Scheduling Problems (RCPSP) from BL set and PSPLib librairies are reported. These results show that in practice the new algorithm is a good trade-off between the filtering power and the running time on instances where the number of tasks is less than 30. Keywords: Constraint-Based Scheduling; Global Constraint; Cumulative Resource; Energetic Reasoning; Edge-Finding; Extended Edge-Finding; Maximum Density; Minimum Slack 1. Introduction Scheduling is the process of assigning resources to tasks or activities over the time. There exist many types of scheduling problems following the tasks properties (pre- emptive or non-preemptive), the type of resources (dis- junctive or cumulative) and the objective function (make- span, time late...). When a unique cumulative resource with non-preemptive tasks is considered, the problem is called cumulative scheduling problem (CuSP). In a CuSP, a set of tasks T has to be executed on a resource of fixed capacity C. Each task i requires a fixed and constant amount of resource i c, and has to be executed during a fixed amount of time i p without in- terruption between an earliest start time est i (release date) and a latest completion time lct i (deadline). A solution of a CuSP instance is an assignment of valid start time i to each task i in such a way that resource constraints are satisfied i.e., :est lct iii ii iTs s p (1) , : iii i iTss p cC (2) The inequalities in (1) ensure that each task is assigned a feasible start and end time, while (2) enforces the re- source constraint. An example of CuSP is given in Figure 1. The energy of a task i, is defined as iii ecp , its earliest completion time as ect est iii p and its latest start time as lst lct iii p . The energy notation along with that of earliest start and latest completion time may be extended to non-empty sets of tasks as follows: ,estmin est,lctmax lct jj jj j ee (3) where is a non-empty set of tasks. By convention, if is the empty set, est, lct, and 0e . Throughout the paper, it is assumed that for any  R. KAMEUGNE ET AL. Open Access AJOR 590 Figure 1. A scheduling problem of 5 tasks sharing a resource of capa c i ty C = 3. task iT, est lct ii i p and i cC, otherwise the problem has no solution. The CuSP is a NP-complete problem [1]. Therefore, only relaxation of the problem, for which it is possible to implement a polynomial time algorithm exists. In [2], the cumulative resource constraint is modelized by the global constraint CUMULATIVE in a constraint programming approach. The global constraint CUMULATIVE embeds many filtering algorithms. Among these algorithms, en- ergetic reasoning, edge-finding and timetabling are the most used. 1.1. Related Works To our knowledge, the word “energetic edge-finder” was firstly used in [3] where the author incorporates the en- ergy-based deduction rule to edge-finder algorithm for disjunctive (unary) resource. The idea of hybridization of the edge-finding rule and the energetic reasoning for cumulative resource was suggested in [4]. Indeed, in [4], Mercier and Van Hentenryck propose a two phase edge-finding algorithm where in the first phase, the po- tential adjustment values are computed. They found that many of these potential update values are unused and can be used inside an energetic-based second phase. After this suggestion, many filtering algorithms, hybridization of edge-finding rule and energetic reasoning have been proposed [5,6]. In [6], the authors use in the first phase, the edge-finding algorithm of [7,8] to compute the poten- tial update values and identify the corresponding time bounds of task intervals which provide the maximum update values. To each task, the time bounds used in the second phase is either the task intervals of maximum density or the task intervals of minimum slack. The re- sulting algorithm runs in 2 n since both phases have this complexity. This algorithm was later improved in [5] by choosing for each task, the time bounds of task inter- vals of both maximum density and minimum slack which provide the maximum update values. Experimental re- sults on RCPSP of the PSPLib [9] library and BL set [10] show that this variant is a good trade-off between the filtering power and the complexity but it does not domi- nate the edge-finding algorithm. Energetic reasoning is one of the most powerful filter- ing algorithm in cumulative scheduling problems [1,10] since it dominates all the other rules (edge-finding [4,7, 8,21], extended edge-finding [4,11], timetable [1], time- table edge-finding [12], timetable extended edge-finding [13]) except the not-first/not-last rule [14,15]. However, it is not commonly used because it has a high running time ( 3 n time complexity), needs a high number of time-intervals to be considered and its success highly depends on the tightness of the variable bounds (highly cumulative problems). Recently, in [16], the authors pro- posed an approximative criterion for the potential of the energetic reasoning which allows the decrease of the running time with more nodes to explore in the search tree. The combination of a solver of the CP and SAT techniques for conflict analysis played recently an im- portant role to solve cumulative scheduling problems effi- ciently [17,18]. In this paper, it is extended the energetic edge finder of [5] by adding the guarantee that the final algorithm de- duces more than edge-finding and extended edge-finding. The main idea of our energetic extended edge finder is the combination of the best properties of (extended) edge-finding rule (interesting time bounds and good run- ning time) and energetic reasoning (powerful filtering rule). The paper starts with the hypothesis that, the time bounds of task intervals used in the (extended) edge- finding algorithm can be interesting in an energetic rea- soning. Based on this hypothesis, the number of time intervals to be considered in an energetic reasoning is reduced to those of (extended) edge-finding. 1.2. Contribution This paper uses the time-bounds of task intervals consid- ered in the computation of the edge-finding algorithm [7,8] and the extended edge-finding algorithm [11] in an  R. KAMEUGNE ET AL. Open Access AJOR 591 energetic reasoning. Indeed, in [7,8], a complete edge- finding algorithm is proposed based on maximum density and minimum slack. The minimum slack is used in [11] to perform the extended edge-finding algorithm. The algorithm presented in this paper is an energetic version of the edge-finding and the extended edge-finding algo- rithms of [7,8,11] respectively. The complexity of the corresponding algorithm is 3 n where n is the number of tasks since each of the algorithm of [7,8] and [11] are quadratic. It is obvious that the new algorithm subsumes the edge-finding and the extended edge-finding algorithms. The filtering power of this algorithm is less than the one of the energetic reasoning, but in practice, it is a good trade-off between the filtering power and the running time. Empirical evaluation of the algorithm on the RCPSP instances of well known library prove that, the new algorithm performs in most of the cases better in term of reduction of number of nodes of the search tree than the quadratic extended edge-finding [11], but needs more time to do so, for instances of more than 30 tasks. The rest of the paper is organized as follows: Section 2 is devoted to the specification of the edge-finding rule and the energetic reasoning. In Section 3, the new ener- getic extended edge-finder is described and some of its properties are deduced. Experimental results are provided in the last Section. 2. Edge-Finding Rule and Energetic Reasoning Rule In this section, it is specified the (extended) edge-finding rule as well as the energetic reasoning. 2.1. Edge-Finding and Extended Edge-Finding Rules Let T be the set of tasks of a CuSP. If the energy e of a set of tasks T is larger than the available en- ergy lct estC , then the problem has no feasible solution. Overload checking algorithms typically enforce the following relaxation of this feasibility condition, which may be computed in lognn time [19,20]. Definition 1 (E-Feasibility) ([4]) A CuSP problem is E-feasible if: ,,lctest.TC e (4) For a given CuSP, an edge-finding rule identifies a set of tasks T and a task i such that, in any so- lution, all tasks of end before the end of i. More precisely, if the scheduling of task i as early as possi- ble (i.e., starting at es ti) induces an overload in the in- terval est, lct then, all the tasks in end before the end of i noted here i as in [21]. When all tasks of a set end before the end of a task i, then the release date of task i is updated to: 1 estestrest , ii i ic c (5) for all such that rest ,0 i c , lct estif rest ,0otherwise i i eCc c (6) Proposition 1 provides conditions under which all tasks of a set of a CuSP end before the end of a task .i Proposition 1 [4,7,8,11,21] Let T be a set of tasks of a CuSP of capacity C and iT be a task. lct est; ii eC i (EF) ect lct; ii (EF1) est estect. ect estlctest ii ii i ec C (EEF) And if i then the earliest start time of task i is updated to rest ,0 1 estmaxest ,maxestrest, i ii i i c c c (Upd) with if rest ,0otherwise i i eCclctest c (7) Rules (EF) and (EF1) are known as edge-finding de- tection rules while (EEF) is the extended edge-finding detection rule. It is proved in [4] that a complete edge-finding algorithm that only considers sets T and , which are task intervals can be imple- mented. The definition of the task intervals is given in Definition 2. Definition 2 (Task Intervals) (After [22]) Let ,jkT . The task intervals , k is the set of tasks ,estestlctlct . jkjssk sT (8) In [7,8], the authors propose a quadratic edge-finding algorithm based on maximum density and minimum slack notions. Definition 3 [7,8] Let be a task set of an E- feasible CuSP. The slack of the task set , denoted SL , is given by: lct est.SL Ce Definition 4 [7,8] Let i and k be two tasks of an E-feasible CuSP. ,ki is a task depending on the tasks k and i, where , est esti ki and that defines the task intervals with the minimum slack: for all jT  R. KAMEUGNE ET AL. Open Access AJOR 592 such that est est i , , ,, , lct estlct est. jk ki k kkj ki CeCe (9) The detection of the classic edge-finding rule (EF) is done with the task intervals of minimum slack. For ad- justment, as it is proved in [7,8], the task intervals of minimum slack and the one of maximum density are considered. Definition 5 [7,8] Let be a task set of an E- feasible CuSP. The density of the task set , denoted Dens, is given by: . lct est e Dens Definition 6 [7,8] Let i, k be two tasks of an E-feasible CuSP. ,ki is a task depending on the tasks k and i, where , est est iki and that defines the task intervals with the maximum density: for all tasks jT such that estest ij , ,, , , . lct estlct est ki k jk kjk ki e e (10) The main idea of the edge-finding algorithm of [7,8] is that once the relation i is discovered, then it is not necessary to iterate over all subsets of . It is enough to consider only (1) subset with minimum slack and est esti and (2) subset with maximum density and est esti. Using those two subsets, if esti can be improved, then it will be updated, although not necessar- ily immediately to the best value. More iterations of the algorithm may be needed for that. The extended edge-finding rule (EEF) detects addi- tional updates missing by the edge-finding rule. In [11], the authors propose a quadratic extended edge-finding algorithm based on minimum slack notion. This algo- rithm supposes that the fix point of the edge-finding is reached and looks for the upper bound of the task inter- vals of minimal slack instead of the lower bound as it is the case for the edge-finding algorithm. Definition 7 [11] Let i and j be two tasks of an E-feasible CuSP with est est ij . ,ji is a task de- pending on the tasks j and i, where , lct lcti ji and that defines the largest task intervals with the mini- mum slack: for all kT such that lct lct ki , ,, , lctestlct est. jk jji jkj ji CeCe (11) 2.2. Energetic Reasoning In the edge-finding rule, the energy required by a non- empty set of tasks only considers tasks which are completely processed within the time window est, lct while, the partial contribution of each task is taken into account in the energetic reasoning. There exists many varieties of energy consumption required by a task de- pending on the type of tasks, Fully Elastic energy and Partial Elastic energy for preemptive tasks and Left- shift/Right-shift energy for non-preemptive tasks [10]. Let i be a task and ,ab be a time interval with ab . The left-shift/right-shift energy consumption re- quired by i over ,ab noted ,,Wabi is the non- negative minimum of 1) the volume in the interval ,ab , 2) the energy of task i, 3) the left shifted en- ergy, and 4) the right shifted energy i.e., ,, max0, min,, ect,lst iiii Wabi cbapab (12) The overall energy consumption required by all tasks noted ,Wab over an interval ,ab is defined as ,,,. iT Wab Wabi (13) For a given CuSP, it is obvious that if there exists a time interval ,ab with ab such that its overall required energy consumption is more than available en- ergy, then the problem is infeasible. This necessary con- dition is provided in the following proposition. Proposition 2 [1] Let ,ab be a time interval with ab . If ,Cb aWab (14) then the problem is infeasible. In [1,10], the authors give a precise characterization of time bounds for which the necessary condition of the existence of a feasible scheduling should be guaranteed. This necessary condition is more powerful than the E-feasible one defined earlier. There exist 2 n rele- vant intervals to be considered to detect infeasibility. These intervals correspond to start and completion times of tasks. If 1 2 :est ,ect ,lst, :lct ,ect ,lst and:est lct iii iT iii iT ii iT O O Ot t then the relevant intervals are given by 12 ,abO O , for a fixed 1 aO : 1 ,abOO a , and for a fixed 2 bO : 2 ,abOb O , with ab. The authors propose a quadratic algorithm for testing this necessary condition in [1,10]. The left-shift energy required of a task i over a time interval ,ab defined by ,, min,,minect ,maxest , l iiii Wabi cbap ba (15)  R. KAMEUGNE ET AL. Open Access AJOR 593 is i c times the number of time units during which i executes after time a if i is left-shifted, i.e., sche- duled as soon as possible. If scheduling task i as early as possible (i.e., starting at esti) induces an overload in the interval ,ab then task i ends after b and esti can be updated according to Proposition 3. Proposition 3 [1] Let ,ab be an interval with ab and i be a task such that ,est,ect ii ab . If ,,,,, l W abW abiWabiCba (ER) holds, then the earliest start time of task i is updated to: estmaxest , 1,,, . ii i i a WabWabiC cb a c (ERupd) No specific characterization of relevant intervals for the adjustment was proposed so far. With the 2 n relevant intervals used for infeasibility test, it is derived a 3 n algorithm for adjustment in [1,10]. In practice, the energetic reasoning adjustment is too time-consum- ing for producing any useful result [1]. The paper tries to determine a better trade off between the filtering power and running time by reducing the number of intervals to examine. It is used the time bounds of task intervals of edge-finding and extended edge-finding algorithm in an energetic reasoning. The corresponding algorithm runs in 3 n as pure energetic reasoning adjustment. 3. The Energetic Extended Edge-Finder 3.1. The Rule The energetic extended edge-finding rule is obtained by substituting e by est, lctW in the edge-finding detection rule (EF) and the extended edge-finding detec- tion rule (EEF). It can be observed that the energetic reasoning rule (ER) is a generalization of rules (EF) and (EEF) with more strong energy consumption required by tasks over interval est, lct. The energetic extended edge-finding combines the techniques of edge-finding, extended edge-finding and partially the energetic rea- soning. The new adjustment rule is obtained by substi- tuting the energy e by est, lctW in the (ex- tended) edge-finding adjustment rule. 3.2. Algorithm The algorithm proposed in this Section is an energetic version of the edge-finding and the extended edge-find- ing algorithm of [7,8,11] respectively. The time bounds of task intervals used in the edge-finding (resp. the ex- tended edge-finding) for detection and adjustment are used in an energetic reasoning. The new algorithm runs in 3 n since each of the edge-finding and extended edge-finding algorithms are quadratic [7,8,11]. The algorithm is broken into two parts to make it more digest. The first part is an energetic variant of the edge- finding algorithm of [7,8] while the second part is the one of the extended edge-finding algorithm of [11] (ad- justments missing by the edge-finding and detect with the extended edge-finding). 3.2.1. First Part This part consists only in adding an inner loop in the edge-finding algorithm of [7,8] after detection of time bounds, to recompute the energy of each task intervals plus the partial contribution of the rest of tasks .T It is presented in Algorithm 1 where: 1) The first outer loop (line 3) selects, in the order of non-decreasing deadlines, the tasks kT which form the possible upper bounds of the task intervals. 2) The first inner loop (line 5) selects the tasks iT that includes the possible lower bounds for the task in- tervals, in non-increasing order by release date. If lct lct ik , then the energy and density of ,ik are cal- culated; if the new density is higher than ,,ki k where the task ,ki is specified in Definition 6, then ,ki becomes i (line 9). If lct lct ik , then if the current ,ki satisfies , est lctk ki and ecti , est ki (line 12), then the energy required by interval , est ,lctk ki is computed in the inner loop of line 13. The condition of line 15 checks if the interval , est ,lctk ki is overloaded (see inequality (12)) and if the condition of line 17 is fulfilled, then the potential update i Dupd of the release date of i is calculated (line 18), based on the current interval , est, lctk ki . This potential update is stored only if it is greater than the previous potential update value calculated for this task using the maximum density time bounds. The re- lease date of task i is updated at line 20 when the en- ergetic reasoning condition of line 19 is fulfilled (see inequality (ER)). 3) The second inner loop (line 23) selects i in non-decreasing order by release date. The energies stored in the previous loop (line 21) are used to compute the slack of the current interval ,ik . If the slack is lower than that of ,,kik where ,ki is specified in Definition 4, then ,ki becomes i (see line 25). For any task i with a deadline greater than lc tk, if the current ,ki satisfies , est lctk ki (line 28), then the energy required by interval , est, lctk ki is com- puted in the inner loop of line 29. The condition of line  R. KAMEUGNE ET AL. Open Access AJOR 594 Require: T is an array of tasks Ensure: A lower bound i est is computed for the release date of each task 1 for iT do 2 :=,:= ,:= ii ii estest DupdSLupd 3 for kT by non-decreasing deadline do 4 :0,max:0, :EnergyEnergy est 5 for iT by non-increasing release dates do 6 if ik lct lct then 7 := i nergyEnergy e 8 if max ki k nergy Energy lct estlct est then 9 max:, :i nergyEnergy estest 10 else 11 :=,:=,,:= 0 k aestblctWab 12 if >i ba ecta then 13 for T do 14 ,:= ,,,WabWab Wabj 15 if <,Cb aWab then 16 fail (No solution exists) 17 if ,,, >0 i WabWabiCcb a then 18 ,,, := max,i ii i WabWabiC cb a DupdDupd ac 19 if ,,,,,> l W abWabiWabiCba then 20 := max, iii estestDupd 21 := i Energ y 22 min :SL , := k est lct 23 for iT by non-decreasing release date do 24 if min kii C lctestESL then 25 :,min:( ) iki estestSLC lctestE 26 if > ik lct lct then 27 :,:,,:0 k aestblctWab 28 if >ba then 29 for T do 30 ,: ,,,WabWab Wabj 31 if <,Cb aWab then 32 fail (No solution exists) 33 if ,,, >0 i WabWabiC cba then 34 ,,, :max,i ii i WabWabiC cb a SLupdSLupd ac 35 if ,,,,,> l WabWabiWabiCb a then 36 :max ,, estest SLu dDu d Algorithm 1. Energetic extended edge finding algorithm in 3 ()n time. 31 checks if the interval , est, lctk ki is overloaded (see inequality (12)). If the condition of line 33 is ful- filled, then the potential update i SLupd of the release date of i is calculated (line 34), based on the current interval , est, lctk ki . This potential update is stored only if it is greater than the previous potential update value calculated for this task using the minimum slack time bounds. If the energetic reasoning condition is ful- filled at line 35 (see inequality (ER)), then the release date of task i is updated at line 36. 4) At the next iteration of this first outer loop, ,ki and ,ki are re-initialized. This first algorithm (Algorithm 1) corresponds to the energetic edge-finding algorithm. 3.2.2. S ec ond Part This part is the energetic version of the extended edge- finding algorithm of [11]. It consist in adding an inner loop in the extended edge-finding algorithm of [11] after detection of time bounds, to recompute the energy of each task intervals plus the partial contribution of the rest of tasks .T The corresponding algorithm is presented in Algorithm 2 where: 1) The outer loop (line 37) iterates through the tasks jT forming the possible lower bounds of the task intervals. 2) The inner loop (line 39) selects the tasks iT that comprise the possible upper bounds for the task intervals, in non-decreasing order of deadlines. If estest i , then the energy and the slack of , i are calculated. The slack is then compared to the slack of ,, ji (see line 42) where ,ji is specified in Definition 7. If the new slack is higher, ,ji becomes i (line 43). If est est i (line 44), then if the current ,ji satisfies 37 for jT do 38 :0,max:0, :j EnergyEnergylct est 39 for iT ( T sorted by non-decreasing deadlines) do 40 if ji est est then 41 :i nergyEnergy e 42 if max ij j C lctestEnergyClctestEnergy then 43 max:,:i nergyEnergy lctlct 44 else 45 :,:,,:0 j aestblctWab 46 if >i ba ecta then 47 for kT do 48 ,:=,,,WabWab Wabk 49 if <,Cb aWab then 50 fail (No solution exists) 51 if ,,,,,> l W abW abiWabiCba then 52 ,,, := max,i ii i WabWabiC cba estest ac 53 for iT do 54 := est est Algorithm 2. Energetic extended edge finding algorithm in 3 ()n time.  R. KAMEUGNE ET AL. Open Access AJOR 595 , lct est ji and ectest ij (line 46), then the energy required by interval , est, lct j i is computed in the inner loop of line 47. The condition of line 49 checks if the interval , est, lctk ki is overloaded (see inequality (12)). If the energetic reasoning condition is fulfilled at line 51 (see inequality (ER)), then the release date of task i is updated at line 52 based on the current potential update value determined by interval , est ,lct j i . 3) At the next iteration of this outer loop, ,ji is re-initialized. Merging Algorithms 1 and 2, the corresponding algo- rithm title “EnEEF” is an energetic extended edge-find- ing algorithm. 3.3. Some Properties of EnEEF The energetic extended edge-finding algorithm EnEEF is compared to the conjunction of the edge-finding and the extended edge-finding. It is proved that, this algorithm subsumes the conjunction of edge-finding and extended edge-finding algorithm. 3.3.1. The Energetic Extended Edge-Finder EnEEF Performs Some Additional Adjustments Missing by (Extended) Edge-Finding Using the CuSP instance of Figure 1, it is found that the energetic extended edge-finder EnEEF performs addi- tional adjustments missing by (extended) edge-finding. Indeed, the application of the (extended) edge-finding algorithm on the CuSP instance of Figure 1 doesn’t produce any adjustment whereas the application of our energetic extended edge finder EnEEF permits to update the release date of task A from 1 to 5. When the task B (resp. C or D) is considered at the outer loop of line 3, the bounds of the task intervals of maximum density are [3,6) and the condition of line 19 holds for 3a and 6.b It follows that ,,, ,, 821093 63 l W abWabAWabA Cba and ,,, 80 31632. A WabWabACcb a Therefore, the release date est A is updated to ,,, est 325. A AA WabWabAC cb a ac The reader can check that no propagation is performed by the timetable edge-finding rule of [12] and the timeta- ble extended edge-finding rule of [13] on the CuSP in- stance of Figure 1. 3.3.2. The Energetic Extended Edge-Finder EnEEF Subsumes the Edge-Finding Algorithm Theorem 1 The energetic extended edge-finder EnEEF subsumes the edge-finding algorithm of [7,8]. Proof. It is important to prove that the edge-finding algorithm can not propagate anything when the energetic extended edge-finder EnEEF reaches the fix point. By contradiction: assume that the energetic extended edge-finder EnEEF reaches the fix point, and that how- ever, the edge-finding algorithm can propagate i.e., there are i, and , such that (EF) or (EF1) holds and (Upd) improves esti using . It will be prove (by contradiction) that the energetic extended edge-finding algorithm EnEEF can update the time bounds of task i. 1) The rule (EF1) holds. In this case, two subcases are considered: (a) If est esti , then the energy contribution of task i in the time interval est, lct is lct est ii c since ectlct . i The inequality 1 estrest ,est ii i c c (16) holds since the release date of task i is updated using the rule (Upd) and it is algebraically equivalent to lctestlctest . ii ec C (17) Let kT be a task such that :. k lct lct According to [7,8], is the task intervals of minimum slack (Definition 4) and it follows ,, , lct estlctest lctest . ki k kki ii CeCe c (18) When the task k is considered in the outer loop of line 3, in the second inner loop of line 23 the condition ,,,,, l W abW abiWabiCba (19) is detected at line 35 since ,, ,,, ki k WabWabie and ,,lct est lii Wabi c where , :est ki a and :lct k b and the adjustment follows. (b) If est est i , then the energy contribution of task i in the time interval est, lct is lct est i c since ectlct . i The inequality rest ,0 i c (20) holds since the release date of task i is updated using the set and the rule (Upd) and it is algebraically equivalent to lctestlctest . i ec C (21) Let kT be a task such that :. k lct lct According to [7,8], is the task intervals of maximum density  R. KAMEUGNE ET AL. Open Access AJOR 596 (Definition 6) and it follows ,, , . lct estlctest ki k i kki eeCc (22) Therefore, it appears that ,, ,, lct estlct est. ki kik k ki ki ec C (23) When the task k is considered in the outer loop of line 3, in the first inner loop of line 5 the condition ,,,,, l W abW abiWabiCba (24) is detected at line 19 since ,, ,,, ki k WabWabie and , ,,lct est lik ki Wabic where , :estki a and :lct k b and the adjustment follows. 2) The rule (EF) holds: Let kT be a task such that lct:lct . k According to [7,8], is the task intervals of minimum slack (Definition 4) and it follows ,, , lct est. ki k ki ki Cee (25) When the task k is considered in the outer loop of line 3, in the second inner loop of line 23 the condition ,,,,, l W abW abiWabiCba (26) is detected at line 35 since ,, ,,, ki k Wab Wabie and ,, li Wabie where , :est ki a and :lct k b and the adjustment follows using the potential update values previously computed.■ According to this theorem, the first outer loop of line 3 ensures us that the fix point of the edge-finding rule will always be reached. This result is used to demonstrate that our algorithm dominates the extended edge-finding rule. In the following theorem, it is proved that, at the fix point of the edge-finding rule, if the extended edge-finding rule detects the relation i for a set of tasks and a task i then the set can help to compute the poten- tial updated value of esti. 3.3.3. The Energetic Extended Edge-Finder EnEEF Subsumes the Extended Edge-Finding Algorithm Theorem 2 [11] Let T be a set of tasks and iT be a task of an E-feasible CuSP. At the fix point of the edge-finding rule, if the extended edge- finding rule detects i then 1 rest,0andestrest,est . iii i cc c Using theorem 2, it is derived the following theorem: Theorem 3 The energetic extended edge-finder EnEEF subsumes the extended edge-finding algorithm of [11]. Proof. As in Theorem 1, it is prove that the extended edge-finding algorithm can not propagate anything when the energetic extended edge-finder EnEEF reaches the fix point. The contradiction is used: assume that the energetic extended edge-finder EnEEF reaches the fix point, and that however, the extended edge-finding algorithm can propagate i.e., there are i, and , such that (EEF) holds and (Upd) improves esti using . It will be prove (by contradiction) that the energetic ex- tended edge-finding algorithm EnEEF can update the time bounds of task i. Let jT be a task such that est:est . j Accord- ing to [11], is the task intervals of minimum slack (Definition 7) and it follows ,, , lctestlct est ectest . jji j ji ii CeCe c (27) When the task j is considered in the outer loop of line 37, in the inner loop of line 39 the condition ,,,,, l W abW abiWabiCba (28) is detected at line 51 since ,, ,,, ji WabWabie and , ,ectest lii Wabic where :est a and , : i blct . According to Theorem 1, the fix point of the edge-finding rule is reached and the Theorem 3 shows that the task intervals used for detection can also be used to perform the adjustment. Therefore, an adjust- ment is performed at line 52 since this adjustment is jus- tified by the condition of line 51.■ 4. Experimental Results For our experiments, it is consided the resource-con- strained project scheduling problems (RCPSP). A RCPSP consists of a set of resources of finite capacities, a set of tasks of given processing times, an acyclic network of precedence constraints between tasks, and a horizon (a deadline for all tasks). Each task requires a fixed amount of each resource over its execution time. The problem is to find a start time assignment for every task satisfying the precedence and resource capacity constraints, with a makespan (i.e., the time at which all tasks are completed) at most equal to the horizon. The cumulative scheduling problem (CuSP) is a sub-problem of the RCPSP, where precedence constraints are relaxed and a single resource is considered at a time; both problems are NP-complete [10]. Tests were performed on the RCPSP single-mode J30, J60 and J90 test sets of the well-established benchmark library PSPLib [9] as well as on the library of [10] (BL). The data sets J30, J60 and J90 consist of 480 instances of 30, 60 and 90 tasks respectively, while BL consists of 40  R. KAMEUGNE ET AL. Open Access AJOR 597 instances of 20 and 25 tasks respectively. Each instance from the PSPLib sets includes tasks to be scheduled over 4 resources, while instances from the BL suite share 3 resources. Starting with the provided horizon as an upper bound, each instance of problem is modeled as an instance of Constraint Satisfaction Problem (CSP); variables are start times of tasks and they are constrained by precedence graph (i.e., precedence relations between pairs of tasks were enforced with linear constraints) and resource limi- tation (i.e., each resource was modeled with a single CU- MULATIVE constraint [2]). Dynamic branching schemes are the most used branch- ing strategy in CP, as they typically result in smaller search trees. However, when comparing filtering algo- rithms of differing pruning strengths, dynamic branching can be misleading: in some cases the domain resulting from weaker pruning may result in a choice point yield- ing a smaller subtree, and hence a faster solution. In or- der to minimize the effect of differing pruning strength on the shape of the search trees, it is consided two branching models: 1) For dynamic branching, variable selection was based on the minimum of domain size, divided by degree (i.e., the number of propagators depending on the vari- able). Ties were broken by selecting the task with the minimum latest start time; values were taken from the smallest range for domains with multiple ranges, or the lesser half of the domain when only one range existed [23]. 2) For static branching, it is selected the first unas- signed variable, and the smallest value in the domain. Tests were performed on a Pentium(R) Dual-Core processor, CPU 2.70 ghz, 1.96 GB of RAM. The imple- mentation was done in c++ using the Gecode 3.7.3 [23] constraint solver. For each benchmark instance, it is used branch and bound search to minimize the makespan, stopping only when the optimum solution was found. Each test was run three times, with the best result re- ported; any search taking more than 300 seconds was counted as a failure. Two filtering algorithms for different configurations of the global constraint CUMULATIVE have been considered. 1) The first CUMULATIVE propagator noted “EEF” for tasks of fixed duration is a sequence of three filters: the 2 n extended edge-finding algorithm from [11], the overload checking from [19] and timetabling algo- rithm from [1]. 2) The second propagator noted “EnEEF” is a modi- fied version of “EEF” that substitutes the extended edge- finding algorithm from [11] for the 3 n energetic extended edge-finder of this paper (EnEEF). 4.1. Dynamic Branching Table 1 reports the results for all instances from the test sets BL, J30, J60 and J90 that were solved by at least one propagator using dynamic branching. There were 40, 392, 341 and 324 for BL, J30, J60 and J90 respectively. In this table, the line “solve” reports the number of in- stances in which each algorithm found the optimal solu- tion, did so in the fastest time “time”, and generated the smallest search tree “nodes”, using dynamic branching. Line “Av.time” reports the average CPU time (in second) used to reach the optimal solution while line “Av.node” denotes the average number of nodes reported on in- stances solved by both propagators. Both propagators solve the same number of instances in each test sets. As can be observed form Figure 2, using dynamic branching EnEEF performs the strongest among the two algorithms on instances less than 30 tasks. Unfortunately, the use of a dynamic branching scheme appears to hide the domina- tion of EnEEF on EEF. On instances with more than 30 tasks, EnEEF requires more time for small reduction of tree search. Here, on BL set (reputed to be highly cumulative [10]), 87.5% of instances were solved by EnEEF with better running time and 85% of instances were solved with smallest search tree. On J30, J60 and J90 instances (re- puted to be highly disjunctive [10]), the performance of the EnEEF is reduced. This result confirms that of Bap- tiste et al. [1] concerning the usage of the energetic rea- soning on tightness instances. Table 1. Number of instances in which each algorithm found the optimal solution (solve), did so in the fastest time (time), and generated the smallest search tree (nodes), using dynamic branching. Average runtime (Av.time) and nodes (Av.node) count on instances where both solvers can found the optimal solution are consider ed. BL20 BL25 J30 J60 J90 EEF EnEEFEEF EnEEFEEF EnEEF EEF EnEEF EEF EnEEF solve 20 20 20 20 392 392 341 341 324 324 time 5 15 0 20 289 101 319 21 319 5 node 0 14 0 20 5 59 3 21 4 10 Av.time 4.04 3.44 35.60 15.00 5.64 6.59 1.93 2.10 1.08 2.94 Av.node 27073 20410 16638986930 1946217302 3792 3161 2031 2050  R. KAMEUGNE ET AL. Open Access AJOR 598 4.2. Static Branching In Tab le 2, lines “solve”, “time”, “node”, “Av.time” and “Av.node” have the same meaning as in Table 1. For static branching scheme, an instance of BL25 was solved only by the propagator EnEEF in the time available. Two other instances for J30 and J60 respectively was soled by EEF only in the time available. The tests show that the EEF propagator is faster in a large majority of test in- stances but the EnEEF remains the best on BL test set. As in Table 1, the average running time of EEF is more than two times the one of EnEEF on the BL25 test set. The same remark can be observed on the average of nodes count of the different propagators on BL25 for both static and dynamic branching scheme. Figure 3 compares (left) the proportional runtime of EnEEF over Runtimes comparison: EnEEF/EEF 10 1 10 0 10 -1 20 25 30 60 90 number of tasks Proportional runtime 10 2 Nodes comparison: EnEEF/EEF 10 1 10 -1 20 253060 90 number of tasks Proportional nodes count 10 -2 10 0 Figure 2. Comparison of (left) proportional runtimes of EnEEF over EEF and (right) proportional nodes count when using dynamic branching, sorted by number of tasks of instances. Table 2. Number of instances in which each algorithm found the optimal solution (solve), did so in the fastest time (time), and generated the smallest search tree (nodes), using static branching. Average runtime (Av.time ) and nodes (Av.node) count on instances were both solvers can found the optimal solutions are considered. BL20 BL25 J30 J60 J90 EEF EnEEF EEF EnEEF EEF EnEEF EEF EnEEF EEF EnEEF solve 18 18 17 18 359 358 326 325 325 325 time 3 15 3 14 280 78 304 20 322 3 node 0 17 0 17 0 52 0 24 0 11 Av.time 3.69 2.50 28.86 14.11 4.31 5.56 1.37 1.56 0.43 1.36 Av.node 28818 13291 149298 53120 12465 11150 2616 2313 195 190 Runtimes comparison: EnEEF/EEF 10 1 10 0 10 -1 20 25 30 60 90 number of tasks Proportional runtime Nodes comparison: EnEEF/EEF 10 0 10 -1 20253060 90 number of tasks Proportional nodes count Figure 3. Comparison of (left) proportional runtimes of EnEEF over EEF and (right) proportional nodes count when using static branching, sorted by number of tasks of instances.  R. KAMEUGNE ET AL. Open Access AJOR 599 EEF and (right) the proportional nodes count when using static branching, sorted by number of tasks of instances. It appears that the propagator EnEEF subsumes the EEF in almost all test instances. On tests set J30, J60 and J90, EnEEF need more time for a weak reduction of the tree search on instances solved by the propagators. 5. Conclusion In this paper, it is presented a new filtering algorithm for cumulative resource, hybridization of the extended edge- finding rule and the energetic reasoning. The new algo- rithm is stronger than the extended edge-finding algo- rithm, but weaker than the energetic reasoning and runs in 3 n where n is the number of tasks sharing the resource. In practice, it is a good trade-off between the filtering power and the running time. Experimental re- sults demonstrate that on a standard benchmark suite, our new algorithm reduces substantially more number of nodes—thus the tree search—than the extended edge- finding algorithm on instances where the number of tasks is less than 30. The time complexity of this algorithm remains too high. Our future work will focus on the re- duction of the complexity of this algorithm from 3 n to 2lognn using a -tree data structures. 6. Acknowledgements The authors would like to thank Pierre Ouellet and Claude-Guy Quimper for providing their paper. We also thank anonymous referees sincerely for their constructive and insightful feedback. REFERENCES [1] P. Baptiste, C. Le Pape and W. P. M. Nuijten, “Con- straint-Based Scheduling: Applying Constraint Program- ming to Scheduling Problems,” Springer, Berlin, 2001. http://dx.doi.org/10.1007/978-1-4615-1479-4 [2] A. Aggoun and N. Beldiceanu, “Extending CHIP in Order to Solve Complex Scheduling and Placement Problems,” Mathematical and Computer Modelling, Vol. 17, No. 7, 1993, pp. 57-73. http://dx.doi.org/10.1016/0895-7177(93)90068-A [3] P. Baptiste, “Resource Constraints for Preemptive and Non-Preemptive Scheduling,” Master 2 in Computer Science and Operation Research, University of Paris VI, Institut Blaise Pascal, 1995. [4] L. Mercier and P. Van Hentenryck, “Edge Finding for Cumulative Scheduling,” INFORMS Journal on Comput- ing, Vol. 20, No. 1, 2008, pp. 143-153. http://dx.doi.org/10.1287/ijoc.1070.0226 [5] S. F. Betmbe, “Energetic Edge Finder: Propagator of cUmulative Resource Constraints,” Master 2 in Computer Science, University of Yaounde 1, 2012. [6] R. Kameugne and L. P. Fotso, “Energetic Edge-Finder for Cumulative Resource Constraint,” Proceeding of CPDP 2009 Doctoral Program, Lisbone, 2009, pp. 54-63. [7] R. Kameugne, L. P. Fotso, J. Scott and Y. Ngo-Kateu, “A Quadratic Edge-Finding Filtering Algorithm for Cumula- tive Resource Constraints,” In: J. H. M. Lee, Ed., CP 2011—Principles and Practice of Constraint Program- ming, Springer, Berlin, 2011, pp. 478-492. http://dx.doi.org/10.1007/978-3-642-23786-7_37 [8] R. Kameugne, L. P. Fotso, J. Scott and Y. Ngo-Kateu, “A Quadratic Edge-Finding Filtering Algorithm for Cumula- tive Resource Constraints,” Extended Version of the CP 2011 Paper, Constraints, Forthcoming, 2013. [9] “PSPLib—Project Scheduling Problem Library,” Online, 2012. http://129.187.106.231/psplib/ [10] P. Baptiste and C. Le Pape, “Constraint Propagation and Decomposition Techniques for Highly Disjunctive and Highly Cumulative Project Scheduling Problems,” Con- straints, Vol. 5, No. 1, 2000, pp. 119-139. http://dx.doi.org/10.1023/A:1009822502231 [11] R. Kameugne, L. P. Fotso and J. Scott, “A Quadratic Extended Edge-Finding Filtering Algorithm for Cumula- tive Resource Constraints,” International Journal of Plan- ning and Scheduling, Forthcoming, 2013. [12] P. Vilm, “Timetable Edge Finding Filtering Algorithm for Discrete Cumulative Resources,” In: T. Achterberg and J. C. Beck, Eds., CPAIOR 2011—Integration of AI and OR Techniques in Constraint Programming, Springer, Berlin, 2011, pp. 230-245. http://dx.doi.org/10.1007/978-3-642-21311-3_22 [13] P. Ouellet and C.-G. Quimper, “Time-Table Extended- Edge-Finding for the Cumulative Constraint,” Proceeding of the 19th International Conference on Principles and Practice of Constraint Programming, LNCS, 2013, Springer, Berlin, Vol. 8124, pp. 562-577. [14] R. Kameugne and L. P. Fotso, “A Cumulative Not-First/ Not-Last Filtering Algorithm in O(n2logn),” Indian Journal of Pure and Applied Mathematics, Vol. 44, No. 1, 2013, pp. 95-115. http://dx.doi.org/10.1007/s13226-013-0005-z [15] A. Schutt and A. Wolf, “A New O(n2logn) Not-First/ Not-Last Pruning Algorithm for Cumulative Resource Constraints,” In: D. Cohen, Ed., CP 2010—Principles and Practice of Constraint Programming, Springer, Ber- lin, 2010, pp. 445-459. http://dx.doi.org/10.1007/978-3-642-15396-9_36 [16] T. Berthold, S. Heinz and J. Schulz, “An Approximative Criterion for the Potential of Energetic Reasoning,” In: A. Marchetti-Spaccamela and M. Segal, Eds., Theory and Practice of Algorithms in (Computer) Sy ste ms, Springer, Berlin, 2011, pp. 229-239. http://dx.doi.org/10.1007/978-3-642-19754-3_23 [17] S. Heinz and J. Schulz, “Explanations for the Cumulative Constraint: An Experimental Study,” In: P. M. Pardalos and S. Rebennack, Eds., Experimental Algorith ms, Springer, Berlin, 2011, pp. 400-409. http://dx.doi.org/10.1007/978-3-642-20662-7_34 [18] A. Schutt, T. Feydy and P. J. Stuckey, “Explaining Time- Table-Edge-Finding Propagation for the Cumulative Re- source Constraint,” CPAIOR 2011—Integration of AI  R. KAMEUGNE ET AL. Open Access AJOR 600 and OR Techniques in Constraint Programming, 2013, pp. 234-250. [19] P. Vilm, “Max Energy Filtering Algorithm for Discrete Cumulative Resources,” In: W. J. van Hoeve and J. N. Hooker, Eds., CPAIOR 2009—Integration of AI and OR Techniques in Constraint Programming, Springer, Berlin, 2009, pp. 294-308. http://dx.doi.org/10.1007/978-3-642-01929-6_22 [20] A. Wolf and G. Schrader, “O(nlogn) Overload Checking for the Cumulative Constraint and Its Application,” In: M. Umeda, A. Wolf, O. Bartenstein, U. Geske, D. Seipel and O. Takata, Eds., INAP 2005—Applications of Declarative Programming for Knowledge Management, Springer, Berlin, 2006, pp. 88-101. http://dx.doi.org/10.1007/11963578_8 [21] P. Vilm, “Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(knlogn),” In: I. P. Gent, Ed., CP 2009—Principles and Practice of Constraint Pro- gramming, Springer, Berlin, 2009, pp. 802-816. http://dx.doi.org/10.1007/978-3-642-04244-7_62 [22] Y. Caseau and F. Laburthe, “Improved CLP Scheduling with Task Intervals,” In: P. Van Hentenryck, Ed., ICLP 1994—Logic Programming, MIT Press, Cambridge, 1994, pp. 369-383. [23] Gecode, 2012. http://www.gecode.org
|
