solverresource.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * *
3  * Copyright (C) 2007-2012 by Johan De Taeye, frePPLe bvba *
4  * *
5  * This library is free software; you can redistribute it and/or modify it *
6  * under the terms of the GNU Affero General Public License as published *
7  * by the Free Software Foundation; either version 3 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This library is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU Affero General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU Affero General Public *
16  * License along with this program. *
17  * If not, see <http://www.gnu.org/licenses/>. *
18  * *
19  ***************************************************************************/
20 
21 #define FREPPLE_CORE
22 #include "frepple/solver.h"
23 
24 namespace frepple
25 {
26 
27 
28 /** @todo resource solver should be using a move command rather than direct move */
29 DECLARE_EXPORT void SolverMRP::solve(const Resource* res, void* v)
30 {
31  SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
32 
33  // Call the user exit
34  if (userexit_resource) userexit_resource.call(res, PythonObject(data->constrainedPlanning));
35 
36  // Message
37  if (data->getSolver()->getLogLevel()>1)
38  {
39  if (!data->constrainedPlanning || !data->getSolver()->isConstrained())
40  logger << indent(res->getLevel()) << " Resource '" << res->getName()
41  << "' is asked in unconstrained mode: "<< (-data->state->q_qty) << " "
42  << data->state->q_operationplan->getDates() << endl;
43  else
44  logger << indent(res->getLevel()) << " Resource '" << res->getName()
45  << "' is asked: "<< (-data->state->q_qty) << " "
46  << data->state->q_operationplan->getDates() << endl;
47  }
48 
49  // Unconstrained plan
50  if (!data->constrainedPlanning)
51  {
52  // Reply whatever is requested, regardless of date and quantity.
53  data->state->a_qty = data->state->q_qty;
54  data->state->a_date = data->state->q_date;
55  data->state->a_cost += data->state->a_qty * res->getCost()
57  / 3600.0;
58 
59  // Message
60  if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
61  logger << indent(res->getLevel()) << " Resource '" << res << "' answers: "
62  << (-data->state->a_qty) << " " << data->state->a_date << endl;
63  }
64 
65  // Find the setup operationplan
66  OperationPlan *setupOpplan = NULL;
67  DateRange currentSetupOpplanDates;
68  LoadPlan *setupLdplan = NULL;
69  if (res->getSetupMatrix() && !data->state->q_loadplan->getLoad()->getSetup().empty())
71  if (i->getOperation() == OperationSetup::setupoperation)
72  {
73  setupOpplan = &*i;
74  currentSetupOpplanDates = i->getDates();
75  for (OperationPlan::LoadPlanIterator j = setupOpplan->beginLoadPlans();
76  j != setupOpplan->endLoadPlans(); ++j)
77  if (j->getLoad()->getResource() == res && !j->isStart())
78  {
79  setupLdplan = &*j;
80  break;
81  }
82  if (!setupLdplan)
83  throw LogicException("Can't find loadplan on setup operationplan");
84  break;
85  }
86 
87  // Initialize some variables
88  double orig_q_qty = -data->state->q_qty;
89  OperationPlanState currentOpplan(data->state->q_operationplan);
90  Resource::loadplanlist::const_iterator cur = res->getLoadPlans().end();
91  Date curdate;
92  double curMax, prevMax;
93  bool HasOverload;
94  bool HasSetupOverload;
95  bool noRestore = data->state->forceLate;
96  bool forced_late = data->state->forceLate;
97 
98  // Initialize the default reply
99  data->state->a_date = data->state->q_date;
100  data->state->a_qty = orig_q_qty;
101  Date prevdate;
102 
103  // Loop for a valid location by using EARLIER capacity
104  if (!data->state->forceLate)
105  do
106  {
107  // Check the leadtime constraints
108  prevdate = data->state->q_operationplan->getDates().getEnd();
109  noRestore = data->state->forceLate;
110 
112  // Note that the check function can update the answered date and quantity
113  if (data->constrainedPlanning && !checkOperationLeadtime(data->state->q_operationplan,*data,false))
114  {
115  // Operationplan violates the lead time and/or fence constraint
116  noRestore = true;
117  break;
118  }
119 
120  // Check if this operation overloads the resource at its current time
121  HasOverload = false;
122  HasSetupOverload = false;
123  Date earliestdate = data->state->q_operationplan->getDates().getStart();
124  curdate = data->state->q_loadplan->getDate();
125  curMax = data->state->q_loadplan->getMax(false);
126  prevMax = curMax;
127  for (cur = res->getLoadPlans().begin(data->state->q_loadplan);
128  cur!=res->getLoadPlans().end() && cur->getDate()>=earliestdate;
129  --cur)
130  {
131  // A change in the maximum capacity
132  prevMax = curMax;
133  if (cur->getType() == 4)
134  curMax = cur->getMax(false);
135 
136  const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
137  if (ldplan && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
138  && ldplan->getOperationPlan()->getDates().overlap(data->state->q_operationplan->getDates()) > 0L
139  && ldplan->getOperationPlan() != setupOpplan)
140  {
141  // Ongoing setup
142  HasOverload = true;
143  HasSetupOverload = true;
144  break;
145  }
146 
147  // Not interested if date doesn't change
148  if (cur->getDate() == curdate) continue;
149 
150  if (cur->getOnhand() > prevMax + ROUNDING_ERROR)
151  {
152  // Overload: We are exceeding the limit!
153  // At this point:
154  // - cur points to a loadplan where we exceed the capacity
155  // - curdate points to the latest date without overload
156  // - curdate != cur->getDate()
157  HasOverload = true;
158  break;
159  }
160  curdate = cur->getDate();
161  }
162 
163  // Check if the setup operationplan overloads the resource or if a
164  // different setup is already active on the resource.
165  if (setupOpplan && !HasOverload)
166  {
167  earliestdate = setupOpplan->getDates().getStart();
168  for (cur = res->getLoadPlans().begin(setupLdplan);
169  cur!=res->getLoadPlans().end() && cur->getDate()>=earliestdate;
170  --cur)
171  {
172  // A change in the maximum capacity
173  prevMax = curMax;
174  if (cur->getType() == 4)
175  curMax = cur->getMax(false);
176 
177  // Must be same setup
178  const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
179  if (ldplan
180  && ldplan->getOperationPlan()->getDates().overlap(setupOpplan->getDates()) > 0L
181  && ldplan->getSetup() != setupLdplan->getSetup())
182  {
183  HasOverload = true;
184  HasSetupOverload = true;
185  break;
186  }
187 
188  // Not interested if date doesn't change
189  if (cur->getDate() == curdate) continue;
190  if (cur->getOnhand() > prevMax + ROUNDING_ERROR)
191  {
192  // Overload: We are exceeding the limit!
193  // At this point:
194  // - cur points to a loadplan where we exceed the capacity
195  // - curdate points to the latest date without overload
196  // - curdate != cur->getDate()
197  HasOverload = true;
198  HasSetupOverload = true;
199  break;
200  }
201  curdate = cur->getDate();
202  }
203  }
204 
205  // Try solving the overload by resizing the operationplan.
206  // The capacity isn't overloaded in the time between "curdate" and
207  // "current end of the operationplan". We can try to resize the
208  // operationplan to fit in this time period...
209  if (HasOverload && !HasSetupOverload
210  && curdate < data->state->q_loadplan->getDate())
211  {
212  Date currentEnd = data->state->q_operationplan->getDates().getEnd();
214  data->state->q_operationplan,
215  currentOpplan.quantity,
216  curdate,
217  currentEnd
218  );
219  if (data->state->q_operationplan->getQuantity() > 0
220  && data->state->q_operationplan->getDates().getEnd() <= currentEnd
221  && data->state->q_operationplan->getDates().getStart() >= curdate)
222  {
223  // The squeezing did work!
224  // The operationplan quantity is now reduced. The buffer solver will
225  // ask again for the remaining short quantity, so we don't need to
226  // bother about that here.
227  HasOverload = false;
228  }
229  else
230  {
231  // It didn't work. Restore the original operationplan.
232  // @todo this undoing is a performance bottleneck: trying to resize
233  // and restoring the original are causing lots of updates in the
234  // buffer and resource timelines...
235  // We need an api that only checks the resizing.
237  data->state->q_operationplan,
238  currentOpplan.quantity,
239  Date::infinitePast,
240  currentEnd
241  );
242  }
243  }
244 
245  // Try solving the overload by moving the operationplan to an earlier date
246  if (HasOverload)
247  {
248  // Search backward in time for a period where there is no overload
249  curMax = cur->getMax(false);
250  prevMax = curMax;
251  curdate = cur->getDate();
252  for (; cur!=res->getLoadPlans().end() && curdate > currentOpplan.end - res->getMaxEarly(); --cur)
253  {
254  // A change in the maximum capacity
255  prevMax = curMax;
256  if (cur->getType() == 4) curMax = cur->getMax(false);
257 
258  // Ongoing setup
259  const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
260  if (ldplan
262  && ldplan->isStart()
263  && ldplan->getOperationPlan()->getDates().getDuration() > 0L
264  && ldplan->getOperationPlan() != setupOpplan)
265  continue;
266 
267  // Not interested if date doesn't change
268  if (cur->getDate() == curdate) continue;
269 
270  // We are below the max limit now.
271  if (cur->getOnhand() < prevMax + ROUNDING_ERROR && curdate < prevdate)
272  break;
273  curdate = cur->getDate();
274  }
275  assert (curdate != prevdate);
276 
277  // We found a date where the load goes below the maximum
278  // At this point:
279  // - curdate is a latest date where we are above the maximum
280  // - cur is the first loadplan where we are below the max
281  if (cur != res->getLoadPlans().end() && curdate > currentOpplan.end - res->getMaxEarly())
282  {
283  // Move the operationplan
284  data->state->q_operationplan->setEnd(curdate);
285 
286  // Verify the move is successfull
287  if (data->state->q_operationplan->getDates().getEnd() > curdate)
288  // If there isn't available time in the location calendar, the move
289  // can fail.
290  data->state->a_qty = 0.0;
291  else if (data->constrainedPlanning && (isLeadtimeConstrained() || isFenceConstrained()))
292  // Check the leadtime constraints after the move
293  // Note that the check function can update the answered date
294  // and quantity
295  checkOperationLeadtime(data->state->q_operationplan,*data,false);
296  }
297  else
298  // No earlier capacity found: get out of the loop
299  data->state->a_qty = 0.0;
300  } // End of if-statement, solve by moving earlier
301  }
302  while (HasOverload && data->state->a_qty!=0.0);
303 
304  // Loop for a valid location by using LATER capacity
305  // If the answered quantity is 0, the operationplan is moved into the past.
306  // Or, the solver may be forced to produce a late reply.
307  // In these cases we need to search for capacity at later dates.
308  if (data->constrainedPlanning && (data->state->a_qty == 0.0 || data->state->forceLate))
309  {
310  // Put the operationplan back at its original end date
311  if (!noRestore)
312  data->state->q_operationplan->restore(currentOpplan);
313 
314  // Moving an operation earlier is driven by the ending loadplan,
315  // while searching for later capacity is driven from the starting loadplan.
316  LoadPlan* old_q_loadplan = data->state->q_loadplan;
317  data->state->q_loadplan = data->state->q_loadplan->getOtherLoadPlan();
318 
319  // Loop to find a later date where the operationplan will fit
320  Date newDate;
321  do
322  {
323  // Search for a date where we go below the maximum load.
324  // and verify whether there are still some overloads
325  HasOverload = false;
326  newDate = Date::infinitePast;
327  curMax = data->state->q_loadplan->getMax();
328  double curOnhand = data->state->q_loadplan->getOnhand();
329 
330  // Find how many uncommitted operationplans are loading the resource
331  // before of the loadplan.
332  // If the same resource is used multiple times in the supply path of a
333  // demand we need to use only the capacity used by other demands. Otherwise
334  // our estimate is of the feasible next date is too pessimistic.
335  // If the operation is the same, the operationplans are at the same stage
336  // in the supply path and we need to include these in our estimate of the
337  // next date.
338  double ignored = 0.0;
339  for (cur = res->getLoadPlans().begin(); cur!=res->getLoadPlans().begin(data->state->q_loadplan); ++cur)
340  {
341  const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
342  if (ldplan && !ldplan->getOperationPlan()->getIdentifier()
343  && ldplan->getOperationPlan()->getOperation()!=data->state->q_operationplan->getOperation() )
344  ignored += ldplan->getQuantity();
345  }
346 
347  for (cur=res->getLoadPlans().begin(data->state->q_loadplan);
348  !(HasOverload && newDate) && cur != res->getLoadPlans().end(); )
349  {
350  // New maximum
351  if (cur->getType() == 4)
352  curMax = cur->getMax();
353 
354  /* @todo is this required?
355  const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
356  if (ldplan && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
357  && ldplan->getOperationPlan()->getDates().getDuration() > 0L)
358  {
359  // Ongoing setup
360  HasOverload = true;
361  ++cur;
362  continue;
363  }
364  */
365  const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
366  if (ldplan && !ldplan->getOperationPlan()->getIdentifier()
368  ignored += ldplan->getQuantity();
369 
370  // Only consider the last loadplan for a certain date
371  const TimeLine<LoadPlan>::Event *loadpl = &*(cur++);
372  if (cur!=res->getLoadPlans().end() && cur->getDate()==loadpl->getDate())
373  continue;
374  curOnhand = loadpl->getOnhand();
375 
376  // Check if overloaded
377  if (loadpl->getOnhand() - ignored > curMax + ROUNDING_ERROR)
378  // There is still a capacity problem
379  HasOverload = true;
380  else if (!HasOverload && loadpl->getDate() > data->state->q_operationplan->getDates().getEnd())
381  // Break out of loop if no overload and we're beyond the
382  // operationplan end date.
383  break;
384  else if (!newDate && loadpl->getDate()!=data->state->q_loadplan->getDate() && curMax >= fabs(loadpl->getQuantity()))
385  {
386  // We are below the max limit for the first time now.
387  // This means that the previous date may be a proper start.
388  newDate = loadpl->getDate();
389  }
390  }
391 
392  // Found a date with available capacity
393  if (HasOverload && newDate)
394  {
395  // Multiple operations could be executed in parallel
396  int parallelOps = static_cast<int>((curMax - curOnhand) / data->state->q_loadplan->getQuantity());
397  if (parallelOps <= 0) parallelOps = 1;
398  // Move the operationplan to the new date
400  data->state->q_operationplan,
401  (currentOpplan.quantity ? currentOpplan.quantity : 0.001) / parallelOps, // 0.001 @todo this calculation doesn't give minimization of the lateness
402  newDate,
403  Date::infinitePast
404  );
405  HasOverload = true;
406  if (data->state->q_operationplan->getDates().getStart() < newDate)
407  // Moving to the new date turns out to be infeasible! Give it up.
408  // For instance, this can happen when the location calendar doesn't
409  // have any up-time after the specified date.
410  break;
411  }
412  }
413  while (HasOverload && newDate);
414  data->state->q_loadplan = old_q_loadplan;
415 
416  // Set the date where a next trial date can happen
417  if (HasOverload)
418  // No available capacity found anywhere in the horizon
419  data->state->a_date = Date::infiniteFuture;
420  else
421  data->state->a_date = data->state->q_operationplan->getDates().getEnd();
422 
423  // Create a zero quantity reply
424  data->state->a_qty = 0.0;
425  }
426 
427  // Force ok in unconstrained plan
428  if (!data->constrainedPlanning && data->state->a_qty == 0.0)
429  {
430  data->state->q_operationplan->restore(currentOpplan);
431  data->state->a_date = data->state->q_date;
432  data->state->a_qty = orig_q_qty;
433  }
434 
435  // Increment the cost
436  if (data->state->a_qty > 0.0)
437  {
438  // Resource usage
439  data->state->a_cost += data->state->a_qty * res->getCost()
440  * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable()) / 3600.0;
441  // Setup penalty and cost
442  if (setupOpplan)
443  {
444  data->state->a_cost += data->state->a_qty * res->getCost()
445  * (setupOpplan->getDates().getDuration() - setupOpplan->getUnavailable()) / 3600.0;
446  data->state->a_penalty += setupOpplan->getPenalty();
447  }
448  // Build-ahead penalty: 5% of the cost @todo buildahead penalty is hardcoded
449  if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
450  data->state->a_penalty +=
451  (currentOpplan.end - data->state->q_operationplan->getDates().getEnd()) * res->getCost() * 0.05 / 3600.0;
452  }
453 
454  // Maintain the constraint list
455  if (data->state->a_qty == 0.0 && data->logConstraints)
456  data->planningDemand->getConstraints().push(
458  res, currentOpplan.start, currentOpplan.end, orig_q_qty);
459 
460  // Message
461  if (data->getSolver()->getLogLevel()>1)
462  {
463  logger << indent(res->getLevel()) << " Resource '" << res << "' answers: "
464  << data->state->a_qty << " " << data->state->a_date;
465  if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
466  logger << " using earlier capacity "
467  << data->state->q_operationplan->getDates().getEnd();
468  if (data->state->a_qty>0.0 && data->state->q_operationplan->getQuantity() < currentOpplan.quantity)
469  logger << " with reduced quantity " << data->state->q_operationplan->getQuantity();
470  logger << endl;
471  }
472 
473 }
474 
475 
477 {
478  SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
479 
480  // Call the user exit
481  if (userexit_resource) userexit_resource.call(res, PythonObject(data->constrainedPlanning));
482 
483  // Message
484  if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
485  logger << indent(res->getLevel()) << " Infinite resource '" << res << "' is asked: "
486  << (-data->state->q_qty) << " " << data->state->q_operationplan->getDates() << endl;
487 
488  // @todo Need to make the setups feasible - move to earlier dates till max_early fence is reached
489 
490  // Reply whatever is requested, regardless of date and quantity.
491  data->state->a_qty = data->state->q_qty;
492  data->state->a_date = data->state->q_date;
493  data->state->a_cost += data->state->a_qty * res->getCost()
495  / 3600.0;
496 
497  // Message
498  if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
499  logger << indent(res->getLevel()) << " Infinite resource '" << res << "' answers: "
500  << (-data->state->a_qty) << " " << data->state->a_date << endl;
501 }
502 
503 
504 }