Generated on Thu Jan 31 2019 20:56:35 for Gecode by doxygen 1.8.15
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, 2015
9  * Guido Tack, 2010
10  *
11  * Last modified:
12  * $Date: 2016-04-19 17:19:45 +0200 (Tue, 19 Apr 2016) $ by $Author: schulte $
13  * $Revision: 14967 $
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 Unary {
41 
42  template<class Task>
45  Region r(home);
46 
47  bool assigned;
48  if (Event* e = Event::events(r,t,assigned)) {
49  // Whether resource is free
50  bool free = true;
51  // Set of current but not required tasks
52  Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size()));
53 
54  // Process events
55  do {
56  // Current time
57  int time = e->time();
58 
59  // Process events for completion of required part
60  for ( ; (e->type() == Event::LRT) && (e->time() == time); e++)
61  if (t[e->idx()].mandatory()) {
62  tasks.set(static_cast<unsigned int>(e->idx()));
63  free = true;
64  }
65 
66  // Process events for completion of task
67  for ( ; (e->type() == Event::LCT) && (e->time() == time); e++)
68  tasks.clear(static_cast<unsigned int>(e->idx()));
69 
70  // Process events for start of task
71  for ( ; (e->type() == Event::EST) && (e->time() == time); e++)
72  tasks.set(static_cast<unsigned int>(e->idx()));
73 
74  // Process events for zero-length task
75  for ( ; (e->type() == Event::ZRO) && (e->time() == time); e++)
76  if (!free)
77  return ES_FAILED;
78 
79  // Norun start time
80  int nrstime = time;
81  // Process events for start of required part
82  for ( ; (e->type() == Event::ERT) && (e->time() == time); e++)
83  if (t[e->idx()].mandatory()) {
84  tasks.clear(static_cast<unsigned int>(e->idx()));
85  if (!free)
86  return ES_FAILED;
87  free = false;
88  nrstime = time+1;
89  } else if (t[e->idx()].optional() && !free) {
90  GECODE_ME_CHECK(t[e->idx()].excluded(home));
91  }
92 
93  if (!free)
95  j(); ++j)
96  // Task j cannot run from time to next time - 1
97  if (t[j.val()].mandatory())
98  GECODE_ME_CHECK(t[j.val()].norun(home, nrstime, e->time() - 1));
99 
100  } while (e->type() != Event::END);
101  }
102 
103  if (assigned)
104  return home.ES_SUBSUMED(p);
105 
106  return ES_NOFIX;
107  }
108 
109 }}}
110 
111 // 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:3614
void clear(unsigned int i)
Clear bit i.
ExecStatus timetabling(Space &home, Propagator &p, TaskArray< Task > &t)
Perform time-tabling propagation.
Base-class for propagators.
Definition: core.hpp:1092
Earliest required time of task.
Definition: task.hh:502
Task array.
Definition: task.hh:169
Handle to region.
Definition: region.hpp:61
Computation spaces.
Definition: core.hpp:1748
Value iterator for values in a bitset.
End marker.
Definition: task.hh:503
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Time-tabling event for task.
Definition: task.hh:494
Execution has resulted in failure.
Definition: core.hpp:542
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:784
ExecStatus
Definition: core.hpp:540
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:543
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
Earliest start time of task.
Definition: task.hh:500