solveroperation.cpp

Go to the documentation of this file.
00001 /***************************************************************************
00002   file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/tags/0.8.0/src/solver/solveroperation.cpp $
00003   version : $LastChangedRevision: 1201 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2010-03-08 19:00:55 +0100 (Mon, 08 Mar 2010) $
00005  ***************************************************************************/
00006 
00007 /***************************************************************************
00008  *                                                                         *
00009  * Copyright (C) 2007 by Johan De Taeye                                    *
00010  *                                                                         *
00011  * This library is free software; you can redistribute it and/or modify it *
00012  * under the terms of the GNU Lesser General Public License as published   *
00013  * by the Free Software Foundation; either version 2.1 of the License, or  *
00014  * (at your option) any later version.                                     *
00015  *                                                                         *
00016  * This library is distributed in the hope that it will be useful,         *
00017  * but WITHOUT ANY WARRANTY; without even the implied warranty of          *
00018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser *
00019  * General Public License for more details.                                *
00020  *                                                                         *
00021  * You should have received a copy of the GNU Lesser General Public        *
00022  * License along with this library; if not, write to the Free Software     *
00023  * Foundation Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 *
00024  * USA                                                                     *
00025  *                                                                         *
00026  ***************************************************************************/
00027 
00028 #define FREPPLE_CORE
00029 #include "frepple/solver.h"
00030 namespace frepple
00031 {
00032 
00033 
00034 DECLARE_EXPORT void SolverMRP::checkOperationCapacity
00035   (OperationPlan* opplan, SolverMRP::SolverMRPdata& data)
00036 {
00037   unsigned short constrainedLoads = 0;
00038   for (OperationPlan::LoadPlanIterator h=opplan->beginLoadPlans();
00039     h!=opplan->endLoadPlans(); ++h)
00040     if (h->getResource()->getType() != *(ResourceInfinite::metadata)
00041       && h->isStart() && h->getLoad()->getQuantity() != 0.0)
00042     {
00043       if (++constrainedLoads > 1) break;
00044     }
00045   DateRange orig;
00046 
00047   // Loop through all loadplans, and solve for the resource.
00048   // This may move an operationplan early or late.
00049   do
00050   {
00051     orig = opplan->getDates();
00052     for (OperationPlan::LoadPlanIterator h=opplan->beginLoadPlans();
00053       h!=opplan->endLoadPlans() && opplan->getDates()==orig; ++h)
00054     {
00055       data.state->q_operationplan = opplan;
00056       data.state->q_loadplan = &*h;
00057       data.state->q_qty = h->getQuantity();
00058       data.state->q_date = h->getDate();
00059       // Call the load solver - which will call the resource solver.
00060       if (h->getLoad()->getQuantity() != 0.0)
00061         h->getLoad()->solve(*this,&data);
00062     }
00063   }
00064   // Imagine there are multiple loads. As soon as one of them is moved, we
00065   // need to redo the capacity check for the ones we already checked.
00066   // Repeat until no load has touched the opplan, or till proven infeasible.
00067   // No need to reloop if there is only a single load (= 2 loadplans)
00068   while (constrainedLoads>1 && opplan->getDates()!=orig && (data.state->a_qty!=0.0 || data.state->forceLate));
00069 }
00070 
00071 
00072 DECLARE_EXPORT bool SolverMRP::checkOperation
00073 (OperationPlan* opplan, SolverMRP::SolverMRPdata& data)
00074 {
00075   // The default answer...
00076   data.state->a_date = Date::infiniteFuture;
00077   data.state->a_qty = data.state->q_qty;
00078 
00079   // Handle unavailable time.
00080   // Note that this unavailable time is checked also in an unconstrained plan.
00081   // This means that also an unconstrained plan can plan demand late!
00082   if (opplan->getQuantity() == 0.0)
00083   {
00084     // It is possible that the operation could not be created properly.
00085     // This happens when the operation is not available for enough time.
00086     // Eg. A fixed time operation needs 10 days on jan 20 on an operation
00087     //     that is only available only 2 days since the start of the horizon.
00088     // Resize to the minimum quantity
00089     opplan->setQuantity(0.0001,false);
00090     // Move to the earliest start date
00091     opplan->setStart(Plan::instance().getCurrent());
00092     // Pick up the earliest date we can reply back
00093     data.state->a_date = opplan->getDates().getEnd();
00094     data.state->a_qty = 0.0;
00095     return false;
00096   }
00097 
00098   // Check the leadtime constraints
00099   if (data.constrainedPlanning && !checkOperationLeadtime(opplan,data,true))
00100     // This operationplan is a wreck. It is impossible to make it meet the
00101     // leadtime constraints
00102     return false;
00103 
00104   // Store the last command in the list, in order to undo the following
00105   // commands if required.
00106   Command* topcommand = data.getLastCommand();
00107 
00108   // Temporary variables
00109   DateRange orig_dates = opplan->getDates();
00110   bool okay = true;
00111   Date a_date;
00112   double a_qty;
00113   Date orig_q_date = data.state->q_date;
00114   double orig_opplan_qty = data.state->q_qty;
00115   double q_qty_Flow;
00116   Date q_date_Flow;
00117   bool incomplete;
00118   bool tmp_forceLate = data.state->forceLate;
00119   bool isPlannedEarly;
00120   DateRange matnext;
00121 
00122   // Loop till everything is okay. During this loop the quanity and date of the
00123   // operationplan can be updated, but it cannot be split or deleted.
00124   data.state->forceLate = false;
00125   do
00126   {
00127     if (isCapacityConstrained())
00128     {
00129       // Verify the capacity. This can move the operationplan early or late.
00130       checkOperationCapacity(opplan,data);
00131       // Return false if no capacity is available
00132       if (data.state->a_qty==0.0) return false;
00133     }
00134 
00135     // Check material
00136     data.state->q_qty = opplan->getQuantity();
00137     data.state->q_date = opplan->getDates().getEnd();
00138     a_qty = opplan->getQuantity();
00139     a_date = data.state->q_date;
00140     incomplete = false;
00141     matnext.setStart(Date::infinitePast);
00142     matnext.setEnd(Date::infiniteFuture);
00143 
00144     // Loop through all flowplans  // xxx @todo need some kind of coordination run here!!! see test alternate_flow_1
00145     for (OperationPlan::FlowPlanIterator g=opplan->beginFlowPlans();
00146         g!=opplan->endFlowPlans(); ++g)
00147       if (g->getFlow()->isConsumer())
00148       {
00149         // Switch back to the main alternate if this flowplan was already    // @todo is this really required? If yes, in this place?
00150         // planned on an alternate
00151         if (g->getFlow()->getAlternate())
00152           g->setFlow(g->getFlow()->getAlternate());
00153 
00154         // Trigger the flow solver, which will call the buffer solver
00155         data.state->q_flowplan = &*g;
00156         q_qty_Flow = - data.state->q_flowplan->getQuantity(); // @todo flow quantity can change when using alternate flows -> move to flow solver!
00157         q_date_Flow = data.state->q_flowplan->getDate();
00158         g->getFlow()->solve(*this,&data);
00159 
00160         // Validate the answered quantity
00161         if (data.state->a_qty < q_qty_Flow)
00162         {
00163           // Update the opplan, which is required to (1) update the flowplans
00164           // and to (2) take care of lot sizing constraints of this operation.
00165           g->setQuantity(-data.state->a_qty, true);
00166           a_qty = opplan->getQuantity();
00167           incomplete = true;
00168 
00169           // Validate the answered date of the most limiting flowplan.
00170           // Note that the delay variable only reflects the delay due to
00171           // material constraints. If the operationplan is moved early or late
00172           // for capacity constraints, this is not included.
00173           if (data.state->a_date < Date::infiniteFuture)
00174           {
00175             OperationPlanState at = opplan->getOperation()->setOperationPlanParameters(
00176               opplan, 0.01, data.state->a_date, Date::infinitePast, false, false
00177               );
00178             if (at.end < matnext.getEnd()) matnext = DateRange(at.start, at.end);
00179             //xxxif (matnext.getEnd() <= orig_q_date) logger << "STRANGE" << matnext << "  " << orig_q_date << "  " << at.second << "  " << opplan->getQuantity() << endl;
00180           }
00181 
00182           // Jump out of the loop if the answered quantity is 0.
00183           if (a_qty <= ROUNDING_ERROR)
00184           {
00185             // @TODO disabled To speed up the planning the constraining flow is moved up a
00186             // position in the list of flows. It'll thus be checked earlier
00187             // when this operation is asked again
00188             //const_cast<Operation::flowlist&>(g->getFlow()->getOperation()->getFlows()).promote(g->getFlow());
00189             // There is absolutely no need to check other flowplans if the
00190             // operationplan quantity is already at 0.
00191             break;
00192           }
00193         }
00194         else if (data.state->a_qty >+ q_qty_Flow + ROUNDING_ERROR)
00195           // Never answer more than asked.
00196           // The actual operationplan could be bigger because of lot sizing.
00197           a_qty = - q_qty_Flow / g->getFlow()->getQuantity();
00198       }
00199 
00200     isPlannedEarly = opplan->getDates().getEnd() < orig_dates.getEnd();
00201 
00202     if (matnext.getEnd() != Date::infiniteFuture && a_qty <= ROUNDING_ERROR
00203       && matnext.getEnd() <= data.state->q_date_max && matnext.getEnd() > orig_q_date)
00204     {
00205       // The reply is 0, but the next-date is still less than the maximum
00206       // ask date. In this case we will violate the post-operation -soft-
00207       // constraint.
00208       data.state->q_date = matnext.getEnd();
00209       orig_q_date = data.state->q_date;
00210       data.state->q_qty = orig_opplan_qty;
00211       data.state->a_date = Date::infiniteFuture;
00212       data.state->a_qty = data.state->q_qty;
00213       opplan->getOperation()->setOperationPlanParameters(
00214         opplan, orig_opplan_qty, Date::infinitePast, matnext.getEnd()
00215         );
00216       okay = false;
00217       // Pop actions from the command "stack" in the command list
00218       data.undo(topcommand);
00219       // Echo a message
00220       if (data.getSolver()->getLogLevel()>1)
00221         logger << indent(opplan->getOperation()->getLevel())
00222           << "   Retrying new date." << endl;
00223     }
00224     else if (matnext.getEnd() != Date::infiniteFuture && a_qty <= ROUNDING_ERROR
00225       && matnext.getStart() < a_date)
00226     {
00227       // The reply is 0, but the next-date is not too far out.
00228       // If the operationplan would fit in a smaller timeframe we can potentially
00229       // create a non-zero reply...
00230       // Resize the operationplan
00231       opplan->getOperation()->setOperationPlanParameters(
00232         opplan, orig_opplan_qty, matnext.getStart(),
00233         a_date
00234         );
00235       if (opplan->getDates().getStart() >= matnext.getStart()
00236         && opplan->getDates().getEnd() <= a_date
00237         && opplan->getQuantity() > ROUNDING_ERROR)
00238       {
00239         // It worked
00240         orig_dates = opplan->getDates();
00241         data.state->q_date = orig_dates.getEnd();
00242         data.state->q_qty = opplan->getQuantity();
00243         data.state->a_date = Date::infiniteFuture;
00244         data.state->a_qty = data.state->q_qty;
00245         okay = false;
00246         // Pop actions from the command stack in the command list
00247         data.undo(topcommand);
00248         // Echo a message
00249         if (data.getSolver()->getLogLevel()>1)
00250           logger << indent(opplan->getOperation()->getLevel())
00251             << "   Retrying with a smaller quantity: "
00252             << opplan->getQuantity() << endl;
00253       }
00254       else
00255       {
00256         // It didn't work
00257         opplan->setQuantity(0);
00258         okay = true;
00259       }
00260     }
00261     else
00262       okay = true;
00263   }
00264   while (!okay);  // Repeat the loop if the operation was moved and the
00265                   // feasibility needs to be rechecked.
00266 
00267   if (a_qty <= ROUNDING_ERROR && !data.state->forceLate
00268       && isPlannedEarly
00269       && matnext.getStart() != Date::infiniteFuture 
00270       && matnext.getStart() != Date::infinitePast
00271       && (data.constrainedPlanning && isCapacityConstrained()))
00272     {
00273       // The operationplan was moved early (because of a resource constraint)
00274       // and we can't properly trust the reply date in such cases...
00275       // We want to enforce rechecking the next date.
00276 
00277       // Move the operationplan to the next date where the material is feasible
00278       opplan->getOperation()->setOperationPlanParameters
00279         (opplan, orig_opplan_qty, matnext.getStart(), Date::infinitePast);
00280 
00281       // Move the operationplan to a later date where it is feasible.
00282       data.state->forceLate = true;
00283       checkOperationCapacity(opplan,data);
00284 
00285       // Reply of this function
00286       a_qty = 0.0;
00287       matnext.setEnd(opplan->getDates().getEnd());
00288     }
00289 
00290   // Compute the final reply
00291   data.state->a_date = incomplete ? matnext.getEnd() : Date::infiniteFuture;
00292   data.state->a_qty = a_qty;
00293   data.state->forceLate = tmp_forceLate;
00294   if (a_qty > ROUNDING_ERROR)
00295     return true;
00296   else
00297   {
00298     // Undo the plan
00299     data.undo(topcommand);
00300     return false;
00301   }
00302 }
00303 
00304 
00305 DECLARE_EXPORT bool SolverMRP::checkOperationLeadtime
00306 (OperationPlan* opplan, SolverMRP::SolverMRPdata& data, bool extra)
00307 {
00308   // No lead time constraints
00309   if (!data.constrainedPlanning || (!isFenceConstrained() && !isLeadtimeConstrained())) 
00310     return true;
00311 
00312   // Compute offset from the current date: A fence problem uses the release
00313   // fence window, while a leadtimeconstrained constraint has an offset of 0.
00314   // If both constraints apply, we need the bigger of the two (since it is the
00315   // most constraining date.
00316   Date threshold = Plan::instance().getCurrent();
00317   if (isFenceConstrained() 
00318     && !(isLeadtimeConstrained() && opplan->getOperation()->getFence()<0L))
00319     threshold += opplan->getOperation()->getFence();
00320 
00321   // Check the setup operationplan
00322   Date currentOpplanEnd = opplan->getDates().getEnd();
00323   bool ok = true;
00324   bool checkSetup = true;
00325   // If there are alternate loads we take the best case and assume that
00326   // at least one of those can give us a zero-time setup.
00327   // When evaluating the leadtime when solving for capacity we don't use
00328   // this assumption. The resource solver takes care of the constraints.
00329   if (extra && isCapacityConstrained())
00330     for (Operation::loadlist::const_iterator j = opplan->getOperation()->getLoads().begin();
00331       j != opplan->getOperation()->getLoads().end(); ++j)  
00332       if (j->hasAlternates())
00333       {
00334         checkSetup = false;
00335         break;
00336       }
00337   if (checkSetup)
00338   {
00339     OperationPlan::iterator i(opplan);
00340     if (i != opplan->end() 
00341       && i->getOperation() == OperationSetup::setupoperation 
00342       && i->getDates().getStart() < threshold)
00343     {
00344       // The setup operationplan is violating the lead time and/or fence 
00345       // constraint. We move it to start on the earliest allowed date,
00346       // which automatically also moves the owner operationplan.
00347       i->setStart(threshold);
00348       threshold = i->getDates().getEnd();
00349       ok = false;
00350     }
00351   }
00352 
00353   // Compare the operation plan start with the threshold date
00354   if (ok && opplan->getDates().getStart() >= threshold)
00355     // There is no problem
00356     return true;
00357 
00358   // Compute how much we can supply in the current timeframe.
00359   // In other words, we try to resize the operation quantity to fit the
00360   // available timeframe: used for e.g. time-per operations
00361   // Note that we allow the complete post-operation time to be eaten
00362   if (extra)
00363     // Leadtime check during operation resolver
00364     opplan->getOperation()->setOperationPlanParameters(
00365       opplan, opplan->getQuantity(),
00366       threshold,
00367       currentOpplanEnd + opplan->getOperation()->getPostTime(),
00368       false
00369     );
00370   else
00371     // Leadtime check during capacity resolver
00372     opplan->getOperation()->setOperationPlanParameters(
00373       opplan, opplan->getQuantity(),
00374       threshold,
00375       currentOpplanEnd,
00376       true
00377     );
00378 
00379   // Check the result of the resize
00380   if (opplan->getDates().getStart() >= threshold
00381     && (!extra || opplan->getDates().getEnd() <= data.state->q_date_max)
00382     && opplan->getQuantity() > ROUNDING_ERROR)
00383   {
00384     // Resizing did work! The operation now fits within constrained limits
00385     data.state->a_qty = opplan->getQuantity();
00386     data.state->a_date = opplan->getDates().getEnd();
00387     // Acknowledge creation of operationplan
00388     return true;
00389   }
00390   else
00391   {
00392     // This operation doesn't fit at all within the constrained window.
00393     data.state->a_qty = 0.0;
00394     // Resize to the minimum quantity
00395     if (opplan->getQuantity() + ROUNDING_ERROR < opplan->getOperation()->getSizeMinimum())
00396       opplan->setQuantity(0.0001,false);
00397     // Move to the earliest start date
00398     opplan->setStart(threshold);
00399     // Pick up the earliest date we can reply back
00400     data.state->a_date = opplan->getDates().getEnd();
00401     // Set the quantity to 0 (to make sure the buffer doesn't see the supply).
00402     opplan->setQuantity(0.0);
00403     // Deny creation of the operationplan
00404     return false;
00405   }
00406 }
00407 
00408 
00409 DECLARE_EXPORT void SolverMRP::solve(const Operation* oper, void* v)
00410 {
00411   // Make sure we have a valid operation
00412   assert(oper);
00413 
00414   SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
00415   OperationPlan *z;
00416 
00417   // Call the user exit
00418   if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning));
00419 
00420   // Find the flow for the quantity-per. This can throw an exception if no
00421   // valid flow can be found.
00422   double flow_qty_per = 1.0;
00423   if (data->state->curBuffer)
00424   {
00425     Flow* f = oper->findFlow(data->state->curBuffer, data->state->q_date);
00426     if (f && f->getQuantity()>0.0)
00427       flow_qty_per = f->getQuantity();
00428     else
00429       // The producing operation doesn't have a valid flow into the current
00430       // buffer. Either it is missing or it is producing a negative quantity.
00431       throw DataException("Invalid producing operation '" + oper->getName()
00432           + "' for buffer '" + data->state->curBuffer->getName() + "'");
00433   }
00434 
00435   // Message
00436   if (data->getSolver()->getLogLevel()>1)
00437     logger << indent(oper->getLevel()) << "   Operation '" << oper->getName()
00438       << "' is asked: " << data->state->q_qty << "  " << data->state->q_date << endl;
00439 
00440   // Subtract the post-operation time
00441   Date prev_q_date_max = data->state->q_date_max;
00442   data->state->q_date_max = data->state->q_date;
00443   data->state->q_date -= oper->getPostTime();
00444 
00445   // Create the operation plan.
00446   if (data->state->curOwnerOpplan)
00447   {
00448     // There is already an owner and thus also an owner command
00449     assert(!data->state->curDemand);
00450     z = oper->createOperationPlan(
00451           data->state->q_qty / flow_qty_per,
00452           Date::infinitePast, data->state->q_date, data->state->curDemand,
00453           data->state->curOwnerOpplan, 0
00454           );
00455   }
00456   else
00457   {
00458     // There is no owner operationplan yet. We need a new command.
00459     CommandCreateOperationPlan *a =
00460       new CommandCreateOperationPlan(
00461         oper, data->state->q_qty / flow_qty_per,
00462         Date::infinitePast, data->state->q_date, data->state->curDemand,
00463         data->state->curOwnerOpplan
00464         );
00465     data->state->curDemand = NULL;
00466     z = a->getOperationPlan();
00467     data->add(a);
00468   }
00469   assert(z);
00470 
00471   // Check the constraints
00472   data->getSolver()->checkOperation(z,*data);
00473   data->state->q_date_max = prev_q_date_max;
00474 
00475   // Multiply the operation reqply with the flow quantity to get a final reply
00476   if (data->state->curBuffer) data->state->a_qty *= flow_qty_per;
00477 
00478   // Check positive reply quantity
00479   assert(data->state->a_qty >= 0);
00480 
00481   // Increment the cost
00482   if (data->state->a_qty > 0.0)
00483     data->state->a_cost += z->getQuantity() * oper->getCost();
00484 
00485   // Message
00486   if (data->getSolver()->getLogLevel()>1)
00487     logger << indent(oper->getLevel()) << "   Operation '" << oper->getName()
00488       << "' answers: " << data->state->a_qty << "  " << data->state->a_date
00489       << "  " << data->state->a_cost << "  " << data->state->a_penalty << endl;
00490 }
00491 
00492 
00493 // No need to take post- and pre-operation times into account
00494 DECLARE_EXPORT void SolverMRP::solve(const OperationRouting* oper, void* v)
00495 {
00496   SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
00497 
00498   // Call the user exit
00499   if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning));
00500 
00501   // Message
00502   if (data->getSolver()->getLogLevel()>1)
00503     logger << indent(oper->getLevel()) << "   Routing operation '" << oper->getName()
00504       << "' is asked: " << data->state->q_qty << "  " << data->state->q_date << endl;
00505 
00506   // Find the total quantity to flow into the buffer.
00507   // Multiple suboperations can all produce into the buffer.
00508   double flow_qty = 1.0;
00509   if (data->state->curBuffer)
00510   {
00511     flow_qty = 0.0;
00512     Flow *f = oper->findFlow(data->state->curBuffer, data->state->q_date);
00513     if (f) flow_qty += f->getQuantity();
00514     for (Operation::Operationlist::const_iterator
00515         e = oper->getSubOperations().begin();
00516         e != oper->getSubOperations().end();
00517         ++e)
00518     {
00519       f = (*e)->findFlow(data->state->curBuffer, data->state->q_date);
00520       if (f) flow_qty += f->getQuantity();
00521     }
00522     if (flow_qty <= 0.0)
00523       throw DataException("Invalid producing operation '" + oper->getName()
00524           + "' for buffer '" + data->state->curBuffer->getName() + "'");
00525   }
00526   // Because we already took care of it... @todo not correct if the suboperation is again a owning operation
00527   data->state->curBuffer = NULL;
00528   double a_qty(data->state->q_qty / flow_qty);
00529 
00530   // Create the top operationplan
00531   CommandCreateOperationPlan *a = new CommandCreateOperationPlan(
00532     oper, a_qty, Date::infinitePast,
00533     data->state->q_date, data->state->curDemand, data->state->curOwnerOpplan, false
00534     );
00535   data->state->curDemand = NULL;
00536 
00537   // Make sure the subopplans know their owner & store the previous value
00538   OperationPlan *prev_owner_opplan = data->state->curOwnerOpplan;
00539   data->state->curOwnerOpplan = a->getOperationPlan();
00540 
00541   // Loop through the steps
00542   Date max_Date;
00543   for (Operation::Operationlist::const_reverse_iterator
00544       e = oper->getSubOperations().rbegin();
00545       e != oper->getSubOperations().rend() && a_qty > 0.0;
00546       ++e)
00547   {
00548     // Plan the next step
00549     data->state->q_qty = a_qty;
00550     data->state->q_date = data->state->curOwnerOpplan->getDates().getStart();
00551     (*e)->solve(*this,v);  // @todo if the step itself has child operations, the curOwnerOpplan field is changed here!!!
00552     a_qty = data->state->a_qty;
00553 
00554     // Update the top operationplan
00555     data->state->curOwnerOpplan->setQuantity(a_qty,true);
00556 
00557     // Maximum for the next date
00558     if (data->state->a_date != Date::infiniteFuture)
00559     {
00560       OperationPlanState at = data->state->curOwnerOpplan->getOperation()->setOperationPlanParameters(
00561         data->state->curOwnerOpplan, 0.01, //data->state->curOwnerOpplan->getQuantity(),
00562         data->state->a_date, Date::infinitePast, false, false
00563         );
00564       if (at.end > max_Date) max_Date = at.end;
00565     }
00566   }
00567 
00568   // Check the flows and loads on the top operationplan.
00569   // This can happen only after the suboperations have been dealt with
00570   // because only now we know how long the operation lasts in total.
00571   // Solving for the top operationplan can resize and move the steps that are
00572   // in the routing!
00573   /** @todo moving routing opplan doesn't recheck for feasibility of steps... */
00574   data->state->curOwnerOpplan->createFlowLoads();
00575   if (data->state->curOwnerOpplan->getQuantity() > 0.0)
00576   {
00577     data->state->q_qty = a_qty;
00578     data->state->q_date = data->state->curOwnerOpplan->getDates().getEnd();
00579     data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data);
00580     a_qty = data->state->a_qty;
00581     // The reply date is the combination of the reply date of all steps and the
00582     // reply date of the top operationplan.
00583     if (data->state->a_date > max_Date && data->state->a_date != Date::infiniteFuture)
00584       max_Date = data->state->a_date;
00585   }
00586   data->state->a_date = (max_Date ? max_Date : Date::infiniteFuture);
00587   if (data->state->a_date < data->state->q_date)
00588     data->state->a_date = data->state->q_date;
00589 
00590   // Multiply the operationplan quantity with the flow quantity to get the
00591   // final reply quantity
00592   data->state->a_qty = a_qty * flow_qty;
00593 
00594   // Add to the list (even if zero-quantity!)
00595   if (!prev_owner_opplan) data->add(a);
00596 
00597   // Increment the cost
00598   if (data->state->a_qty > 0.0)
00599     data->state->a_cost += data->state->curOwnerOpplan->getQuantity() * oper->getCost();
00600 
00601   // Make other operationplans don't take this one as owner any more.
00602   // We restore the previous owner, which could be NULL.
00603   data->state->curOwnerOpplan = prev_owner_opplan;
00604 
00605   // Check positive reply quantity
00606   assert(data->state->a_qty >= 0);
00607 
00608   // Check reply date is later than requested date
00609   assert(data->state->a_date >= data->state->q_date);
00610 
00611   // Message
00612   if (data->getSolver()->getLogLevel()>1)
00613     logger << indent(oper->getLevel()) << "   Routing operation '" << oper->getName()
00614       << "' answers: " << data->state->a_qty << "  " << data->state->a_date << "  "
00615       << data->state->a_cost << "  " << data->state->a_penalty << endl;
00616 }
00617 
00618 
00619 // No need to take post- and pre-operation times into account
00620 DECLARE_EXPORT void SolverMRP::solve(const OperationAlternate* oper, void* v)
00621 {
00622   SolverMRPdata *data = static_cast<SolverMRPdata*>(v);
00623   Date origQDate = data->state->q_date;
00624   double origQqty = data->state->q_qty;
00625   Buffer *buf = data->state->curBuffer;
00626   Demand *d = data->state->curDemand;
00627 
00628   // Call the user exit
00629   if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning));
00630 
00631   unsigned int loglevel = data->getSolver()->getLogLevel();
00632   SearchMode search = oper->getSearch();
00633 
00634   // Message
00635   if (loglevel>1)
00636     logger << indent(oper->getLevel()) << "   Alternate operation '" << oper->getName()
00637       << "' is asked: " << data->state->q_qty << "  " << data->state->q_date << endl;
00638 
00639   // Make sure sub-operationplans know their owner & store the previous value
00640   OperationPlan *prev_owner_opplan = data->state->curOwnerOpplan;
00641 
00642   // Find the flow into the requesting buffer for the quantity-per
00643   double top_flow_qty_per = 0.0;
00644   bool top_flow_exists = false;
00645   if (buf)
00646   {
00647     Flow* f = oper->findFlow(buf, data->state->q_date);
00648     if (f && f->getQuantity() > 0.0)
00649     {
00650       top_flow_qty_per = f->getQuantity();
00651       top_flow_exists = true;
00652     }
00653   }
00654 
00655   // Control the planning mode
00656   bool originalPlanningMode = data->constrainedPlanning;
00657   data->constrainedPlanning = true;
00658 
00659   // Try all alternates:
00660   // - First, all alternates that are fully effective in the order of priority.
00661   // - Next, the alternates beyond their effectivity date.
00662   //   We loop through these since they can help in meeting a demand on time,
00663   //   but using them will also create extra inventory or delays.
00664   double a_qty = data->state->q_qty;
00665   bool effectiveOnly = true;
00666   Date a_date = Date::infiniteFuture;
00667   Date ask_date;
00668   Operation *firstAlternate = NULL;
00669   double firstFlowPer;
00670   while (a_qty > 0)
00671   {
00672     // Evaluate all alternates
00673     bool plannedAlternate = false;
00674     double bestAlternateValue = DBL_MAX;
00675     double bestAlternateQuantity = 0;
00676     Operation* bestAlternateSelection = NULL;
00677     double bestFlowPer;
00678     Date bestQDate;
00679     for (Operation::Operationlist::const_iterator altIter
00680         = oper->getSubOperations().begin();
00681         altIter != oper->getSubOperations().end(); )
00682     {
00683       // Store the last command in the list, in order to undo the following
00684       // commands if required.
00685       Command* topcommand = data->getLastCommand();
00686       bool nextalternate = true;
00687 
00688       // Operations with 0 priority are considered unavailable
00689       const OperationAlternate::alternateProperty& props
00690         = oper->getProperties(*altIter);
00691 
00692       // Filter out alternates that are not suitable
00693       if (props.first == 0.0
00694         || (effectiveOnly && !props.second.within(data->state->q_date))
00695         || (!effectiveOnly && props.second.getEnd() > data->state->q_date)
00696         )
00697       {
00698         ++altIter;
00699         if (altIter == oper->getSubOperations().end() && effectiveOnly)
00700         {
00701           // Prepare for a second iteration over all alternates
00702           effectiveOnly = false;
00703           altIter = oper->getSubOperations().begin();
00704         }
00705         continue;
00706       }
00707 
00708       // Establish the ask date
00709       ask_date = effectiveOnly ? origQDate : props.second.getEnd();
00710 
00711       // Find the flow into the requesting buffer. It may or may not exist, since
00712       // the flow could already exist on the top operationplan
00713       double sub_flow_qty_per = 0.0;
00714       if (buf)
00715       {
00716         Flow* f = (*altIter)->findFlow(buf, ask_date);
00717         if (f && f->getQuantity() > 0.0)
00718           sub_flow_qty_per = f->getQuantity();
00719         else if (!top_flow_exists)
00720         {
00721           // Neither the top nor the sub operation have a flow in the buffer,
00722           // we're in trouble...
00723           // Restore the planning mode
00724           data->constrainedPlanning = originalPlanningMode;
00725           throw DataException("Invalid producing operation '" + oper->getName()
00726               + "' for buffer '" + buf->getName() + "'");
00727         }
00728       }
00729       else
00730         // Default value is 1.0, if no matching flow is required
00731         sub_flow_qty_per = 1.0;
00732 
00733       // Remember the first alternate
00734       if (!firstAlternate)
00735       {
00736         firstAlternate = *altIter;
00737         firstFlowPer = sub_flow_qty_per + top_flow_qty_per;
00738       }
00739 
00740       // Create the top operationplan.
00741       // Note that both the top- and the sub-operation can have a flow in the
00742       // requested buffer
00743       CommandCreateOperationPlan *a = new CommandCreateOperationPlan(
00744           oper, a_qty, Date::infinitePast, ask_date,
00745           d, prev_owner_opplan, false
00746           );
00747       if (!prev_owner_opplan) data->add(a);
00748 
00749       // Create a sub operationplan
00750       data->state->q_date = ask_date;
00751       data->state->curDemand = NULL;
00752       data->state->curOwnerOpplan = a->getOperationPlan();
00753       data->state->curBuffer = NULL;  // Because we already took care of it... @todo not correct if the suboperation is again a owning operation
00754       data->state->q_qty = a_qty / (sub_flow_qty_per + top_flow_qty_per);
00755 
00756       // Solve constraints on the sub operationplan
00757       double beforeCost = data->state->a_cost;
00758       double beforePenalty = data->state->a_penalty;
00759       if (search == PRIORITY)
00760       {
00761         // Message
00762         if (loglevel)
00763           logger << indent(oper->getLevel()) << "   Alternate operation '" << oper->getName()
00764             << "' tries alternate '" << *altIter << "' " << endl;
00765         (*altIter)->solve(*this,v);
00766       }
00767       else
00768       {
00769         data->getSolver()->setLogLevel(0);
00770         try {(*altIter)->solve(*this,v);}
00771         catch (...)
00772         {
00773           data->getSolver()->setLogLevel(loglevel);
00774           // Restore the planning mode
00775           data->constrainedPlanning = originalPlanningMode;
00776           throw;
00777         }
00778         data->getSolver()->setLogLevel(loglevel);
00779       }
00780       double deltaCost = data->state->a_cost - beforeCost;
00781       double deltaPenalty = data->state->a_penalty - beforePenalty;
00782       data->state->a_cost = beforeCost;
00783       data->state->a_penalty = beforePenalty;
00784 
00785       // Keep the lowest of all next-date answers on the effective alternates
00786       if (effectiveOnly && data->state->a_date < a_date && data->state->a_date > ask_date)
00787         a_date = data->state->a_date;
00788 
00789       // Now solve for loads and flows of the top operationplan.
00790       // Only now we know how long that top-operation lasts in total.
00791       if (data->state->a_qty > ROUNDING_ERROR)
00792       {
00793         // Multiply the operation reply with the flow quantity to obtain the
00794         // reply to return
00795         data->state->q_qty = data->state->a_qty;
00796         data->state->q_date = origQDate;
00797         data->state->curOwnerOpplan->createFlowLoads();
00798         data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data);
00799         data->state->a_qty *= (sub_flow_qty_per + top_flow_qty_per);
00800 
00801         // Combine the reply date of the top-opplan with the alternate check: we
00802         // need to return the minimum next-date.
00803         if (data->state->a_date < a_date && data->state->a_date > ask_date)
00804           a_date = data->state->a_date;
00805       }
00806 
00807       // Message
00808       if (loglevel && search != PRIORITY)
00809         logger << indent(oper->getLevel()) << "   Alternate operation '" << oper->getName()
00810           << "' evaluates alternate '" << *altIter << "': quantity " << data->state->a_qty
00811           << ", cost " << deltaCost << ", penalty " << deltaPenalty << endl;
00812 
00813       // Process the result
00814       if (search == PRIORITY)
00815       {
00816         // Prepare for the next loop
00817         a_qty -= data->state->a_qty;
00818         plannedAlternate = true;
00819 
00820         // As long as we get a positive reply we replan on this alternate
00821         if (data->state->a_qty > 0) nextalternate = false;
00822 
00823         // Are we at the end already?
00824         if (a_qty < ROUNDING_ERROR)
00825         {
00826           a_qty = 0.0;
00827           break;
00828         }
00829       }
00830       else
00831       {
00832         double val;
00833         switch (search)
00834         {
00835           case MINCOST:
00836             val = deltaCost / data->state->a_qty;
00837             break;
00838           case MINPENALTY:
00839             val = deltaPenalty / data->state->a_qty;
00840             break;
00841           case MINCOSTPENALTY:
00842             val = (deltaCost + deltaPenalty) / data->state->a_qty;
00843             break;
00844           default:
00845             LogicException("Unsupported search mode for alternate operation '"
00846               +  oper->getName() + "'");
00847         }
00848         if (data->state->a_qty > ROUNDING_ERROR && (
00849           val + ROUNDING_ERROR < bestAlternateValue
00850           || (fabs(val - bestAlternateValue) < ROUNDING_ERROR 
00851               && data->state->a_qty > bestAlternateQuantity)
00852           ))
00853         {
00854           // Found a better alternate
00855           bestAlternateValue = val;
00856           bestAlternateSelection = *altIter;
00857           bestAlternateQuantity = data->state->a_qty;
00858           bestFlowPer = sub_flow_qty_per + top_flow_qty_per;
00859           bestQDate = ask_date;  
00860         }
00861         // This was only an evaluation
00862         data->undo(topcommand);
00863       }
00864 
00865       // Select the next alternate
00866       if (nextalternate)
00867       {
00868         ++altIter;
00869         if (altIter == oper->getSubOperations().end() && effectiveOnly)
00870         {
00871           // Prepare for a second iteration over all alternates
00872           effectiveOnly = false;
00873           altIter = oper->getSubOperations().begin();
00874         }
00875       }
00876     } // End loop over all alternates
00877 
00878     // Replan on the best alternate
00879     if (bestAlternateQuantity > ROUNDING_ERROR && search != PRIORITY)
00880     {
00881       // Message
00882       if (loglevel)
00883         logger << indent(oper->getLevel()) << "   Alternate operation '" << oper->getName()
00884           << "' chooses alternate '" << bestAlternateSelection << "' " << search << endl;
00885 
00886       // Create the top operationplan.
00887       // Note that both the top- and the sub-operation can have a flow in the
00888       // requested buffer
00889       CommandCreateOperationPlan *a = new CommandCreateOperationPlan(
00890           oper, a_qty, Date::infinitePast, bestQDate,
00891           d, prev_owner_opplan, false
00892           );
00893       if (!prev_owner_opplan) data->add(a);
00894 
00895       // Recreate the ask
00896       data->state->q_qty = a_qty / bestFlowPer;
00897       data->state->q_date = bestQDate;
00898       data->state->curDemand = NULL;
00899       data->state->curOwnerOpplan = a->getOperationPlan();
00900       data->state->curBuffer = NULL;  // Because we already took care of it... @todo not correct if the suboperation is again a owning operation
00901 
00902       // Create a sub operationplan and solve constraints
00903       bestAlternateSelection->solve(*this,v);
00904 
00905       // Now solve for loads and flows of the top operationplan.
00906       // Only now we know how long that top-operation lasts in total.
00907       data->state->q_qty = data->state->a_qty;
00908       data->state->q_date = origQDate;
00909       data->state->curOwnerOpplan->createFlowLoads();
00910       data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data);
00911 
00912       // Multiply the operation reply with the flow quantity to obtain the
00913       // reply to return
00914       data->state->a_qty *= bestFlowPer;
00915 
00916       // Combine the reply date of the top-opplan with the alternate check: we
00917       // need to return the minimum next-date.
00918       if (data->state->a_date < a_date && data->state->a_date > ask_date)
00919         a_date = data->state->a_date;
00920 
00921       // Prepare for the next loop
00922       a_qty -= data->state->a_qty;
00923 
00924       // Are we at the end already?
00925       if (a_qty < ROUNDING_ERROR)
00926       {
00927         a_qty = 0.0;
00928         break;
00929       }
00930     }
00931     else
00932       // No alternate can plan anything any more
00933       break;
00934 
00935   } // End while loop until the a_qty > 0
00936 
00937 
00938   // Unconstrained plan: if nothing was planned, plan unconstrained on the first alternate
00939   if (!originalPlanningMode && fabs(origQqty - a_qty) < ROUNDING_ERROR && firstAlternate)
00940   {
00941     // Switch to unconstrained planning 
00942     data->constrainedPlanning = false;
00943     // Message
00944     if (loglevel)
00945       logger << indent(oper->getLevel()) << "   Alternate operation '" << oper->getName()
00946         << "' plans unconstrained on alternate '" << firstAlternate << "' " << search << endl;
00947 
00948     // Create the top operationplan.
00949     // Note that both the top- and the sub-operation can have a flow in the
00950     // requested buffer
00951     CommandCreateOperationPlan *a = new CommandCreateOperationPlan(
00952         oper, a_qty, Date::infinitePast, origQDate,
00953         d, prev_owner_opplan, false
00954         );
00955     if (!prev_owner_opplan) data->add(a);
00956 
00957     // Recreate the ask
00958     data->state->q_qty = a_qty / firstFlowPer;
00959     data->state->q_date = origQDate;
00960     data->state->curDemand = NULL;
00961     data->state->curOwnerOpplan = a->getOperationPlan();
00962     data->state->curBuffer = NULL;  // Because we already took care of it... @todo not correct if the suboperation is again a owning operation
00963 
00964     // Create a sub operationplan and solve constraints
00965     firstAlternate->solve(*this,v);
00966 
00967     // Expand flows of the top operationplan.
00968     data->state->q_qty = data->state->a_qty;
00969     data->state->q_date = origQDate;
00970     data->state->curOwnerOpplan->createFlowLoads();
00971     data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data);
00972 
00973     // Fully planned
00974     a_qty = 0.0;
00975     data->state->a_date = origQDate;
00976   }
00977 
00978   // Set up the reply
00979   data->state->a_qty = origQqty - a_qty; // a_qty is the unplanned quantity
00980   data->state->a_date = a_date;
00981   assert(data->state->a_qty >= 0);
00982   assert(data->state->a_date >= data->state->q_date);
00983 
00984   // Restore the planning mode
00985   data->constrainedPlanning = originalPlanningMode;
00986 
00987   // Increment the cost
00988   if (data->state->a_qty > 0.0)
00989     data->state->a_cost += data->state->curOwnerOpplan->getQuantity() * oper->getCost();
00990 
00991   // Make other opplans don't take this one as owner any more.
00992   // We restore the previous owner, which could be NULL.
00993   data->state->curOwnerOpplan = prev_owner_opplan;
00994 
00995   // Message
00996   if (loglevel>1)
00997     logger << indent(oper->getLevel()) << "   Alternate operation '" << oper->getName()
00998       << "' answers: " << data->state->a_qty << "  " << data->state->a_date
00999       << "  " << data->state->a_cost << "  " << data->state->a_penalty << endl;
01000 }
01001 
01002 
01003 }