Generated on Wed Jan 4 17:49:13 2006 for Gecode by doxygen 1.4.6

scheduling.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Mikael Lagerkvist <lagerkvist@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Mikael Lagerkvist, 2005
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-08-05 10:53:14 +0200 (Fri, 05 Aug 2005) $ by $Author: zayenz $
00010  *     $Revision: 2143 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "minimodel.hh"
00023 
00024 #include <algorithm>
00025 
00026 namespace Gecode {
00027 
00028   using namespace Int;
00029 
00030   void
00031   producer_consumer(Space *home, 
00032                     const IntVarArgs& produce_date, const IntArgs& produce_amount,
00033                     const IntVarArgs& consume_date, const IntArgs& consume_amount,
00034                     int initial, IntConLevel cl)
00035   {
00036     if(produce_date.size() != produce_amount.size() ||
00037        consume_date.size() != consume_amount.size())
00038       throw new ArgumentSizeMismatch("Minimodel::producer_consumer");
00039 
00040     int ntasks = produce_date.size() + consume_date.size();
00041 
00042     IntArgs machine(ntasks), height(ntasks), limit(1);
00043     IntVarArgs start(ntasks), duration(ntasks), end(ntasks);
00044 
00045     int i = 0;
00046     int sum_height = initial;
00047     if(initial < Limits::Int::int_min ||
00048        initial > Limits::Int::int_max)
00049       throw new NumericalOverflow("MiniModel::producer_consumer");
00050     
00051     int maxval = 0;
00052     for (int j = produce_date.size(); j--; ) 
00053         maxval = std::max(produce_date[i].max(), maxval);
00054     for (int j = consume_date.size(); j--; ) 
00055         maxval = std::max(consume_date[j].max(), maxval);
00056     ++maxval;
00057 
00058     IntVar minvar = IntVar(home, 0, 0);
00059     IntVar maxvar = IntVar(home, maxval, maxval);
00060 
00061 
00062     // Construct producer tasks
00063     for (int k = produce_date.size(); k--; ++i) {
00064       sum_height += produce_amount[k];
00065       machine[i] = 0;
00066       
00067       start[i] = minvar;
00068       end[i] = produce_date[k];
00069       duration[i] = IntVar(home, end[i].min(), end[i].max());
00070       height[i] = produce_amount[k];
00071       if(height[i] < Limits::Int::int_min ||
00072          height[i] > Limits::Int::int_max)
00073         throw new NumericalOverflow("MiniModel::producer_consumer");
00074     }
00075 
00076     // Construct consumer tasks
00077     for (int k = consume_date.size(); k--; ++i) {
00078       machine[i] = 0;
00079       
00080       start[i] = consume_date[k];
00081       end[i] = maxvar;
00082       duration[i] = IntVar(home, maxval - start[i].max(),
00083                            maxval - start[i].min());
00084       height[i] = consume_amount[k];
00085       if(height[i] < Limits::Int::int_min ||
00086          height[i] > Limits::Int::int_max)
00087         throw new NumericalOverflow("MiniModel::producer_consumer");
00088     }
00089 
00090     limit[0] = sum_height;
00091 
00092     cumulatives(home, machine, start, duration, end, height, limit, true, cl);
00093   }
00094 
00095   /*
00096   template<class In> class ArgType;
00097   
00098   template<>
00099   class ArgType<IntArgs> {
00100   public:
00101     typedef IntArgs Result;
00102   };
00103   
00104   template<>
00105   class ArgType<IntVarArgs> {
00106   public:
00107     typedef IntView Result;
00108   };
00109   */
00110   namespace {
00111     class ConstVar {
00112       Space *home_;
00113       int val_;
00114     public:
00115       ConstVar(Space *home, int val) : home_(home), val_(val) {}
00116 
00117       operator int() { return val_; }
00118       operator IntVar() { return IntVar(home_, val_, val_); }
00119     };
00120 
00121     IntVar make_intvar(Space *home, int val)
00122     {
00123       return IntVar(home, val, val);
00124     }
00125 
00126     IntVar make_intvar(Space *home, IntVar iv)
00127     {
00128       return iv;
00129     }
00130     
00131     template<class Duration, class Height>
00132     void
00133     post_cumulative(Space *home, const IntVarArgs& start, const Duration& duration,
00134                     const Height& height, int limit, bool at_most, IntConLevel cl)
00135     {
00136       if(start.size() != duration.size() || 
00137          duration.size() !=  height.size())
00138         throw new ArgumentSizeMismatch("MiniModel::cumulative");
00139       
00140       if(limit < Limits::Int::int_min ||
00141          limit > Limits::Int::int_max)
00142         throw new NumericalOverflow("MiniModel::cumulative");
00143       
00144       int n = start.size() + !at_most;
00145       IntArgs m(n), l(1, limit);
00146       IntVarArgs s(n), d(n), e(n);
00147       Height h(n);
00148       
00149       if(!at_most) {
00150         int smin, smax, emin, emax;
00151         IntVarArgs end(n-1);
00152         for (int i = start.size(); i--; ) {
00153           m[i] = 0;
00154           s[i] = start[i];
00155           smin = std::min(s[i].min(), smin);
00156           smax = std::max(s[i].max(), smax);
00157           d[i] = make_intvar(home, duration[i]);
00158           e[i] = IntVar(home, Limits::Int::int_min, Limits::Int::int_max); 
00159           //s[i].min()+d[i].min(), s[i].max()+d[i].max());
00160           end[i] = e[i];
00161           emin = std::min(e[i].min(), emin);
00162           emax = std::max(e[i].max(), emax);
00163           h[i] = height[i];
00164         }
00165         m[n-1] = 0;
00166         s[n-1] = IntVar(home, smin, smax);
00167         d[n-1] = IntVar(home, 0, emax - smin);
00168         e[n-1] = IntVar(home, emin, emax);
00169         h[n-1] = ConstVar(home, 0);
00170         
00171         min(home, start, s[n-1]);
00172         max(home, end, e[n-1]);
00173       } else {
00174         for (int i = start.size(); i--; ) {
00175           m[i] = 0;
00176           s[i] = start[i];
00177           d[i] = make_intvar(home, duration[i]);
00178           e[i] = IntVar(home, s[i].min()+d[i].min(), s[i].max()+d[i].max());
00179           h[i] = height[i];
00180         }
00181       }
00182 
00183       cumulatives(home, m, s, d, e, h, l, at_most, cl);
00184     }
00185     
00186   }
00187 
00188   void
00189   cumulative(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
00190              const IntVarArgs& height, int limit, bool at_most, IntConLevel cl)
00191   {
00192     post_cumulative(home, start, duration, height, limit, at_most, cl);
00193   }
00194 
00195   void
00196   cumulative(Space *home, const IntVarArgs& start, const IntArgs& duration,
00197              const IntVarArgs& height, int limit, bool at_most, IntConLevel cl)
00198   {
00199     post_cumulative(home, start, duration, height, limit, at_most, cl);
00200   }
00201 
00202   void
00203   cumulative(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
00204              const IntArgs& height, int limit, bool at_most, IntConLevel cl)
00205   {
00206     post_cumulative(home, start, duration, height, limit, at_most, cl);
00207   }
00208 
00209   void
00210   cumulative(Space *home, const IntVarArgs& start, const IntArgs& duration,
00211              const IntArgs& height, int limit, bool at_most, IntConLevel cl)
00212   {
00213     post_cumulative(home, start, duration, height, limit, at_most, cl);
00214   }
00215 
00216 
00217   namespace {
00218     template <class Duration>
00219     void
00220     post_serialized(Space *home, const IntVarArgs& start, const Duration& duration,
00221                IntConLevel cl)
00222     {
00223       if(start.size() != duration.size())
00224         throw new ArgumentSizeMismatch("MiniModel::serialized");
00225       
00226       IntArgs height(start.size());
00227       for (int i = start.size(); i--; ) height[i] = 1;
00228 
00229       post_cumulative(home, start, duration, height, 1, true, cl);
00230     }
00231   }
00232 
00233   void
00234   serialized(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
00235              IntConLevel cl)
00236   {
00237     post_serialized(home, start, duration, cl);
00238   }
00239   
00240 
00241   void
00242   serialized(Space *home, const IntVarArgs& start, const IntArgs& duration,
00243              IntConLevel cl)
00244   {
00245         post_serialized(home, start, duration, cl);
00246   }
00247 
00248 }
00249   
00250 // STATISTICS: minimodel-any