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 }