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

edge-finding.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, 2009
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-06-03 13:11:11 +0200 (Thu, 03 Jun 2010) $ by $Author: tack $
00011  *     $Revision: 11013 $
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 #include <algorithm>
00039 
00040 namespace Gecode { namespace Scheduling { namespace Cumulative {
00041 
00043   template<class TaskView, bool inc>
00044   class StoCap {
00045   public:
00047     bool operator ()(const TaskView& t1, const TaskView& t2) const {
00048       return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
00049     }
00050   };
00051 
00053   class PrecOrder {
00054   public:
00055     int* prec;
00057     PrecOrder(int* prec0) : prec(prec0) {}
00059     bool operator ()(int i, int j) const {
00060       return prec[i] > prec[j];
00061     }
00062   };
00063 
00064   template<class TaskView>
00065   forceinline ExecStatus
00066   edgefinding(Space& home, int c, TaskViewArray<TaskView>& t) {
00067     sort<TaskView,STO_LCT,false>(t);
00068 
00069     Region r(home);
00070 
00072     // Detection
00073 
00074     int* prec = r.alloc<int>(t.size());
00075     for (int i=t.size(); i--; )
00076       prec[i] = t[i].ect();
00077 
00078     OmegaLambdaTree<TaskView> ol(r,c,t);
00079 
00080     for (int j=0; j<t.size(); j++) {
00081       while (!ol.lempty() && 
00082              (ol.lenv() > static_cast<double>(c)*t[j].lct())) {
00083         int i = ol.responsible();
00084         prec[i] = std::max(prec[i], t[j].lct());
00085         ol.lremove(i);
00086       }
00087       ol.shift(j);
00088     }      
00089 
00091     // Propagation
00092     
00093     // Compute array of unique capacities and a mapping
00094     // from the task array to the corresponding entry in
00095     // the capacity array
00096     
00097     int* cap = r.alloc<int>(t.size());
00098     for (int i=t.size(); i--;)
00099       cap[i] = i;
00100     SortMap<TaskView,StoCap,true> o(t);
00101     Support::quicksort(cap, t.size(), o);
00102 
00103     int* capacities = r.alloc<int>(t.size());
00104     int* capInv = r.alloc<int>(t.size());
00105     for (int i=t.size(); i--;) {
00106       capacities[cap[i]] = t[i].c();
00107       capInv[cap[i]] = i;
00108     }
00109     
00110     int n_c = 0;
00111     for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
00112       if (capacities[i] != cur_c)
00113         capacities[n_c++] = cur_c = capacities[i];
00114       cap[capInv[i]] = n_c-1;
00115     }
00116     r.free<int>(capInv, t.size());
00117 
00118     // Compute update values for each capacity and LCut
00119 
00120     int* update = r.alloc<int>(t.size()*n_c);
00121     for (int i=t.size()*n_c; i--;)
00122       update[i] = -Int::Limits::infinity;
00123 
00124     ExtOmegaTree<TaskView> eo(r,c,ol);
00125     for (int i=0; i<n_c; i++) {
00126       eo.init(capacities[i]);
00127       int u = -Int::Limits::infinity;
00128       for (int j=t.size(); j--;) {
00129         double lctj = static_cast<double>(c-capacities[i])*t[j].lct();
00130         double diff_d = ceil(div(plus(eo.env(j), -lctj),capacities[i]));
00131         int diff = (diff_d == -Int::Limits::double_infinity) ? 
00132           -Int::Limits::infinity : static_cast<int>(diff_d);
00133         u = std::max(u,diff);
00134         update[i*t.size()+j] = u;
00135       }
00136     }
00137 
00138     // Update est by iterating in parallel over the prec array
00139     // and the task array, both sorted by lct
00140 
00141     int* precMap = r.alloc<int>(t.size());
00142     for (int i=t.size(); i--;)
00143       precMap[i] = i;
00144     PrecOrder po(prec);
00145     Support::quicksort(precMap, t.size(), po);
00146     
00147     int curJ = 0;
00148     for (int i=0; i<t.size(); i++) {
00149       while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
00150         curJ++;
00151       while (curJ < t.size() && t[curJ].lct() == prec[precMap[i]]) {
00152         if (t[curJ].lct() != t[precMap[i]].lct()) {
00153           GECODE_ME_CHECK(
00154             t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+curJ]));
00155         }
00156         curJ++;
00157       }
00158     }
00159 
00160     return ES_OK;
00161   }
00162 
00163   template<class Task>
00164   ExecStatus
00165   edgefinding(Space& home, int c, TaskArray<Task>& t) {
00166     TaskViewArray<typename TaskTraits<Task>::TaskViewFwd> f(t);
00167     GECODE_ES_CHECK(edgefinding(home,c,f));
00168     TaskViewArray<typename TaskTraits<Task>::TaskViewBwd> b(t);
00169     GECODE_ES_CHECK(edgefinding(home,c,b));
00170     return ES_OK;
00171   }
00172     
00173 }}}
00174 
00175 // STATISTICS: scheduling-prop