solverresource.cpp
Go to the documentation of this file.
00001 /***************************************************************************
00002   file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/tags/0.9.1/src/solver/solverresource.cpp $
00003   version : $LastChangedRevision: 1667 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2012-04-04 11:16:55 +0200 (Wed, 04 Apr 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 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   bool forced_late = data->state->forceLate;
00104 
00105   // Initialize the default reply
00106   data->state->a_date = data->state->q_date;
00107   data->state->a_qty = orig_q_qty;
00108   Date prevdate;
00109 
00110   // Loop for a valid location by using EARLIER capacity
00111   if (!data->state->forceLate)
00112     do
00113     {
00114       // Check the leadtime constraints
00115       prevdate = data->state->q_operationplan->getDates().getEnd();
00116       noRestore = data->state->forceLate;
00117 
00118       if (isLeadtimeConstrained() || isFenceConstrained())
00119         // Note that the check function can update the answered date and quantity
00120          if (data->constrainedPlanning && !checkOperationLeadtime(data->state->q_operationplan,*data,false))
00121          {
00122            // Operationplan violates the lead time and/or fence constraint
00123            noRestore = true;
00124            break;
00125          }
00126 
00127       // Check if this operation overloads the resource at its current time
00128       HasOverload = false;
00129       HasSetupOverload = false;
00130       Date earliestdate = data->state->q_operationplan->getDates().getStart();
00131       curdate = data->state->q_loadplan->getDate();
00132       curMax = data->state->q_loadplan->getMax(false);
00133       prevMax = curMax;
00134       for (cur = res->getLoadPlans().begin(data->state->q_loadplan);
00135         cur!=res->getLoadPlans().end() && cur->getDate()>=earliestdate;
00136         --cur)
00137       {
00138         // A change in the maximum capacity
00139         prevMax = curMax;
00140         if (cur->getType() == 4)
00141           curMax = cur->getMax(false);
00142 
00143         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00144         if (ldplan && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
00145           && ldplan->getOperationPlan()->getDates().overlap(data->state->q_operationplan->getDates()) > 0L
00146           && ldplan->getOperationPlan() != setupOpplan)
00147         {
00148           // Ongoing setup
00149           HasOverload = true;
00150           HasSetupOverload = true;
00151           break;
00152         }
00153 
00154         // Not interested if date doesn't change
00155         if (cur->getDate() == curdate) continue;
00156 
00157         if (cur->getOnhand() > prevMax + ROUNDING_ERROR)
00158         {
00159           // Overload: We are exceeding the limit!
00160           // At this point:
00161           //  - cur points to a loadplan where we exceed the capacity
00162           //  - curdate points to the latest date without overload
00163           //  - curdate != cur->getDate()
00164           HasOverload = true;
00165           break;
00166         }
00167         curdate = cur->getDate();
00168       }
00169 
00170       // Check if the setup operationplan overloads the resource or if a
00171       // different setup is already active on the resource.
00172       if (setupOpplan && !HasOverload)
00173       {
00174         earliestdate = setupOpplan->getDates().getStart();
00175         for (cur = res->getLoadPlans().begin(setupLdplan);
00176           cur!=res->getLoadPlans().end() && cur->getDate()>=earliestdate;
00177           --cur)
00178         {
00179           // A change in the maximum capacity
00180           prevMax = curMax;
00181           if (cur->getType() == 4)
00182             curMax = cur->getMax(false);
00183 
00184           // Must be same setup
00185           const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00186           if (ldplan
00187             && ldplan->getOperationPlan()->getDates().overlap(setupOpplan->getDates()) > 0L
00188             && ldplan->getSetup() != setupLdplan->getSetup())
00189           {
00190             HasOverload = true;
00191             HasSetupOverload = true;
00192             break;
00193           }
00194 
00195           // Not interested if date doesn't change
00196           if (cur->getDate() == curdate) continue;
00197           if (cur->getOnhand() > prevMax + ROUNDING_ERROR)
00198           {
00199             // Overload: We are exceeding the limit!
00200             // At this point:
00201             //  - cur points to a loadplan where we exceed the capacity
00202             //  - curdate points to the latest date without overload
00203             //  - curdate != cur->getDate()
00204             HasOverload = true;
00205             HasSetupOverload = true;
00206             break;
00207           }
00208           curdate = cur->getDate();
00209         }
00210       }
00211 
00212       // Try solving the overload by resizing the operationplan.
00213       // The capacity isn't overloaded in the time between "curdate" and
00214       // "current end of the operationplan". We can try to resize the
00215       // operationplan to fit in this time period...
00216       if (HasOverload && !HasSetupOverload
00217         && curdate < data->state->q_loadplan->getDate())
00218       {
00219         Date currentEnd = data->state->q_operationplan->getDates().getEnd();
00220         data->state->q_operationplan->getOperation()->setOperationPlanParameters(
00221           data->state->q_operationplan,
00222           currentOpplan.quantity,
00223           curdate,
00224           currentEnd
00225           );
00226         if (data->state->q_operationplan->getQuantity() > 0
00227           && data->state->q_operationplan->getDates().getEnd() <= currentEnd
00228           && data->state->q_operationplan->getDates().getStart() >= curdate)
00229         {
00230           // The squeezing did work!
00231           // The operationplan quantity is now reduced. The buffer solver will
00232           // ask again for the remaining short quantity, so we don't need to
00233           // bother about that here.
00234           HasOverload = false;
00235         }
00236         else
00237         {
00238           // It didn't work. Restore the original operationplan.
00239           // @todo this undoing is a performance bottleneck: trying to resize
00240           // and restoring the original are causing lots of updates in the
00241           // buffer and resource timelines...
00242           // We need an api that only checks the resizing.
00243           data->state->q_operationplan->getOperation()->setOperationPlanParameters(
00244             data->state->q_operationplan,
00245             currentOpplan.quantity,
00246             Date::infinitePast,
00247             currentEnd
00248             );
00249         }
00250       }
00251 
00252       // Try solving the overload by moving the operationplan to an earlier date
00253       if (HasOverload)
00254       {
00255         // Search backward in time for a period where there is no overload
00256         curMax = cur->getMax(false);
00257         prevMax = curMax;
00258         curdate = cur->getDate();
00259         for (; cur!=res->getLoadPlans().end() && curdate > currentOpplan.end - res->getMaxEarly(); --cur)
00260         {
00261           // A change in the maximum capacity
00262           prevMax = curMax;
00263           if (cur->getType() == 4) curMax = cur->getMax(false);
00264 
00265           // Ongoing setup
00266           const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00267           if (ldplan
00268             && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
00269             && ldplan->isStart()
00270             && ldplan->getOperationPlan()->getDates().getDuration() > 0L
00271             && ldplan->getOperationPlan() != setupOpplan)
00272             continue;
00273 
00274           // Not interested if date doesn't change
00275           if (cur->getDate() == curdate) continue;
00276 
00277           // We are below the max limit now.
00278           if (cur->getOnhand() < prevMax + ROUNDING_ERROR && curdate < prevdate)
00279             break;
00280           curdate = cur->getDate();
00281         }
00282         assert (curdate != prevdate);
00283 
00284         // We found a date where the load goes below the maximum
00285         // At this point:
00286         //  - curdate is a latest date where we are above the maximum
00287         //  - cur is the first loadplan where we are below the max
00288         if (cur != res->getLoadPlans().end() && curdate > currentOpplan.end - res->getMaxEarly())
00289         {
00290           // Move the operationplan
00291           data->state->q_operationplan->setEnd(curdate);
00292 
00293           // Verify the move is successfull
00294           if (data->state->q_operationplan->getDates().getEnd() > curdate)
00295             // If there isn't available time in the location calendar, the move
00296             // can fail.
00297             data->state->a_qty = 0.0;
00298           else if (data->constrainedPlanning && (isLeadtimeConstrained() || isFenceConstrained()))
00299             // Check the leadtime constraints after the move
00300             // Note that the check function can update the answered date
00301             // and quantity
00302             checkOperationLeadtime(data->state->q_operationplan,*data,false);
00303         }
00304         else
00305           // No earlier capacity found: get out of the loop
00306           data->state->a_qty = 0.0;
00307       }  // End of if-statement, solve by moving earlier
00308     }
00309     while (HasOverload && data->state->a_qty!=0.0);
00310 
00311   // Loop for a valid location by using LATER capacity
00312   // If the answered quantity is 0, the operationplan is moved into the 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 
00337       // Find how many uncommitted operationplans are loading the resource
00338       // before of the loadplan.
00339       // If the same resource is used multiple times in the supply path of a
00340       // demand we need to use only the capacity used by other demands. Otherwise
00341       // our estimate is of the feasible next date is too pessimistic.
00342       // If the operation is the same, the operationplans are at the same stage
00343       // in the supply path and we need to include these in our estimate of the
00344       // next date.
00345       double ignored = 0.0;
00346       for (cur = res->getLoadPlans().begin(); cur!=res->getLoadPlans().begin(data->state->q_loadplan); ++cur)
00347       {
00348         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00349         if (ldplan && !ldplan->getOperationPlan()->getIdentifier() 
00350           && ldplan->getOperationPlan()->getOperation()!=data->state->q_operationplan->getOperation() )
00351           ignored += ldplan->getQuantity();
00352       }
00353 
00354       for (cur=res->getLoadPlans().begin(data->state->q_loadplan);
00355           !(HasOverload && newDate) && cur != res->getLoadPlans().end(); )
00356       {
00357         // New maximum
00358         if (cur->getType() == 4)
00359           curMax = cur->getMax();
00360 
00361         /* @todo is this required?
00362         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00363         if (ldplan && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
00364           && ldplan->getOperationPlan()->getDates().getDuration() > 0L)
00365         {
00366           // Ongoing setup
00367           HasOverload = true;
00368           ++cur;
00369           continue;
00370         }
00371         */
00372         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00373         if (ldplan && !ldplan->getOperationPlan()->getIdentifier() 
00374           && ldplan->getOperationPlan()->getOperation()!=data->state->q_operationplan->getOperation())
00375           ignored += ldplan->getQuantity();
00376 
00377         // Only consider the last loadplan for a certain date
00378         const TimeLine<LoadPlan>::Event *loadpl = &*(cur++);
00379         if (cur!=res->getLoadPlans().end() && cur->getDate()==loadpl->getDate())
00380           continue;
00381         curOnhand = loadpl->getOnhand();
00382 
00383         // Check if overloaded
00384         if (loadpl->getOnhand() - ignored > curMax + ROUNDING_ERROR)
00385           // There is still a capacity problem
00386           HasOverload = true;
00387         else if (!HasOverload && loadpl->getDate() > data->state->q_operationplan->getDates().getEnd())
00388           // Break out of loop if no overload and we're beyond the
00389           // operationplan end date.
00390           break;
00391         else if (!newDate && loadpl->getDate()!=data->state->q_loadplan->getDate() && curMax >= fabs(loadpl->getQuantity()))
00392         {
00393           // We are below the max limit for the first time now.
00394           // This means that the previous date may be a proper start.
00395           newDate = loadpl->getDate();
00396         }
00397       }
00398 
00399       // Found a date with available capacity
00400       if (HasOverload && newDate)
00401       {
00402         // Multiple operations could be executed in parallel
00403         int parallelOps = static_cast<int>((curMax - curOnhand) / data->state->q_loadplan->getQuantity());
00404         if (parallelOps <= 0) parallelOps = 1;
00405         // Move the operationplan to the new date
00406         data->state->q_operationplan->getOperation()->setOperationPlanParameters(
00407             data->state->q_operationplan,
00408             (currentOpplan.quantity ? currentOpplan.quantity : 0.001) / parallelOps, // 0.001  @todo this calculation doesn't give minimization of the lateness
00409             newDate,
00410             Date::infinitePast
00411             );
00412         HasOverload = true;
00413         if (data->state->q_operationplan->getDates().getStart() < newDate)
00414           // Moving to the new date turns out to be infeasible! Give it up.
00415           // For instance, this can happen when the location calendar doesn't
00416           // have any up-time after the specified date.
00417           break;
00418       }
00419     }
00420     while (HasOverload && newDate);
00421     data->state->q_loadplan = old_q_loadplan;
00422 
00423     // Set the date where a next trial date can happen
00424     if (HasOverload)
00425       // No available capacity found anywhere in the horizon
00426       data->state->a_date = Date::infiniteFuture;
00427     else
00428       data->state->a_date = data->state->q_operationplan->getDates().getEnd();
00429 
00430     // Create a zero quantity reply
00431     data->state->a_qty = 0.0;
00432   }
00433 
00434   // Force ok in unconstrained plan
00435   if (!data->constrainedPlanning && data->state->a_qty == 0.0)
00436   {
00437     data->state->q_operationplan->restore(currentOpplan);
00438     data->state->a_date = data->state->q_date;
00439     data->state->a_qty = orig_q_qty;
00440   }
00441 
00442   // Increment the cost
00443   if (data->state->a_qty > 0.0)
00444   {
00445     // Resource usage
00446     data->state->a_cost += data->state->a_qty * res->getCost()
00447        * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable()) / 3600.0;
00448     // Setup penalty and cost
00449     if (setupOpplan)
00450     {
00451       data->state->a_cost += data->state->a_qty * res->getCost()
00452        * (setupOpplan->getDates().getDuration() - setupOpplan->getUnavailable()) / 3600.0;
00453       data->state->a_penalty += setupOpplan->getPenalty();
00454     }
00455     // Build-ahead penalty: 1 per day
00456     if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
00457       data->state->a_penalty +=
00458         (currentOpplan.end - data->state->q_operationplan->getDates().getEnd()) / 86400.0;
00459   }
00460 
00461   // Maintain the constraint list
00462   if (data->state->a_qty == 0.0 && data->logConstraints)
00463     data->planningDemand->getConstraints().push(
00464       ProblemCapacityOverload::metadata,
00465       res, currentOpplan.start, currentOpplan.end, orig_q_qty);
00466 
00467   // Message
00468   if (data->getSolver()->getLogLevel()>1)
00469   {
00470     logger << indent(res->getLevel()) << "   Resource '" << res << "' answers: "
00471       << data->state->a_qty << "  " << data->state->a_date;
00472     if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
00473       logger << " using earlier capacity "
00474         << data->state->q_operationplan->getDates().getEnd();
00475     if (data->state->a_qty>0.0 && data->state->q_operationplan->getQuantity() < currentOpplan.quantity)
00476       logger << " with reduced quantity " << data->state->q_operationplan->getQuantity();
00477     logger << endl;
00478   }
00479 
00480 }
00481 
00482 
00483 DECLARE_EXPORT void SolverMRP::solve(const ResourceInfinite* res, void* v)
00484 {
00485   SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
00486 
00487   // Call the user exit
00488   if (userexit_resource) userexit_resource.call(res, PythonObject(data->constrainedPlanning));
00489 
00490   // Message
00491   if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00492     logger << indent(res->getLevel()) << "  Infinite resource '" << res << "' is asked: "
00493     << (-data->state->q_qty) << "  " << data->state->q_operationplan->getDates() << endl;
00494 
00495   // @todo Need to make the setups feasible - move to earlier dates till max_early fence is reached
00496 
00497   // Reply whatever is requested, regardless of date and quantity.
00498   data->state->a_qty = data->state->q_qty;
00499   data->state->a_date = data->state->q_date;
00500   data->state->a_cost += data->state->a_qty * res->getCost()
00501     * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable())
00502     / 3600.0;
00503 
00504   // Message
00505   if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00506     logger << indent(res->getLevel()) << "  Infinite resource '" << res << "' answers: "
00507     << (-data->state->a_qty) << "  " << data->state->a_date << endl;
00508 }
00509 
00510 
00511 }

Documentation generated for frePPLe by  doxygen