solverresource.cpp
Go to the documentation of this file.
00001 /***************************************************************************
00002   file : $URL: http://svn.code.sf.net/p/frepple/code/trunk/src/solver/solverresource.cpp $
00003   version : $LastChangedRevision: 1713 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2012-07-18 11:46:01 +0200 (Wed, 18 Jul 2012) $
00005  ***************************************************************************/
00006 
00007 /***************************************************************************
00008  *                                                                         *
00009  * Copyright (C) 2007-2012 by Johan De Taeye, frePPLe bvba                 *
00010  *                                                                         *
00011  * This library is free software; you can redistribute it and/or modify it *
00012  * under the terms of the GNU Affero General Public License as published   *
00013  * by the Free Software Foundation; either version 3 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            *
00019  * GNU Affero General Public License for more details.                     *
00020  *                                                                         *
00021  * You should have received a copy of the GNU Affero General Public        *
00022  * License along with this program.                                        *
00023  * If not, see <http://www.gnu.org/licenses/>.                             *
00024  *                                                                         *
00025  ***************************************************************************/
00026 
00027 #define FREPPLE_CORE
00028 #include "frepple/solver.h"
00029 
00030 namespace frepple
00031 {
00032 
00033 
00034 /** @todo resource solver should be using a move command rather than direct move */
00035 DECLARE_EXPORT void SolverMRP::solve(const Resource* res, void* v)
00036 {
00037   SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
00038 
00039   // Call the user exit
00040   if (userexit_resource) userexit_resource.call(res, PythonObject(data->constrainedPlanning));
00041 
00042   // Message
00043   if (data->getSolver()->getLogLevel()>1)
00044   {
00045     if (!data->constrainedPlanning || !data->getSolver()->isConstrained())
00046       logger << indent(res->getLevel()) << "   Resource '" << res->getName()
00047         << "' is asked in unconstrained mode: "<< (-data->state->q_qty) << "  "
00048         << data->state->q_operationplan->getDates() << endl;
00049     else
00050       logger << indent(res->getLevel()) << "   Resource '" << res->getName()
00051         << "' is asked: "<< (-data->state->q_qty) << "  "
00052         << data->state->q_operationplan->getDates() << endl;
00053   }
00054 
00055   // Unconstrained plan
00056   if (!data->constrainedPlanning)
00057   {
00058     // Reply whatever is requested, regardless of date and quantity.
00059     data->state->a_qty = data->state->q_qty;
00060     data->state->a_date = data->state->q_date;
00061     data->state->a_cost += data->state->a_qty * res->getCost()
00062       * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable())
00063       / 3600.0;
00064 
00065     // Message
00066     if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00067       logger << indent(res->getLevel()) << "  Resource '" << res << "' answers: "
00068       << (-data->state->a_qty) << "  " << data->state->a_date << endl;
00069   }
00070 
00071   // Find the setup operationplan
00072   OperationPlan *setupOpplan = NULL;
00073   DateRange currentSetupOpplanDates;
00074   LoadPlan *setupLdplan = NULL;
00075   if (res->getSetupMatrix() && !data->state->q_loadplan->getLoad()->getSetup().empty())
00076     for (OperationPlan::iterator i(data->state->q_operationplan); i != OperationPlan::end(); ++i)
00077       if (i->getOperation() == OperationSetup::setupoperation)
00078       {
00079         setupOpplan = &*i;
00080         currentSetupOpplanDates = i->getDates();
00081         for (OperationPlan::LoadPlanIterator j = setupOpplan->beginLoadPlans();
00082           j != setupOpplan->endLoadPlans(); ++j)
00083           if (j->getLoad()->getResource() == res && !j->isStart())
00084           {
00085             setupLdplan = &*j;
00086             break;
00087           }
00088         if (!setupLdplan)
00089           throw LogicException("Can't find loadplan on setup operationplan");
00090         break;
00091       }
00092 
00093   // Initialize some variables
00094   double orig_q_qty = -data->state->q_qty;
00095   OperationPlanState currentOpplan(data->state->q_operationplan);
00096   Resource::loadplanlist::const_iterator cur = res->getLoadPlans().end();
00097   Date curdate;
00098   double curMax, prevMax;
00099   bool HasOverload;
00100   bool HasSetupOverload;
00101   bool noRestore = data->state->forceLate;
00102   bool forced_late = data->state->forceLate;
00103 
00104   // Initialize the default reply
00105   data->state->a_date = data->state->q_date;
00106   data->state->a_qty = orig_q_qty;
00107   Date prevdate;
00108 
00109   // Loop for a valid location by using EARLIER capacity
00110   if (!data->state->forceLate)
00111     do
00112     {
00113       // Check the leadtime constraints
00114       prevdate = data->state->q_operationplan->getDates().getEnd();
00115       noRestore = data->state->forceLate;
00116 
00117       if (isLeadtimeConstrained() || isFenceConstrained())
00118         // Note that the check function can update the answered date and quantity
00119          if (data->constrainedPlanning && !checkOperationLeadtime(data->state->q_operationplan,*data,false))
00120          {
00121            // Operationplan violates the lead time and/or fence constraint
00122            noRestore = true;
00123            break;
00124          }
00125 
00126       // Check if this operation overloads the resource at its current time
00127       HasOverload = false;
00128       HasSetupOverload = false;
00129       Date earliestdate = data->state->q_operationplan->getDates().getStart();
00130       curdate = data->state->q_loadplan->getDate();
00131       curMax = data->state->q_loadplan->getMax(false);
00132       prevMax = curMax;
00133       for (cur = res->getLoadPlans().begin(data->state->q_loadplan);
00134         cur!=res->getLoadPlans().end() && cur->getDate()>=earliestdate;
00135         --cur)
00136       {
00137         // A change in the maximum capacity
00138         prevMax = curMax;
00139         if (cur->getType() == 4)
00140           curMax = cur->getMax(false);
00141 
00142         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00143         if (ldplan && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
00144           && ldplan->getOperationPlan()->getDates().overlap(data->state->q_operationplan->getDates()) > 0L
00145           && ldplan->getOperationPlan() != setupOpplan)
00146         {
00147           // Ongoing setup
00148           HasOverload = true;
00149           HasSetupOverload = true;
00150           break;
00151         }
00152 
00153         // Not interested if date doesn't change
00154         if (cur->getDate() == curdate) continue;
00155 
00156         if (cur->getOnhand() > prevMax + ROUNDING_ERROR)
00157         {
00158           // Overload: We are exceeding the limit!
00159           // At this point:
00160           //  - cur points to a loadplan where we exceed the capacity
00161           //  - curdate points to the latest date without overload
00162           //  - curdate != cur->getDate()
00163           HasOverload = true;
00164           break;
00165         }
00166         curdate = cur->getDate();
00167       }
00168 
00169       // Check if the setup operationplan overloads the resource or if a
00170       // different setup is already active on the resource.
00171       if (setupOpplan && !HasOverload)
00172       {
00173         earliestdate = setupOpplan->getDates().getStart();
00174         for (cur = res->getLoadPlans().begin(setupLdplan);
00175           cur!=res->getLoadPlans().end() && cur->getDate()>=earliestdate;
00176           --cur)
00177         {
00178           // A change in the maximum capacity
00179           prevMax = curMax;
00180           if (cur->getType() == 4)
00181             curMax = cur->getMax(false);
00182 
00183           // Must be same setup
00184           const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00185           if (ldplan
00186             && ldplan->getOperationPlan()->getDates().overlap(setupOpplan->getDates()) > 0L
00187             && ldplan->getSetup() != setupLdplan->getSetup())
00188           {
00189             HasOverload = true;
00190             HasSetupOverload = true;
00191             break;
00192           }
00193 
00194           // Not interested if date doesn't change
00195           if (cur->getDate() == curdate) continue;
00196           if (cur->getOnhand() > prevMax + ROUNDING_ERROR)
00197           {
00198             // Overload: We are exceeding the limit!
00199             // At this point:
00200             //  - cur points to a loadplan where we exceed the capacity
00201             //  - curdate points to the latest date without overload
00202             //  - curdate != cur->getDate()
00203             HasOverload = true;
00204             HasSetupOverload = true;
00205             break;
00206           }
00207           curdate = cur->getDate();
00208         }
00209       }
00210 
00211       // Try solving the overload by resizing the operationplan.
00212       // The capacity isn't overloaded in the time between "curdate" and
00213       // "current end of the operationplan". We can try to resize the
00214       // operationplan to fit in this time period...
00215       if (HasOverload && !HasSetupOverload
00216         && curdate < data->state->q_loadplan->getDate())
00217       {
00218         Date currentEnd = data->state->q_operationplan->getDates().getEnd();
00219         data->state->q_operationplan->getOperation()->setOperationPlanParameters(
00220           data->state->q_operationplan,
00221           currentOpplan.quantity,
00222           curdate,
00223           currentEnd
00224           );
00225         if (data->state->q_operationplan->getQuantity() > 0
00226           && data->state->q_operationplan->getDates().getEnd() <= currentEnd
00227           && data->state->q_operationplan->getDates().getStart() >= curdate)
00228         {
00229           // The squeezing did work!
00230           // The operationplan quantity is now reduced. The buffer solver will
00231           // ask again for the remaining short quantity, so we don't need to
00232           // bother about that here.
00233           HasOverload = false;
00234         }
00235         else
00236         {
00237           // It didn't work. Restore the original operationplan.
00238           // @todo this undoing is a performance bottleneck: trying to resize
00239           // and restoring the original are causing lots of updates in the
00240           // buffer and resource timelines...
00241           // We need an api that only checks the resizing.
00242           data->state->q_operationplan->getOperation()->setOperationPlanParameters(
00243             data->state->q_operationplan,
00244             currentOpplan.quantity,
00245             Date::infinitePast,
00246             currentEnd
00247             );
00248         }
00249       }
00250 
00251       // Try solving the overload by moving the operationplan to an earlier date
00252       if (HasOverload)
00253       {
00254         // Search backward in time for a period where there is no overload
00255         curMax = cur->getMax(false);
00256         prevMax = curMax;
00257         curdate = cur->getDate();
00258         for (; cur!=res->getLoadPlans().end() && curdate > currentOpplan.end - res->getMaxEarly(); --cur)
00259         {
00260           // A change in the maximum capacity
00261           prevMax = curMax;
00262           if (cur->getType() == 4) curMax = cur->getMax(false);
00263 
00264           // Ongoing setup
00265           const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00266           if (ldplan
00267             && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
00268             && ldplan->isStart()
00269             && ldplan->getOperationPlan()->getDates().getDuration() > 0L
00270             && ldplan->getOperationPlan() != setupOpplan)
00271             continue;
00272 
00273           // Not interested if date doesn't change
00274           if (cur->getDate() == curdate) continue;
00275 
00276           // We are below the max limit now.
00277           if (cur->getOnhand() < prevMax + ROUNDING_ERROR && curdate < prevdate)
00278             break;
00279           curdate = cur->getDate();
00280         }
00281         assert (curdate != prevdate);
00282 
00283         // We found a date where the load goes below the maximum
00284         // At this point:
00285         //  - curdate is a latest date where we are above the maximum
00286         //  - cur is the first loadplan where we are below the max
00287         if (cur != res->getLoadPlans().end() && curdate > currentOpplan.end - res->getMaxEarly())
00288         {
00289           // Move the operationplan
00290           data->state->q_operationplan->setEnd(curdate);
00291 
00292           // Verify the move is successfull
00293           if (data->state->q_operationplan->getDates().getEnd() > curdate)
00294             // If there isn't available time in the location calendar, the move
00295             // can fail.
00296             data->state->a_qty = 0.0;
00297           else if (data->constrainedPlanning && (isLeadtimeConstrained() || isFenceConstrained()))
00298             // Check the leadtime constraints after the move
00299             // Note that the check function can update the answered date
00300             // and quantity
00301             checkOperationLeadtime(data->state->q_operationplan,*data,false);
00302         }
00303         else
00304           // No earlier capacity found: get out of the loop
00305           data->state->a_qty = 0.0;
00306       }  // End of if-statement, solve by moving earlier
00307     }
00308     while (HasOverload && data->state->a_qty!=0.0);
00309 
00310   // Loop for a valid location by using LATER capacity
00311   // If the answered quantity is 0, the operationplan is moved into the past.
00312   // Or, the solver may be forced to produce a late reply.
00313   // In these cases we need to search for capacity at later dates.
00314   if (data->constrainedPlanning && (data->state->a_qty == 0.0 || data->state->forceLate))
00315   {
00316     // Put the operationplan back at its original end date
00317     if (!noRestore)
00318       data->state->q_operationplan->restore(currentOpplan);
00319 
00320     // Moving an operation earlier is driven by the ending loadplan,
00321     // while searching for later capacity is driven from the starting loadplan.
00322     LoadPlan* old_q_loadplan = data->state->q_loadplan;
00323     data->state->q_loadplan = data->state->q_loadplan->getOtherLoadPlan();
00324 
00325     // Loop to find a later date where the operationplan will fit
00326     Date newDate;
00327     do
00328     {
00329       // Search for a date where we go below the maximum load.
00330       // and verify whether there are still some overloads
00331       HasOverload = false;
00332       newDate = Date::infinitePast;
00333       curMax = data->state->q_loadplan->getMax();
00334       double curOnhand = data->state->q_loadplan->getOnhand();
00335 
00336       // Find how many uncommitted operationplans are loading the resource
00337       // before of the loadplan.
00338       // If the same resource is used multiple times in the supply path of a
00339       // demand we need to use only the capacity used by other demands. Otherwise
00340       // our estimate is of the feasible next date is too pessimistic.
00341       // If the operation is the same, the operationplans are at the same stage
00342       // in the supply path and we need to include these in our estimate of the
00343       // next date.
00344       double ignored = 0.0;
00345       for (cur = res->getLoadPlans().begin(); cur!=res->getLoadPlans().begin(data->state->q_loadplan); ++cur)
00346       {
00347         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00348         if (ldplan && !ldplan->getOperationPlan()->getIdentifier() 
00349           && ldplan->getOperationPlan()->getOperation()!=data->state->q_operationplan->getOperation() )
00350           ignored += ldplan->getQuantity();
00351       }
00352 
00353       for (cur=res->getLoadPlans().begin(data->state->q_loadplan);
00354           !(HasOverload && newDate) && cur != res->getLoadPlans().end(); )
00355       {
00356         // New maximum
00357         if (cur->getType() == 4)
00358           curMax = cur->getMax();
00359 
00360         /* @todo is this required?
00361         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00362         if (ldplan && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
00363           && ldplan->getOperationPlan()->getDates().getDuration() > 0L)
00364         {
00365           // Ongoing setup
00366           HasOverload = true;
00367           ++cur;
00368           continue;
00369         }
00370         */
00371         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00372         if (ldplan && !ldplan->getOperationPlan()->getIdentifier() 
00373           && ldplan->getOperationPlan()->getOperation()!=data->state->q_operationplan->getOperation())
00374           ignored += ldplan->getQuantity();
00375 
00376         // Only consider the last loadplan for a certain date
00377         const TimeLine<LoadPlan>::Event *loadpl = &*(cur++);
00378         if (cur!=res->getLoadPlans().end() && cur->getDate()==loadpl->getDate())
00379           continue;
00380         curOnhand = loadpl->getOnhand();
00381 
00382         // Check if overloaded
00383         if (loadpl->getOnhand() - ignored > curMax + ROUNDING_ERROR)
00384           // There is still a capacity problem
00385           HasOverload = true;
00386         else if (!HasOverload && loadpl->getDate() > data->state->q_operationplan->getDates().getEnd())
00387           // Break out of loop if no overload and we're beyond the
00388           // operationplan end date.
00389           break;
00390         else if (!newDate && loadpl->getDate()!=data->state->q_loadplan->getDate() && curMax >= fabs(loadpl->getQuantity()))
00391         {
00392           // We are below the max limit for the first time now.
00393           // This means that the previous date may be a proper start.
00394           newDate = loadpl->getDate();
00395         }
00396       }
00397 
00398       // Found a date with available capacity
00399       if (HasOverload && newDate)
00400       {
00401         // Multiple operations could be executed in parallel
00402         int parallelOps = static_cast<int>((curMax - curOnhand) / data->state->q_loadplan->getQuantity());
00403         if (parallelOps <= 0) parallelOps = 1;
00404         // Move the operationplan to the new date
00405         data->state->q_operationplan->getOperation()->setOperationPlanParameters(
00406             data->state->q_operationplan,
00407             (currentOpplan.quantity ? currentOpplan.quantity : 0.001) / parallelOps, // 0.001  @todo this calculation doesn't give minimization of the lateness
00408             newDate,
00409             Date::infinitePast
00410             );
00411         HasOverload = true;
00412         if (data->state->q_operationplan->getDates().getStart() < newDate)
00413           // Moving to the new date turns out to be infeasible! Give it up.
00414           // For instance, this can happen when the location calendar doesn't
00415           // have any up-time after the specified date.
00416           break;
00417       }
00418     }
00419     while (HasOverload && newDate);
00420     data->state->q_loadplan = old_q_loadplan;
00421 
00422     // Set the date where a next trial date can happen
00423     if (HasOverload)
00424       // No available capacity found anywhere in the horizon
00425       data->state->a_date = Date::infiniteFuture;
00426     else
00427       data->state->a_date = data->state->q_operationplan->getDates().getEnd();
00428 
00429     // Create a zero quantity reply
00430     data->state->a_qty = 0.0;
00431   }
00432 
00433   // Force ok in unconstrained plan
00434   if (!data->constrainedPlanning && data->state->a_qty == 0.0)
00435   {
00436     data->state->q_operationplan->restore(currentOpplan);
00437     data->state->a_date = data->state->q_date;
00438     data->state->a_qty = orig_q_qty;
00439   }
00440 
00441   // Increment the cost
00442   if (data->state->a_qty > 0.0)
00443   {
00444     // Resource usage
00445     data->state->a_cost += data->state->a_qty * res->getCost()
00446        * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable()) / 3600.0;
00447     // Setup penalty and cost
00448     if (setupOpplan)
00449     {
00450       data->state->a_cost += data->state->a_qty * res->getCost()
00451        * (setupOpplan->getDates().getDuration() - setupOpplan->getUnavailable()) / 3600.0;
00452       data->state->a_penalty += setupOpplan->getPenalty();
00453     }
00454     // Build-ahead penalty: 1 per day
00455     if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
00456       data->state->a_penalty +=
00457         (currentOpplan.end - data->state->q_operationplan->getDates().getEnd()) / 86400.0;
00458   }
00459 
00460   // Maintain the constraint list
00461   if (data->state->a_qty == 0.0 && data->logConstraints)
00462     data->planningDemand->getConstraints().push(
00463       ProblemCapacityOverload::metadata,
00464       res, currentOpplan.start, currentOpplan.end, orig_q_qty);
00465 
00466   // Message
00467   if (data->getSolver()->getLogLevel()>1)
00468   {
00469     logger << indent(res->getLevel()) << "   Resource '" << res << "' answers: "
00470       << data->state->a_qty << "  " << data->state->a_date;
00471     if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
00472       logger << " using earlier capacity "
00473         << data->state->q_operationplan->getDates().getEnd();
00474     if (data->state->a_qty>0.0 && data->state->q_operationplan->getQuantity() < currentOpplan.quantity)
00475       logger << " with reduced quantity " << data->state->q_operationplan->getQuantity();
00476     logger << endl;
00477   }
00478 
00479 }
00480 
00481 
00482 DECLARE_EXPORT void SolverMRP::solve(const ResourceInfinite* res, void* v)
00483 {
00484   SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
00485 
00486   // Call the user exit
00487   if (userexit_resource) userexit_resource.call(res, PythonObject(data->constrainedPlanning));
00488 
00489   // Message
00490   if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00491     logger << indent(res->getLevel()) << "  Infinite resource '" << res << "' is asked: "
00492     << (-data->state->q_qty) << "  " << data->state->q_operationplan->getDates() << endl;
00493 
00494   // @todo Need to make the setups feasible - move to earlier dates till max_early fence is reached
00495 
00496   // Reply whatever is requested, regardless of date and quantity.
00497   data->state->a_qty = data->state->q_qty;
00498   data->state->a_date = data->state->q_date;
00499   data->state->a_cost += data->state->a_qty * res->getCost()
00500     * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable())
00501     / 3600.0;
00502 
00503   // Message
00504   if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00505     logger << indent(res->getLevel()) << "  Infinite resource '" << res << "' answers: "
00506     << (-data->state->a_qty) << "  " << data->state->a_date << endl;
00507 }
00508 
00509 
00510 }

Documentation generated for frePPLe by  doxygen