solveroperation.cpp
Go to the documentation of this file.
00001 /*************************************************************************** 00002 file : $URL: http://svn.code.sf.net/p/frepple/code/trunk/src/solver/solveroperation.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 namespace frepple 00030 { 00031 00032 00033 DECLARE_EXPORT void SolverMRP::checkOperationCapacity 00034 (OperationPlan* opplan, SolverMRP::SolverMRPdata& data) 00035 { 00036 unsigned short constrainedLoads = 0; 00037 for (OperationPlan::LoadPlanIterator h=opplan->beginLoadPlans(); 00038 h!=opplan->endLoadPlans(); ++h) 00039 if (h->getResource()->getType() != *(ResourceInfinite::metadata) 00040 && h->isStart() && h->getLoad()->getQuantity() != 0.0) 00041 { 00042 if (++constrainedLoads > 1) break; 00043 } 00044 DateRange orig; 00045 Date minimumEndDate = opplan->getDates().getEnd(); 00046 bool backuplogconstraints = data.logConstraints; 00047 bool backupForceLate = data.state->forceLate; 00048 bool recheck, first; 00049 double loadqty = 1.0; 00050 00051 // Loop through all loadplans, and solve for the resource. 00052 // This may move an operationplan early or late. 00053 do 00054 { 00055 orig = opplan->getDates(); 00056 recheck = false; 00057 first = true; 00058 for (OperationPlan::LoadPlanIterator h=opplan->beginLoadPlans(); 00059 h!=opplan->endLoadPlans() && opplan->getDates()==orig; ++h) 00060 { 00061 if (h->getLoad()->getQuantity() == 0.0 || h->getQuantity() == 0.0) 00062 // Empty load or loadplan (eg when load is not effective) 00063 continue; 00064 // Call the load solver - which will call the resource solver. 00065 data.state->q_operationplan = opplan; 00066 data.state->q_loadplan = &*h; 00067 data.state->q_qty = h->getQuantity(); 00068 loadqty = h->getQuantity(); 00069 data.state->q_date = h->getDate(); 00070 h->getLoad()->solve(*this,&data); 00071 if (opplan->getDates()!=orig) 00072 { 00073 if (data.state->a_qty==0) 00074 // One of the resources is late. We want to prevent that other resources 00075 // are trying to pull in the operationplan again. It can only be delayed 00076 // from now on in this loop. 00077 data.state->forceLate = true; 00078 if (!first) recheck = true; 00079 } 00080 first = false; 00081 } 00082 data.logConstraints = false; // Only first loop collects constraint info 00083 } 00084 // Imagine there are multiple loads. As soon as one of them is moved, we 00085 // need to redo the capacity check for the ones we already checked. 00086 // Repeat until no load has touched the opplan, or till proven infeasible. 00087 // No need to reloop if there is only a single load (= 2 loadplans) 00088 while (constrainedLoads>1 && opplan->getDates()!=orig 00089 && ((data.state->a_qty==0.0 && data.state->a_date > minimumEndDate) 00090 || recheck)); 00091 // TODO doesn't this loop increment a_penalty incorrectly??? 00092 00093 // Restore original flags 00094 data.logConstraints = backuplogconstraints; // restore the original value 00095 data.state->forceLate = backupForceLate; 00096 00097 // In case of a zero reply, we resize the operationplan to 0 right away. 00098 // This is required to make sure that the buffer inventory profile also 00099 // respects this answer. 00100 if (data.state->a_qty==0.0 && opplan->getQuantity() > 0.0) 00101 opplan->setQuantity(0.0); 00102 } 00103 00104 00105 DECLARE_EXPORT bool SolverMRP::checkOperation 00106 (OperationPlan* opplan, SolverMRP::SolverMRPdata& data) 00107 { 00108 // The default answer... 00109 data.state->a_date = Date::infiniteFuture; 00110 data.state->a_qty = data.state->q_qty; 00111 00112 // Handle unavailable time. 00113 // Note that this unavailable time is checked also in an unconstrained plan. 00114 // This means that also an unconstrained plan can plan demand late! 00115 if (opplan->getQuantity() == 0.0) 00116 { 00117 // It is possible that the operation could not be created properly. 00118 // This happens when the operation is not available for enough time. 00119 // Eg. A fixed time operation needs 10 days on jan 20 on an operation 00120 // that is only available only 2 days since the start of the horizon. 00121 // Resize to the minimum quantity 00122 opplan->setQuantity(0.0001,false); 00123 // Move to the earliest start date 00124 opplan->setStart(Plan::instance().getCurrent()); 00125 // Pick up the earliest date we can reply back 00126 data.state->a_date = opplan->getDates().getEnd(); 00127 data.state->a_qty = 0.0; 00128 return false; 00129 } 00130 00131 // Check the leadtime constraints 00132 if (data.constrainedPlanning && !checkOperationLeadtime(opplan,data,true)) 00133 // This operationplan is a wreck. It is impossible to make it meet the 00134 // leadtime constraints 00135 return false; 00136 00137 // Set a bookmark in the command list. 00138 CommandManager::Bookmark* topcommand = data.setBookmark(); 00139 00140 // Temporary variables 00141 DateRange orig_dates = opplan->getDates(); 00142 bool okay = true; 00143 Date a_date; 00144 double a_qty; 00145 Date orig_q_date = data.state->q_date; 00146 double orig_opplan_qty = data.state->q_qty; 00147 double q_qty_Flow; 00148 Date q_date_Flow; 00149 bool incomplete; 00150 bool tmp_forceLate = data.state->forceLate; 00151 bool isPlannedEarly; 00152 DateRange matnext; 00153 00154 // Loop till everything is okay. During this loop the quanity and date of the 00155 // operationplan can be updated, but it cannot be split or deleted. 00156 data.state->forceLate = false; 00157 do 00158 { 00159 if (isCapacityConstrained()) 00160 { 00161 // Verify the capacity. This can move the operationplan early or late. 00162 checkOperationCapacity(opplan,data); 00163 // Return false if no capacity is available 00164 if (data.state->a_qty==0.0) return false; 00165 } 00166 00167 // Check material 00168 data.state->q_qty = opplan->getQuantity(); 00169 data.state->q_date = opplan->getDates().getEnd(); 00170 a_qty = opplan->getQuantity(); 00171 a_date = data.state->q_date; 00172 incomplete = false; 00173 matnext.setStart(Date::infinitePast); 00174 matnext.setEnd(Date::infiniteFuture); 00175 00176 // Loop through all flowplans // @todo need some kind of coordination run here!!! see test alternate_flow_1 00177 for (OperationPlan::FlowPlanIterator g=opplan->beginFlowPlans(); 00178 g!=opplan->endFlowPlans(); ++g) 00179 if (g->getFlow()->isConsumer()) 00180 { 00181 // Switch back to the main alternate if this flowplan was already // @todo is this really required? If yes, in this place? 00182 // planned on an alternate 00183 if (g->getFlow()->getAlternate()) 00184 g->setFlow(g->getFlow()->getAlternate()); 00185 00186 // Trigger the flow solver, which will call the buffer solver 00187 data.state->q_flowplan = &*g; 00188 q_qty_Flow = - data.state->q_flowplan->getQuantity(); // @todo flow quantity can change when using alternate flows -> move to flow solver! 00189 q_date_Flow = data.state->q_flowplan->getDate(); 00190 g->getFlow()->solve(*this,&data); 00191 00192 // Validate the answered quantity 00193 if (data.state->a_qty < q_qty_Flow) 00194 { 00195 // Update the opplan, which is required to (1) update the flowplans 00196 // and to (2) take care of lot sizing constraints of this operation. 00197 g->setQuantity(-data.state->a_qty, true); 00198 a_qty = opplan->getQuantity(); 00199 incomplete = true; 00200 00201 // Validate the answered date of the most limiting flowplan. 00202 // Note that the delay variable only reflects the delay due to 00203 // material constraints. If the operationplan is moved early or late 00204 // for capacity constraints, this is not included. 00205 if (data.state->a_date < Date::infiniteFuture) 00206 { 00207 OperationPlanState at = opplan->getOperation()->setOperationPlanParameters( 00208 opplan, 0.01, data.state->a_date, Date::infinitePast, false, false 00209 ); 00210 if (at.end < matnext.getEnd()) matnext = DateRange(at.start, at.end); 00211 //xxxif (matnext.getEnd() <= orig_q_date) logger << "STRANGE" << matnext << " " << orig_q_date << " " << at.second << " " << opplan->getQuantity() << endl; 00212 } 00213 00214 // Jump out of the loop if the answered quantity is 0. 00215 if (a_qty <= ROUNDING_ERROR) 00216 { 00217 // @TODO disabled To speed up the planning the constraining flow is moved up a 00218 // position in the list of flows. It'll thus be checked earlier 00219 // when this operation is asked again 00220 //const_cast<Operation::flowlist&>(g->getFlow()->getOperation()->getFlows()).promote(g->getFlow()); 00221 // There is absolutely no need to check other flowplans if the 00222 // operationplan quantity is already at 0. 00223 break; 00224 } 00225 } 00226 else if (data.state->a_qty >+ q_qty_Flow + ROUNDING_ERROR) 00227 // Never answer more than asked. 00228 // The actual operationplan could be bigger because of lot sizing. 00229 a_qty = - q_qty_Flow / g->getFlow()->getQuantity(); 00230 } 00231 00232 isPlannedEarly = opplan->getDates().getEnd() < orig_dates.getEnd(); 00233 00234 if (matnext.getEnd() != Date::infiniteFuture && a_qty <= ROUNDING_ERROR 00235 && matnext.getEnd() <= data.state->q_date_max && matnext.getEnd() > orig_q_date) 00236 { 00237 // The reply is 0, but the next-date is still less than the maximum 00238 // ask date. In this case we will violate the post-operation -soft- 00239 // constraint. 00240 data.state->q_date = matnext.getEnd(); 00241 orig_q_date = data.state->q_date; 00242 data.state->q_qty = orig_opplan_qty; 00243 data.state->a_date = Date::infiniteFuture; 00244 data.state->a_qty = data.state->q_qty; 00245 opplan->getOperation()->setOperationPlanParameters( 00246 opplan, orig_opplan_qty, Date::infinitePast, matnext.getEnd() 00247 ); 00248 okay = false; 00249 // Pop actions from the command "stack" in the command list 00250 data.rollback(topcommand); 00251 // Echo a message 00252 if (data.getSolver()->getLogLevel()>1) 00253 logger << indent(opplan->getOperation()->getLevel()) 00254 << " Retrying new date." << endl; 00255 } 00256 else if (matnext.getEnd() != Date::infiniteFuture && a_qty <= ROUNDING_ERROR 00257 && matnext.getStart() < a_date) 00258 { 00259 // The reply is 0, but the next-date is not too far out. 00260 // If the operationplan would fit in a smaller timeframe we can potentially 00261 // create a non-zero reply... 00262 // Resize the operationplan 00263 opplan->getOperation()->setOperationPlanParameters( 00264 opplan, orig_opplan_qty, matnext.getStart(), 00265 a_date 00266 ); 00267 if (opplan->getDates().getStart() >= matnext.getStart() 00268 && opplan->getDates().getEnd() <= a_date 00269 && opplan->getQuantity() > ROUNDING_ERROR) 00270 { 00271 // It worked 00272 orig_dates = opplan->getDates(); 00273 data.state->q_date = orig_dates.getEnd(); 00274 data.state->q_qty = opplan->getQuantity(); 00275 data.state->a_date = Date::infiniteFuture; 00276 data.state->a_qty = data.state->q_qty; 00277 okay = false; 00278 // Pop actions from the command stack in the command list 00279 data.rollback(topcommand); 00280 // Echo a message 00281 if (data.getSolver()->getLogLevel()>1) 00282 logger << indent(opplan->getOperation()->getLevel()) 00283 << " Retrying with a smaller quantity: " 00284 << opplan->getQuantity() << endl; 00285 } 00286 else 00287 { 00288 // It didn't work 00289 opplan->setQuantity(0); 00290 okay = true; 00291 } 00292 } 00293 else 00294 okay = true; 00295 } 00296 while (!okay); // Repeat the loop if the operation was moved and the 00297 // feasibility needs to be rechecked. 00298 00299 if (a_qty <= ROUNDING_ERROR && !data.state->forceLate 00300 && isPlannedEarly 00301 && matnext.getStart() != Date::infiniteFuture 00302 && matnext.getStart() != Date::infinitePast 00303 && (data.constrainedPlanning && isCapacityConstrained())) 00304 { 00305 // The operationplan was moved early (because of a resource constraint) 00306 // and we can't properly trust the reply date in such cases... 00307 // We want to enforce rechecking the next date. 00308 if (data.getSolver()->getLogLevel()>1) 00309 logger << indent(opplan->getOperation()->getLevel()) 00310 << " Recheck capacity" << endl; 00311 00312 // Move the operationplan to the next date where the material is feasible 00313 opplan->getOperation()->setOperationPlanParameters 00314 (opplan, orig_opplan_qty, 00315 matnext.getStart()>orig_dates.getStart() ? matnext.getStart() : orig_dates.getStart(), 00316 Date::infinitePast); 00317 00318 // Move the operationplan to a later date where it is feasible. 00319 data.state->forceLate = true; 00320 checkOperationCapacity(opplan,data); 00321 00322 // Reply of this function 00323 a_qty = 0.0; 00324 matnext.setEnd(opplan->getDates().getEnd()); 00325 } 00326 00327 // Compute the final reply 00328 data.state->a_date = incomplete ? matnext.getEnd() : Date::infiniteFuture; 00329 data.state->a_qty = a_qty; 00330 data.state->forceLate = tmp_forceLate; 00331 if (a_qty > ROUNDING_ERROR) 00332 return true; 00333 else 00334 { 00335 // Undo the plan 00336 data.rollback(topcommand); 00337 return false; 00338 } 00339 } 00340 00341 00342 DECLARE_EXPORT bool SolverMRP::checkOperationLeadtime 00343 (OperationPlan* opplan, SolverMRP::SolverMRPdata& data, bool extra) 00344 { 00345 // No lead time constraints 00346 if (!data.constrainedPlanning || (!isFenceConstrained() && !isLeadtimeConstrained())) 00347 return true; 00348 00349 // Compute offset from the current date: A fence problem uses the release 00350 // fence window, while a leadtimeconstrained constraint has an offset of 0. 00351 // If both constraints apply, we need the bigger of the two (since it is the 00352 // most constraining date. 00353 Date threshold = Plan::instance().getCurrent(); 00354 if (isFenceConstrained() 00355 && !(isLeadtimeConstrained() && opplan->getOperation()->getFence()<0L)) 00356 threshold += opplan->getOperation()->getFence(); 00357 00358 // Check the setup operationplan 00359 OperationPlanState original(opplan); 00360 bool ok = true; 00361 bool checkSetup = true; 00362 00363 // If there are alternate loads we take the best case and assume that 00364 // at least one of those can give us a zero-time setup. 00365 // When evaluating the leadtime when solving for capacity we don't use 00366 // this assumption. The resource solver takes care of the constraints. 00367 if (extra && isCapacityConstrained()) 00368 for (Operation::loadlist::const_iterator j = opplan->getOperation()->getLoads().begin(); 00369 j != opplan->getOperation()->getLoads().end(); ++j) 00370 if (j->hasAlternates()) 00371 { 00372 checkSetup = false; 00373 break; 00374 } 00375 if (checkSetup) 00376 { 00377 OperationPlan::iterator i(opplan); 00378 if (i != opplan->end() 00379 && i->getOperation() == OperationSetup::setupoperation 00380 && i->getDates().getStart() < threshold) 00381 { 00382 // The setup operationplan is violating the lead time and/or fence 00383 // constraint. We move it to start on the earliest allowed date, 00384 // which automatically also moves the owner operationplan. 00385 i->setStart(threshold); 00386 threshold = i->getDates().getEnd(); 00387 ok = false; 00388 } 00389 } 00390 00391 // Compare the operation plan start with the threshold date 00392 if (ok && opplan->getDates().getStart() >= threshold) 00393 // There is no problem 00394 return true; 00395 00396 // Compute how much we can supply in the current timeframe. 00397 // In other words, we try to resize the operation quantity to fit the 00398 // available timeframe: used for e.g. time-per operations 00399 // Note that we allow the complete post-operation time to be eaten 00400 if (extra) 00401 // Leadtime check during operation resolver 00402 opplan->getOperation()->setOperationPlanParameters( 00403 opplan, opplan->getQuantity(), 00404 threshold, 00405 original.end + opplan->getOperation()->getPostTime(), 00406 false 00407 ); 00408 else 00409 // Leadtime check during capacity resolver 00410 opplan->getOperation()->setOperationPlanParameters( 00411 opplan, opplan->getQuantity(), 00412 threshold, 00413 original.end, 00414 true 00415 ); 00416 00417 // Check the result of the resize 00418 if (opplan->getDates().getStart() >= threshold 00419 && (!extra || opplan->getDates().getEnd() <= data.state->q_date_max) 00420 && opplan->getQuantity() > ROUNDING_ERROR) 00421 { 00422 // Resizing did work! The operation now fits within constrained limits 00423 data.state->a_qty = opplan->getQuantity(); 00424 data.state->a_date = opplan->getDates().getEnd(); 00425 // Acknowledge creation of operationplan 00426 return true; 00427 } 00428 else 00429 { 00430 // This operation doesn't fit at all within the constrained window. 00431 data.state->a_qty = 0.0; 00432 // Resize to the minimum quantity 00433 if (opplan->getQuantity() + ROUNDING_ERROR < opplan->getOperation()->getSizeMinimum()) 00434 opplan->setQuantity(0.0001,false); 00435 // Move to the earliest start date 00436 opplan->setStart(threshold); 00437 // Pick up the earliest date we can reply back 00438 data.state->a_date = opplan->getDates().getEnd(); 00439 // Set the quantity to 0 (to make sure the buffer doesn't see the supply). 00440 opplan->setQuantity(0.0); 00441 00442 // Log the constraint 00443 if (data.logConstraints) 00444 data.planningDemand->getConstraints().push( 00445 (threshold == Plan::instance().getCurrent()) ? 00446 ProblemBeforeCurrent::metadata : 00447 ProblemBeforeFence::metadata, 00448 opplan->getOperation(), original.start, original.end, 00449 original.quantity 00450 ); 00451 00452 // Deny creation of the operationplan 00453 return false; 00454 } 00455 } 00456 00457 00458 DECLARE_EXPORT void SolverMRP::solve(const Operation* oper, void* v) 00459 { 00460 // Make sure we have a valid operation 00461 assert(oper); 00462 00463 SolverMRPdata* data = static_cast<SolverMRPdata*>(v); 00464 OperationPlan *z; 00465 00466 // Call the user exit 00467 if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning)); 00468 00469 // Find the flow for the quantity-per. This can throw an exception if no 00470 // valid flow can be found. 00471 double flow_qty_per = 1.0; 00472 if (data->state->curBuffer) 00473 { 00474 Flow* f = oper->findFlow(data->state->curBuffer, data->state->q_date); 00475 if (f && f->getQuantity()>0.0) 00476 flow_qty_per = f->getQuantity(); 00477 else 00478 // The producing operation doesn't have a valid flow into the current 00479 // buffer. Either it is missing or it is producing a negative quantity. 00480 throw DataException("Invalid producing operation '" + oper->getName() 00481 + "' for buffer '" + data->state->curBuffer->getName() + "'"); 00482 } 00483 00484 // Message 00485 if (data->getSolver()->getLogLevel()>1) 00486 logger << indent(oper->getLevel()) << " Operation '" << oper->getName() 00487 << "' is asked: " << data->state->q_qty << " " << data->state->q_date << endl; 00488 00489 // Find the current list of constraints 00490 Problem* topConstraint = data->planningDemand->getConstraints().top(); 00491 double originalqty = data->state->q_qty; 00492 00493 // Subtract the post-operation time 00494 Date prev_q_date_max = data->state->q_date_max; 00495 data->state->q_date_max = data->state->q_date; 00496 data->state->q_date -= oper->getPostTime(); 00497 00498 // Create the operation plan. 00499 if (data->state->curOwnerOpplan) 00500 { 00501 // There is already an owner and thus also an owner command 00502 assert(!data->state->curDemand); 00503 z = oper->createOperationPlan( 00504 data->state->q_qty / flow_qty_per, 00505 Date::infinitePast, data->state->q_date, data->state->curDemand, 00506 data->state->curOwnerOpplan, 0 00507 ); 00508 } 00509 else 00510 { 00511 // There is no owner operationplan yet. We need a new command. 00512 CommandCreateOperationPlan *a = 00513 new CommandCreateOperationPlan( 00514 oper, data->state->q_qty / flow_qty_per, 00515 Date::infinitePast, data->state->q_date, data->state->curDemand, 00516 data->state->curOwnerOpplan 00517 ); 00518 data->state->curDemand = NULL; 00519 a->getOperationPlan()->setMotive(data->state->motive); 00520 z = a->getOperationPlan(); 00521 data->add(a); 00522 } 00523 assert(z); 00524 00525 // Check the constraints 00526 data->getSolver()->checkOperation(z,*data); 00527 data->state->q_date_max = prev_q_date_max; 00528 00529 // Multiply the operation reqply with the flow quantity to get a final reply 00530 if (data->state->curBuffer) data->state->a_qty *= flow_qty_per; 00531 00532 // Ignore any constraints if we get a complete reply. 00533 // Sometimes constraints are flagged due to a pre- or post-operation time. 00534 // Such constraints ultimately don't result in lateness and can be ignored. 00535 if (data->state->a_qty >= originalqty - ROUNDING_ERROR) 00536 data->planningDemand->getConstraints().pop(topConstraint); 00537 00538 // Check positive reply quantity 00539 assert(data->state->a_qty >= 0); 00540 00541 // Increment the cost 00542 if (data->state->a_qty > 0.0) 00543 data->state->a_cost += z->getQuantity() * oper->getCost(); 00544 00545 // Message 00546 if (data->getSolver()->getLogLevel()>1) 00547 logger << indent(oper->getLevel()) << " Operation '" << oper->getName() 00548 << "' answers: " << data->state->a_qty << " " << data->state->a_date 00549 << " " << data->state->a_cost << " " << data->state->a_penalty << endl; 00550 } 00551 00552 00553 // No need to take post- and pre-operation times into account 00554 DECLARE_EXPORT void SolverMRP::solve(const OperationRouting* oper, void* v) 00555 { 00556 SolverMRPdata* data = static_cast<SolverMRPdata*>(v); 00557 00558 // Call the user exit 00559 if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning)); 00560 00561 // Message 00562 if (data->getSolver()->getLogLevel()>1) 00563 logger << indent(oper->getLevel()) << " Routing operation '" << oper->getName() 00564 << "' is asked: " << data->state->q_qty << " " << data->state->q_date << endl; 00565 00566 // Find the total quantity to flow into the buffer. 00567 // Multiple suboperations can all produce into the buffer. 00568 double flow_qty = 1.0; 00569 if (data->state->curBuffer) 00570 { 00571 flow_qty = 0.0; 00572 Flow *f = oper->findFlow(data->state->curBuffer, data->state->q_date); 00573 if (f) flow_qty += f->getQuantity(); 00574 for (Operation::Operationlist::const_iterator 00575 e = oper->getSubOperations().begin(); 00576 e != oper->getSubOperations().end(); 00577 ++e) 00578 { 00579 f = (*e)->findFlow(data->state->curBuffer, data->state->q_date); 00580 if (f) flow_qty += f->getQuantity(); 00581 } 00582 if (flow_qty <= 0.0) 00583 throw DataException("Invalid producing operation '" + oper->getName() 00584 + "' for buffer '" + data->state->curBuffer->getName() + "'"); 00585 } 00586 // Because we already took care of it... @todo not correct if the suboperation is again a owning operation 00587 data->state->curBuffer = NULL; 00588 double a_qty(data->state->q_qty / flow_qty); 00589 00590 // Create the top operationplan 00591 CommandCreateOperationPlan *a = new CommandCreateOperationPlan( 00592 oper, a_qty, Date::infinitePast, 00593 data->state->q_date, data->state->curDemand, data->state->curOwnerOpplan, false 00594 ); 00595 data->state->curDemand = NULL; 00596 a->getOperationPlan()->setMotive(data->state->motive); 00597 00598 // Make sure the subopplans know their owner & store the previous value 00599 OperationPlan *prev_owner_opplan = data->state->curOwnerOpplan; 00600 data->state->curOwnerOpplan = a->getOperationPlan(); 00601 00602 // Loop through the steps 00603 Date max_Date; 00604 TimePeriod delay; 00605 Date top_q_date(data->state->q_date); 00606 Date q_date; 00607 for (Operation::Operationlist::const_reverse_iterator 00608 e = oper->getSubOperations().rbegin(); 00609 e != oper->getSubOperations().rend() && a_qty > 0.0; 00610 ++e) 00611 { 00612 // Plan the next step 00613 data->state->q_qty = a_qty; 00614 data->state->q_date = data->state->curOwnerOpplan->getDates().getStart(); 00615 q_date = data->state->q_date; 00616 (*e)->solve(*this,v); // @todo if the step itself has child operations, the curOwnerOpplan field is changed here!!! 00617 a_qty = data->state->a_qty; 00618 00619 // Update the top operationplan 00620 data->state->curOwnerOpplan->setQuantity(a_qty,true); 00621 00622 // Maximum for the next date 00623 if (data->state->a_date != Date::infiniteFuture) 00624 { 00625 if (delay < data->state->a_date - q_date) 00626 delay = data->state->a_date - q_date; 00627 OperationPlanState at = data->state->curOwnerOpplan->getOperation()->setOperationPlanParameters( 00628 data->state->curOwnerOpplan, 0.01, //data->state->curOwnerOpplan->getQuantity(), 00629 data->state->a_date, Date::infinitePast, false, false 00630 ); 00631 if (at.end > max_Date) max_Date = at.end; 00632 } 00633 } 00634 00635 // Check the flows and loads on the top operationplan. 00636 // This can happen only after the suboperations have been dealt with 00637 // because only now we know how long the operation lasts in total. 00638 // Solving for the top operationplan can resize and move the steps that are 00639 // in the routing! 00640 /** @todo moving routing opplan doesn't recheck for feasibility of steps... */ 00641 data->state->curOwnerOpplan->createFlowLoads(); 00642 if (data->state->curOwnerOpplan->getQuantity() > 0.0) 00643 { 00644 data->state->q_qty = a_qty; 00645 data->state->q_date = data->state->curOwnerOpplan->getDates().getEnd(); 00646 data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data); 00647 a_qty = data->state->a_qty; 00648 // The reply date is the combination of the reply date of all steps and the 00649 // reply date of the top operationplan. 00650 if (data->state->a_date > max_Date && data->state->a_date != Date::infiniteFuture) 00651 max_Date = data->state->a_date; 00652 } 00653 data->state->a_date = (max_Date ? max_Date : Date::infiniteFuture); 00654 if (data->state->a_date < data->state->q_date) 00655 data->state->a_date = data->state->q_date; 00656 00657 // Multiply the operationplan quantity with the flow quantity to get the 00658 // final reply quantity 00659 data->state->a_qty = a_qty * flow_qty; 00660 00661 // Add to the list (even if zero-quantity!) 00662 if (!prev_owner_opplan) data->add(a); 00663 00664 // Increment the cost 00665 if (data->state->a_qty > 0.0) 00666 data->state->a_cost += data->state->curOwnerOpplan->getQuantity() * oper->getCost(); 00667 00668 // Make other operationplans don't take this one as owner any more. 00669 // We restore the previous owner, which could be NULL. 00670 data->state->curOwnerOpplan = prev_owner_opplan; 00671 00672 // Check positive reply quantity 00673 assert(data->state->a_qty >= 0); 00674 00675 if (data->state->a_date <= top_q_date && delay > TimePeriod(0L)) 00676 // At least one of the steps is late, but the reply date at the overall routing level is not late. 00677 // This causes trouble, so we enforce a lateness of at least one hour. @todo not very cool/performant/generic... 00678 data->state->a_date = top_q_date + delay; // TimePeriod(3600L); 00679 00680 // Check reply date is later than requested date 00681 assert(data->state->a_date >= data->state->q_date); 00682 00683 // Message 00684 if (data->getSolver()->getLogLevel()>1) 00685 logger << indent(oper->getLevel()) << " Routing operation '" << oper->getName() 00686 << "' answers: " << data->state->a_qty << " " << data->state->a_date << " " 00687 << data->state->a_cost << " " << data->state->a_penalty << endl; 00688 } 00689 00690 00691 // No need to take post- and pre-operation times into account 00692 // @todo This method should only be allowed to create 1 operationplan 00693 DECLARE_EXPORT void SolverMRP::solve(const OperationAlternate* oper, void* v) 00694 { 00695 SolverMRPdata *data = static_cast<SolverMRPdata*>(v); 00696 Date origQDate = data->state->q_date; 00697 double origQqty = data->state->q_qty; 00698 Buffer *buf = data->state->curBuffer; 00699 Demand *d = data->state->curDemand; 00700 00701 // Call the user exit 00702 if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning)); 00703 00704 unsigned int loglevel = data->getSolver()->getLogLevel(); 00705 SearchMode search = oper->getSearch(); 00706 00707 // Message 00708 if (loglevel>1) 00709 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 00710 << "' is asked: " << data->state->q_qty << " " << data->state->q_date << endl; 00711 00712 // Make sure sub-operationplans know their owner & store the previous value 00713 OperationPlan *prev_owner_opplan = data->state->curOwnerOpplan; 00714 00715 // Find the flow into the requesting buffer for the quantity-per 00716 double top_flow_qty_per = 0.0; 00717 bool top_flow_exists = false; 00718 if (buf) 00719 { 00720 Flow* f = oper->findFlow(buf, data->state->q_date); 00721 if (f && f->getQuantity() > 0.0) 00722 { 00723 top_flow_qty_per = f->getQuantity(); 00724 top_flow_exists = true; 00725 } 00726 } 00727 00728 // Control the planning mode 00729 bool originalPlanningMode = data->constrainedPlanning; 00730 data->constrainedPlanning = true; 00731 00732 // Remember the top constraint 00733 bool originalLogConstraints = data->logConstraints; 00734 Problem* topConstraint = data->planningDemand->getConstraints().top(); 00735 00736 // Try all alternates: 00737 // - First, all alternates that are fully effective in the order of priority. 00738 // - Next, the alternates beyond their effective end date. 00739 // We loop through these since they can help in meeting a demand on time, 00740 // but using them will also create extra inventory or delays. 00741 double a_qty = data->state->q_qty; 00742 bool effectiveOnly = true; 00743 Date a_date = Date::infiniteFuture; 00744 Date ask_date; 00745 Operation *firstAlternate = NULL; 00746 double firstFlowPer; 00747 while (a_qty > 0) 00748 { 00749 // Evaluate all alternates 00750 bool plannedAlternate = false; 00751 double bestAlternateValue = DBL_MAX; 00752 double bestAlternateQuantity = 0; 00753 Operation* bestAlternateSelection = NULL; 00754 double bestFlowPer; 00755 Date bestQDate; 00756 for (Operation::Operationlist::const_iterator altIter 00757 = oper->getSubOperations().begin(); 00758 altIter != oper->getSubOperations().end(); ) 00759 { 00760 // Set a bookmark in the command list. 00761 CommandManager::Bookmark* topcommand = data->setBookmark(); 00762 bool nextalternate = true; 00763 00764 // Operations with 0 priority are considered unavailable 00765 const OperationAlternate::alternateProperty& props 00766 = oper->getProperties(*altIter); 00767 00768 // Filter out alternates that are not suitable 00769 if (props.first == 0.0 00770 || (effectiveOnly && !props.second.within(data->state->q_date)) 00771 || (!effectiveOnly && props.second.getEnd() > data->state->q_date) 00772 ) 00773 { 00774 ++altIter; 00775 if (altIter == oper->getSubOperations().end() && effectiveOnly) 00776 { 00777 // Prepare for a second iteration over all alternates 00778 effectiveOnly = false; 00779 altIter = oper->getSubOperations().begin(); 00780 } 00781 continue; 00782 } 00783 00784 // Establish the ask date 00785 ask_date = effectiveOnly ? origQDate : props.second.getEnd(); 00786 00787 // Find the flow into the requesting buffer. It may or may not exist, since 00788 // the flow could already exist on the top operationplan 00789 double sub_flow_qty_per = 0.0; 00790 if (buf) 00791 { 00792 Flow* f = (*altIter)->findFlow(buf, ask_date); 00793 if (f && f->getQuantity() > 0.0) 00794 sub_flow_qty_per = f->getQuantity(); 00795 else if (!top_flow_exists) 00796 { 00797 // Neither the top nor the sub operation have a flow in the buffer, 00798 // we're in trouble... 00799 // Restore the planning mode 00800 data->constrainedPlanning = originalPlanningMode; 00801 throw DataException("Invalid producing operation '" + oper->getName() 00802 + "' for buffer '" + buf->getName() + "'"); 00803 } 00804 } 00805 else 00806 // Default value is 1.0, if no matching flow is required 00807 sub_flow_qty_per = 1.0; 00808 00809 // Remember the first alternate 00810 if (!firstAlternate) 00811 { 00812 firstAlternate = *altIter; 00813 firstFlowPer = sub_flow_qty_per + top_flow_qty_per; 00814 } 00815 00816 // Constraint tracking 00817 if (*altIter != firstAlternate) 00818 // Only enabled on first alternate 00819 data->logConstraints = false; 00820 else 00821 { 00822 // Forget previous constraints if we are replanning the first alternate 00823 // multiple times 00824 data->planningDemand->getConstraints().pop(topConstraint); 00825 // Potentially keep track of constraints 00826 data->logConstraints = originalLogConstraints; 00827 } 00828 00829 // Create the top operationplan. 00830 // Note that both the top- and the sub-operation can have a flow in the 00831 // requested buffer 00832 CommandCreateOperationPlan *a = new CommandCreateOperationPlan( 00833 oper, a_qty, Date::infinitePast, ask_date, 00834 d, prev_owner_opplan, false 00835 ); 00836 a->getOperationPlan()->setMotive(data->state->motive); 00837 if (!prev_owner_opplan) data->add(a); 00838 00839 // Create a sub operationplan 00840 data->state->q_date = ask_date; 00841 data->state->curDemand = NULL; 00842 data->state->curOwnerOpplan = a->getOperationPlan(); 00843 data->state->curBuffer = NULL; // Because we already took care of it... @todo not correct if the suboperation is again a owning operation 00844 data->state->q_qty = a_qty / (sub_flow_qty_per + top_flow_qty_per); 00845 00846 // Solve constraints on the sub operationplan 00847 double beforeCost = data->state->a_cost; 00848 double beforePenalty = data->state->a_penalty; 00849 if (search == PRIORITY) 00850 { 00851 // Message 00852 if (loglevel) 00853 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 00854 << "' tries alternate '" << *altIter << "' " << endl; 00855 (*altIter)->solve(*this,v); 00856 } 00857 else 00858 { 00859 data->getSolver()->setLogLevel(0); 00860 try {(*altIter)->solve(*this,v);} 00861 catch (...) 00862 { 00863 data->getSolver()->setLogLevel(loglevel); 00864 // Restore the planning mode 00865 data->constrainedPlanning = originalPlanningMode; 00866 data->logConstraints = originalLogConstraints; 00867 throw; 00868 } 00869 data->getSolver()->setLogLevel(loglevel); 00870 } 00871 double deltaCost = data->state->a_cost - beforeCost; 00872 double deltaPenalty = data->state->a_penalty - beforePenalty; 00873 data->state->a_cost = beforeCost; 00874 data->state->a_penalty = beforePenalty; 00875 00876 // Keep the lowest of all next-date answers on the effective alternates 00877 if (effectiveOnly && data->state->a_date < a_date && data->state->a_date > ask_date) 00878 a_date = data->state->a_date; 00879 00880 // Now solve for loads and flows of the top operationplan. 00881 // Only now we know how long that top-operation lasts in total. 00882 if (data->state->a_qty > ROUNDING_ERROR) 00883 { 00884 // Multiply the operation reply with the flow quantity to obtain the 00885 // reply to return 00886 data->state->q_qty = data->state->a_qty; 00887 data->state->q_date = origQDate; 00888 data->state->curOwnerOpplan->createFlowLoads(); 00889 data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data); 00890 data->state->a_qty *= (sub_flow_qty_per + top_flow_qty_per); 00891 00892 // Combine the reply date of the top-opplan with the alternate check: we 00893 // need to return the minimum next-date. 00894 if (data->state->a_date < a_date && data->state->a_date > ask_date) 00895 a_date = data->state->a_date; 00896 } 00897 00898 // Message 00899 if (loglevel && search != PRIORITY) 00900 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 00901 << "' evaluates alternate '" << *altIter << "': quantity " << data->state->a_qty 00902 << ", cost " << deltaCost << ", penalty " << deltaPenalty << endl; 00903 00904 // Process the result 00905 if (search == PRIORITY) 00906 { 00907 // Undo the operationplans of this alternate 00908 if (data->state->a_qty < ROUNDING_ERROR) data->rollback(topcommand); 00909 00910 // Prepare for the next loop 00911 a_qty -= data->state->a_qty; 00912 plannedAlternate = true; 00913 00914 // As long as we get a positive reply we replan on this alternate 00915 if (data->state->a_qty > 0) nextalternate = false; 00916 00917 // Are we at the end already? 00918 if (a_qty < ROUNDING_ERROR) 00919 { 00920 a_qty = 0.0; 00921 break; 00922 } 00923 } 00924 else 00925 { 00926 double val = 0.0; 00927 switch (search) 00928 { 00929 case MINCOST: 00930 val = deltaCost / data->state->a_qty; 00931 break; 00932 case MINPENALTY: 00933 val = deltaPenalty / data->state->a_qty; 00934 break; 00935 case MINCOSTPENALTY: 00936 val = (deltaCost + deltaPenalty) / data->state->a_qty; 00937 break; 00938 default: 00939 LogicException("Unsupported search mode for alternate operation '" 00940 + oper->getName() + "'"); 00941 } 00942 if (data->state->a_qty > ROUNDING_ERROR && ( 00943 val + ROUNDING_ERROR < bestAlternateValue 00944 || (fabs(val - bestAlternateValue) < ROUNDING_ERROR 00945 && data->state->a_qty > bestAlternateQuantity) 00946 )) 00947 { 00948 // Found a better alternate 00949 bestAlternateValue = val; 00950 bestAlternateSelection = *altIter; 00951 bestAlternateQuantity = data->state->a_qty; 00952 bestFlowPer = sub_flow_qty_per + top_flow_qty_per; 00953 bestQDate = ask_date; 00954 } 00955 // This was only an evaluation 00956 data->rollback(topcommand); 00957 } 00958 00959 // Select the next alternate 00960 if (nextalternate) 00961 { 00962 ++altIter; 00963 if (altIter == oper->getSubOperations().end() && effectiveOnly) 00964 { 00965 // Prepare for a second iteration over all alternates 00966 effectiveOnly = false; 00967 altIter = oper->getSubOperations().begin(); 00968 } 00969 } 00970 } // End loop over all alternates 00971 00972 // Replan on the best alternate 00973 if (bestAlternateQuantity > ROUNDING_ERROR && search != PRIORITY) 00974 { 00975 // Message 00976 if (loglevel) 00977 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 00978 << "' chooses alternate '" << bestAlternateSelection << "' " << search << endl; 00979 00980 // Create the top operationplan. 00981 // Note that both the top- and the sub-operation can have a flow in the 00982 // requested buffer 00983 CommandCreateOperationPlan *a = new CommandCreateOperationPlan( 00984 oper, a_qty, Date::infinitePast, bestQDate, 00985 d, prev_owner_opplan, false 00986 ); 00987 a->getOperationPlan()->setMotive(data->state->motive); 00988 if (!prev_owner_opplan) data->add(a); 00989 00990 // Recreate the ask 00991 data->state->q_qty = a_qty / bestFlowPer; 00992 data->state->q_date = bestQDate; 00993 data->state->curDemand = NULL; 00994 data->state->curOwnerOpplan = a->getOperationPlan(); 00995 data->state->curBuffer = NULL; // Because we already took care of it... @todo not correct if the suboperation is again a owning operation 00996 00997 // Create a sub operationplan and solve constraints 00998 bestAlternateSelection->solve(*this,v); 00999 01000 // Now solve for loads and flows of the top operationplan. 01001 // Only now we know how long that top-operation lasts in total. 01002 data->state->q_qty = data->state->a_qty; 01003 data->state->q_date = origQDate; 01004 data->state->curOwnerOpplan->createFlowLoads(); 01005 data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data); 01006 01007 // Multiply the operation reply with the flow quantity to obtain the 01008 // reply to return 01009 data->state->a_qty *= bestFlowPer; 01010 01011 // Combine the reply date of the top-opplan with the alternate check: we 01012 // need to return the minimum next-date. 01013 if (data->state->a_date < a_date && data->state->a_date > ask_date) 01014 a_date = data->state->a_date; 01015 01016 // Prepare for the next loop 01017 a_qty -= data->state->a_qty; 01018 01019 // Are we at the end already? 01020 if (a_qty < ROUNDING_ERROR) 01021 { 01022 a_qty = 0.0; 01023 break; 01024 } 01025 } 01026 else 01027 // No alternate can plan anything any more 01028 break; 01029 01030 } // End while loop until the a_qty > 0 01031 01032 // Forget any constraints if we are not short or are planning unconstrained 01033 if (a_qty < ROUNDING_ERROR || !originalLogConstraints) 01034 data->planningDemand->getConstraints().pop(topConstraint); 01035 01036 // Unconstrained plan: If some unplanned quantity remains, switch to 01037 // unconstrained planning on the first alternate. 01038 // If something could be planned, we expect the caller to re-ask this 01039 // operation. 01040 if (!originalPlanningMode && fabs(origQqty - a_qty) < ROUNDING_ERROR && firstAlternate) 01041 { 01042 // Switch to unconstrained planning 01043 data->constrainedPlanning = false; 01044 data->logConstraints = false; 01045 01046 // Message 01047 if (loglevel) 01048 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 01049 << "' plans unconstrained on alternate '" << firstAlternate << "' " << search << endl; 01050 01051 // Create the top operationplan. 01052 // Note that both the top- and the sub-operation can have a flow in the 01053 // requested buffer 01054 CommandCreateOperationPlan *a = new CommandCreateOperationPlan( 01055 oper, a_qty, Date::infinitePast, origQDate, 01056 d, prev_owner_opplan, false 01057 ); 01058 a->getOperationPlan()->setMotive(data->state->motive); 01059 if (!prev_owner_opplan) data->add(a); 01060 01061 // Recreate the ask 01062 data->state->q_qty = a_qty / firstFlowPer; 01063 data->state->q_date = origQDate; 01064 data->state->curDemand = NULL; 01065 data->state->curOwnerOpplan = a->getOperationPlan(); 01066 data->state->curBuffer = NULL; // Because we already took care of it... @todo not correct if the suboperation is again a owning operation 01067 01068 // Create a sub operationplan and solve constraints 01069 firstAlternate->solve(*this,v); 01070 01071 // Expand flows of the top operationplan. 01072 data->state->q_qty = data->state->a_qty; 01073 data->state->q_date = origQDate; 01074 data->state->curOwnerOpplan->createFlowLoads(); 01075 data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data); 01076 01077 // Fully planned 01078 a_qty = 0.0; 01079 data->state->a_date = origQDate; 01080 } 01081 01082 // Set up the reply 01083 data->state->a_qty = origQqty - a_qty; // a_qty is the unplanned quantity 01084 data->state->a_date = a_date; 01085 assert(data->state->a_qty >= 0); 01086 assert(data->state->a_date >= data->state->q_date); 01087 01088 // Restore the planning mode 01089 data->constrainedPlanning = originalPlanningMode; 01090 data->logConstraints = originalLogConstraints; 01091 01092 // Increment the cost 01093 if (data->state->a_qty > 0.0) 01094 data->state->a_cost += data->state->curOwnerOpplan->getQuantity() * oper->getCost(); 01095 01096 // Make sure other operationplans don't take this one as owner any more. 01097 // We restore the previous owner, which could be NULL. 01098 data->state->curOwnerOpplan = prev_owner_opplan; 01099 01100 // Message 01101 if (loglevel>1) 01102 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 01103 << "' answers: " << data->state->a_qty << " " << data->state->a_date 01104 << " " << data->state->a_cost << " " << data->state->a_penalty << endl; 01105 } 01106 01107 01108 }