Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
time-tabling.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Copyright:
8  * Christian Schulte, 2010
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date$ by $Author$
13  * $Revision$
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 namespace Gecode { namespace Int { namespace Cumulative {
41 
43  template<class Task>
44  class TaskByDecCap {
45  public:
47  bool operator ()(const Task& t1, const Task& t2) const;
48  };
49 
50  template<class Task>
51  forceinline bool
52  TaskByDecCap<Task>::operator ()(const Task& t1, const Task& t2) const {
53  return t1.c() > t2.c();
54  }
55 
56  // Basic propagation (timetabling)
57  template<class Task, class Cap>
60  int ccur = c.max();
61  int cmax = ccur;
62  int cmin = ccur;
63 
64  // Sort tasks by decreasing capacity
65  TaskByDecCap<Task> tbdc;
66  Support::quicksort(&t[0], t.size(), tbdc);
67 
68  Region r;
69 
70  bool assigned;
71  if (Event* e = Event::events(r,t,assigned)) {
72  // Set of current but not required tasks
73  Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size()));
74 
75  // Process events, use ccur as the capacity that is still free
76  do {
77  // Current time
78  int time = e->time();
79 
80  // Process events for completion of required part
81  for ( ; (e->type() == Event::LRT) && (e->time() == time); e++)
82  if (t[e->idx()].mandatory()) {
83  tasks.set(static_cast<unsigned int>(e->idx()));
84  ccur += t[e->idx()].c();
85  }
86  // Process events for completion of task
87  for ( ; (e->type() == Event::LCT) && (e->time() == time); e++)
88  tasks.clear(static_cast<unsigned int>(e->idx()));
89  // Process events for start of task
90  for ( ; (e->type() == Event::EST) && (e->time() == time); e++)
91  tasks.set(static_cast<unsigned int>(e->idx()));
92  // Process events for zero-length task
93  for ( ; (e->type() == Event::ZRO) && (e->time() == time); e++) {
94  ccur -= t[e->idx()].c();
95  if (ccur < cmin) cmin=ccur;
96  if (ccur < 0)
97  return ES_FAILED;
98  ccur += t[e->idx()].c();
99  }
100 
101  // norun start time
102  int nrstime = time;
103  // Process events for start of required part
104  for ( ; (e->type() == Event::ERT) && (e->time() == time); e++)
105  if (t[e->idx()].mandatory()) {
106  tasks.clear(static_cast<unsigned int>(e->idx()));
107  ccur -= t[e->idx()].c();
108  if (ccur < cmin) cmin=ccur;
109  nrstime = time+1;
110  if (ccur < 0)
111  return ES_FAILED;
112  } else if (t[e->idx()].optional() && (t[e->idx()].c() > ccur)) {
113  GECODE_ME_CHECK(t[e->idx()].excluded(home));
114  }
115 
116  // Exploit that tasks are sorted according to capacity
118  j() && (t[j.val()].c() > ccur); ++j)
119  // Task j cannot run from zltime to next time - 1
120  if (t[j.val()].mandatory())
121  GECODE_ME_CHECK(t[j.val()].norun(home, nrstime, e->time() - 1));
122  } while (e->type() != Event::END);
123 
124  GECODE_ME_CHECK(c.gq(home,cmax-cmin));
125  }
126 
127  if (assigned)
128  return home.ES_SUBSUMED(p);
129  return ES_NOFIX;
130  }
131 
132 }}}
133 
134 // STATISTICS: int-prop
Zero-length task start time.
Definition: task.hh:501
NodeType t
Type of node.
Definition: bool-expr.cpp:234
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
void clear(unsigned int i)
Clear bit i.
Base-class for propagators.
Definition: core.hpp:1016
Earliest required time of task.
Definition: task.hh:502
Task array.
Definition: task.hh:169
Handle to region.
Definition: region.hpp:57
#define forceinline
Definition: config.hpp:182
Computation spaces.
Definition: core.hpp:1668
Value iterator for values in a bitset.
Gecode::FloatVal c(-8, 8)
End marker.
Definition: task.hh:503
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:134
bool operator()(const Task &t1, const Task &t2) const
Sort order.
Time-tabling event for task.
Definition: task.hh:494
Execution has resulted in failure.
Definition: core.hpp:466
void set(unsigned int i)
Set bit i.
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
Latest completion time of task.
Definition: task.hh:499
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
Sort order for tasks by decreasing capacity.
ExecStatus timetabling(Space &home, Propagator &p, Cap c, TaskArray< Task > &t)
Perform time-tabling propagation.
ExecStatus
Definition: core.hpp:464
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
Propagation has not computed fixpoint.
Definition: core.hpp:467
Latest required time of task.
Definition: task.hh:498
static Event * events(Region &r, const TaskArray< Task > &t, bool &assigned)
Allocate from r and initialize event array with tasks t.
Definition: event.hpp:87
Gecode toplevel namespace
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:67
Earliest start time of task.
Definition: task.hh:500