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