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: 1505 $ $LastChangedBy: jdetaeye $ 00004 date : $LastChangedDate: 2011-08-26 18:55:08 +0200 (Fri, 26 Aug 2011) $ 00005 ***************************************************************************/ 00006 00007 /*************************************************************************** 00008 * * 00009 * Copyright (C) 2007-2011 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 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 }