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