solverresource.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/solverresource.cpp $
00003   version : $LastChangedRevision: 1204 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2010-03-20 15:17:28 +0100 (Sat, 20 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 
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           // Check the leadtime constraints after the move
00293           if (data->constrainedPlanning && (isLeadtimeConstrained() || isFenceConstrained()))
00294             // Note that the check function can update the answered date
00295             // and quantity
00296             checkOperationLeadtime(data->state->q_operationplan,*data,false);
00297         }
00298         else
00299           // No earlier capacity found: get out of the loop
00300           data->state->a_qty = 0.0;
00301       }  // End of if-statement, solve by moving earlier
00302     }
00303     while (HasOverload && data->state->a_qty!=0.0);
00304 
00305   // Loop for a valid location by using LATER capacity
00306   // If the answered quantity is 0, the operationplan is moved into the
00307   // past.
00308   // Or, the solver may be forced to produce a late reply.
00309   // In these cases we need to search for capacity at later dates.
00310   if (data->constrainedPlanning && (data->state->a_qty == 0.0 || data->state->forceLate))
00311   {
00312     // Put the operationplan back at its original end date
00313     if (!noRestore)
00314       data->state->q_operationplan->restore(currentOpplan);
00315 
00316     // Moving an operation earlier is driven by the ending loadplan,
00317     // while searching for later capacity is driven from the starting loadplan.
00318     LoadPlan* old_q_loadplan = data->state->q_loadplan;
00319     data->state->q_loadplan = data->state->q_loadplan->getOtherLoadPlan();
00320 
00321     // Loop to find a later date where the operationplan will fit
00322     Date newDate;
00323     do
00324     {
00325       // Search for a date where we go below the maximum load.
00326       // and verify whether there are still some overloads
00327       HasOverload = false;
00328       newDate = Date::infinitePast;
00329       curMax = data->state->q_loadplan->getMax();
00330       double curOnhand = data->state->q_loadplan->getOnhand();
00331       for (cur=res->getLoadPlans().begin(data->state->q_loadplan);
00332           !(HasOverload && newDate) && cur != res->getLoadPlans().end(); )
00333       {
00334         // New maximum
00335         if (cur->getType() == 4)
00336           curMax = cur->getMax();
00337 
00338         /* xxx
00339         const LoadPlan* ldplan = dynamic_cast<const LoadPlan*>(&*cur);
00340         if (ldplan && ldplan->getOperationPlan()->getOperation() == OperationSetup::setupoperation
00341           && ldplan->getOperationPlan()->getDates().getDuration() > 0L)
00342         {
00343           // Ongoing setup
00344           HasOverload = true;
00345           ++cur;
00346           continue;
00347         }
00348         */
00349 
00350         // Only consider the last loadplan for a certain date
00351         const TimeLine<LoadPlan>::Event *loadpl = &*(cur++);
00352         if (cur!=res->getLoadPlans().end() && cur->getDate()==loadpl->getDate())
00353           continue;
00354         curOnhand = loadpl->getOnhand();
00355 
00356         // Check if overloaded
00357         if (loadpl->getOnhand() > curMax + ROUNDING_ERROR)
00358           // There is still a capacity problem
00359           HasOverload = true;
00360         else if (!HasOverload && loadpl->getDate() > data->state->q_operationplan->getDates().getEnd())
00361           // Break out of loop if no overload and we're beyond the
00362           // operationplan end date.
00363           break;
00364         else if (!newDate && loadpl->getDate()!=data->state->q_loadplan->getDate() && curMax >= fabs(loadpl->getQuantity()))
00365         {
00366           // We are below the max limit for the first time now.
00367           // This means that the previous date may be a proper start.
00368           newDate = loadpl->getDate();
00369         }
00370       }
00371 
00372       // Found a date with available capacity
00373       if (HasOverload && newDate)
00374       {
00375         // Multiple operations could be executed in parallel
00376         int parallelOps = static_cast<int>((curMax - curOnhand) / data->state->q_loadplan->getQuantity());
00377         if (parallelOps <= 0) parallelOps = 1;
00378         // Move the operationplan to the new date
00379         data->state->q_operationplan->getOperation()->setOperationPlanParameters(
00380             data->state->q_operationplan,
00381             currentOpplan.quantity / parallelOps, // 0.001  @todo this calculation doesn't give minimization of the lateness
00382             newDate,
00383             Date::infinitePast
00384             );
00385         HasOverload = true;
00386         if (data->state->q_operationplan->getDates().getStart() < newDate)
00387           // Moving to the new date turns out to be infeasible! Give it up.
00388           // For instance, this can happen when the location calendar doesn't 
00389           // have any up-time after the specified date.
00390           break;
00391       }
00392     }
00393     while (HasOverload && newDate);
00394     data->state->q_loadplan = old_q_loadplan;
00395 
00396     // Set the date where a next trial date can happen
00397     if (HasOverload)
00398       // No available capacity found anywhere in the horizon
00399       data->state->a_date = Date::infiniteFuture;
00400     else
00401       data->state->a_date = data->state->q_operationplan->getDates().getEnd();
00402 
00403     // Create a zero quantity reply
00404     data->state->a_qty = 0.0;
00405   }
00406 
00407   // Force ok in unconstrained plan
00408   if (!data->constrainedPlanning && data->state->a_qty == 0.0)
00409   {
00410     data->state->q_operationplan->restore(currentOpplan);
00411     data->state->a_date = data->state->q_date;
00412     data->state->a_qty = orig_q_qty;
00413   }
00414 
00415   // Increment the cost
00416   if (data->state->a_qty > 0.0)
00417   {
00418     // Resource usage
00419     data->state->a_cost += data->state->a_qty * res->getCost()
00420        * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable()) / 3600.0;
00421     // Setup penalty and cost
00422     if (setupOpplan)
00423     {
00424       data->state->a_cost += data->state->a_qty * res->getCost()
00425        * (setupOpplan->getDates().getDuration() - setupOpplan->getUnavailable()) / 3600.0;
00426       data->state->a_penalty += setupOpplan->getPenalty();
00427     }
00428     // Build-ahead penalty: 1 per day
00429     if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
00430       data->state->a_penalty += 
00431         (currentOpplan.end - data->state->q_operationplan->getDates().getEnd()) / 86400.0;
00432   }
00433   else if (data->state->q_operationplan->getQuantity() > 0.0)
00434     data->state->q_operationplan->setQuantity(0.0);
00435 if (userexit_resource) userexit_resource.call(res, PythonObject(data->constrainedPlanning));
00436   // Message
00437   if (data->getSolver()->getLogLevel()>1)
00438   {
00439     logger << indent(res->getLevel()) << "   Resource '" << res << "' answers: "
00440       << data->state->a_qty << "  " << data->state->a_date;
00441     if (currentOpplan.end > data->state->q_operationplan->getDates().getEnd())
00442       logger << " using earlier capacity "
00443         << data->state->q_operationplan->getDates().getEnd();
00444     if (data->state->a_qty>0.0 && data->state->q_operationplan->getQuantity() < currentOpplan.quantity)
00445       logger << " with reduced quantity " << data->state->q_operationplan->getQuantity();
00446     logger << endl;
00447   }
00448 
00449 }
00450 
00451 
00452 DECLARE_EXPORT void SolverMRP::solve(const ResourceInfinite* res, void* v)
00453 {
00454   SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
00455 
00456   // Call the user exit
00457   if (userexit_resource) userexit_resource.call(res, PythonObject(data->constrainedPlanning));
00458 
00459   // Message
00460   if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00461     logger << indent(res->getLevel()) << "  Infinite resource '" << res << "' is asked: "
00462     << (-data->state->q_qty) << "  " << data->state->q_operationplan->getDates() << endl;
00463 
00464   // TODO xxx Need to make the setups feasible - move to earlier dates till max_early fence is reached
00465 
00466   // Reply whatever is requested, regardless of date and quantity.
00467   data->state->a_qty = data->state->q_qty;
00468   data->state->a_date = data->state->q_date;
00469   data->state->a_cost += data->state->a_qty * res->getCost()
00470     * (data->state->q_operationplan->getDates().getDuration() - data->state->q_operationplan->getUnavailable())
00471     / 3600.0;
00472 
00473   // Message
00474   if (data->getSolver()->getLogLevel()>1 && data->state->q_qty < 0)
00475     logger << indent(res->getLevel()) << "  Infinite resource '" << res << "' answers: "
00476     << (-data->state->a_qty) << "  " << data->state->a_date << endl;
00477 }
00478 
00479 
00480 }

Generated on 21 Mar 2010 for frePPLe by  doxygen 1.6.1