Generated on Tue Jul 27 2010 21:59:14 for Gecode by doxygen 1.7.1

basic.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2010
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-07-15 13:39:19 +0200 (Thu, 15 Jul 2010) $ by $Author: tack $
00011  *     $Revision: 11201 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 namespace Gecode { namespace Scheduling { namespace Cumulative {
00039 
00041   class Event {
00042   public:
00044     enum Type {
00045       LRT = 0, 
00046       LCT = 1, 
00047       EST = 2, 
00048       ZRO = 3, 
00049       ERT = 4, 
00050       END = 5  
00051     };
00052     Type e; 
00053     int t;  
00054     int i;  
00055 
00056     void init(Type e, int t, int i);
00058     bool operator <(const Event& e) const;
00059   };
00060 
00062   template<class Task>
00063   class TaskByDecCap {
00064   public:
00066     bool operator ()(const Task& t1, const Task& t2) const;
00067   };
00068 
00069   forceinline void
00070   Event::init(Event::Type e0, int t0, int i0) {
00071     e=e0; t=t0; i=i0;
00072   }
00073 
00074   forceinline bool
00075   Event::operator <(const Event& e) const {
00076     if (this->t == e.t)
00077       return this->e < e.e;
00078     return this->t < e.t;
00079   }
00080 
00081   template<class Task>
00082   forceinline bool
00083   TaskByDecCap<Task>::operator ()(const Task& t1, const Task& t2) const {
00084     return t1.c() > t2.c();
00085   }
00086 
00087 
00088   // Basic propagation
00089   template<class Task>
00090   ExecStatus
00091   basic(Space& home, Propagator& p, int c, TaskArray<Task>& t) {
00092     // Sort tasks by decreasing capacity
00093     TaskByDecCap<Task> tbdc;
00094     Support::quicksort(&t[0], t.size(), tbdc);
00095 
00096     Region r(home);
00097 
00098     Event* e = r.alloc<Event>(4*t.size()+1);
00099 
00100     // Initialize events
00101     bool assigned=true;
00102     {
00103       bool required=false;
00104       int n=0;
00105       for (int i=t.size(); i--; ) 
00106         if (t[i].assigned()) {
00107           // Only add required part
00108           if (t[i].pmin() > 0) {
00109             required = true;
00110             e[n++].init(Event::ERT,t[i].lst(),i);
00111             e[n++].init(Event::LRT,t[i].ect(),i);
00112           } else if (t[i].pmax() == 0) {
00113             required = true;
00114             e[n++].init(Event::ZRO,t[i].lst(),i);
00115           }
00116         } else {
00117           assigned = false;
00118           e[n++].init(Event::EST,t[i].est(),i);
00119           e[n++].init(Event::LCT,t[i].lct(),i);
00120           // Check whether task has required part
00121           if (t[i].lst() < t[i].ect()) {
00122             required = true;
00123             e[n++].init(Event::ERT,t[i].lst(),i);
00124             e[n++].init(Event::LRT,t[i].ect(),i);
00125           }
00126         }
00127       
00128       // Check whether no task has a required part
00129       if (!required)
00130         return assigned ? home.ES_SUBSUMED(p) : ES_FIX;
00131       
00132       // Write end marker
00133       e[n++].init(Event::END,Int::Limits::infinity,-1);
00134       
00135       // Sort events
00136       Support::quicksort(e, n);
00137     }
00138 
00139     // Set of current but not required tasks
00140     Support::BitSet<Region> tasks(r,static_cast<unsigned int>(t.size()));
00141 
00142     // Process events, use c as the capacity that is still free
00143     while (e->e != Event::END) {
00144       // Current time
00145       int time = e->t;
00146 
00147       // Process events for completion of required part
00148       for ( ; (e->t == time) && (e->e == Event::LRT); e++) 
00149         if (t[e->i].mandatory()) {
00150           tasks.set(static_cast<unsigned int>(e->i)); c += t[e->i].c();
00151         }
00152       // Process events for completion of task
00153       for ( ; (e->t == time) && (e->e == Event::LCT); e++)
00154         tasks.clear(static_cast<unsigned int>(e->i));
00155       // Process events for start of task
00156       for ( ; (e->t == time) && (e->e == Event::EST); e++)
00157         tasks.set(static_cast<unsigned int>(e->i));
00158       // Process events for zero-length task
00159       for ( ; (e->t == time) && (e->e == Event::ZRO); e++)
00160         if (c < t[e->i].c())
00161           return ES_FAILED;
00162 
00163       // norun start time for 0-length tasks
00164       int zltime = time;
00165       // Process events for start of required part
00166       for ( ; (e->t == time) && (e->e == Event::ERT); e++) 
00167         if (t[e->i].mandatory()) {
00168           tasks.clear(static_cast<unsigned int>(e->i)); 
00169           c -= t[e->i].c(); zltime = time+1;
00170           if (c < 0)
00171             return ES_FAILED;
00172         } else if (t[e->i].optional() && (t[e->i].c() > c)) {
00173           GECODE_ME_CHECK(t[e->i].excluded(home));
00174         }
00175       
00176       // Exploit that tasks are sorted according to capacity
00177       for (Iter::Values::BitSet<Support::BitSet<Region> > j(tasks); 
00178            j() && (t[j.val()].c() > c); ++j) 
00179         // Task j cannot run from time to next time - 1
00180         if (t[j.val()].mandatory())
00181           if (t[j.val()].pmin() > 0) {
00182             GECODE_ME_CHECK(t[j.val()].norun(home, time, e->t - 1));
00183           } else {
00184             GECODE_ME_CHECK(t[j.val()].norun(home, zltime, e->t - 1));
00185           }
00186     }
00187     
00188     return assigned ? home.ES_SUBSUMED(p) : ES_NOFIX;
00189   }
00190 
00191 }}}
00192 
00193 // STATISTICS: scheduling-prop