A Quadratic Propagator for the Inter-Distance
Contents
1. 245 250 2003 K Mehlhorn and S Thiel Faster algorithms for bound consistency of the sortedness and alldifferent con straint In Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming pages pp 306 319 2000 L Mercier and P Van Hentenryck Edge finding for cumulative scheduling Submitted for publication 2005 14 J F Puget A fast algorithm for the bound consistency of alldiff constraints In Proceedings of the Fifteenth National Conference on Artificial Intelligence pages pp 359 366 1998 C G Quimper A L pez Ortiz and G Pesant A quadratic propagator for the inter distance constraint In Proceedings of the 2Irst National Conference on Artificial Intelligence AAAI 06 pages pp 123 128 2006 J C R gin A filtering algorithm for constraints of difference in CSPs Proceedings of AAAI 94 pages pp 362 367 1994 J C R gin The global minimum distance constraint Technical report ILOG 1997 152. 6 2 Runway Scheduling Problem We then study a runway scheduling problem Artiouchine et al 2004 In this problem n airplanes have certain time intervals in which they can land Airplane number i has s time intervals r dj r d Following Artiouchine and Baptiste 2005 we create for each airplane a variable t with domain r d representing the landing time and a variable c with domain 1 s representing the landing time interval We have the constraints c gt k lt gt ti gt rk adag lt k ti lt d Finally we have the constraint INTER DISTANCE t1 tn P that ensures a gap of P between each landing For security reasons we want to maximize the time P between each landing In order to fairly compare both propagators we enhanced the Artiouchine Baptiste propagator with the algorithm presented in Section 5 to prune the variable P With ILOG Solver we set the goal of performing a binary search on P We also set the objective of minimizing P We use the default heuristics and parameters proposed by ILOG Solver 12 We used the same benchmark as Artiouchine and Baptiste 2005 on random runway scheduling problems where the sizes of intervals and the gap between intervals may vary Figure 4 shows the number of problems solved in the benchmark in a given period of time Our propagator has consistently solved the problems at greater speed than the Artiouchine Baptiste propagator The two levels of consist
3. generated by a pair of time points r dj from Example 1 Intervals are written in decreasing order with respect to parameter g The forbidden regions are F 83 1 3 3 9 9 3 Towards a Quadratic Time Propagator Internal and external adjustment intervals in the worst case may be computed with up to n possible release times r n possible deadlines d and produce O n adjustment intervals each Therefore O n adjustment intervals could be checked in the worst case hence the cubic time complexity of the Artiouchine Baptiste propagator In fact the union of all internal and external adjustment intervals consists of a maximum of O n disjoint intervals It is therefore possible to ignore intervals that are subsets of already discovered intervals in order to achieve a quadratic complexity To avoid computing redundant adjustment intervals we introduce the notion of dominance between two pairs of time points When a pair of time points dominates another pair the adjustment regions of the dominant pair contain some adjustment regions of the other pair Definition 5 Dominance A pair of time points r d dominates a pair of time points r d if we have min I aq lt min I a q and max 1r aq gt max Ir aq for all 0 lt q lt min A r d A r d We write r d gt r d Notice that we usually have A r d A r d The definition of dominance only applies for q below min A r d A r
4. in which a pair of time points dominates another one The first case is described in Lemma 8 Lemma 8 Consider the pairs of time points r d and r d such that d lt d If A r d A r d then r d gt r d Proof Let k A r d A r d We have Ist F d 0 lt Ist F d 0 and by Lemma 7 for any 0 lt q lt k we have lst F d q 1 lt Ist F d q 1 This implies min J lt min J a q and since we have max J a max I a q we have r d gt r d 4 From Lemma 8 we conclude that 10 20 gt 10 21 in Example 1 Similarly we have the following Lemma Lemma 9 Consider the pairs of time points r d and r d such that r lt r and A r d A r d Then r d lt r d Proof Let k A r d A r d We have ect F r 0 lt ect F r 0 and by Lemma 6 for any 0 lt q lt k ect F r k q lt ect F r k q This implies max I a q lt max J a q and since we have min I q min I a q we have r d lt r d a In Example 1 Lemma 9 detects 4 20 lt 10 20 We show a last case where a pair of time points dominates another one Lemma 10 Let r d and r d be two pairs of time points such that A r d A r d k and ect F r k lt ect F r 0 Then r d gt r d Proof Clearly for O lt q lt A r d the internal adjustment intervals I a q and Iy a q share the same lower bound For the upper bound
5. of integer values between a and b inclusively If a gt b then the interval a b is empty We nevertheless say that the lower bound of the interval is min a b a and the upper bound is max a b b as for non empty intervals We present in Section 2 some notions about how bounds consistency can be enforced on the INTER DISTANCE constraint We then explain in Section 3 how the computation can be simplified Based on this simplification we present in Section 4 our algorithm and a data structure that ensures the quadratic behaviour of our propa gator We show in Section 5 how bounds consistency can be enforced on the distance variable P Finally we present in Section 6 some experiments proving the efficiency of our propagator 2 The INTER DISTANCE Constraint R gin 1997 first introduced the INTER DISTANCE constraint under the name global minimum distance constraint The expression INTER DISTANCE X1 Xn P holds if and only if X X gt P for alli j When P 1 the INTER DISTANCE specializes into an ALL DIFFERENT constraint R gin 1994 Mehlhorn and Thiel 2000 L pez Ortiz et al 2003 R gin 1994 showed that a single global constraint in many cases causes more domain reduction than the an equivalent binary constraints This observation also applies to the INTER DISTANCE constraint which is the general case Artiouchine and Baptiste provided the first propagator for the bounds consistency of the INTER DISTANCE
6. offers two levels 1 The code discussed in this section is available upon request from the first author 11 Scalability Test Artiouchine Baptiste Our propagator Figure 3 Running time of the Artiouchine Baptiste propagator O n and our propagator O n7 as a function of the number of tasks For this scalability test we set all release times to r 0 and deadlines to d 6n of consistency namely I cBasic and IlcExtended We also implemented the Artiouchine Baptiste propagator Artiouchine and Baptiste 2005 The scalability test presented in Section 6 1 was run on a Pentium III 900 MHz with 256 Mb of memory and ILOG Solver 4 2 The experiments on the runway scheduling problem presented in Section 6 2 were run on a AMD64 Opteron 250 with a 2 4 GHz dual processor only one processor was used and 3 GB of RAM We used on this computer the library ILOG Solver 6 1 All reported times are averaged over 10 runs 6 1 Scalability Test In order to test the scalability of our propagator we first consider a scheduling problem with a single INTER DISTANCE constraint over n tasks whose release times are r 0 and deadlines are d np for all tasks This problem has a trivial solution and is solved without backtracking We clearly see on Fig ure 3 that our propagator has a quadratic behaviour while the Artiouchine Baptiste propagator has a cubic behaviour This observation is supported by the study of the third and second derivative
7. A Quadratic Propagator for the Inter Distance Constraint Claude Guy Quimper QUIMPER ALUMNI UWATERLOO CA University of Waterloo School of Computer Science Alejandro L pez Ortiz ALOPEZ O UWATERLOO CA University of Waterloo School of Computer Science Gilles Pesant PESANT CRT UMONTREAL CA Ecole Polytechnique de Montr al Department of Computer Engineering Editor Pascal Van Hentenryck Abstract We present a new propagator achieving bounds consistency for the INTER DISTANCE constraint This con straint ensures that among a set of variables X1 Xn the difference between two variables is at least p This restriction models in particular scheduling problems in which tasks require p contiguous units of a disjunctive resource to be completed Until now the best known propagator for bounds consistency had time complexity O n In this work we propose a quadratic propagator for the same level of consistency We then show that the theoretical gain gives savings of an order of magnitude in our benchmark of scheduling problems Our propagator is also the first one to filter the variable p 1 Introduction The cumulative scheduling problem with one resource of capacity C consists of a set of tasks T Tn to which we associate four integer variables a release time r a deadline d a processing time p and a capacity requirement c Each task T must start at time t such that r lt t lt di pi Let Q t be the set of t
8. TER DISTANCE constraint An internal Fe R the set of release times D the set of deadlines for r R in decreasing order do d argmin Ist F d A r d r deD s Ist F d A r d r if s lt 0 then return The problem is unsolvable else if s lt p then Fe Fujist F d A r d 1 1 r 1 return F Algorithm 1 Algorithm that computes the forbidden regions Garey et al 1981 use special data structures to obtain a complexity of O n log n adjustment interval is an interval in which no task is allowed to start The set of internal adjustment intervals is a superset of the forbidden regions F Definition 1 Internal Adjustment Interval Given two time points r and d and an integer 0 lt q lt A r d the internal adjustment interval T 4 4 is defined as follows Irag lst F d q 1 1 ect F r A r d q 1 3 Theorem 2 presents in which context we will use internal adjustment intervals Theorem 2 Artiouchine and Baptiste 2005 Given two time points r d and an integer 0 lt q lt A r d no task can start in the interval I 4 q Internal adjustment intervals appear in problems where a group of variables must be assigned to values in an interval that is small enough to force a certain structure to be maintained The internal adjustment intervals ensure that a single variable does not occupy the space of two variables The external adjustment intervals are intervals in
9. and return t where j max s Lemma 15 Updating and requesting the variables t is performed in O n steps Proof There are up to O n intervals in the data structure A and each of them can be visited at most once Indeed the pointers p make sure that the search is always resumed from the last visited position in the list A The union find data structure ensures that if an interval J A increases more than one release time this operation is done in constant time since all release times are grouped in the same set in S and only the representative t of this set is updated Merging the elements in S and requesting the representive elements takes O na n The total complexity is therefore O n E 4 3 Running Time Analysis The function lst F di q can be implemented with a table L where Ist F r q L i q Such a table requires O n steps to initialize and supports function evaluation in constant time We use a similar table to evaluate ect F r q The function A r1 d can trivially be computed in O n steps Since the release times are sorted in non decreasing order one can compute A r d using the following recursion 10 A rj 1 di if dj_1 gt di A r di ee otherwise ad The function A r d can be implemented with a table D such that D i j A ri d Initializing the table using the recursion above requires O n steps Each function call then takes constant time Theorem 16 The running time c
10. asks in process at time t i e the tasks T such that t lt t lt ti pi We have the resource capacity constraint Drew ci lt C This problem is NP Hard even in the case where C 1 which we call in this particular case the disjunctive scheduling problem Edge finders Carlier and Pinson 1994 Mercier and Van Hentenryck 2005 have largely been used to solve scheduling problems This technique reduces the intervals r d by detecting time zones that must be allocated to a subset of the tasks making these zones unavailable for other tasks The goal is to increase release times and reduce deadlines without eliminating any feasible solution The problem is said to be bounds consistent when intervals r d have been fully shrunk i e when there exists at least one feasible schedule in which task 7 starts on time r and at least one feasible schedule in which task T finishes on time d It is NP Hard to make a scheduling problem bounds consistent even in the disjunctive case For this reason edge finders try to reduce in polynomial time the size of the intervals without necessarily achieving bounds consistency A backtracking search assigns starting times to tasks and uses the edge finder to reduce the size of the search tree We study the disjunctive scheduling problem when all tasks have the same processing time p p This problem can be solved in polynomial time Garey et al 1981 but traditional algorithms only return one solutio
11. constraint The running time complexity of their propagator is cubic Throughout the paper we will assume that P is fixed to a value p and therefore can be assigned to this value In Section 5 we generalize to the case where P is not fixed and show how to enforce bounds consistency on all constrained variables We use the following problem as a running example Example 1 Consider a problem with n 3 tasks with starting times T Tz and T and processing time p 6 subject to the following release times and deadlines Ty 2 r 10 r3 4 d 12 dy 20 dz 21 Figure 1 shows the release times and deadlines as well as a feasible schedule Let the domain of T be the interval r di p i e T 2 6 T 10 14 and T3 4 15 After propagation of the constraint INTER DISTANCE T T2 73 p the variables get assigned to the following values Task 1 7 Task 2 L M Task 3 aay 0 5 10 15 20 25 Figure 1 Release times and deadlines for the three tasks described in Example The black rectangles represent a feasible schedule Here task T must finish before or at time 8 in order to allow tasks T gt and T to meet their deadlines Task Tz cannot start before time 14 since the two other tasks are not completed before this time Finally task T must be executed between tasks T and T forcing its release time to be increased and its deadline to be reduced Garey et al 1981 designed an algorithm t
12. d Also for a fixed deadline d the dominance operator lt is transitive ie if r d lt rj d and r d lt rg d hold then r d lt rx d holds In Example 1 we have 2 21 gt 4 21 The following lemmas describe a property of the ect and Lst functions that will allow us to efficiently decide if a pair of time points dominates another one Lemma 6 f ect F r q lt ect F r q then ect F r q k lt ect F r q k for any k gt 0 Proof The proof is by induction on k The base case k 0 is trivial Suppose that the lemma holds for k 1 We have ect F r q k ect F r q k 1 p s where s is a potentially null shift caused by the potentially empty forbidden region F ect F r q k 1 ect F r q k 1 s C F Similarly we have ect F r q k ect F r q k 1 p s where s is the shift caused by the forbidden region F ect F r q k 1 ect F r q k 1 C F If s is large enough to obtain ect F r q k gt ect F r q k then we have Fj C Fj Since F is a subset of Fi both functions ect F r q k and ect F r q k are shifted to the same value We therefore obtain ect F r q k ect F r q k which completes the induction step Oo Lemma 7 Iflst F d q lt lst F d q then lst F d q k lt lst F d q k for any k gt 0 Proof Symmetric to the proof of Lemma 6 Oo We now describe three different situations
13. e The idea behind the algorithm is the following We process each deadline in increasing order If two deadlines d and d are equal and their associated release times satisfy r lt r we process both deadlines at the same time but use d as a reference For every deadline d we compute the longest sequence of release times Tay lt Tes lt lt T p such that ro di lt Tx di lt lt rep di as we did in Theorem 11 Using this sequence and Equation 9 we compute the union of all internal adjustment intervals generated by the pairs of time points whose deadline is d To build the sequence we iterate through all the release times in non decreasing order Two cases can occur where we can safely skip a release time rj Case 1 dj gt d i Suppose that the deadline dj associated to r has not been processed yet i e dj gt dj For such a release time rj two cases can occur We choose the smallest release time rz whose deadline has already been processed and such that rg gt rj If such a rz exists then A r di A rx di and Lemma 9 insures that rg di gt rj di All adjustment intervals from r d will be taken into account when iterating through r If no such r exists then we have A r d and no adjustment intervals are associated to the pair r d In either case the pair r d can be ignored Case 2 r gt ri A release time rj greater than r can also be safely ignored Let d be the deadli
14. ency provided in ILOG for the I cAllMinDistance constraint were not able to compete with the Artiouchine Baptiste propagator nor with ours Number of Random Problems Solved in a Given Period of Time Number of Problems Solved Our propagator Artiouchine Baptiste 0 0 0001 0 001 0 01 0 1 1 10 Time s Figure 4 Number of random problems from the benchmark that were solved in a given period of time We then consider the runway scheduling problem where all intervals have the same length Over both series of problems available in the benchmark Artiouchine and Baptiste 2005 we obtain an improvement over the Artiouchine Baptiste propagator proportional to n This observation is compatible with the running time complexities of the algorithms Figure 5 shows the number of problems solved in a given period of time Again the two levels of consistency provided in ILOG for the cAllMinDistance constraint were not competitive 7 Conclusion We presented a new propagator achieving bounds consistency for the INTER DISTANCE constraint The running time complexity of O n improves by a factor of n the previous best known propagator This theoretical improvement gives practical savings in scheduling problems It is still an open problem whether there exists an O n log n propagator for the INTER DISTANCE con straint achieving bounds consistency It would also be interesting to study how the constraint could be gener alized for the cumulative
15. f Equation 9 has O n intervals while the right hand side has only O n intervals Indeed the number of intervals to unite is given by a A r d A ri41 The telescopic series simplifies to A 1r1 d A rk 1 d A r1 d In Example 1 since we have 2 20 lt 10 20 we obtain the following 12 20 0 U I2 20 1 U Lio 20 0 12 20 1 U Lio 20 0 9 7 U 15 15 15 15 Theorem 11 There are O n internal adjustment intervals that subsume any other internal adjustment interval Proof Consider a deadline d and two release times r lt rj For every value 0 lt q lt A r d we have min J a g min J a q We have max I a q gt max J d q if and only if r d gt rj d Consequently we have I a Ir d q if and only if r d gt rj d Consider the list of release times r lt rg lt lt rn sorted in non decreasing order If for some k we have rz d gt rk 1 d we can safely ignore the release time 7 41 since for every interval we have Irnard q Iry d q for O lt q lt A rey1 d q After removing all dominated release times we obtain a list of release times rp lt Tka lt lt Tkm Equation 9 shows how the internal adjustment intervals Z 4 4 for any r and q are subsumed by O n intervals Since there are O n deadlines d there are O n internal adjustment intervals that subsume any other internal adjustment interval E 4 A Quadratic Propagator 4 1 General Schem
16. hat finds a solution satisfying the INTER DISTANCE constraint in O n logn steps Their algorithm proceeds in two phases In the first phase the algorithm computes a set of intervals F in which no tasks are allowed to start We call this set the forbidden regions and denote it by F Their number is bounded above by n the number of tasks Once these forbidden regions are computed the second phase uses a greedy strategy to schedule the tasks Artiouchine and Baptiste 2005 and Garey et al 1981 use two basic functions as main pillars of their algorithm We define the completion time of a schedule as the time of completion of the very last task and the starting time of a schedule as the starting time of the very first task Let ect F r q be the earliest completion time of a schedule of q tasks with release time r and unbounded deadline such that no task starts in a forbidden region contained in the set of forbidden regions F Symmetrically let lst F d q be the latest starting time of a schedule of q tasks with deadline d and unbounded release time such that no task starts in a forbidden region in F Computing ect F r q and lst F d q can be done in O q steps using the following recurrences 7 F ifq 0 ect F r q min t g F t gt ect F r q 1 p ifq gt 0 1 7 d ifg 0 lst F d q max t g F t lt Ist F d q 1 p ifq gt 0 2 The function st helps to explain the algorithm of Garey et al see Algorithm 1 that computes the fo
17. here r and r might be equal If the interval 4 q41 does not exist the pointer is undefined The data structure initially contains an empty interval with lower bound oo used as a sentinel We implement Line 7 of Algorithm 2 as follows We insert the intervals in decreasing order of lower bounds Since we process variables by increasing deadlines the lower bound of J a 0 is larger or equal to any lower bound inserted in A and is therefore inserted at the end of the linked list Suppose we have inserted the interval J 14 disd and we now want to insert the interval 2 I 4 q 1 Algorithm 3 computes the insertion point in the linked list The algorithm follows the previous pointers starting from J until it either finds the insertion point or finds an interval I dp Whose next pointer is assigned In the latter case the algorithm follows the nextQ pointer to finally follow the next pointers until the insertion point is reached When following the nextQ Ir a q pointer the algorithm necessarily goes to or beyond the insertion point since we have min J lt min J and by Lemma 7 we have min nextQ I d q lt min nextQ I and therefore min J 1 lt min J2 We show that Algorithm 3 inserts a sequence of O n intervals in the linked list A in O n steps Lemma 13 Algorithm 3 inserts on line 7 a sequence of O n internal adjustment intervals in the linked list A in O n time Proof There is a maximum
18. if iF X X gt P 14 Clearly if there is an assignment X1 Xn that satisfies the case when P p then this assignment is also a support for P p 1 Therefore any value that has a support in the domain of X for P p has a support in the same domain for P lt p To prune the X variables one only needs to find the values in the domains that have a support for P min D P The algorithm presented in Section 4 when used with p min D P can therefore prune the X variables To prune the domain of P we rely on the following observation If the constraint is unsatisfiable with P p then it is unsatisfiable for P gt p Therefore to achieve bounds consistency on the variable P one only needs to prune the value max D P The algorithm by Garey et al allows testing in O n log n steps whether there exists a solution for P p Using a one sided binary search we can find the largest value in D P such that the INTER DISTANCE constraint is satisfiable A one sided binary search returning value p whose test requires O n log n time has a running time complexity of O n log n log p We can enforce bounds consistency on the INTER DISTANCE constraint when the distance variable is not fixed in O n n log n log p steps 6 Experiments We implemented our algorithm using the ILOG Solver C library ILOG 1998 The library already provides a propagator for the INTER DISTANCE constraint called cAllMinDistance and
19. ing Algorithm 3 Lemma 14 A sequence of O n external adjustment intervals can be inserted in O n time Proof For every pair j q Ui one can keep a pointer on its associated interval 7 a q in the data structure A Following the nextQ pointer to reach Ir 4 q 1 takes constant time Setting the new upper bound of Ty di q 1 also takes constant time The nextQ pointer is undefined for the last interval to insert Algorithm 3 can insert the interval I 4 q 1 in O n steps The total running time complexity is therefore O n Line 9 of Algorithm 2 can be implemented in O a n steps where a is the inverse of Ackermann s function We create a union find data structure S with elements from 1 to n For each element 7 we associate a time t initially set to r and a pointer p initially unassigned When inserting adjustment intervals in A in decreasing order of lower bounds we simultaneously iterate in decreasing order the sets in S If an interval I is inserted such that t I we change t to max J 1 We then follow the next pointers from I to check if other intervals intersect t and increase t for each intersecting interval If t becomes greater or equal to ti41 we merge the set in S containing 7 with the set containing 7 1 The pointer p is used to keep track of the last interval J tested with t in order not to check twice a same interval When executing Line 9 of Algorithm 2 we simply retrieve from S the set s containing i
20. intervals associated to the deadline d Proof The for loop on line 2 processes each release time rj such that dj lt dj andr lt ri Other release times can be safely ignored as they correspond to the cases and 2 stated above Line 3 tests whether ect F r b a lt rj The first time Line 3 is executed the test is positive since l j min P anda b We therefore include rin p di in the sequence Subsequent tests are positive only if the pair r d dominates the last pair r d tested positive as proved below ect F r b a lt r gt ect F r b a lt ect F r 0 by definition of ect 10 ect F r b q lt ect F r a q YO0 lt q lt a by Lemma 6 11 gt ri di lt rj di by def of dominance 12 Similarly one can prove that a negative test implies that r d gt rj di and that the pair rj d should not belong to the sequence The sequence r lt r2 lt lt rp is therefore not missing any release time Each time the relation r d lt rj d is discovered the algorithm appends to U the tuples j q for A r di lt q lt A r d Each tuple j q U will be used later to create the internal internal adjust ment intervals I q According to Equation 9 these intervals are sufficient E Following Artiouchine and Baptiste 2005 the second for loop on line 8 processes the deadlines in non decreasing order The external adjustment intervals are therefo
21. n that generally does not satisfy the side constraints These side constraints can even make the problem NP Hard See for instance the runway scheduling problem Artiouchine et al 2004 The flexibility that constraint programming offers to encode such problems is an asset A single INTER DISTANCE constraint can encode the disjunctive scheduling problem This constraint ensures that starting times are pairwise distant by at least p units of time The global constraint offers a stronger pruning than the O n associated binary constraints X X gt p Artiouchine and Baptiste 2005 recently proposed an O n propagator that enforces bounds consistency on the INTER DISTANCE constraint By achieving bounds consistency their propagator prunes the search space better than edge finding algorithms resulting in smaller choice points in the backtracking search and a better time performance We propose in this work a quadratic propagator that is faster both in theory and in practice even for small instances We generalize the INTER DISTANCE constraint by letting the distance P be a constrained variable whose domain can be pruned This proves to be useful when one wants to maximize the distance between each pair of variables The generalization of the INTER DISTANCE constraint as well as the experiments with this new constraint extend the work previously presented in Quimper et al 2006 Throughout the paper we will consider the set a b as the interval
22. ne processed before d Since A r d A r d Lemma 8 insures that we have rj di gt rj di and adjustment intervals from rj d have already been taken into account when processing d We prove that Algorithm 2 constructs for every deadline d a sequence rj lt rj lt lt Tj such that ridi lt rja di lt lt rip di This sequence with Equation 9 compute the adjustment intervals Let D be the set of deadlines sorted in increasing order If two deadlines are equal exclude from D the one whose associated release time is the smallest P A 0 U 0 V1 lt i lt n 1 for d D do P PU j dj di l min P 2 for j PA l i do a A r di b A 71 di if ect F r b a lt r then U U U l q a lt q lt bd A U n l j 6 Ui UiU l 4 0 lt q lt A r di 7 for j q U do A AU Ir aig 8 for all deadlines d in non decreasing order do 9 r min t g A t gt r if d D then for j q U do A AU Ex dig fori 1 n do r r Algorithm 2 Enforcing bounds consistency for the INTER DISTANCE constraint We assume that the forbidden regions F have already been computed and that release times are sorted such that r lt ri and Pi fii gt a lt digi Lemma 12 Algorithm 2 encodes in the data structure U a sequence rj di lt rja di lt lt lt Tips di generating all internal adjustment
23. of n intervals in A whose nextQ pointer is undefined therefore the first while loop runs in O n Let I4 be an interval explored by the second while loop The interval J lies between nextQ I and the insertion point By Lemma 7 if an interval J was pointing to J with its nextQ pointer the interval 3 would lie between J and J4 Since I3 4 I we conclude that no intervals point to J4 with its nextQ pointer There is a maximum of n such intervals The second while loop runs in O n We therefore showed that Line 7 can be implemented in O n steps E nextQ Ira dy qt1 gt insert point Irda q a e Ty Figure 2 Nodes in the doubly linked list that Algorithm 3 visits to find the insertion point of an adjustment interval I previous Ir d q In Lp diq 1 while nextQ JZ is undefined min I gt min J2 do I previous L if min Z gt min 2 then I nexstQ I while min nezxt I lt min I2 do I nezt I Insert J gt after I Algorithm 3 Compute the insertion point of J rj di q 1 provided that Iv a q has already been inserted Line 10 inserts in A a sequence of O n external adjustment intervals Notice that at this point A already contains the internal adjustment intervals and that by definition the lower bound of E 4 q is equal to the lower bound of J 4 q 1 Line 10 can be implemented by simply changing Ir a q 1 in A by E gt a q If Tp dj q 1 does not exist in A it can be added us
24. omplexity of Algorithm 2 is O n Proof We assume that the forbidden regions F have already been computed in O n log n time as explained by Garey et al 1981 The data structures P and U are implemented using linked lists and the functions Ist ect and A r d are implemented using tables The data structure A is implemented with the data structure described in Section 4 2 Release times and deadlines are sorted in O n log n time Initializing the algorithm therefore requires O n time For a fixed i every pair l q added to U on line 4 and line 6 have a distinct component q ranging from 0 to n exclusively There are therefore at most O n elements in U that were appended in O 1 time The complexity to build the list U is therefore O n Line 7 takes O n time to execute as stated by Lemma 13 The total running time for the for loop on line 1 is therefore O n By Lemma 15 the cummulative running time complexity of the line 9 is O n Line 10 takes O n time to execute as stated in Lemma 14 The for loop on line 8 therefore runs in O n Since the initialization and the for loops on lines 1 and 8 all run in O n time the total running time complexity of Algorithm 2 is also O n 5 Achieving Bounds Consistency on the Distance Variable We now consider the general form of the INTER DISTANCE constraint i e when the distance variable P is not fixed The constraint INTER DISTANCE X Xn P is satisfied if and only
25. rbidden regions F Their algorithm starts with an empty set of regions F and processes each release time r in decreasing order Consider a deadline d and let A r d be the tasks whose release times and deadlines are both contained in the interval r d The value Ist F d A r d r represents the amount of slack in the interval r d i e an upper bound on the processing time that can be used in the interval r d for tasks that are not in A r d If lst F d A r d r is smaller than p then there is not enough room to fit a whole task not in A r d The algorithm therefore appends to F the forbidden region lst F d A r d 1 1 r 1 Indeed any task starting in this region consumes too much time in the interval r d to allow the completion of the tasks in A r d If Ist F d A r d r lt 0 there are too many tasks that require to be executed in the interval r d the problem is unsolvable Upon termination the set of forbidden regions contains up to n distinct regions These regions are sufficient to find a solution to the problem but are insufficient to enforce bounds consistency on the INTER DISTANCE constraint Artiouchine and Baptiste explain how to compute a larger set of regions that are sufficient to filter the INTER DISTANCE constraint Using the functions ect and lst Artiouchine and Baptiste describe two types of adjustment intervals necessary and sufficient to maintain bounds consistency on the IN
26. re computed in an order that ensures that the processed variable is not contained in any A r dj considered so far Algorithm 2 only prunes the release times Following Puget 1998 one can prune the deadlines by creat ing the symmetric problem where task T has release time r d and deadline d r Algorithm 2 can then prune the release times in the symmetric problem which prunes the deadlines in the original problem The data structures P and U can be implemented using some linked lists However to obtain an algorithm running in quadratic time we need to craft a special data structure to store the adjustment intervals in A This data structure should allow the execution of lines 7 9 and 10 in no more than O n time even if A contains up to O n intervals The next section describes how the adjustment data structure A can meet these requirements 4 2 Keeping Track of Adjustment Intervals To guarantee a quadratic running time we must carefully design the data structure A that contains the ad justment intervals We use a doubly linked list containing all adjustment intervals sorted by lower bounds including empty intervals Each interval I q has a pointer next I a q and previous J a q pointing to the next and previous intervals in the list The first interval has its previous pointer undefined as the last interval has its neat pointer undefined Each interval has also a pointer nextQ Ip id a pointing to 1r dj q 1 w
27. s we have the following max I 4 q ect F r A r d q 1 ect F r A r d k q 1 Il 5 lt ect F r A r d q 1 Using Lemma 6 and ect F r k lt ect F r 0 lt max Ir aq Therefore we have r d gt r d E In Example 1 we have 10 20 gt 2 20 from Lemma 10 Lemma 10 is crucial to obtain a quadratic algorithm Consider a deadline d and a sequence of release times r lt r2 lt lt rp such that r1 d lt r2 d lt lt rpk d There can be up to O n internal adjustment intervals associated to these pairs of time points Nevertheless the union of all O n intervals can be given by the union of only O n intervals Given two integers j and q such that 1 lt j lt k and 0 lt q lt A r d we first notice that the following intervals all share a same lower bound The union of the intervals is therefore equal to the interval whose upper bound is the greatest j U traa min a q mar max Ir a q 6 min q max J a q 7 desig 8 We see that up to O n adjustment intervals can be contained in a single interval Using this observation we compute the union of all adjustment intervals formed by the pairs r1 d r d using the following equation To simplify the notation we let A rg 1 d 0 since rg 1 is undefined k A ri d 1 k A ri d 1 U lada U U Leeda 9 i 1 q 0 i 1 q A ri 1 d Notice that the left hand side o
28. scheduling problem 13 Percentage of Solved Problems in the Mono Pattern Benchmark in a Given Period of Time 60 50 40 30 20 Percentage of Solved Problems Our propagator Artiouchine Baptiste 0 001 0 01 0 1 1 10 100 Time s Figure 5 Number of problems with equal intervals from the benchmark that were solved in a given period of time References K Artiouchine and P Baptiste Inter distance constraint An extension of the all different constraint for scheduling equal length jobs In Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming pages pp 62 76 2005 K Artiouchine P Baptiste and C Diirr Runway scheduling with holding loop In Proceedings of Second International Workshop on Discrete Optimization Methods in Production and Logistics pages pp 96 101 2004 J Carlier and E Pinson Adjustment of heads and tails for the job shop problem European Journal of Operation Rsearch 1718 146 161 1994 M R Garey D S Johnson B B Simons and R E Tarjan Scheduling unit time tasks with arbitrary release times and deadlines SIAM Journal on Computing 10 2 256 269 1981 ILOG ILOG Solver 4 2 user s manual 1998 A Lopez Ortiz C G Quimper J Tromp and P van Beek A fast and simple algorithm for bounds consistency of the alldifferent constraint In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence pages pp
29. which a subset of the tasks are not allowed to start Definition 3 External Adjustment Intervals Given two time points r and d and an integer O lt q lt A r d the internal adjustment interval E a q is defined as follows Erag lst F d q 2 1 ect F r A r d q 1 4 Theorem 4 shows the main property of external adjustment intervals Theorem 4 Artiouchine and Baptiste 2005 Given two time points r d andan integer 0 lt q lt A r d a task i A r d cannot start in the interval Er d q External adjustment intervals appear in problems where a group of variables compete for an interval of values The variables whose domain is not restricted to this small interval and hence do not belong to this group of competing variables must be assigned to values outside of the interval Table 1 shows the internal and external adjustment intervals from Example 1 Artiouchine and Baptiste formally proved that the internal and external adjustment intervals are necessary and sufficient to enforce bounds consistency on the INTER DISTANCE constraint Internal Adjustment Intervals ri dj 12 20 21 2 7 7 9 7 15 13 8 7 9 13 16 19 4 0 15 9 9 9 16 15 10 0 15 15 16 15 External Adjustment Intervals ri d 12 20 21 2 3 7 3 7 9 13 3 7 3 13 9 19 4 0 9 9 8 9 9 15 10 0 9 15 9 15 Table 1 Internal and external adjustment intervals
Download Pdf Manuals
Related Search