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