solveroperation.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * *
3  * Copyright (C) 2007-2013 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 namespace frepple
24 {
25 
26 
29 {
30  unsigned short constrainedLoads = 0;
32  h!=opplan->endLoadPlans(); ++h)
33  if (h->getResource()->getType() != *(ResourceInfinite::metadata)
34  && h->isStart() && h->getLoad()->getQuantity() != 0.0)
35  {
36  if (++constrainedLoads > 1) break;
37  }
38  DateRange orig;
39  Date minimumEndDate = opplan->getDates().getEnd();
40  bool backuplogconstraints = data.logConstraints;
41  bool backupForceLate = data.state->forceLate;
42  bool recheck, first;
43  double loadqty = 1.0;
44 
45  // Loop through all loadplans, and solve for the resource.
46  // This may move an operationplan early or late.
47  do
48  {
49  orig = opplan->getDates();
50  recheck = false;
51  first = true;
53  h!=opplan->endLoadPlans() && opplan->getDates()==orig; ++h)
54  {
55  if (h->getLoad()->getQuantity() == 0.0 || h->getQuantity() == 0.0)
56  // Empty load or loadplan (eg when load is not effective)
57  continue;
58  // Call the load solver - which will call the resource solver.
59  data.state->q_operationplan = opplan;
60  data.state->q_loadplan = &*h;
61  data.state->q_qty = h->getQuantity();
62  loadqty = h->getQuantity();
63  data.state->q_date = h->getDate();
64  h->getLoad()->solve(*this,&data);
65  if (opplan->getDates()!=orig)
66  {
67  if (data.state->a_qty==0)
68  // One of the resources is late. We want to prevent that other resources
69  // are trying to pull in the operationplan again. It can only be delayed
70  // from now on in this loop.
71  data.state->forceLate = true;
72  if (!first) recheck = true;
73  }
74  first = false;
75  }
76  data.logConstraints = false; // Only first loop collects constraint info
77  }
78  // Imagine there are multiple loads. As soon as one of them is moved, we
79  // need to redo the capacity check for the ones we already checked.
80  // Repeat until no load has touched the opplan, or till proven infeasible.
81  // No need to reloop if there is only a single load (= 2 loadplans)
82  while (constrainedLoads>1 && opplan->getDates()!=orig
83  && ((data.state->a_qty==0.0 && data.state->a_date > minimumEndDate)
84  || recheck));
85  // TODO doesn't this loop increment a_penalty incorrectly???
86 
87  // Restore original flags
88  data.logConstraints = backuplogconstraints; // restore the original value
89  data.state->forceLate = backupForceLate;
90 
91  // In case of a zero reply, we resize the operationplan to 0 right away.
92  // This is required to make sure that the buffer inventory profile also
93  // respects this answer.
94  if (data.state->a_qty==0.0 && opplan->getQuantity() > 0.0)
95  opplan->setQuantity(0.0);
96 }
97 
98 
101 {
102  // The default answer...
103  data.state->a_date = Date::infiniteFuture;
104  data.state->a_qty = data.state->q_qty;
105 
106  // Handle unavailable time.
107  // Note that this unavailable time is checked also in an unconstrained plan.
108  // This means that also an unconstrained plan can plan demand late!
109  if (opplan->getQuantity() == 0.0)
110  {
111  // It is possible that the operation could not be created properly.
112  // This happens when the operation is not available for enough time.
113  // Eg. A fixed time operation needs 10 days on jan 20 on an operation
114  // that is only available only 2 days since the start of the horizon.
115  // Resize to the minimum quantity
116  opplan->setQuantity(0.0001,false);
117  // Move to the earliest start date
118  opplan->setStart(Plan::instance().getCurrent());
119  // Pick up the earliest date we can reply back
120  data.state->a_date = opplan->getDates().getEnd();
121  data.state->a_qty = 0.0;
122  return false;
123  }
124 
125  // Check the leadtime constraints
126  if (data.constrainedPlanning && !checkOperationLeadtime(opplan,data,true))
127  // This operationplan is a wreck. It is impossible to make it meet the
128  // leadtime constraints
129  return false;
130 
131  // Set a bookmark in the command list.
132  CommandManager::Bookmark* topcommand = data.setBookmark();
133 
134  // Temporary variables
135  DateRange orig_dates = opplan->getDates();
136  bool okay = true;
137  Date a_date;
138  double a_qty;
139  Date orig_q_date = data.state->q_date;
140  Date orig_q_date_max = data.state->q_date_max;
141  double orig_opplan_qty = data.state->q_qty;
142  double q_qty_Flow;
143  Date q_date_Flow;
144  bool incomplete;
145  bool tmp_forceLate = data.state->forceLate;
146  bool isPlannedEarly;
147  DateRange matnext;
148 
149  // Loop till everything is okay. During this loop the quanity and date of the
150  // operationplan can be updated, but it cannot be split or deleted.
151  data.state->forceLate = false;
152  do
153  {
154  if (isCapacityConstrained())
155  {
156  // Verify the capacity. This can move the operationplan early or late.
157  checkOperationCapacity(opplan,data);
158  // Return false if no capacity is available
159  if (data.state->a_qty==0.0)
160  {
161  while (data.state->a_date <= orig_q_date_max)
162  {
164  (opplan, orig_opplan_qty,
165  orig_q_date_max,
166  Date::infinitePast);
167  data.state->forceLate = true;
168  checkOperationCapacity(opplan,data);
169  }
170  return false;
171  }
172  }
173 
174  // Check material
175  data.state->q_qty = opplan->getQuantity();
176  data.state->q_date = opplan->getDates().getEnd();
177  a_qty = opplan->getQuantity();
178  a_date = data.state->q_date;
179  incomplete = false;
180  matnext.setStart(Date::infinitePast);
181  matnext.setEnd(Date::infiniteFuture);
182 
183  // Loop through all flowplans // @todo need some kind of coordination run here!!! see test alternate_flow_1
185  g!=opplan->endFlowPlans(); ++g)
186  if (g->getFlow()->isConsumer())
187  {
188  // Switch back to the main alternate if this flowplan was already // @todo is this really required? If yes, in this place?
189  // planned on an alternate
190  if (g->getFlow()->getAlternate())
191  g->setFlow(g->getFlow()->getAlternate());
192 
193  // Trigger the flow solver, which will call the buffer solver
194  data.state->q_flowplan = &*g;
195  q_qty_Flow = - data.state->q_flowplan->getQuantity(); // @todo flow quantity can change when using alternate flows -> move to flow solver!
196  q_date_Flow = data.state->q_flowplan->getDate();
197  g->getFlow()->solve(*this,&data);
198 
199  // Validate the answered quantity
200  if (data.state->a_qty < q_qty_Flow)
201  {
202  // Update the opplan, which is required to (1) update the flowplans
203  // and to (2) take care of lot sizing constraints of this operation.
204  g->setQuantity(-data.state->a_qty, true);
205  a_qty = opplan->getQuantity();
206  incomplete = true;
207 
208  // Validate the answered date of the most limiting flowplan.
209  // Note that the delay variable only reflects the delay due to
210  // material constraints. If the operationplan is moved early or late
211  // for capacity constraints, this is not included.
212  if (data.state->a_date < Date::infiniteFuture)
213  {
215  opplan, 0.01, data.state->a_date, Date::infinitePast, false, false
216  );
217  if (at.end < matnext.getEnd()) matnext = DateRange(at.start, at.end);
218  //xxxif (matnext.getEnd() <= orig_q_date) logger << "STRANGE" << matnext << " " << orig_q_date << " " << at.second << " " << opplan->getQuantity() << endl;
219  }
220 
221  // Jump out of the loop if the answered quantity is 0.
222  if (a_qty <= ROUNDING_ERROR)
223  {
224  // @TODO disabled To speed up the planning the constraining flow is moved up a
225  // position in the list of flows. It'll thus be checked earlier
226  // when this operation is asked again
227  //const_cast<Operation::flowlist&>(g->getFlow()->getOperation()->getFlows()).promote(g->getFlow());
228  // There is absolutely no need to check other flowplans if the
229  // operationplan quantity is already at 0.
230  break;
231  }
232  }
233  else if (data.state->a_qty >+ q_qty_Flow + ROUNDING_ERROR)
234  // Never answer more than asked.
235  // The actual operationplan could be bigger because of lot sizing.
236  a_qty = - q_qty_Flow / g->getFlow()->getQuantity();
237  }
238 
239  isPlannedEarly = opplan->getDates().getEnd() < orig_dates.getEnd();
240 
241  if (matnext.getEnd() != Date::infiniteFuture && a_qty <= ROUNDING_ERROR
242  && matnext.getEnd() <= orig_q_date_max && matnext.getEnd() > orig_q_date)
243  {
244  // The reply is 0, but the next-date is still less than the maximum
245  // ask date. In this case we will violate the post-operation -soft-
246  // constraint.
247  data.state->q_date = matnext.getEnd();
248  orig_q_date = data.state->q_date;
249  data.state->q_qty = orig_opplan_qty;
250  data.state->a_date = Date::infiniteFuture;
251  data.state->a_qty = data.state->q_qty;
253  opplan, orig_opplan_qty, Date::infinitePast, matnext.getEnd()
254  );
255  okay = false;
256  // Pop actions from the command "stack" in the command list
257  data.rollback(topcommand);
258  // Echo a message
259  if (data.getSolver()->getLogLevel()>1)
260  logger << indent(opplan->getOperation()->getLevel())
261  << " Retrying new date." << endl;
262  }
263  else if (matnext.getEnd() != Date::infiniteFuture && a_qty <= ROUNDING_ERROR
264  && matnext.getStart() < a_date && orig_opplan_qty > opplan->getOperation()->getSizeMinimum())
265  {
266  // The reply is 0, but the next-date is not too far out.
267  // If the operationplan would fit in a smaller timeframe we can potentially
268  // create a non-zero reply...
269  // Resize the operationplan
271  opplan, orig_opplan_qty, matnext.getStart(),
272  a_date
273  );
274  if (opplan->getDates().getStart() >= matnext.getStart()
275  && opplan->getDates().getEnd() <= a_date
276  && opplan->getQuantity() > ROUNDING_ERROR)
277  {
278  // It worked
279  orig_dates = opplan->getDates();
280  data.state->q_date = orig_dates.getEnd();
281  data.state->q_qty = opplan->getQuantity();
282  data.state->a_date = Date::infiniteFuture;
283  data.state->a_qty = data.state->q_qty;
284  okay = false;
285  // Pop actions from the command stack in the command list
286  data.rollback(topcommand);
287  // Echo a message
288  if (data.getSolver()->getLogLevel()>1)
289  logger << indent(opplan->getOperation()->getLevel())
290  << " Retrying with a smaller quantity: "
291  << opplan->getQuantity() << endl;
292  }
293  else
294  {
295  // It didn't work
296  opplan->setQuantity(0);
297  okay = true;
298  }
299  }
300  else
301  okay = true;
302  }
303  while (!okay); // Repeat the loop if the operation was moved and the
304  // feasibility needs to be rechecked.
305 
306  if (a_qty <= ROUNDING_ERROR && !data.state->forceLate
307  && isPlannedEarly
308  && matnext.getStart() != Date::infiniteFuture
309  && matnext.getStart() != Date::infinitePast
310  && (data.constrainedPlanning && isCapacityConstrained()))
311  {
312  // The operationplan was moved early (because of a resource constraint)
313  // and we can't properly trust the reply date in such cases...
314  // We want to enforce rechecking the next date.
315  if (data.getSolver()->getLogLevel()>1)
316  logger << indent(opplan->getOperation()->getLevel())
317  << " Recheck capacity" << endl;
318 
319  // Move the operationplan to the next date where the material is feasible
321  (opplan, orig_opplan_qty,
322  matnext.getStart()>orig_dates.getStart() ? matnext.getStart() : orig_dates.getStart(),
323  Date::infinitePast);
324 
325  // Move the operationplan to a later date where it is feasible.
326  data.state->forceLate = true;
327  checkOperationCapacity(opplan,data);
328 
329  // Reply isn't late enough
330  if (opplan->getDates().getEnd() <= orig_q_date_max)
331  {
333  (opplan, orig_opplan_qty,
334  Date::infinitePast,
335  orig_q_date_max);
336  data.state->forceLate = true;
337  checkOperationCapacity(opplan,data);
338  }
339 
340  // Reply of this function
341  a_qty = 0.0;
342  matnext.setEnd(opplan->getDates().getEnd());
343  }
344 
345  // Compute the final reply
346  data.state->a_date = incomplete ? matnext.getEnd() : Date::infiniteFuture;
347  data.state->a_qty = a_qty;
348  data.state->forceLate = tmp_forceLate;
349  if (a_qty > ROUNDING_ERROR)
350  return true;
351  else
352  {
353  // Undo the plan
354  data.rollback(topcommand);
355  return false;
356  }
357 }
358 
359 
361 (OperationPlan* opplan, SolverMRP::SolverMRPdata& data, bool extra)
362 {
363  // No lead time constraints
364  if (!data.constrainedPlanning || (!isFenceConstrained() && !isLeadtimeConstrained()))
365  return true;
366 
367  // Compute offset from the current date: A fence problem uses the release
368  // fence window, while a leadtimeconstrained constraint has an offset of 0.
369  // If both constraints apply, we need the bigger of the two (since it is the
370  // most constraining date.
371  Date threshold = Plan::instance().getCurrent();
372  if (isFenceConstrained()
373  && !(isLeadtimeConstrained() && opplan->getOperation()->getFence()<0L))
374  threshold += opplan->getOperation()->getFence();
375 
376  // Check the setup operationplan
377  OperationPlanState original(opplan);
378  bool ok = true;
379  bool checkSetup = true;
380 
381  // If there are alternate loads we take the best case and assume that
382  // at least one of those can give us a zero-time setup.
383  // When evaluating the leadtime when solving for capacity we don't use
384  // this assumption. The resource solver takes care of the constraints.
385  if (extra && isCapacityConstrained())
386  for (Operation::loadlist::const_iterator j = opplan->getOperation()->getLoads().begin();
387  j != opplan->getOperation()->getLoads().end(); ++j)
388  if (j->hasAlternates())
389  {
390  checkSetup = false;
391  break;
392  }
393  if (checkSetup)
394  {
395  OperationPlan::iterator i(opplan);
396  if (i != opplan->end()
398  && i->getDates().getStart() < threshold)
399  {
400  // The setup operationplan is violating the lead time and/or fence
401  // constraint. We move it to start on the earliest allowed date,
402  // which automatically also moves the owner operationplan.
403  i->setStart(threshold);
404  threshold = i->getDates().getEnd();
405  ok = false;
406  }
407  }
408 
409  // Compare the operation plan start with the threshold date
410  if (ok && opplan->getDates().getStart() >= threshold)
411  // There is no problem
412  return true;
413 
414  // Compute how much we can supply in the current timeframe.
415  // In other words, we try to resize the operation quantity to fit the
416  // available timeframe: used for e.g. time-per operations
417  // Note that we allow the complete post-operation time to be eaten
418  if (extra)
419  // Leadtime check during operation resolver
421  opplan, opplan->getQuantity(),
422  threshold,
423  original.end + opplan->getOperation()->getPostTime(),
424  false
425  );
426  else
427  // Leadtime check during capacity resolver
429  opplan, opplan->getQuantity(),
430  threshold,
431  original.end,
432  true
433  );
434 
435  // Check the result of the resize
436  if (opplan->getDates().getStart() >= threshold
437  && (!extra || opplan->getDates().getEnd() <= data.state->q_date_max)
438  && opplan->getQuantity() > ROUNDING_ERROR)
439  {
440  // Resizing did work! The operation now fits within constrained limits
441  data.state->a_qty = opplan->getQuantity();
442  data.state->a_date = opplan->getDates().getEnd();
443  // Acknowledge creation of operationplan
444  return true;
445  }
446  else
447  {
448  // This operation doesn't fit at all within the constrained window.
449  data.state->a_qty = 0.0;
450  // Resize to the minimum quantity
451  if (opplan->getQuantity() + ROUNDING_ERROR < opplan->getOperation()->getSizeMinimum())
452  opplan->setQuantity(0.0001,false);
453  // Move to the earliest start date
454  opplan->setStart(threshold);
455  // Pick up the earliest date we can reply back
456  data.state->a_date = opplan->getDates().getEnd();
457  // Set the quantity to 0 (to make sure the buffer doesn't see the supply).
458  opplan->setQuantity(0.0);
459 
460  // Log the constraint
461  if (data.logConstraints)
462  data.planningDemand->getConstraints().push(
463  (threshold == Plan::instance().getCurrent()) ?
466  opplan->getOperation(), original.start, original.end,
467  original.quantity
468  );
469 
470  // Deny creation of the operationplan
471  return false;
472  }
473 }
474 
475 
476 DECLARE_EXPORT void SolverMRP::solve(const Operation* oper, void* v)
477 {
478  // Make sure we have a valid operation
479  assert(oper);
480 
481  SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
482  OperationPlan *z;
483 
484  // Call the user exit
485  if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning));
486 
487  // Find the flow for the quantity-per. This can throw an exception if no
488  // valid flow can be found.
489  Date orig_q_date = data->state->q_date;
490  double flow_qty_per = 1.0;
491  double flow_qty_fixed = 0.0;
492  bool fixed_flow = false;
493  if (data->state->curBuffer)
494  {
495  Flow* f = oper->findFlow(data->state->curBuffer, data->state->q_date);
496  if (f && f->getQuantity()>0.0)
497  {
499  {
500  fixed_flow = true;
501  flow_qty_fixed = (oper->getSizeMinimum()<=0 ? 0.001 : oper->getSizeMinimum());
502  }
503  flow_qty_per = f->getQuantity();
504  }
505  else
506  // The producing operation doesn't have a valid flow into the current
507  // buffer. Either it is missing or it is producing a negative quantity.
508  throw DataException("Invalid producing operation '" + oper->getName()
509  + "' for buffer '" + data->state->curBuffer->getName() + "'");
510  }
511 
512  // Message
513  if (data->getSolver()->getLogLevel()>1)
514  logger << indent(oper->getLevel()) << " Operation '" << oper->getName()
515  << "' is asked: " << data->state->q_qty << " " << data->state->q_date << endl;
516 
517  // Find the current list of constraints
518  Problem* topConstraint = data->planningDemand->getConstraints().top();
519 
520  // Subtract the post-operation time
521  Date prev_q_date_max = data->state->q_date_max;
522  data->state->q_date_max = data->state->q_date;
523  data->state->q_date -= oper->getPostTime();
524 
525  // Create the operation plan.
526  if (data->state->curOwnerOpplan)
527  {
528  // There is already an owner and thus also an owner command
529  assert(!data->state->curDemand);
530  z = oper->createOperationPlan(
531  fixed_flow ? flow_qty_fixed : data->state->q_qty / flow_qty_per,
532  Date::infinitePast, data->state->q_date, data->state->curDemand,
533  data->state->curOwnerOpplan, 0
534  );
535  }
536  else
537  {
538  // There is no owner operationplan yet. We need a new command.
541  oper, fixed_flow ? flow_qty_fixed : data->state->q_qty / flow_qty_per,
542  Date::infinitePast, data->state->q_date, data->state->curDemand,
543  data->state->curOwnerOpplan
544  );
545  data->state->curDemand = NULL;
546  a->getOperationPlan()->setMotive(data->state->motive);
547  z = a->getOperationPlan();
548  data->add(a);
549  }
550  assert(z);
551  double orig_q_qty = z->getQuantity();
552 
553  // Check the constraints
554  data->getSolver()->checkOperation(z,*data);
555  data->state->q_date_max = prev_q_date_max;
556 
557  // Multiply the operation reply with the flow quantity to get a final reply
558  if (data->state->curBuffer)
559  {
560  if (fixed_flow)
561  {
562  if (data->state->a_qty > 0.0)
563  data->state->a_qty = flow_qty_per;
564  }
565  else
566  data->state->a_qty *= flow_qty_per;
567  }
568 
569  // Ignore any constraints if we get a complete reply.
570  // Sometimes constraints are flagged due to a pre- or post-operation time.
571  // Such constraints ultimately don't result in lateness and can be ignored.
572  if (data->state->a_qty >= orig_q_qty - ROUNDING_ERROR)
573  data->planningDemand->getConstraints().pop(topConstraint);
574 
575  // Increment the cost
576  if (data->state->a_qty > 0.0)
577  data->state->a_cost += z->getQuantity() * oper->getCost();
578 
579  // Verify the reply
580  if (data->state->a_qty == 0 && data->state->a_date <= orig_q_date)
581  {
582  if (data->getSolver()->getLogLevel()>1)
583  logger << indent(oper->getLevel()) << " Applying lazy delay " << data->getSolver()->getLazyDelay() << endl;
584  data->state->a_date = orig_q_date + data->getSolver()->getLazyDelay();
585  }
586  assert(data->state->a_qty >= 0);
587 
588  // Message
589  if (data->getSolver()->getLogLevel()>1)
590  logger << indent(oper->getLevel()) << " Operation '" << oper->getName()
591  << "' answers: " << data->state->a_qty << " " << data->state->a_date
592  << " " << data->state->a_cost << " " << data->state->a_penalty << endl;
593 }
594 
595 
596 // No need to take post- and pre-operation times into account
598 {
599  SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
600 
601  // Call the user exit
602  if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning));
603 
604  // Message
605  if (data->getSolver()->getLogLevel()>1)
606  logger << indent(oper->getLevel()) << " Routing operation '" << oper->getName()
607  << "' is asked: " << data->state->q_qty << " " << data->state->q_date << endl;
608 
609  // Find the total quantity to flow into the buffer.
610  // Multiple suboperations can all produce into the buffer.
611  double flow_qty = 1.0;
612  double flow_qty_fixed = 0.0;
613  short fixed_flow = -1;
614  if (data->state->curBuffer)
615  {
616  flow_qty = 0.0;
617  Flow *f = oper->findFlow(data->state->curBuffer, data->state->q_date);
618  if (f)
619  {
620  // Flow on routing operation
622  {
623  fixed_flow = 1;
624  flow_qty_fixed = f->getQuantity();
625  }
626  else
627  {
628  fixed_flow = 0;
629  flow_qty += f->getQuantity();
630  }
631  }
632  for (Operation::Operationlist::const_iterator
633  e = oper->getSubOperations().begin();
634  e != oper->getSubOperations().end();
635  ++e)
636  {
637  f = (*e)->findFlow(data->state->curBuffer, data->state->q_date);
638  if (f)
639  {
640  // Flow on routing steps
642  {
643  if (fixed_flow == 0)
644  throw DataException("Can't mix fixed and proportional quantity flows on operation '" + oper->getName()
645  + "' for buffer '" + data->state->curBuffer->getName() + "'");
646  fixed_flow = 1;
647  flow_qty_fixed += f->getQuantity();
648  }
649  else
650  {
651  if (fixed_flow == 1)
652  throw DataException("Can't mix fixed and proportional quantity flows on operation '" + oper->getName()
653  + "' for buffer '" + data->state->curBuffer->getName() + "'");
654  fixed_flow = 0;
655  flow_qty += f->getQuantity();
656  }
657  }
658  }
659  if ((fixed_flow == 0 && flow_qty <= 0.0) || (fixed_flow == 1 && flow_qty_fixed <= 0.0) || (fixed_flow == -1))
660  throw DataException("Invalid producing operation '" + oper->getName()
661  + "' for buffer '" + data->state->curBuffer->getName() + "'");
662  }
663  // Because we already took care of it... @todo not correct if the suboperation is again a owning operation
664  data->state->curBuffer = NULL;
665  double a_qty;
666  if (fixed_flow == -1) fixed_flow = 0;
667  if (fixed_flow)
668  a_qty = (oper->getSizeMinimum()<=0) ? 0.001 : oper->getSizeMinimum();
669  else
670  a_qty = data->state->q_qty / flow_qty;
671 
672  // Create the top operationplan
674  oper, a_qty, Date::infinitePast,
675  data->state->q_date, data->state->curDemand, data->state->curOwnerOpplan, false
676  );
677  data->state->curDemand = NULL;
678  a->getOperationPlan()->setMotive(data->state->motive);
679 
680  // Make sure the subopplans know their owner & store the previous value
681  OperationPlan *prev_owner_opplan = data->state->curOwnerOpplan;
682  data->state->curOwnerOpplan = a->getOperationPlan();
683 
684  // Reset the max date on the state.
685  data->state->q_date_max = data->state->q_date;
686 
687  // Loop through the steps
688  Date max_Date;
689  TimePeriod delay;
690  Date top_q_date(data->state->q_date);
691  Date q_date;
692  for (Operation::Operationlist::const_reverse_iterator
693  e = oper->getSubOperations().rbegin();
694  e != oper->getSubOperations().rend() && a_qty > 0.0;
695  ++e)
696  {
697  // Plan the next step
698  data->state->q_qty = a_qty;
699  data->state->q_date = data->state->curOwnerOpplan->getDates().getStart();
700  Buffer *tmpBuf = data->state->curBuffer;
701  q_date = data->state->q_date;
702  (*e)->solve(*this,v); // @todo if the step itself has child operations, the curOwnerOpplan field is changed here!!!
703  a_qty = data->state->a_qty;
704  data->state->curBuffer = tmpBuf;
705 
706  // Update the top operationplan
707  data->state->curOwnerOpplan->setQuantity(a_qty,true);
708 
709  // Maximum for the next date
710  if (data->state->a_date != Date::infiniteFuture)
711  {
712  if (delay < data->state->a_date - q_date)
713  delay = data->state->a_date - q_date;
715  data->state->curOwnerOpplan, 0.01, //data->state->curOwnerOpplan->getQuantity(),
716  data->state->a_date, Date::infinitePast, false, false
717  );
718  if (at.end > max_Date) max_Date = at.end;
719  }
720  }
721 
722  // Check the flows and loads on the top operationplan.
723  // This can happen only after the suboperations have been dealt with
724  // because only now we know how long the operation lasts in total.
725  // Solving for the top operationplan can resize and move the steps that are
726  // in the routing!
727  /** @todo moving routing opplan doesn't recheck for feasibility of steps... */
729  if (data->state->curOwnerOpplan->getQuantity() > 0.0)
730  {
731  data->state->q_qty = a_qty;
732  data->state->q_date = data->state->curOwnerOpplan->getDates().getEnd();
733  q_date = data->state->q_date;
734  data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data);
735  a_qty = data->state->a_qty;
736  if (a_qty == 0.0 && data->state->a_date != Date::infiniteFuture)
737  {
738  // The reply date is the combination of the reply date of all steps and the
739  // reply date of the top operationplan.
740  if (data->state->a_date > q_date && delay < data->state->a_date - q_date)
741  delay = data->state->a_date - q_date;
742  if (data->state->a_date > max_Date || max_Date == Date::infiniteFuture)
743  max_Date = data->state->a_date;
744  }
745  }
746  data->state->a_date = (max_Date ? max_Date : Date::infiniteFuture);
747 
748  if (fixed_flow)
749  {
750  // Final reply of fixed quantity flow
751  if (data->state->a_qty > 0.0)
752  data->state->a_qty = flow_qty_fixed;
753  }
754  else
755  // Multiply the operationplan quantity with the flow quantity to get the
756  // final reply quantity
757  data->state->a_qty = a_qty * flow_qty;
758 
759  // Add to the list (even if zero-quantity!)
760  if (!prev_owner_opplan) data->add(a);
761 
762  // Increment the cost
763  if (data->state->a_qty > 0.0)
764  data->state->a_cost += data->state->curOwnerOpplan->getQuantity() * oper->getCost();
765 
766  // Make other operationplans don't take this one as owner any more.
767  // We restore the previous owner, which could be NULL.
768  data->state->curOwnerOpplan = prev_owner_opplan;
769 
770  if (data->state->a_qty == 0 && data->state->a_date <= top_q_date)
771  {
772  // At least one of the steps is late, but the reply date at the overall routing level is not late.
773  // This situation is possible when capacity or material constraints of routing steps create
774  // slack in the routing. The real constrained next date becomes very hard to estimate.
775  delay = data->getSolver()->getLazyDelay();
776  if (data->getSolver()->getLogLevel()>1)
777  logger << indent(oper->getLevel()) << " Applying lazy delay " << delay << " in routing" << endl;
778  data->state->a_date = top_q_date + delay;
779  }
780 
781  // Check reply date is later than requested date
782  assert(data->state->a_date >= top_q_date);
783  assert(data->state->a_qty >= 0);
784 
785  // Message
786  if (data->getSolver()->getLogLevel()>1)
787  logger << indent(oper->getLevel()) << " Routing operation '" << oper->getName()
788  << "' answers: " << data->state->a_qty << " " << data->state->a_date << " "
789  << data->state->a_cost << " " << data->state->a_penalty << endl;
790 }
791 
792 
793 // No need to take post- and pre-operation times into account
794 // @todo This method should only be allowed to create 1 operationplan
796 {
797  SolverMRPdata *data = static_cast<SolverMRPdata*>(v);
798  Date origQDate = data->state->q_date;
799  double origQqty = data->state->q_qty;
800  Buffer *buf = data->state->curBuffer;
801  Demand *d = data->state->curDemand;
802 
803  // Call the user exit
804  if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning));
805 
806  unsigned int loglevel = data->getSolver()->getLogLevel();
807  SearchMode search = oper->getSearch();
808 
809  // Message
810  if (loglevel>1)
811  logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName()
812  << "' is asked: " << data->state->q_qty << " " << data->state->q_date << endl;
813 
814  // Make sure sub-operationplans know their owner & store the previous value
815  OperationPlan *prev_owner_opplan = data->state->curOwnerOpplan;
816 
817  // Find the flow into the requesting buffer for the quantity-per
818  double top_flow_qty_per = 0.0;
819  bool top_flow_exists = false;
820  bool fixed_flow = false;
821  if (buf)
822  {
823  Flow* f = oper->findFlow(buf, data->state->q_date);
824  if (f && f->getQuantity() > 0.0)
825  {
827  fixed_flow = true;
828  top_flow_qty_per = f->getQuantity();
829  top_flow_exists = true;
830  }
831  }
832 
833  // Control the planning mode
834  bool originalPlanningMode = data->constrainedPlanning;
835  data->constrainedPlanning = true;
836 
837  // Remember the top constraint
838  bool originalLogConstraints = data->logConstraints;
839  Problem* topConstraint = data->planningDemand->getConstraints().top();
840 
841  // Try all alternates:
842  // - First, all alternates that are fully effective in the order of priority.
843  // - Next, the alternates beyond their effective end date.
844  // We loop through these since they can help in meeting a demand on time,
845  // but using them will also create extra inventory or delays.
846  double a_qty = data->state->q_qty;
847  bool effectiveOnly = true;
848  Date a_date = Date::infiniteFuture;
849  Date ask_date;
850  Operation *firstAlternate = NULL;
851  double firstFlowPer;
852  while (a_qty > 0)
853  {
854  // Evaluate all alternates
855  bool plannedAlternate = false;
856  double bestAlternateValue = DBL_MAX;
857  double bestAlternateQuantity = 0;
858  Operation* bestAlternateSelection = NULL;
859  double bestFlowPer;
860  Date bestQDate;
861  for (Operation::Operationlist::const_iterator altIter
862  = oper->getSubOperations().begin();
863  altIter != oper->getSubOperations().end(); )
864  {
865  // Set a bookmark in the command list.
866  CommandManager::Bookmark* topcommand = data->setBookmark();
867  bool nextalternate = true;
868 
869  // Operations with 0 priority are considered unavailable
871  = oper->getProperties(*altIter);
872 
873  // Filter out alternates that are not suitable
874  if (props.first == 0.0
875  || (effectiveOnly && !props.second.within(data->state->q_date))
876  || (!effectiveOnly && props.second.getEnd() > data->state->q_date)
877  )
878  {
879  ++altIter;
880  if (altIter == oper->getSubOperations().end() && effectiveOnly)
881  {
882  // Prepare for a second iteration over all alternates
883  effectiveOnly = false;
884  altIter = oper->getSubOperations().begin();
885  }
886  continue;
887  }
888 
889  // Establish the ask date
890  ask_date = effectiveOnly ? origQDate : props.second.getEnd();
891 
892  // Find the flow into the requesting buffer. It may or may not exist, since
893  // the flow could already exist on the top operationplan
894  double sub_flow_qty_per = 0.0;
895  if (buf)
896  {
897  Flow* f = (*altIter)->findFlow(buf, ask_date);
898  if (f && f->getQuantity() > 0.0)
899  sub_flow_qty_per = f->getQuantity();
900  else if (!top_flow_exists)
901  {
902  // Neither the top nor the sub operation have a flow in the buffer,
903  // we're in trouble...
904  // Restore the planning mode
905  data->constrainedPlanning = originalPlanningMode;
906  throw DataException("Invalid producing operation '" + oper->getName()
907  + "' for buffer '" + buf->getName() + "'");
908  }
909  else if (f && top_flow_exists)
910  {
911  if ((fixed_flow && f->getType() != *FlowFixedEnd::metadata && f->getType() != *FlowFixedStart::metadata)
912  || (!fixed_flow && (f->getType() == *FlowFixedEnd::metadata || f->getType() == *FlowFixedStart::metadata)))
913  throw DataException("Can't mix fixed and proportional quantity flows on operation '" + oper->getName()
914  + "' for buffer '" + data->state->curBuffer->getName() + "'");
915  }
916  else if (f && (f->getType() == *FlowFixedEnd::metadata || f->getType() == *FlowFixedStart::metadata))
917  fixed_flow = true;
918  }
919  else
920  // Default value is 1.0, if no matching flow is required
921  sub_flow_qty_per = 1.0;
922 
923  // Remember the first alternate
924  if (!firstAlternate)
925  {
926  firstAlternate = *altIter;
927  firstFlowPer = sub_flow_qty_per + top_flow_qty_per;
928  }
929 
930  // Constraint tracking
931  if (*altIter != firstAlternate)
932  // Only enabled on first alternate
933  data->logConstraints = false;
934  else
935  {
936  // Forget previous constraints if we are replanning the first alternate
937  // multiple times
938  data->planningDemand->getConstraints().pop(topConstraint);
939  // Potentially keep track of constraints
940  data->logConstraints = originalLogConstraints;
941  }
942 
943  // Create the top operationplan.
944  // Note that both the top- and the sub-operation can have a flow in the
945  // requested buffer
947  oper, a_qty, Date::infinitePast, ask_date,
948  d, prev_owner_opplan, false
949  );
950  a->getOperationPlan()->setMotive(data->state->motive);
951  if (!prev_owner_opplan) data->add(a);
952 
953  // Create a sub operationplan
954  data->state->q_date = ask_date;
955  data->state->curDemand = NULL;
956  data->state->curOwnerOpplan = a->getOperationPlan();
957  data->state->curBuffer = NULL; // Because we already took care of it... @todo not correct if the suboperation is again a owning operation
958  if (fixed_flow)
959  data->state->q_qty = (oper->getSizeMinimum()<=0) ? 0.001 : oper->getSizeMinimum();
960  else
961  data->state->q_qty = a_qty / (sub_flow_qty_per + top_flow_qty_per);
962 
963  // Solve constraints on the sub operationplan
964  double beforeCost = data->state->a_cost;
965  double beforePenalty = data->state->a_penalty;
966  if (search == PRIORITY)
967  {
968  // Message
969  if (loglevel)
970  logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName()
971  << "' tries alternate '" << *altIter << "' " << endl;
972  (*altIter)->solve(*this,v);
973  }
974  else
975  {
976  data->getSolver()->setLogLevel(0);
977  try {(*altIter)->solve(*this,v);}
978  catch (...)
979  {
980  data->getSolver()->setLogLevel(loglevel);
981  // Restore the planning mode
982  data->constrainedPlanning = originalPlanningMode;
983  data->logConstraints = originalLogConstraints;
984  throw;
985  }
986  data->getSolver()->setLogLevel(loglevel);
987  }
988  double deltaCost = data->state->a_cost - beforeCost;
989  double deltaPenalty = data->state->a_penalty - beforePenalty;
990  data->state->a_cost = beforeCost;
991  data->state->a_penalty = beforePenalty;
992 
993  // Keep the lowest of all next-date answers on the effective alternates
994  if (effectiveOnly && data->state->a_date < a_date && data->state->a_date > ask_date)
995  a_date = data->state->a_date;
996 
997  // Now solve for loads and flows of the top operationplan.
998  // Only now we know how long that top-operation lasts in total.
999  if (data->state->a_qty > ROUNDING_ERROR)
1000  {
1001  // Multiply the operation reply with the flow quantity to obtain the
1002  // reply to return
1003  data->state->q_qty = data->state->a_qty;
1004  data->state->q_date = origQDate;
1006  data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data);
1007  if (fixed_flow)
1008  data->state->a_qty = (sub_flow_qty_per + top_flow_qty_per);
1009  else
1010  data->state->a_qty *= (sub_flow_qty_per + top_flow_qty_per);
1011 
1012  // Combine the reply date of the top-opplan with the alternate check: we
1013  // need to return the minimum next-date.
1014  if (data->state->a_date < a_date && data->state->a_date > ask_date)
1015  a_date = data->state->a_date;
1016  }
1017 
1018  // Message
1019  if (loglevel && search != PRIORITY)
1020  logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName()
1021  << "' evaluates alternate '" << *altIter << "': quantity " << data->state->a_qty
1022  << ", cost " << deltaCost << ", penalty " << deltaPenalty << endl;
1023 
1024  // Process the result
1025  if (search == PRIORITY)
1026  {
1027  // Undo the operationplans of this alternate
1028  if (data->state->a_qty < ROUNDING_ERROR) data->rollback(topcommand);
1029 
1030  // Prepare for the next loop
1031  a_qty -= data->state->a_qty;
1032  plannedAlternate = true;
1033 
1034  // As long as we get a positive reply we replan on this alternate
1035  if (data->state->a_qty > 0) nextalternate = false;
1036 
1037  // Are we at the end already?
1038  if (a_qty < ROUNDING_ERROR)
1039  {
1040  a_qty = 0.0;
1041  break;
1042  }
1043  }
1044  else
1045  {
1046  double val = 0.0;
1047  switch (search)
1048  {
1049  case MINCOST:
1050  val = deltaCost / data->state->a_qty;
1051  break;
1052  case MINPENALTY:
1053  val = deltaPenalty / data->state->a_qty;
1054  break;
1055  case MINCOSTPENALTY:
1056  val = (deltaCost + deltaPenalty) / data->state->a_qty;
1057  break;
1058  default:
1059  LogicException("Unsupported search mode for alternate operation '"
1060  + oper->getName() + "'");
1061  }
1062  if (data->state->a_qty > ROUNDING_ERROR && (
1063  val + ROUNDING_ERROR < bestAlternateValue
1064  || (fabs(val - bestAlternateValue) < ROUNDING_ERROR
1065  && data->state->a_qty > bestAlternateQuantity)
1066  ))
1067  {
1068  // Found a better alternate
1069  bestAlternateValue = val;
1070  bestAlternateSelection = *altIter;
1071  bestAlternateQuantity = data->state->a_qty;
1072  bestFlowPer = sub_flow_qty_per + top_flow_qty_per;
1073  bestQDate = ask_date;
1074  }
1075  // This was only an evaluation
1076  data->rollback(topcommand);
1077  }
1078 
1079  // Select the next alternate
1080  if (nextalternate)
1081  {
1082  ++altIter;
1083  if (altIter == oper->getSubOperations().end() && effectiveOnly)
1084  {
1085  // Prepare for a second iteration over all alternates
1086  effectiveOnly = false;
1087  altIter = oper->getSubOperations().begin();
1088  }
1089  }
1090  } // End loop over all alternates
1091 
1092  // Replan on the best alternate
1093  if (bestAlternateQuantity > ROUNDING_ERROR && search != PRIORITY)
1094  {
1095  // Message
1096  if (loglevel>1)
1097  logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName()
1098  << "' chooses alternate '" << bestAlternateSelection << "' " << search << endl;
1099 
1100  // Create the top operationplan.
1101  // Note that both the top- and the sub-operation can have a flow in the
1102  // requested buffer
1104  oper, a_qty, Date::infinitePast, bestQDate,
1105  d, prev_owner_opplan, false
1106  );
1107  a->getOperationPlan()->setMotive(data->state->motive);
1108  if (!prev_owner_opplan) data->add(a);
1109 
1110  // Recreate the ask
1111  if (fixed_flow)
1112  data->state->q_qty = (oper->getSizeMinimum()<=0) ? 0.001 : oper->getSizeMinimum();
1113  else
1114  data->state->q_qty = a_qty / bestFlowPer;
1115  data->state->q_date = bestQDate;
1116  data->state->curDemand = NULL;
1117  data->state->curOwnerOpplan = a->getOperationPlan();
1118  data->state->curBuffer = NULL; // Because we already took care of it... @todo not correct if the suboperation is again a owning operation
1119 
1120  // Create a sub operationplan and solve constraints
1121  bestAlternateSelection->solve(*this,v);
1122 
1123  // Now solve for loads and flows of the top operationplan.
1124  // Only now we know how long that top-operation lasts in total.
1125  data->state->q_qty = data->state->a_qty;
1126  data->state->q_date = origQDate;
1128  data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data);
1129 
1130  // Multiply the operation reply with the flow quantity to obtain the
1131  // reply to return
1132  if (fixed_flow)
1133  data->state->q_qty = bestFlowPer;
1134  else
1135  data->state->a_qty *= bestFlowPer;
1136 
1137  // Combine the reply date of the top-opplan with the alternate check: we
1138  // need to return the minimum next-date.
1139  if (data->state->a_date < a_date && data->state->a_date > ask_date)
1140  a_date = data->state->a_date;
1141 
1142  // Prepare for the next loop
1143  a_qty -= data->state->a_qty;
1144 
1145  // Are we at the end already?
1146  if (a_qty < ROUNDING_ERROR)
1147  {
1148  a_qty = 0.0;
1149  break;
1150  }
1151  }
1152  else
1153  // No alternate can plan anything any more
1154  break;
1155 
1156  } // End while loop until the a_qty > 0
1157 
1158  // Forget any constraints if we are not short or are planning unconstrained
1159  if (a_qty < ROUNDING_ERROR || !originalLogConstraints)
1160  data->planningDemand->getConstraints().pop(topConstraint);
1161 
1162  // Unconstrained plan: If some unplanned quantity remains, switch to
1163  // unconstrained planning on the first alternate.
1164  // If something could be planned, we expect the caller to re-ask this
1165  // operation.
1166  if (!originalPlanningMode && fabs(origQqty - a_qty) < ROUNDING_ERROR && firstAlternate)
1167  {
1168  // Switch to unconstrained planning
1169  data->constrainedPlanning = false;
1170  data->logConstraints = false;
1171 
1172  // Message
1173  if (loglevel)
1174  logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName()
1175  << "' plans unconstrained on alternate '" << firstAlternate << "' " << search << endl;
1176 
1177  // Create the top operationplan.
1178  // Note that both the top- and the sub-operation can have a flow in the
1179  // requested buffer
1181  oper, a_qty, Date::infinitePast, origQDate,
1182  d, prev_owner_opplan, false
1183  );
1184  a->getOperationPlan()->setMotive(data->state->motive);
1185  if (!prev_owner_opplan) data->add(a);
1186 
1187  // Recreate the ask
1188  data->state->q_qty = a_qty / firstFlowPer;
1189  data->state->q_date = origQDate;
1190  data->state->curDemand = NULL;
1191  data->state->curOwnerOpplan = a->getOperationPlan();
1192  data->state->curBuffer = NULL; // Because we already took care of it... @todo not correct if the suboperation is again a owning operation
1193 
1194  // Create a sub operationplan and solve constraints
1195  firstAlternate->solve(*this,v);
1196 
1197  // Expand flows of the top operationplan.
1198  data->state->q_qty = data->state->a_qty;
1199  data->state->q_date = origQDate;
1201  data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data);
1202 
1203  // Fully planned
1204  a_qty = 0.0;
1205  data->state->a_date = origQDate;
1206  }
1207 
1208  // Set up the reply
1209  data->state->a_qty = origQqty - a_qty; // a_qty is the unplanned quantity
1210  data->state->a_date = a_date;
1211  if (data->state->a_qty == 0 && data->state->a_date <= origQDate)
1212  {
1213  if (data->getSolver()->getLogLevel()>1)
1214  logger << indent(oper->getLevel()) << " Applying lazy delay " <<
1215  data->getSolver()->getLazyDelay() << " in alternate" << endl;
1216  data->state->a_date = origQDate + data->getSolver()->getLazyDelay();
1217  }
1218  assert(data->state->a_qty >= 0);
1219 
1220  // Restore the planning mode
1221  data->constrainedPlanning = originalPlanningMode;
1222  data->logConstraints = originalLogConstraints;
1223 
1224  // Increment the cost
1225  if (data->state->a_qty > 0.0)
1226  data->state->a_cost += data->state->curOwnerOpplan->getQuantity() * oper->getCost();
1227 
1228  // Make sure other operationplans don't take this one as owner any more.
1229  // We restore the previous owner, which could be NULL.
1230  data->state->curOwnerOpplan = prev_owner_opplan;
1231 
1232  // Message
1233  if (loglevel>1)
1234  logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName()
1235  << "' answers: " << data->state->a_qty << " " << data->state->a_date
1236  << " " << data->state->a_cost << " " << data->state->a_penalty << endl;
1237 }
1238 
1239 
1240 }