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