time-tabling.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Christian Schulte, 2010
* Guido Tack, 2010
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
namespace Gecode { namespace Int { namespace Cumulative {
template<class Task>
class TaskByDecCap {
public:
bool operator ()(const Task& t1, const Task& t2) const;
};
template<class Task>
forceinline bool
TaskByDecCap<Task>::operator ()(const Task& t1, const Task& t2) const {
return t1.c() > t2.c();
}
// Basic propagation (timetabling)
template<class Task, class Cap>
forceinline ExecStatus
timetabling(Space& home, Propagator& p, Cap c, TaskArray<Task>& t) {
int ccur = c.max();
int cmax = ccur;
int cmin = ccur;
// Sort tasks by decreasing capacity
TaskByDecCap<Task> tbdc;
Support::quicksort(&t[0], t.size(), tbdc);
Region r;
bool assigned;
if (Event* e = Event::events(r,t,assigned)) {
// Set of current but not required tasks
Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size()));
// Process events, use ccur as the capacity that is still free
do {
// Current time
int time = e->time();
// Process events for completion of required part
for ( ; (e->type() == Event::LRT) && (e->time() == time); e++)
if (t[e->idx()].mandatory()) {
tasks.set(static_cast<unsigned int>(e->idx()));
ccur += t[e->idx()].c();
}
// Process events for completion of task
for ( ; (e->type() == Event::LCT) && (e->time() == time); e++)
tasks.clear(static_cast<unsigned int>(e->idx()));
// Process events for start of task
for ( ; (e->type() == Event::EST) && (e->time() == time); e++)
tasks.set(static_cast<unsigned int>(e->idx()));
// Process events for zero-length task
for ( ; (e->type() == Event::ZRO) && (e->time() == time); e++) {
ccur -= t[e->idx()].c();
if (ccur < cmin) cmin=ccur;
if (ccur < 0)
return ES_FAILED;
ccur += t[e->idx()].c();
}
// norun start time
int nrstime = time;
// Process events for start of required part
for ( ; (e->type() == Event::ERT) && (e->time() == time); e++)
if (t[e->idx()].mandatory()) {
tasks.clear(static_cast<unsigned int>(e->idx()));
ccur -= t[e->idx()].c();
if (ccur < cmin) cmin=ccur;
nrstime = time+1;
if (ccur < 0)
return ES_FAILED;
} else if (t[e->idx()].optional() && (t[e->idx()].c() > ccur)) {
GECODE_ME_CHECK(t[e->idx()].excluded(home));
}
// Exploit that tasks are sorted according to capacity
for (Iter::Values::BitSet<Support::BitSet<Region> > j(tasks);
j() && (t[j.val()].c() > ccur); ++j)
// Task j cannot run from zltime to next time - 1
if (t[j.val()].mandatory())
GECODE_ME_CHECK(t[j.val()].norun(home, nrstime, e->time() - 1));
} while (e->type() != Event::END);
GECODE_ME_CHECK(c.gq(home,cmax-cmin));
}
if (assigned)
return home.ES_SUBSUMED(p);
return ES_NOFIX;
}
}}}
// STATISTICS: int-prop
Gecode::FloatVal::max
friend FloatVal max(const FloatVal &x, const FloatVal &y)
Definition val.hpp:386
Gecode::Int::Cumulative::TaskByDecCap
Sort order for tasks by decreasing capacity.
Definition time-tabling.hpp:40
Gecode::Int::Cumulative::TaskByDecCap::operator()
bool operator()(const Task &t1, const Task &t2) const
Sort order.
Definition time-tabling.hpp:48
Gecode::Int::Event
Time-tabling event for task.
Definition task.hh:490
Gecode::Int::Event::events
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
Gecode::Int::Event::ZRO
@ ZRO
Zero-length task start time.
Definition task.hh:497
Gecode::Int::Event::ERT
@ ERT
Earliest required time of task.
Definition task.hh:498
Gecode::Int::Event::LRT
@ LRT
Latest required time of task.
Definition task.hh:494
Gecode::Int::Event::EST
@ EST
Earliest start time of task.
Definition task.hh:496
Gecode::Int::Event::END
@ END
End marker.
Definition task.hh:499
Gecode::Int::Event::LCT
@ LCT
Latest completion time of task.
Definition task.hh:495
Gecode::Int::TaskArray
Task array.
Definition task.hh:165
Gecode::Int::TaskArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:63
Gecode::Int::Task
Gecode::Iter::Values::BitSet
Value iterator for values in a bitset.
Definition values-bitset.hpp:42
Gecode::Propagator
Base-class for propagators.
Definition core.hpp:1064
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Support::BitSetBase::clear
void clear(unsigned int i)
Clear bit i.
Definition bitset-base.hpp:600
Gecode::Support::BitSetBase::set
void set(unsigned int i)
Set bit i.
Definition bitset-base.hpp:595
Gecode::Support::BitSet
Simple bitsets.
Definition bitset.hpp:45
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
Gecode::Int::Cumulative
Scheduling for cumulative resources
Definition cumulative.cpp:40
Gecode::Int::Cumulative::timetabling
ExecStatus timetabling(Space &home, Propagator &p, Cap c, TaskArray< Task > &t)
Perform time-tabling propagation.
Definition time-tabling.hpp:55
Gecode::Int
Finite domain integers.
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
forceinline
#define forceinline
Definition config.hpp:187