← Back to branch summary

~ubuntu-branches/ubuntu/natty/gecode/natty

« back to all changes in this revision

Viewing changes to minimodel/scheduling.cc

  • Committer: Bazaar Package Importer
  • Author(s): Kari Pahula
  • Date: 2005-12-24 07:51:25 UTC
  • Revision ID: james.westby@ubuntu.com-20051224075125-klkiqofvbfvusfvt
Tags: upstream-1.0.0.dfsg.1
Import upstream version 1.0.0.dfsg.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
minimodel/scheduling.cc
 
1
/*
 
2
 *  Main authors:
 
3
 *     Mikael Lagerkvist <lagerkvist@gecode.org>
 
4
 *
 
5
 *  Copyright:
 
6
 *     Mikael Lagerkvist, 2005
 
7
 *
 
8
 *  Last modified:
 
9
 *     $Date: 2005-08-05 10:53:14 +0200 (Fri, 05 Aug 2005) $ by $Author: zayenz $
 
10
 *     $Revision: 2143 $
 
11
 *
 
12
 *  This file is part of Gecode, the generic constraint
 
13
 *  development environment:
 
14
 *     http://www.gecode.org
 
15
 *
 
16
 *  See the file "LICENSE" for information on usage and
 
17
 *  redistribution of this file, and for a
 
18
 *     DISCLAIMER OF ALL WARRANTIES.
 
19
 *
 
20
 */
 
21
 
 
22
#include "minimodel.hh"
 
23
 
 
24
#include <algorithm>
 
25
 
 
26
namespace Gecode {
 
27
 
 
28
  using namespace Int;
 
29
 
 
30
  void
 
31
  producer_consumer(Space *home, 
 
32
                    const IntVarArgs& produce_date, const IntArgs& produce_amount,
 
33
                    const IntVarArgs& consume_date, const IntArgs& consume_amount,
 
34
                    int initial, IntConLevel cl)
 
35
  {
 
36
    if(produce_date.size() != produce_amount.size() ||
 
37
       consume_date.size() != consume_amount.size())
 
38
      throw new ArgumentSizeMismatch("Minimodel::producer_consumer");
 
39
 
 
40
    int ntasks = produce_date.size() + consume_date.size();
 
41
 
 
42
    IntArgs machine(ntasks), height(ntasks), limit(1);
 
43
    IntVarArgs start(ntasks), duration(ntasks), end(ntasks);
 
44
 
 
45
    int i = 0;
 
46
    int sum_height = initial;
 
47
    if(initial < Limits::Int::int_min ||
 
48
       initial > Limits::Int::int_max)
 
49
      throw new NumericalOverflow("MiniModel::producer_consumer");
 
50
    
 
51
    int maxval = 0;
 
52
    for (int j = produce_date.size(); j--; ) 
 
53
        maxval = std::max(produce_date[i].max(), maxval);
 
54
    for (int j = consume_date.size(); j--; ) 
 
55
        maxval = std::max(consume_date[j].max(), maxval);
 
56
    ++maxval;
 
57
 
 
58
    IntVar minvar = IntVar(home, 0, 0);
 
59
    IntVar maxvar = IntVar(home, maxval, maxval);
 
60
 
 
61
 
 
62
    // Construct producer tasks
 
63
    for (int k = produce_date.size(); k--; ++i) {
 
64
      sum_height += produce_amount[k];
 
65
      machine[i] = 0;
 
66
      
 
67
      start[i] = minvar;
 
68
      end[i] = produce_date[k];
 
69
      duration[i] = IntVar(home, end[i].min(), end[i].max());
 
70
      height[i] = produce_amount[k];
 
71
      if(height[i] < Limits::Int::int_min ||
 
72
         height[i] > Limits::Int::int_max)
 
73
        throw new NumericalOverflow("MiniModel::producer_consumer");
 
74
    }
 
75
 
 
76
    // Construct consumer tasks
 
77
    for (int k = consume_date.size(); k--; ++i) {
 
78
      machine[i] = 0;
 
79
      
 
80
      start[i] = consume_date[k];
 
81
      end[i] = maxvar;
 
82
      duration[i] = IntVar(home, maxval - start[i].max(),
 
83
                           maxval - start[i].min());
 
84
      height[i] = consume_amount[k];
 
85
      if(height[i] < Limits::Int::int_min ||
 
86
         height[i] > Limits::Int::int_max)
 
87
        throw new NumericalOverflow("MiniModel::producer_consumer");
 
88
    }
 
89
 
 
90
    limit[0] = sum_height;
 
91
 
 
92
    cumulatives(home, machine, start, duration, end, height, limit, true, cl);
 
93
  }
 
94
 
 
95
  /*
 
96
  template<class In> class ArgType;
 
97
  
 
98
  template<>
 
99
  class ArgType<IntArgs> {
 
100
  public:
 
101
    typedef IntArgs Result;
 
102
  };
 
103
  
 
104
  template<>
 
105
  class ArgType<IntVarArgs> {
 
106
  public:
 
107
    typedef IntView Result;
 
108
  };
 
109
  */
 
110
  namespace {
 
111
    class ConstVar {
 
112
      Space *home_;
 
113
      int val_;
 
114
    public:
 
115
      ConstVar(Space *home, int val) : home_(home), val_(val) {}
 
116
 
 
117
      operator int() { return val_; }
 
118
      operator IntVar() { return IntVar(home_, val_, val_); }
 
119
    };
 
120
 
 
121
    IntVar make_intvar(Space *home, int val)
 
122
    {
 
123
      return IntVar(home, val, val);
 
124
    }
 
125
 
 
126
    IntVar make_intvar(Space *home, IntVar iv)
 
127
    {
 
128
      return iv;
 
129
    }
 
130
    
 
131
    template<class Duration, class Height>
 
132
    void
 
133
    post_cumulative(Space *home, const IntVarArgs& start, const Duration& duration,
 
134
                    const Height& height, int limit, bool at_most, IntConLevel cl)
 
135
    {
 
136
      if(start.size() != duration.size() || 
 
137
         duration.size() !=  height.size())
 
138
        throw new ArgumentSizeMismatch("MiniModel::cumulative");
 
139
      
 
140
      if(limit < Limits::Int::int_min ||
 
141
         limit > Limits::Int::int_max)
 
142
        throw new NumericalOverflow("MiniModel::cumulative");
 
143
      
 
144
      int n = start.size() + !at_most;
 
145
      IntArgs m(n), l(1, limit);
 
146
      IntVarArgs s(n), d(n), e(n);
 
147
      Height h(n);
 
148
      
 
149
      if(!at_most) {
 
150
        int smin, smax, emin, emax;
 
151
        IntVarArgs end(n-1);
 
152
        for (int i = start.size(); i--; ) {
 
153
          m[i] = 0;
 
154
          s[i] = start[i];
 
155
          smin = std::min(s[i].min(), smin);
 
156
          smax = std::max(s[i].max(), smax);
 
157
          d[i] = make_intvar(home, duration[i]);
 
158
          e[i] = IntVar(home, Limits::Int::int_min, Limits::Int::int_max); 
 
159
          //s[i].min()+d[i].min(), s[i].max()+d[i].max());
 
160
          end[i] = e[i];
 
161
          emin = std::min(e[i].min(), emin);
 
162
          emax = std::max(e[i].max(), emax);
 
163
          h[i] = height[i];
 
164
        }
 
165
        m[n-1] = 0;
 
166
        s[n-1] = IntVar(home, smin, smax);
 
167
        d[n-1] = IntVar(home, 0, emax - smin);
 
168
        e[n-1] = IntVar(home, emin, emax);
 
169
        h[n-1] = ConstVar(home, 0);
 
170
        
 
171
        min(home, start, s[n-1]);
 
172
        max(home, end, e[n-1]);
 
173
      } else {
 
174
        for (int i = start.size(); i--; ) {
 
175
          m[i] = 0;
 
176
          s[i] = start[i];
 
177
          d[i] = make_intvar(home, duration[i]);
 
178
          e[i] = IntVar(home, s[i].min()+d[i].min(), s[i].max()+d[i].max());
 
179
          h[i] = height[i];
 
180
        }
 
181
      }
 
182
 
 
183
      cumulatives(home, m, s, d, e, h, l, at_most, cl);
 
184
    }
 
185
    
 
186
  }
 
187
 
 
188
  void
 
189
  cumulative(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
 
190
             const IntVarArgs& height, int limit, bool at_most, IntConLevel cl)
 
191
  {
 
192
    post_cumulative(home, start, duration, height, limit, at_most, cl);
 
193
  }
 
194
 
 
195
  void
 
196
  cumulative(Space *home, const IntVarArgs& start, const IntArgs& duration,
 
197
             const IntVarArgs& height, int limit, bool at_most, IntConLevel cl)
 
198
  {
 
199
    post_cumulative(home, start, duration, height, limit, at_most, cl);
 
200
  }
 
201
 
 
202
  void
 
203
  cumulative(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
 
204
             const IntArgs& height, int limit, bool at_most, IntConLevel cl)
 
205
  {
 
206
    post_cumulative(home, start, duration, height, limit, at_most, cl);
 
207
  }
 
208
 
 
209
  void
 
210
  cumulative(Space *home, const IntVarArgs& start, const IntArgs& duration,
 
211
             const IntArgs& height, int limit, bool at_most, IntConLevel cl)
 
212
  {
 
213
    post_cumulative(home, start, duration, height, limit, at_most, cl);
 
214
  }
 
215
 
 
216
 
 
217
  namespace {
 
218
    template <class Duration>
 
219
    void
 
220
    post_serialized(Space *home, const IntVarArgs& start, const Duration& duration,
 
221
               IntConLevel cl)
 
222
    {
 
223
      if(start.size() != duration.size())
 
224
        throw new ArgumentSizeMismatch("MiniModel::serialized");
 
225
      
 
226
      IntArgs height(start.size());
 
227
      for (int i = start.size(); i--; ) height[i] = 1;
 
228
 
 
229
      post_cumulative(home, start, duration, height, 1, true, cl);
 
230
    }
 
231
  }
 
232
 
 
233
  void
 
234
  serialized(Space *home, const IntVarArgs& start, const IntVarArgs& duration,
 
235
             IntConLevel cl)
 
236
  {
 
237
    post_serialized(home, start, duration, cl);
 
238
  }
 
239
  
 
240
 
 
241
  void
 
242
  serialized(Space *home, const IntVarArgs& start, const IntArgs& duration,
 
243
             IntConLevel cl)
 
244
  {
 
245
        post_serialized(home, start, duration, cl);
 
246
  }
 
247
 
 
248
}
 
249
  
 
250
// STATISTICS: minimodel-any