solverresource.cpp

Go to the documentation of this file.
00001 /***************************************************************************
00002   file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/trunk/src/solver/solverresource.cpp $
00003   version : $LastChangedRevision: 1324 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2010-07-31 11:03:57 +0200 (Sat, 31 Jul 2010) $
00005  ***************************************************************************/
00006 
00007 /***************************************************************************
00008  *                                                                         *
00009  * Copyright (C) 2007-2010 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 
00031 namespace frepple
00032 {
00033 
00034 
00035 /** @todo resource solver should be using a move command rather than direct move */
00036 DECLARE_EXPORT void SolverMRP::solve(const Resource* res, void* v)
00037 {
00038   SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
00039 
00040   // Call the user exit
00041   if (userexit_resource) userexit_resource.call(res, PythonObject(data->constrainedPlanning));
00042 
00043   // Message
00044   if (data->getSolver()->getLogLevel()>1)
00045   {
00046     if (!data->constrainedPlanning || !data->getSolver()->isConstrained()) 
00047       logger << indent(res->getLevel()) << "   Resource '" << res->getName()
00048         << "' is asked in unconstrained mode: "<< (-data->state->q_qty) << "  "
00049         << data->state->q_operationplan->getDates() << endl;
00050     else
00051       logger << indent(res->getLevel()) << "   Resource '" << res->getName()
00052         << "' is asked: "<< (-data->state->q_qty) << "  "
00053         << data->state->q_operationplan->getDates() << endl;
00054   }
00055 
00056   // Unconstrained plan
00057   if (!data->constrainedPlanning)
00058   {
00059     // Reply whatever is requested, regardless of date and quantity.
00060     data->state->a_qty = data->state->q_qty;
00061     data->state->a_date = data->state->q_date;
00062     data->state->a_cost += data->state->a_qty * res->getCost()
00063       * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable()) 
00064       / 3600.0;
00065 
00066     // Message
00067     if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00068       logger << indent(res->getLevel()) << "  Resource '" << res << "' answers: "
00069       << (-data->state->a_qty) << "  " << data->state->a_date << endl;
00070   }
00071 
00072   // Find the setup operationplan
00073   OperationPlan *setupOpplan = NULL;
00074   DateRange currentSetupOpplanDates;
00075   LoadPlan *setupLdplan = NULL;
00076   if (res->getSetupMatrix() && !data->state->q_loadplan->getLoad()->getSetup().empty())
00077     for (OperationPlan::iterator i(data->state->q_operationplan); i != OperationPlan::end(); ++i)
00078       if (i->getOperation() == OperationSetup::setupoperation)
00079       {
00080         setupOpplan = &*i;
00081         currentSetupOpplanDates = i->getDates();
00082         for (OperationPlan::LoadPlanIterator j = setupOpplan->beginLoadPlans();
00083           j != setupOpplan->endLoadPlans(); ++j)
00084           if (j->getLoad()->getResource() == res && !j->isStart())
00085           {
00086             setupLdplan = &*j;
00087             break;
00088           }
00089         if (!setupLdplan)
00090           throw LogicException("Can't find loadplan on setup operationplan");
00091         break;
00092       }
00093 
00094   // Initialize some variables
00095   double orig_q_qty = -data->state->q_qty;
00096   OperationPlanState currentOpplan(data->state->q_operationplan);
00097   Resource::loadplanlist::const_iterator cur = res->getLoadPlans().end();
00098   Date curdate;
00099   double curMax, prevMax;
00100   bool HasOverload;
00101   bool HasSetupOverload;
00102   bool noRestore = 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
00312   // past.
00313   // Or, the solver may be forced to produce a late reply.
00314   // In these cases we need to search for capacity at later dates.
00315   if (data->constrainedPlanning && (data->state->a_qty == 0.0 || data->state->forceLate))
00316   {
00317     // Put the operationplan back at its original end date
00318     if (!noRestore)
00319       data->state->q_operationplan->restore(currentOpplan);
00320 
00321     // Moving an operation earlier is driven by the ending loadplan,
00322     // while searching for later capacity is driven from the starting loadplan.
00323     LoadPlan* old_q_loadplan = data->state->q_loadplan;
00324     data->state->q_loadplan = data->state->q_loadplan->getOtherLoadPlan();
00325 
00326     // Loop to find a later date where the operationplan will fit
00327     Date newDate;
00328     do
00329     {
00330       // Search for a date where we go below the maximum load.
00331       // and verify whether there are still some overloads
00332       HasOverload = false;
00333       newDate = Date::infinitePast;
00334       curMax = data->state->q_loadplan->getMax();
00335       double curOnhand = data->state->q_loadplan->getOnhand();
00336       for (cur=res->getLoadPlans().begin(data->state->q_loadplan);
00337           !(HasOverload && newDate) && cur != res->getLoadPlans().end(); )
00338       {
00339         // New maximum
00340         if (cur->getType() == 4)
00341           curMax = cur->getMax();
00342 
00343         /* @todo is this required?
00344         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00345         if (ldplan && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
00346           && ldplan->getOperationPlan()->getDates().getDuration() > 0L)
00347         {
00348           // Ongoing setup
00349           HasOverload = true;
00350           ++cur;
00351           continue;
00352         }
00353         */
00354 
00355         // Only consider the last loadplan for a certain date
00356         const TimeLine<LoadPlan>::Event *loadpl = &*(cur++);
00357         if (cur!=res->getLoadPlans().end() && cur->getDate()==loadpl->getDate())
00358           continue;
00359         curOnhand = loadpl->getOnhand();
00360 
00361         // Check if overloaded
00362         if (loadpl->getOnhand() > curMax + ROUNDING_ERROR)
00363           // There is still a capacity problem
00364           HasOverload = true;
00365         else if (!HasOverload && loadpl->getDate() > data->state->q_operationplan->getDates().getEnd())
00366           // Break out of loop if no overload and we're beyond the
00367           // operationplan end date.
00368           break;
00369         else if (!newDate && loadpl->getDate()!=data->state->q_loadplan->getDate() && curMax >= fabs(loadpl->getQuantity()))
00370         {
00371           // We are below the max limit for the first time now.
00372           // This means that the previous date may be a proper start.
00373           newDate = loadpl->getDate();
00374         }
00375       }
00376 
00377       // Found a date with available capacity
00378       if (HasOverload && newDate)
00379       {
00380         // Multiple operations could be executed in parallel
00381         int parallelOps = static_cast<int>((curMax - curOnhand) / data->state->q_loadplan->getQuantity());
00382         if (parallelOps <= 0) parallelOps = 1;
00383         // Move the operationplan to the new date
00384         data->state->q_operationplan->getOperation()->setOperationPlanParameters(
00385             data->state->q_operationplan,
00386             currentOpplan.quantity / parallelOps, // 0.001  @todo this calculation doesn't give minimization of the lateness
00387             newDate,
00388             Date::infinitePast
00389             );
00390         HasOverload = true;
00391         if (data->state->q_operationplan->getDates().getStart() < newDate)
00392           // Moving to the new date turns out to be infeasible! Give it up.
00393           // For instance, this can happen when the location calendar doesn't 
00394           // have any up-time after the specified date.
00395           break;
00396       }
00397     }
00398     while (HasOverload && newDate);
00399     data->state->q_loadplan = old_q_loadplan;
00400 
00401     // Set the date where a next trial date can happen
00402     if (HasOverload)
00403       // No available capacity found anywhere in the horizon
00404       data->state->a_date = Date::infiniteFuture;
00405     else
00406       data->state->a_date = data->state->q_operationplan->getDates().getEnd();
00407 
00408     // Create a zero quantity reply
00409     data->state->a_qty = 0.0;
00410   }
00411 
00412   // Force ok in unconstrained plan
00413   if (!data->constrainedPlanning && data->state->a_qty == 0.0)
00414   {
00415     data->state->q_operationplan->restore(currentOpplan);
00416     data->state->a_date = data->state->q_date;
00417     data->state->a_qty = orig_q_qty;
00418   }
00419 
00420   // Increment the cost
00421   if (data->state->a_qty > 0.0)
00422   {
00423     // Resource usage
00424     data->state->a_cost += data->state->a_qty * res->getCost()
00425        * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable()) / 3600.0;
00426     // Setup penalty and cost
00427     if (setupOpplan)
00428     {
00429       data->state->a_cost += data->state->a_qty * res->getCost()
00430        * (setupOpplan->getDates().getDuration() - setupOpplan->getUnavailable()) / 3600.0;
00431       data->state->a_penalty += setupOpplan->getPenalty();
00432     }
00433     // Build-ahead penalty: 1 per day
00434     if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
00435       data->state->a_penalty += 
00436         (currentOpplan.end - data->state->q_operationplan->getDates().getEnd()) / 86400.0;
00437   }
00438   else if (data->state->q_operationplan->getQuantity() > 0.0)
00439     data->state->q_operationplan->setQuantity(0.0);
00440 
00441   // Maintain the constraint list
00442   if (data->state->a_qty == 0.0 && data->logConstraints)
00443     data->planningDemand->getConstraints().push(
00444       ProblemCapacityOverload::metadata,
00445       res, currentOpplan.start, currentOpplan.end, orig_q_qty);
00446 
00447   // Message
00448   if (data->getSolver()->getLogLevel()>1)
00449   {
00450     logger << indent(res->getLevel()) << "   Resource '" << res << "' answers: "
00451       << data->state->a_qty << "  " << data->state->a_date;
00452     if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
00453       logger << " using earlier capacity "
00454         << data->state->q_operationplan->getDates().getEnd();
00455     if (data->state->a_qty>0.0 && data->state->q_operationplan->getQuantity() < currentOpplan.quantity)
00456       logger << " with reduced quantity " << data->state->q_operationplan->getQuantity();
00457     logger << endl;
00458   }
00459 
00460 }
00461 
00462 
00463 DECLARE_EXPORT void SolverMRP::solve(const ResourceInfinite* res, void* v)
00464 {
00465   SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
00466 
00467   // Call the user exit
00468   if (userexit_resource) userexit_resource.call(res, PythonObject(data->constrainedPlanning));
00469 
00470   // Message
00471   if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00472     logger << indent(res->getLevel()) << "  Infinite resource '" << res << "' is asked: "
00473     << (-data->state->q_qty) << "  " << data->state->q_operationplan->getDates() << endl;
00474 
00475   // @todo Need to make the setups feasible - move to earlier dates till max_early fence is reached
00476 
00477   // Reply whatever is requested, regardless of date and quantity.
00478   data->state->a_qty = data->state->q_qty;
00479   data->state->a_date = data->state->q_date;
00480   data->state->a_cost += data->state->a_qty * res->getCost()
00481     * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable())
00482     / 3600.0;
00483 
00484   // Message
00485   if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00486     logger << indent(res->getLevel()) << "  Infinite resource '" << res << "' answers: "
00487     << (-data->state->a_qty) << "  " << data->state->a_date << endl;
00488 }
00489 
00490 
00491 }

Documentation generated for frePPLe by  doxygen