pcp/propagators/
cumulative.rs

1// Copyright 2016 Pierre Talbot (IRCAM)
2
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6
7//     http://www.apache.org/licenses/LICENSE-2.0
8
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use logic::*;
16use propagators::*;
17use term::*;
18use concept::*;
19
20pub struct Cumulative<VStore>
21{
22  starts: Vec<Var<VStore>>,
23  durations: Vec<Var<VStore>>,
24  resources: Vec<Var<VStore>>,
25  capacity: Var<VStore>,
26  intermediate: Vec<Vec<usize>>, // Given intermediate[j][i], if i left-overlap j, then it contains the number of resources used by i.
27}
28
29impl<VStore> Cumulative<VStore>
30{
31  pub fn new(starts: Vec<Var<VStore>>, durations: Vec<Var<VStore>>,
32   resources: Vec<Var<VStore>>, capacity: Var<VStore>) -> Self
33  {
34    let tasks = starts.len();
35    assert_eq!(tasks, durations.len());
36    assert_eq!(tasks, resources.len());
37    Cumulative {
38      starts: starts,
39      durations: durations,
40      resources: resources,
41      capacity: capacity,
42      intermediate: vec![]
43    }
44  }
45}
46
47impl<VStore, Domain, Bound> Cumulative<VStore> where
48  VStore: VStoreConcept<Item=Domain> + 'static,
49  Domain: IntDomain<Item=Bound> + 'static,
50  Bound: IntBound + 'static,
51{
52  // Decomposition described in `Why cumulative decomposition is not as bad as it sounds`, Schutt and al., 2009.
53  // Intuitively, it says that for each task j, the sum of the resources used by the other tasks overlapping with j must not exceed the capacity.
54  // forall( j in tasks ) (
55  //   c >= r[j] + sum( i in tasks where i != j ) (
56  //     bool2int( s[i] <= s[j] /\ s[j] < s[i] + d[i] ) * r[i]));
57  pub fn join<CStore>(&mut self, vstore: &mut VStore, cstore: &mut CStore) where
58    CStore: IntCStore<VStore> + 'static
59  {
60    let tasks = self.starts.len();
61    // Special case where only one task needs to be scheduled.
62    if tasks == 1 {
63      // c >= r[j]
64      cstore.alloc(Box::new(x_geq_y(self.capacity_var(), self.resource_at(0))));
65    }
66    else {
67      // forall( j in tasks ) (...)
68      for j in 0..tasks {
69        let mut resource_vars = vec![];
70        self.intermediate.push(vec![]);
71        for i in 0..tasks {
72          if i != j {
73            // conj <-> s[i] <= s[j] /\ s[j] < s[i] + d[i]
74            let conj = Box::new(Conjunction::new(vec![
75              // s[i] <= s[j]
76              Box::new(x_leq_y(self.start_at(i), self.start_at(j))),
77              // s[j] < s[i] + d[i]
78              Box::new(XLessYPlusZ::new(self.start_at(j), self.start_at(i), self.duration_at(i)))]));
79
80            // bi <-> conj
81            let bi = Boolean::new(vstore);
82            let equiv = equivalence(Box::new(bi.clone()), conj);
83            cstore.alloc(equiv);
84
85            // r = bi * r[i]
86            let ri = self.resource_at(i);
87            let ri_ub = ri.read(vstore).upper();
88            let r_dom = Domain::new(Bound::zero(), ri_ub);
89            // let hole = Domain::new(Bound::one(), ri_ub.clone() - Bound::one());
90            let r = vstore.alloc(r_dom);
91            self.intermediate.last_mut().unwrap().push(r.index());
92            let r = Box::new(r) as Var<VStore>;
93            cstore.alloc(Box::new(XEqYMulZ::new(r.bclone(), Box::new(bi), ri)));
94            resource_vars.push(r);
95          }
96        }
97        //  sum( i in tasks where i != j )(...)
98        let sum = Box::new(Sum::new(resource_vars));
99        // c >= r[j] + sum
100        cstore.alloc(Box::new(x_geq_y_plus_z(self.capacity_var(), self.resource_at(j), sum)));
101      }
102    }
103  }
104
105  pub fn intermediate_vars(&self) -> Vec<Vec<usize>> {
106    self.intermediate.clone()
107  }
108
109  fn start_at(&self, i: usize) -> Var<VStore> {
110    self.starts[i].bclone()
111  }
112  fn duration_at(&self, i: usize) -> Var<VStore> {
113    self.durations[i].bclone()
114  }
115  fn resource_at(&self, i: usize) -> Var<VStore> {
116    self.resources[i].bclone()
117  }
118  fn capacity_var(&self) -> Var<VStore> {
119    self.capacity.bclone()
120  }
121}
122
123#[cfg(test)]
124mod test {
125  use super::*;
126  use kernel::*;
127  use trilean::SKleene;
128  use trilean::SKleene::*;
129  use variable::VStoreCopy;
130  use propagation::CStoreFD;
131  use interval::interval::*;
132  use interval::ops::Range;
133  use gcollections::ops::*;
134  use model::*;
135  use propagation::ops::Subsumption;
136
137  type Dom = Interval<i32>;
138  type VStoreFD = VStoreCopy<Dom>;
139
140  struct CumulativeTest {
141    starts: Vec<Interval<i32>>,
142    durations: Vec<Interval<i32>>,
143    resources: Vec<Interval<i32>>,
144    capacity: Interval<i32>,
145  }
146
147  impl CumulativeTest {
148    fn new(starts: Vec<Interval<i32>>, durations: Vec<Interval<i32>>,
149      resources: Vec<Interval<i32>>, capacity: Interval<i32>) -> Self
150    {
151      CumulativeTest {
152        starts: starts,
153        durations: durations,
154        resources: resources,
155        capacity: capacity
156      }
157    }
158
159    fn new_assignment(starts: Vec<i32>, durations: Vec<i32>,
160      resources: Vec<i32>, capacity: i32) -> Self
161    {
162      CumulativeTest::new(
163        starts.into_iter().map(|s| Interval::new(s, s)).collect(),
164        durations.into_iter().map(|d| Interval::new(d, d)).collect(),
165        resources.into_iter().map(|r| Interval::new(r, r)).collect(),
166        Interval::new(capacity, capacity)
167      )
168    }
169
170    fn create_var(dom: Interval<i32>, model: &mut Model,
171      vstore: &mut VStoreFD, constant: bool) -> Var<VStoreFD>
172    {
173      if dom.is_singleton() && constant {
174        Box::new(Constant::new(dom.lower()))
175      }
176      else {
177        model.alloc_var(vstore, dom)
178      }
179    }
180
181    fn instantiate(self, model: &mut Model, vstore: &mut VStoreFD,
182      cstore: &mut CStoreFD<VStoreFD>, constant: bool)
183    {
184      model.open_group("s");
185      let starts = self.starts.into_iter()
186        .map(|s| Self::create_var(s,model,vstore,constant)).collect();
187      model.close_group();
188      model.open_group("d");
189      let durations = self.durations.into_iter()
190        .map(|d| Self::create_var(d,model,vstore,constant)).collect();
191      model.close_group();
192      model.open_group("r");
193      let resources = self.resources.into_iter()
194        .map(|r| Self::create_var(r,model,vstore,constant)).collect();
195      model.close_group();
196      let capacity = Box::new(vstore.alloc(self.capacity));
197      model.register_var(capacity.index(), String::from("c"));
198
199      let mut cumulative = Cumulative::new(starts, durations, resources, capacity);
200      cumulative.join(vstore, cstore);
201    }
202
203    // The boolean "constant" indicates if we transform the singleton domains into constant terms or not.
204    fn test(self, test_num: usize, before: SKleene, after: SKleene, constant: bool) {
205      println!("Test number {}", test_num);
206      let mut vstore = VStoreFD::empty();
207      let mut cstore = CStoreFD::empty();
208      let mut model = Model::new();
209      self.instantiate(&mut model, &mut vstore, &mut cstore, constant);
210      cstore.display(&(model, vstore.clone()));
211      assert_eq!(cstore.is_subsumed(&vstore), before);
212      assert_eq!(cstore.consistency(&mut vstore), after);
213      assert_eq!(cstore.is_subsumed(&vstore), after);
214    }
215
216    fn test_assignment(self, test_num: usize, expected: SKleene, constant: bool) {
217      // Unknown because cumulative introduces new variables not fixed.
218      self.test(test_num, Unknown, expected, constant);
219    }
220  }
221
222  #[test]
223  fn disjunctive_test() {
224    CumulativeTest::new_assignment(
225      vec![0,0], vec![0,0], vec![1,1], 1
226    )
227    .test_assignment(1, True, false);
228  }
229
230  #[test]
231  fn singleton_task() {
232    CumulativeTest::new_assignment(vec![0], vec![0], vec![1], 1)
233      .test(1, True, True, false);
234
235    CumulativeTest::new_assignment(vec![0], vec![0], vec![1], 1)
236      .test(1, True, True, true);
237  }
238
239  #[test]
240  fn cumulative_assignment_test() {
241    let constant = false;
242    // The task 2 and 3 overlaps and consume 4 resources altogether.
243    let test = CumulativeTest::new_assignment(
244      vec![0,1,4], vec![3,4,2], vec![1,2,2], 3);
245    test.test(1, Unknown, False, constant);
246
247    // We can delay the task 3 to fix the problem.
248    let test = CumulativeTest::new_assignment(
249      vec![0,1,5], vec![3,4,2], vec![1,2,2], 3);
250    test.test(2, Unknown, True, constant);
251
252    // Another possibility is to reduce the resource of task 3.
253    let test = CumulativeTest::new_assignment(
254      vec![0,1,4], vec![3,4,2], vec![1,2,1], 3);
255    test.test(3, Unknown, True, constant);
256
257    // Or augment the total amount of resources available.
258    let test = CumulativeTest::new_assignment(
259      vec![0,1,4], vec![3,4,2], vec![1,2,2], 4);
260    test.test(4, Unknown, True, constant);
261
262    // Or reduce the duration of task 2.
263    let test = CumulativeTest::new_assignment(
264      vec![0,1,4], vec![3,3,2], vec![1,2,2], 3);
265    test.test(4, Unknown, True, constant);
266  }
267
268  #[test]
269  fn cumulative_test_constant() {
270    cumulative_test_param(true);
271  }
272
273  #[test]
274  fn cumulative_test_variable() {
275    cumulative_test_param(false);
276  }
277
278
279  fn cumulative_test_param(constant: bool) {
280    let mut test = CumulativeTest::new_assignment(
281      vec![0,1,4], vec![3,4,2], vec![1,2,2], 3);
282    // Widden the start date of task 1, should fail anyway.
283    test.starts[0] = Interval::new(0,4);
284    test.test(1, Unknown, False, constant);
285
286    let mut test = CumulativeTest::new_assignment(
287      vec![0,1,4], vec![3,4,2], vec![1,2,2], 3);
288    // Widden the start date of task 2, succeed when schedule at start=0.
289    test.starts[1] = Interval::new(0,1);
290    test.test(2, Unknown, Unknown, constant);
291
292    let mut test = CumulativeTest::new_assignment(
293      vec![0,1,4], vec![3,4,2], vec![1,2,2], 3);
294    // Widden the start date of task 3, succeed when schedule at start=5.
295    test.starts[2] = Interval::new(4,5);
296    test.test(3, Unknown, Unknown, constant);
297  }
298}
pcp/propagators/cumulative.rs

pcp/propagators/
cumulative.rs
